BFS中的双向广搜和A-star
AcWing 179. 八数码
题目链接：https://www.acwing.com/problem/content/181/
思路
A*算法：
A*算法在处理队列中的元素上进行了优化
- 拿出队头并且扩展元素
- 估计扩展元素到终点的距离
- 将扩展后的元素进行从小到大的排序，并且小的作为队头元素，这样做大大的减少了几乎无意义的数据带来的影响
注意：
- 估计距离要小于等于实际距离
- 题目要保证有解，负责搜索的数据和普通bfs一样
- 当逆序对为负数时，一定无解
- 终点出队时即可确定答案
A*算法的证明：
为什么出队的时候就是最优解：
设出队的距离为dist,并且dist>distbest(最优解),设在最优路径上的一个点u，起点->u->终点，
预计距离：d(u)+f(u),实际距离：d(u)+g(u),- 因为：
f(u)<=g(u)【估计距离要小于实际距离】，所以d(u)+f(u)<=d(u)+g(u)=distbest; - 所以
d(u)+f(u)<=distbest<dist - 所以
dist>d(u)+f(u) - 因为dist中肯定有一点u扩展，而
dist>d(u)+f(u)，即实际距离大于估计距离，互相矛盾，所以dist为最优解
逆序对为奇数对时一定无法到达终点
1 3 5 1 3 5 1 3 5 1 3 5
4 6 7 --> 4 6 4 6 7 --> 7 6
8 2 8 7 2 8 2 4 8 2
13547682 13546872 13547682 13576482
当左右交换不影响排序，而上下两对交换后的影响都是双对的：
- 一个为逆序对，一个不为逆序对：交换后一个为逆序对，一个不为逆序对
- 两个都为逆序对：交换为 逆序对-2
- 两个都不为逆序对：交换后逆序对+2
因为终点为12345678 ，所以逆序对为0，是一个偶数 ，所以逆序对的数量不可能是奇数
估计距离：
估计距离为这个点到目标点的【曼哈顿距离】，即为横纵坐标差的绝对值之和
代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<ctime>
#include<unordered_map>
#include<queue>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<int,string> PIS;//第二维是状态
#define sc scanf
#define pr printf
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int f(string state)//估价函数,曼哈顿距离
{
int res=0;
for(int i=0;i<state.size();i++)
if(state[i]!='x')
{
int t=state[i]-'1';
res+=abs(i/3-t/3)+abs(i%3-t%3);
}
return res;
}
string bfs(string start)
{
string end="12345678x";
char op[]="urdl";
unordered_map<string,int> dist;//距离
unordered_map<string,pair<char,string>> prev;//记录下是从哪个状态转移过来的
priority_queue<PIS,vector<PIS>,greater<PIS>> heap;//小根堆
dist[start]=0;//起点为0
heap.push({f(start),start});//{估价函数，状态本身}
while (heap.size())
{
auto t=heap.top();heap.pop();
string state=t.y;
if(state==end) break;
int x,y;
for(int i=0;i<9;i++)
if(state[i]=='x')
{
x=i/3,y=i%3;//横纵坐标
break;
}
//扩展
string source =state;//保存原状态
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<0||a>=3||b<0||b>=3) continue;
state=source;
swap(state[x*3+y],state[a*3+b]);
if(dist.count(state)==0||dist[state]>dist[source]+1)
{
dist[state]=dist[source]+1;
prev[state]={op[i],source};
heap.push({dist[state]+f(state),state});
}
}
}
string res;
while(end!=start)
{
res+=prev[end].x;
end=prev[end].y;
}
reverse(res.begin(),res.end());
return res;
}
int main()
{
string start,seq;//初始状态，初始序列
char c;
while(cin>>c)
{
start+=c;
if(c!='x') seq+=c;
}
int cnt=0;
for(int i=0;i<8;i++)
for(int j=i;j<8;j++)
if(seq[i]>seq[j])
cnt++;
if(cnt&1) puts("unsolvable");
else cout<<bfs(start)<<endl;
return 0;
}
AcWing 178. 第K短路
题目链接：https://www.acwing.com/problem/content/180/ 给定一张 N 个点（编号 1,2…N），M 条边的有向图，求从起点 S 到终点 T 的第 K 短路的长度，路径允许重复经过点或边。 注意： 每条最 短路中至少要包含一条边。
思路
/*
A* 应用场景:
起点→终点的最短距离
状态空间 >> 1e10
启发函数减小搜索空间
A*算法:
while(q.size())
t ← 优先队列的队头 小根堆
当终点第一次出队时 break;
从起点到当前点的真实距离 d_real
从当前点到终点的估计距离 d_estimate
选择一个估计距离最小的点 min(d_estimate)
for j in ne[t]:
将邻边入队
A*算法条件:
估计距离<=真实距离
d[state] + f[state] = 起点到state的真实距离 + state到终点的估计距离=估计距离
^
d[state] + g[state] = 起点到state的真 实距离 + state到终点的真实距离=真实距离
一定是有解才有 d[i] >= d[最优] = d[u]+f[u]
f[u] >= 0
证明终点第一次出队列即最优解
1 假设终点第一次出队列时不是最优
则说明当前队列中存在点u
有 d[估计]< d[真实]
d[u] + f[u] <= d[u] + g[u] = d[队头终点]
即队列中存在比d[终点]小的值,
2 但我们 维护的是一个小根堆,没有比d[队头终点]小的d[u],矛盾
证毕
A* 不用判重
以边权都为1为例
A o→o→o
↑ ↓
S o→o→o→o→o→o→o T
B
dist[A] = dist[S]+1 + f[A] = 7
dist[B] = dist[S]+1 + f[B] = 5
则会优先从B这条路走到T
B走到T后再从A这条路走到T
*/
/*
本题
建反向边dijkstra求各点到终点的距离作为估计值f[u]
*/
代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<ctime>
#include<queue>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
#define sc scanf
#define pr printf
const int N=1010,M=200010;
int n,m,S,T,K;
int h[N],rh[N],e[M],w[M],ne[M],idx;
int dist[N],cnt[N];
bool st[N];//判断有没有出队
void add(int h[],int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra()
{
priority_queue<PII,vector<PII>,greater<PII>> heap;//优先队列
heap.push({0,T});
memset(dist,0x3f,sizeof dist);
dist[T]=0;
while(heap.size())
{
auto t=heap.top();heap.pop();
int ver=t.y;
if(st[ver]) continue;
st[ver]=true;
for(int i=rh[ver];~i;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[ver]+w[i])
{
dist[j]=dist[ver]+w[i];
heap.push({dist[j],j});
}
}
}
}
int astar()
{
priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
// 谁的d[u]+f[u]更小 谁先出队列
heap.push({dist[S], {0, S}});
while(heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.y.y,distance = t.y.x;
cnt[ver]++;
//如果终点已经被访问过k次了 则此时的ver就是终点T 返回答案
if(cnt[T]==K) return distance;
for(int i=h[ver];i!=-1;i=ne[i])
{
int j = e[i];
/*
如果走到一个中间点都cnt[j]>=K，则说明j已经出队k次了，且astar()并没有return distance,
说明从j出发找不到第k短路(让终点出队k次)，
即继续让j入队的话依然无解，
那么就没必要让j继续入队了
*/
if(cnt[j] < K)
{
// 按 真实值+估计值 = d[j]+f[j] = dist[S->t] + w[t->j] + dist[j->T] 堆排
// 真实值 dist[S->t] = distance+w[i]
heap.push({distance+w[i]+dist[j],{distance+w[i],j}});
}
}
}
// 终点没有被访问k次
return -1;
}
int main()
{
sc("%d%d",&n,&m);
memset(h,-1,sizeof h);
memset(rh,-1,sizeof rh);
for(int i=0;i<m;i++)
{
int a,b,c;//起点，终点，边权
sc("%d%d%d",&a,&b,&c);
add(h,a,b,c);//正边
add(rh,b,a,c);//反边
}
sc("%d%d%d",&S,&T,&K);
if(S==T) K++;
dijkstra();
pr("%d\n",astar());
return 0;
}