请选择 进入手机版 | 继续访问电脑版

萝卜头IT论坛

了解更多
搜索
查看: 235|回复: 9
收起左侧

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

[复制链接]
发表于 2020-9-24 19:00:34 | 显示全部楼层 |阅读模式

] 本帖最后由 这个显卡不太冷 于 2020-9-24 20:42 编辑 [/i]

[md]好的。

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

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

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

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

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

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

#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[i] == 'x') continue;
        int t = s[i] - 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[i] == 'x') 
            {
                x = i / n, y = i % n;
                break;
            }
        string src = state;
        for(int i = 0; i < 4; i++)
        {
            int dx = x + dir[i][0], dy = y + dir[i][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[i]};
                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

image.png

image.png

3.exe

也给一个编译好的文件吧。

回复

使用道具 举报

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

3.exe

226.43 KB, 下载次数: 12

回复

使用道具 举报

 楼主| 发表于 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, 下载次数: 21)
回复

使用道具 举报

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

实验课是什么
回复

使用道具 举报

联系站长(Contact)|萝卜头IT论坛 ( 苏ICP备15050961号-1 )

GMT+8, 2020-10-30 15:40 , Processed in 0.233555 second(s), 23 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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