迷宫问题——分支限界法

参考链接

分支限界法求解迷宫问题

题目内容

定义一个二维数组，例如：
int maze[5][5] =
{
0 1 0 0 0

0 1 0 1 0

0 0 0 0 0

0 1 1 1 0

0 0 0 1 0
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

输入格式

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一最短路径。

输出格式

左上角到右下角的最短路径，格式如样例所示。

输入样例

0 1 0 0 0

0 1 0 1 0

0 0 0 0 0

0 1 1 1 0

0 0 0 1 0

输出样例

(0,0)

(1,0)

(2,0)

(2,1)

(2,2)

(2,3)

(2,4)

(3,4)

(4,4)

代码

#include<iostream>
#include<queue>
using namespace std;
int ans[25];
int minnum=25;//到达终点时点的个数
struct dot {
int n;//顶点标号
int num;//顶点的值（0，1）
int count;//当前路径的点数
int temp[24];//当前路径
};
//出队函数
void Pop(queue<dot>* q);
//入队函数
void Push(queue<dot>* q, dot d);
void getAns(queue<dot>* q, dot d[], int pos);
int main() {
dot d[25];
for (int i = 0; i < 25; i++) {
d[i].n = i;
cin >> d[i].num;
d[i].count = 1;
d[i].temp[0] = 0;//起点为0
}
queue<dot>* q=new queue<dot>[25];//
q->push(d[0]);//起点入队
getAns(q, d, 0);
for (int i = 0; i < minnum; i++) {
int x = ans[i] / 5;
int y = ans[i] % 5;
cout <<"("<<x<<","<<y<<")" << endl;
}
delete[] q;
return 0;
}
void Pop(queue<dot>* q) {
q->pop();
}
void Push(queue<dot>* q, dot d) {
q->push(d);
}
void getAns(queue<dot>* q, dot d[], int pos) {
int i = 0;
//如果已经到达终点
if (pos == 24) {
if (d[pos].count < minnum) {
for (int i = 0; i < 25; i++) {
ans[i] = d[pos].temp[i];
}
minnum = d[pos].count;
}
else
return;
}
Pop(q);//当前起点出队
if (d[pos].count > minnum) {
return;//若已经大于最小点数还未到达终点，剪枝
}
//优先级：右、下、上、左
通过if限界
if (pos % 5 != 4 && d[pos + 1].num != 1) {//不在右边界并且右边不为墙
Push(q, d[pos + 1]);
d[pos + 1].count = d[pos].count+1;
for (i = 0; i < 25; i++) {
d[pos + 1].temp[i] = d[pos].temp[i];
}
d[pos + 1].temp[d[pos + 1].count-1] = pos + 1;
getAns(q, d, pos + 1);
}
if (pos / 5 != 4 && d[pos + 5].num != 1) {//不在下边界并且下方不为墙
Push(q, d[pos + 5]);
d[pos + 5].count = d[pos].count + 1;
for (i = 0; i < 25; i++)
d[pos + 5].temp[i] = d[pos].temp[i];
d[pos + 5].temp[d[pos + 5].count-1] = pos + 5;
getAns(q, d, pos + 5);
}
if (pos / 5 != 0 && d[pos - 5].num != 1) {//不在上边界
Push(q, d[pos - 5]);
d[pos - 5].count = d[pos].count + 1;
for (i = 0; i < 25; i++)
d[pos - 5].temp[i] = d[pos].temp[i];
d[pos - 5].temp[d[pos - 5].count-1] = pos - 5;
getAns(q, d, pos - 5);
}
if (pos % 5 != 0 && d[pos - 1].num != 1) {//不在左边界
Push(q, d[pos - 1]);
d[pos - 1].count = d[pos].count + 1;
for (i = 0; i < 25; i++)
d[pos - 1].temp[i] = d[pos].temp[i];
d[pos - 1].temp[d[pos - 1].count-1] = pos - 1;
getAns(q, d, pos - 1);
}
}

最后

以上就是从容音响为你收集整理的迷宫问题——分支限界法的全部内容，希望文章能够帮你解决迷宫问题——分支限界法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。