搜索专项---最小步数模型

2024-02-14 23:44

本文主要是介绍搜索专项---最小步数模型,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


文章目录

  • 魔板

一、魔板OJ链接

        本题思路:最小步数模型: 将整个“图”视为一个状态也即一个节点. 状态的转移视为权值为1的边.

BFS求解, 注意几点:

        状态的存储: 一般用字符串存储状态, 用哈希表存储初始状态到每个状态的距离.

        方案记录: 记忆数组存储. 本题中需要存储上一个状态以及对应操作.

        字典序: 每次状态转移都按A∼C的顺序, 得到的方案一定是字典序最小的方案.

        一种直观理解: 这种扩展方式恰好是字典序定义的顺序.也可用反证法证明: 假设用上述方式得到的方案不是字典序最小.每个方案对应一个字符串, 从左向右依次考虑每个字母(操作).考虑算法解与最优解从左向右第一个不同字母: x与x′, 假设在第k个位置不同.由于最优解字典序更小, 有x<'x',x与x′都是可以到达题目要求状态的合法操作.而在第k步扩展时, 算法是按照A∼C顺序选取, 即算法解一定是取队列中最前面的合法操作.最优解与算法解不同, 而算法解保证取队列最前面的合法操作, 且队列具有单调性, 所以: x≤x′(队列前的操作字典序小于队列后面操作的字典序, 这是算法操作的结果).与假设矛盾. 后续的不同字母依次类推, 所以上述方法得到的算法解一定是字典序最小的方案.

#include <bits/stdc++.h>char g[2][4];
std::unordered_map<std::string,int> dist;//一般用字符串存储状态, 用哈希表存储初始状态到每个状态的距离.
std::unordered_map<std::string,std::pair<char,std::string>> pre;//记忆数组存储. 本题中需要存储上一个状态以及对应操作.
std::queue<std::string> q;void set(std::string state)
{for(int i=0;i<4;i++) g[0][i]=state[i];for(int i=0,j=7;i<4;i++,j--) g[1][i]=state[j];
}std::string get()
{std::string res;for(int i=0;i<4;i++) res+=g[0][i];for(int i=3;i>=0;i--) res+=g[1][i];return res;
}std::string move0(std::string state)
{set(state);for(int i=0;i<4;i++) std::swap(g[0][i],g[1][i]);return get();
}std::string move1(std::string state)
{set(state);int v0 = g[0][3], v1 = g[1][3];for (int i = 3; i > 0; i -- ){g[0][i] = g[0][i - 1];g[1][i] = g[1][i - 1];}g[0][0] = v0, g[1][0] = v1;return get();
}std::string move2(std::string state)
{set(state);int v = g[0][1];g[0][1] = g[1][1];g[1][1] = g[1][2];g[1][2] = g[0][2];g[0][2] = v;return get();
}int bfs(std::string start,std::string end)
{//这里需要注意一下特判if(start==end) return 0;q.push(start);dist[start]=0;while(!q.empty()){std::string t=q.front();q.pop();std::string m[3];m[0]=move0(t);m[1]=move1(t);m[2]=move2(t);for(int i=0;i<3;i++){if(!dist.count(m[i])){dist[m[i]]=dist[t]+1;pre[m[i]]={'A'+i,t};q.push(m[i]);if(m[i]==end) return dist[end];}}}return -1;
}int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int x;std::string start,end;for(int i=0;i<8;i++){std::cin>>x;end+=char(x+'0');}//表示目标状态for(int i=1;i<=8;i++) start+=char(i+'0');//初始的基本状态int step=bfs(start,end);std::cout<<step<<std::endl;std::string res;while(start!=end){res+=pre[end].first;end=pre[end].second;}reverse(res.begin(),res.end());//由于是从目标状态进行的,所以结果应该进行逆序的处理std::cout<<res;return 0;
}

这篇关于搜索专项---最小步数模型的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/709905

相关文章

大模型研发全揭秘:客服工单数据标注的完整攻略

在人工智能(AI)领域,数据标注是模型训练过程中至关重要的一步。无论你是新手还是有经验的从业者,掌握数据标注的技术细节和常见问题的解决方案都能为你的AI项目增添不少价值。在电信运营商的客服系统中,工单数据是客户问题和解决方案的重要记录。通过对这些工单数据进行有效标注,不仅能够帮助提升客服自动化系统的智能化水平,还能优化客户服务流程,提高客户满意度。本文将详细介绍如何在电信运营商客服工单的背景下进行

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

Andrej Karpathy最新采访:认知核心模型10亿参数就够了,AI会打破教育不公的僵局

夕小瑶科技说 原创  作者 | 海野 AI圈子的红人,AI大神Andrej Karpathy,曾是OpenAI联合创始人之一,特斯拉AI总监。上一次的动态是官宣创办一家名为 Eureka Labs 的人工智能+教育公司 ,宣布将长期致力于AI原生教育。 近日,Andrej Karpathy接受了No Priors(投资博客)的采访,与硅谷知名投资人 Sara Guo 和 Elad G

Retrieval-based-Voice-Conversion-WebUI模型构建指南

一、模型介绍 Retrieval-based-Voice-Conversion-WebUI(简称 RVC)模型是一个基于 VITS(Variational Inference with adversarial learning for end-to-end Text-to-Speech)的简单易用的语音转换框架。 具有以下特点 简单易用:RVC 模型通过简单易用的网页界面,使得用户无需深入了

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

图神经网络模型介绍(1)

我们将图神经网络分为基于谱域的模型和基于空域的模型,并按照发展顺序详解每个类别中的重要模型。 1.1基于谱域的图神经网络         谱域上的图卷积在图学习迈向深度学习的发展历程中起到了关键的作用。本节主要介绍三个具有代表性的谱域图神经网络:谱图卷积网络、切比雪夫网络和图卷积网络。 (1)谱图卷积网络 卷积定理:函数卷积的傅里叶变换是函数傅里叶变换的乘积,即F{f*g}