• 欢迎光临~

算法提高课 第二章 搜索之双向广搜和A*

开发技术 开发技术 2022-07-21 次浏览

一、双向广搜

190. 字串变换

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

const int N = 6;

int n;
string a[N],b[N];
int extend(queue<string>&q,unordered_map<string,int>&da,unordered_map<string,int>&db,string a[],string b[])
{
    string t = q.front();q.pop();
    for(int i = 0;i<t.size();i++) //枚举起点
    {
        for(int j = 0;j<n;j++) //枚举变换规则
        {
            if(t.substr(i,a[j].size()) == a[j]) //匹配子串成功,则尝试替换
            {
                string state = t.substr(0,i) + b[j] + t.substr(i+a[j].size()); //替换与拼接成新的字符串
                if(db.count(state)) return da[t] + 1 + db[state]; //如果在b到a的变换中有记录,即成功会师
                //变换次数为a到t + 替换的一次 + b到state
                if(da.count(state)) continue; //如果已经搜过了
                da[state] = da[t] + 1; //更新距离
                q.push(state); //加入队列
            }
        }
    }
    return 11;
}
int bfs(string A,string B)
{
    queue<string>qa,qb;
    unordered_map<string,int>da,db;
    qa.push(A),da[A] = 0;
    qb.push(B),db[B] = 0;
    
    while(qa.size() && qb.size()) //两个队列都不为空时,才进行搜索,否则一定没有方案
    {
        int t;
        if(qa.size() <= qb.size()) //选择队列长度较小的
        {
            t = extend(qa,da,db,a,b); //起点开始拓展
        }
        else t = extend(qb,db,da,b,a);//终点开始拓展
        if(t<=10) return t;
    }
    return 11;
} 
int main()
{
    string A,B;
    cin>>A>>B;
    while(cin>>a[n]>>b[n]) n++; //统计变换规则及次数
    if(A == B)
    {
        cout<<0<<endl;
        return 0;
    }
    int step = bfs(A,B);
    if(step > 10) puts("NO ANSWER!");
    else cout<<step<<endl;
    return 0;
}

二、A*算法(边权非负即可)

在dijkstra的基础上改进,可以认为dijkstra是特殊的A*算法

  1. 把bfs中的队列替换成优先队列(小根堆)
  2. 优先队列中不仅存储从起点到当前点的真实距离,还要存储从当前点到终点的估价距离
  3. 每次选择预测距离最小的点来拓展
    算法提高课 第二章 搜索之双向广搜和A*
    核心条件:1.估计距离必须不大于真实距离,越接近越好 2.题目必须有解,否则会遍历全部情况
    注意事项:A*不能保证除终点外其他所有点第一次出队时就是最优解,且每个点可能会被遍历多次

八数码

估价函数:当前状态的每个数与其真实位置的曼哈顿距离之和

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;
typedef pair<int, string> PII;
const int N = 9;

string start,seq;
int f(string state) //估价函数:计算当前状态中每个"数字"的实际坐标与正确坐标的曼哈顿距离之和
{
    int res = 0;
    for(int i = 0;i<state.size();i++)
    {
        if(state[i]!='x')
        {
            int x = state[i] - '1';
            res += abs(i/3 - x/3) + abs(i%3 - x%3);//横纵坐标之差,注意加上绝对值
        }
    }
    return res;
}

string Astar(string start)
{
    string end = "12345678x";//终点
    char d[] = "dlru";//最好按照字典序进行搜索
    int dx[4] = {1,0,0,-1},dy[4] = {0,-1,1,0};
    priority_queue<PII,vector<PII>,greater<PII>>heap;
    unordered_map<string,int>dist;//与起点的实际距离
    unordered_map<string,pair<char,string>>prev;//记录当前状态的上一个状态以及如何转移的
    
    dist[start] = 0;
    heap.push({f(start),start});//注意:加入的是估价函数
    
    while(!heap.empty())
    {
        PII t = heap.top();heap.pop();
        string state = t.second;
        if(state == end) break;
        int x,y;
        for(int i = 0;i<state.size();i++) //找出x的坐标
        {
            if(state[i] == 'x')
            {
                x = i/3,y = i % 3;
                break;
            }
        }
        string before = state;//暂存该状态,为转移做准备
        for(int i = 0;i<4;i++)
        {
            int nx = x + dx[i],ny = y + dy[i];
            if(nx<0||nx>2||ny<0||ny>2) continue;
            state = before;//每次只能交换一次
            swap(state[nx*3+ny],state[x*3+y]);
            if(!dist.count(state)||dist[state] > dist[before] + 1)//若从未更新过 or 有更短的步数
            {
                dist[state] = dist[before] + 1;
                heap.push({dist[state] + f(state),state});//注意:必须加入估价函数
                prev[state] = {d[i],before};//记录上一状态与转移方法
            }
        }
    }
    string res;
    string cur = end;
    while(cur!=start) //处理答案
    {
        res += prev[cur].first;
        cur = prev[cur].second;
    }
    reverse(res.begin(),res.end()); //由终点反推到起点,故必须翻转
    return res;
}
int main()
{
    char c;
    for(int i = 0;i<9;i++)
    {
        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[j] < seq[i]) ++cnt;
        }
    }
    if(cnt % 2 == 1) puts("unsolvable");//若起始状态中逆序对的个数不为偶数,则无解
    else  cout<<Astar(start)<<endl;
    
    return 0;
}

178. 第K短路

猜想:第1次出队时,是最短路,第K次出队时,是第K短路

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1010,M = 2e4 + 20;
typedef pair<int, int> PII;
typedef pair<int, pair<int,int> > PIII;//估价距离,<实际距离,结点号>

int h[N],e[M],ne[M],w[M],idx;
int rh[N];//建立反向边的头结点,用于计算估价函数
int dist[N];//从终点到其他点的单源最短路距离
bool st[N];
int n,m;
int s,d,k;

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;
    memset(dist,0x3f,sizeof dist);
    dist[d] = 0;
    heap.push({dist[d],d});
    
    while(!heap.empty())
    {
        PII t = heap.top();heap.pop();
        int num = t.second;
        if(st[num]) continue;
        st[num] = 1;
        for(int i = rh[num];i!=-1;i=ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[num] + w[i])
            {
                dist[j] = dist[num] + w[i];
                heap.push({dist[j],j});
            }
        }
    }
    
    return;
}

int Astar()
{
    priority_queue<PIII,vector<PIII>,greater<PIII> >heap; //根据估价距离形成的小根堆
    heap.push({dist[s],{0,s}});
    int cnt = 0;
    
    while(!heap.empty())
    {
        PIII t = heap.top();heap.pop();
        int dis = t.second.first,num = t.second.second;
        if(num == d) ++cnt;
        if(cnt == k) return dis;//第k次出队时,说明实际距离是第k短路
        
        for(int i = h[num];i!=-1;i=ne[i])
        {
            int j = e[i];
            heap.push({dis + w[i] + dist[j],{dis + w[i],j}});//注意:估价函数发生了变化,变成从起点到终点
        }
    }
    return -1;
}

int main()
{
    memset(h, -1, sizeof h);
    memset(rh,-1,sizeof rh);
    scanf("%d%d", &n, &m);
    while (m -- )
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(h,a,b,c);
        add(rh,b,a,c);
    }
    scanf("%d%d%d", &s, &d,&k);
    if(s == d) ++k;
    Dijkstra();
    if(dist[s] == 0x3f3f3f3f) cout<<-1<<endl;//注意:当无方案/路可到达时,不能用A*算法
    //终点到起点距离无穷大说明无法到达
    else cout<<Astar()<<endl;
    return 0;
}
程序员灯塔
转载请注明原文链接:算法提高课 第二章 搜索之双向广搜和A*
喜欢 (0)