萝卜头IT论坛

搜索
查看: 6701|回复: 9
收起左侧

c++ 启发式搜索解决数字华容道问题(N数码问题)

[复制链接]
发表于 2020-9-24 19:00:34 | 显示全部楼层 |阅读模式
本帖最后由 这个显卡不太冷 于 2020-9-24 20:42 编辑

[md]好的。

原因是上实验课太无聊了,教室的电脑是Windows7,还有小工具可以玩。

里面有个自带的华容道游戏,就是数字华容道。

玩法就是把所有数字按升序排列。

由于太蠢了,并不会玩,遂写了个暴力来搜解法。

用A*实现的,启发函数就是所有数字距离它位置的曼哈顿距离。

4*4的大概需要3G的空间可以搜出答案。速度倒是还能接受。

```cpp
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
int n = 4;
unordered_map<string, int> dist;
unordered_map<string, pair<string, char> > pre;
typedef pair<int, string> PIS;
int f(string s)
{
    int res = 0;
    for(int i = 0; i < s.size(); i++)
    {
        if(s == 'x') continue;
        int t = s - 1;
        res += abs(i / n - t / n) + abs(i % n - t % n);
    }
    return res;
}
void out(string s)
{
    for(char x:s) cout << (int)x << ' '; cout << endl;
}
string bfs(string st)
{
    string ed = "";
    for(int i = 1; i < n * n; i++) ed += (char)i; ed += 'x';
    int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
    char op[5] = "udlr";
  
    priority_queue<PIS, vector<PIS>, greater<PIS> > q;
    q.push({f(st), st});
    dist[st] = 0;
    while(q.size())
    {
        auto t = q.top(); q.pop();
        string state = t.second;
        // out(state);
        if(state == ed) break;
        int step = dist[state];
        int x, y;
        for(int i = 0; i < state.size(); i++)
            if(state == 'x')
            {
                x = i / n, y = i % n;
                break;
            }
        string src = state;
        for(int i = 0; i < 4; i++)
        {
            int dx = x + dir[0], dy = y + dir[1];
            if(dx < 0 || dy < 0 || dx >= n || dy >= n) continue;
            // src = state;
            swap(src[x * n + y], src[dx * n + dy]);
            if(!dist.count(src) || dist[src] > step + 1)
            {
                dist[src] = step + 1;
                pair<string, int> o = {state, op};
                q.push({step + 1 + f(src), src});
                pre[src] = o;
            }
            swap(src[x * n + y], src[dx * n + dy]);
        }
    }
    string res = "";
    while(ed != st)
    {
        auto o = pre[ed];
        res += o.second;
        ed = o.first;
    }
    reverse(res.begin(), res.end());
    return res;
}
main()
{
    string x, st;
    for(int i = 1; i <= n * n; i++)
    {
        cin >> x;
        if(x == "x") st += x;
        else st += (char)stoi(x);
    }
    cout << bfs(st);
}
/*
1 8 3 6 11 7 15 9 4 x 12 2 10 14 5 13
1 2 3 4 5 6 7 8 9 10 11 12 13 14 x 15
x 7 11 5 15 3 9 6 1 2 12 14 10 13 4 8
*/
```

用法就是直接输入数字的排列。空格用 `x` 代替。

随便在4399找了个试试。

![image.png](data/attachment/forum/202009/24/185755y0ffg6ay6hc2gc76.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")

![image.png](data/attachment/forum/202009/24/185943f3500c86coj88g6t.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")

![image.png](data/attachment/forum/202009/24/185949l2x8wm2zr2k224rc.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")

[3.exe](data/attachment/forum/?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "3.exe")

也给一个编译好的文件吧。
[/md]
image.png
image.png
image.png
回复

使用道具 举报

 楼主| 发表于 2020-9-24 20:40:36 | 显示全部楼层
markdown 编辑器居然不能插入附件

3.exe

226.43 KB, 下载次数: 295

回复

使用道具 举报

 楼主| 发表于 2020-9-24 20:51:09 | 显示全部楼层
http://www.4399.com/flash/196034_2.htm
附上一个游戏地址
回复

使用道具 举报

发表于 2020-9-28 18:31:39 来自手机 | 显示全部楼层
回复

使用道具 举报

发表于 2020-9-29 10:54:14 | 显示全部楼层
回复

使用道具 举报

发表于 2020-9-29 19:21:36 | 显示全部楼层
发个视频上来吧
回复

使用道具 举报

 楼主| 发表于 2020-9-30 00:07:14 | 显示全部楼层
nkc3g4 发表于 2020-9-29 19:21
发个视频上来吧

这周没有实验课了。只有上次录这个十秒的。

C302C3BC8368978498F21D647116F187.mp4 (6.53 MB, 下载次数: 358)
回复

使用道具 举报

发表于 2020-9-30 19:17:15 来自手机 | 显示全部楼层
这个显卡不太冷 发表于 2020-9-30 00:07
这周没有实验课了。只有上次录这个十秒的。

实验课是什么
回复

使用道具 举报

联系我们(Contact)|手机版|萝卜头IT论坛 ( 苏ICP备15050961号-1 )

GMT+8, 2024-3-29 03:27 , Processed in 0.093987 second(s), 22 queries , Gzip On.

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表