A*算法解决8数码问题

179. 八数码

给定 n 个正整数,将它们分组,使得每组中任意两个数互质。

至少要分成多少个组?

在一个 3×3 的网格中,1∼8这 8 个数字和一个 X 恰好不重不漏地分布在这 3×3的网格中。

例如:

1 2 3
X 4 6
7 5 8

在游戏过程中,可以把 X 与其上、下、左、右四个方向之一的数字交换(如果存在)。

我们的目的是通过交换,使得网格变为如下排列(称为正确排列):

1 2 3
4 5 6
7 8 X

例如,示例中图形就可以通过让 X 先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下:

1 2 3   1 2 3   1 2 3   1 2 3
X 4 6   4 X 6   4 5 6   4 5 6
7 5 8   7 5 8   7 X 8   7 8 X

把 X 与上下左右方向数字交换的行动记录为 udlr

现在,给你一个初始网格,请你通过最少的移动次数,得到正确排列。

输入格式

输入占一行,将 3×3的初始网格描绘出来。

例如,如果初始网格如下所示:

1 2 3 
x 4 6 
7 5 8 

则输入为:1 2 3 x 4 6 7 5 8

输出格式

输出占一行,包含一个字符串,表示得到正确排列的完整行动记录。

如果答案不唯一,输出任意一种合法方案即可。

如果不存在解决方案,则输出 unsolvable

输入样例:

2  3  4  1  5  x  7  6  8 

输出样例

ullddrurdllurdruldr

解析 :   题目求的是路径操作,对于通常的bfs,如果没有搜到合法方案的话,bfs就要把所有的状态都要遍历一遍 9^9=387420489,即使能搜到合法状态,但是由于是一层一层搜,搜索量依旧很大,这题时间卡掉了这种做法。有没有好的搜索方法,A*算法就能很好的解决这种情况,它能把搜索范围迅速缩小。只要搜很小的一部分就能得到最优解。下面是A*算法的伪代码。

A*有点类似Dijkstra,它有两个 参数一个是 d[i]  表示从起点到当前点的距离 , 另外一个是 f[i] 表示当前点到终点的估价距离 <= 真实距离g[i]。

A*
while(!heap.empty())
{
    t <- 优先队列的队头
    当终点第一次出队的时候 break;
    
    for t 所有的邻边
        邻边入队
}
d[u]+f[u]<=d[u]+g[u]
如何保证第一次出队的终点就是最优解
证明: 假设u为最优路径上的一个点,至少起点是,假设终点出队时不是最优解,那么 dist > 最优解d >= d[u]+f[u];
如果不是最优解,那么队列中应该存在 一个点u使得 d[u]+f[u]<= 最优解d,此时就违反优先队列的规则了,最小的元素应该先出队,而现在却找到了比队头更小的元素,因此矛盾了。
//上面这个y总在提高课里讲的证明,但我感觉有问题,不是很懂的亚子。 #include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<queue>

#define x first
#define y second

using namespace std;

typedef pair<int,string> PIS;

const int N=9;

int f(string state)  //估价函数 算的是曼哈顿距离,即x,y 分别差值的绝对值之和
{
    int res=0;
    for(int i=0;i<state.size();++i)
    {
        if(state[i]!='x')
        {
            int t=state[i]-'1';
            res+=abs(t/3-i/3)+abs(t%3-i%3);
        }
    }
    return res;
}

string astar(string start)
{
    unordered_map<string,int> dist;
    unordered_map<string, pair<string,char>> prev; //保存前一个状态,和操作
    priority_queue<PIS,vector<PIS>,greater<PIS>>heap; //堆
    
    heap.push({f(start),start}); 
    string end={"12345678x"};  
    char op[4]={'u','d','l','r'};
    int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
    
    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<state.size(); ++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;
            
            swap(state[a*3+b],state[3*x+y]);
            
            if(!dist.count(state) || dist[state]>dist[source]+1)
            {
                dist[state]=dist[source]+1;
                prev[state]={source,op[i]};
                heap.push({dist[state]+f(state),state});
            }
           swap(state[a*3+b],state[3*x+y]);
        }
          
    }
    
    string res;
    while(end!=start)
    {
        res+=prev[end].y;
        end=prev[end].x;
    }
    reverse(res.begin(),res.end());  //取反,原因res加入的时候,是倒着加入的所以,最终的结果是反着来的,也就是从终点到起点,而我们求的是起点到终点
    return res;
}

int main()
{
    string start,seq;
    char c;
    for(int i=0;i<=8;++i)
    {
        cin>>c;
        start+=c;
        if(c!='x') seq+=c;
    }
    int cnt=0;  //逆序数,12345678x,
//123
//456
//78x 某个数只有上下的移动才会改变逆序数,左右移动是不改变的,改变的逆序数只有+2,或者是-2,逆序数的数量一定是偶数,所以奇数的情况就是无解。
for(int i=0;i<8;++i) for(int j=i;j<8;++j) if(seq[i]>seq[j]) cnt++; if(cnt&1) printf("unsolvable"); else cout<<astar(start); return(0); }

 

 

 

 
上一篇:41、数组中的第K个最大元素(借助堆实现)


下一篇:06.堆(Heap-线程共享)-运行时数据区