求助!!! 一个DFS算法相关的问题请教佬们!!!

开发调优
1

问题描述
给定一个不大于10x10的方阵，在其中随机选择n(不大于10)个不重复的点作为障碍，并在剩余的点中随机选择一个作为起点。从起点开始，要求在不间断的情况下遍历除障碍之外的所有点,不能走重复的点,一笔画路径问题,求解是否存在这样的一条路径。

类似下图
(S 表示起点, X 表示障碍)：
方阵左上角第一个点的index为0, 右上角最后一个点的index为4
方阵左下角第一个点的index为20, 右下角最后一个点的index为24
这个方阵有解,且求解路径为:
7 ,12 ,13 ,8 ,3 ,4 ,9 ,14 ,19 ,24 ,23 ,22 ,21 ,20 ,15 ,16 ,11 ,6 ,1 ,0 ,

*   *   X   *   *   
X   *   S   *   *   
X   *   *   *   *   
*   *   X   X   *   
*   *   *   *   *

我现在用dfs实现了求解,在方阵比较小的情况下(6x6及以下)可以接受,但是当方阵数量大于等于7x7开始,算法就非常慢,我找了些资料,但是也没有找到较好的方法进行优化,AI告诉我这是NP完全问题,请佬们给我指一下路,应该如何做优化,谢谢了 :grin:

2

从 软件开发 到 快问快答

3

是存在性问题还是构造性问题

  • 如果是前者，判断方阵里除障碍外是否有两点没有可达路径，那么只需要判断障碍是否把方阵隔离成多个封闭域，同一个域内的两个点总有可达路径的

  • 如果是后者，要给出任意两点间的可达路径，那 10 x 10 的 dfs 时间上应该还过得去，A* 其实也是 dfs 的变体，找可达路径可以用 A* 的。如果是时间太慢，我估计要检查一下 dfs 的访问标记写得是不是有问题。

1 个赞
4

题目要的是一次走完所有点吧，单判断封闭应该不够，比如这个

.x.
...
...

并不能一次走完

1 个赞
5

要看这里怎么理解了，我猜你的意思不重复的一笔画路径问题，但看它这句话好像没有说不重复

不过判断一笔画问题，那不是更容易了，直接套奇偶性？

1 个赞
6

谢谢,抱歉,我描述没有写清楚,确实是走不重复的一笔画问题

7

A*不是要构造个启发函数嘛

1 个赞
8

也可用bfs+优先队列，或者dfs你做下剪枝

1 个赞
9

请问剪枝策略应该是怎么样的呢?

10

哦哈密顿路径（Hamiltonian Path）问题，那确实只能 dfs 回溯了，A* 是搜索最短路的，这里用不上

1 个赞
11

哦哦,好的,如果A*这类求解最短路径的算法用不上我就暂时不去研究了,谢谢

12

就是在访问一个新点后，如果它周围的未访问点数量少于2且它不是终点，则此路径不能形成有效路径

2 个赞
13

我再瞅瞅题目，看差了

1 个赞
14

不知道我理解得对不对,如果路径中倒数第二个点,它的下一个是终点,它现在的周围的未访问点应该1,这样剪枝好像不对

15

先判断是否构成哈密顿回路然后再回溯剪枝吧

1 个赞
16

:sweat_smile:哈哈哈是的，我说错了，应该是统计当前点的所有未被访问且不是障碍的邻居数，如果当前点在访问后会导致某个邻居点的未访问邻居数少于1且不是终点，则剪枝

1 个赞
17

嗯嗯,谢谢,我理解下来,感觉这个剪枝策略应该对算法整体影响不大, 但还是衷心的感谢您:grinning:

18

谢谢 :grinning:,我不太懂哈密顿回路,我先去学习一下,再向您请教在这种情况下应该如何剪枝, :grinning:

19

帮顶

1 个赞
20

我刚才理解错了,这个剪枝策略应该是会有一定效果的,谢谢 :grinning: