迷宫问题如何找出所有路径和最短路径

显示全部楼层 · 2021-1-27 06:33:05

书里所涉及的迷宫问题都是只给出一条路径而已的，能否弄一个实验报告改进迷宫问题找出全部路径和最短路径？用C或C语言写的程序
分 -->

千问 · 2021-1-27 06:33:05

广搜到底.

千问 · 2021-1-27 06:33:05

最短路径,广搜，比较
最快找到，A*
全部路径,广搜,深搜，A*，瞎走都可以

千问 · 2021-1-27 06:33:05

好的迷宫只有一条路径（参见我的超级迷宫1.0)
如2楼所说，A*的方法是最快的

千问 · 2021-1-27 06:33:05

迷宫生成其实很简单.

千问 · 2021-1-27 06:33:05

迷宫生成，刚才想了下，大概是N*logN复杂度,N=m*n是格子的数量
1，O(N)时间内，插入哈希表的数组Hash[]，就是有N个集合.用x*X+y做Key。
2,开始每个集合都是一个格子，后续会增加，但每步都随机挑选两个集合，比较大小，选择较小的那个集合，这一步是O(1)，这样小的集合无论如何不可能大过N/2。

3，遍历这个里边的格子，如果上下左右4个方向的格子不在这个集合里，把外边的格子和方向信息==“墙”加入墙链表,这两步最坏是(2*N+2)/2其实还是O(N)级别。
4，在墙链表随机选一个墙拆掉。
5，重复这个过程，直到只有一个集合，因为每次合并两个集合，所以会产生对数LogN。
总体是第5步乘第3步，是N*LogN级别的。牺牲线性空间。

千问 · 2021-1-27 06:33:05

使用Hash的目的是O(1)判断格子是否在集合内

千问 · 2021-1-27 06:33:05

引用楼主zhangjiesong的回复:书里所涉及的迷宫问题都是只给出一条路径而已的，能否弄一个实验报告改进迷宫问题找出全部路径和最短路径？用C或C语言写的程序
把求一条路径的算法改成求所有路径的算法很简单：求出一条路径，把这条路径给堵上，重新开始求下一条路径，直到堵得没有路径为止。这样就能求出所有路径。所有路径都出来了，最短路径就知道了。

千问 · 2021-1-27 06:33:05

引用7楼icansaymyabc的回复:引用楼主zhangjiesong的回复:
书里所涉及的迷宫问题都是只给出一条路径而已的，能否弄一个实验报告改进迷宫问题找出全部路径和最短路径？用C或C语言写的程序
把求一条路径的算法改成求所有路径的算法很简单：求出一条路径，把这条路径给堵上，重新开始求下一条路径，直到堵得没有路径为止。这样就能求出所有路径。所有路径都出来了，最短路径就知道了。
这方法有个问题，把路径给堵住了，其他路径可能会通过这个路径的某个点，这样就会出问题。