基于元胞自动机的图中顶点的可达性分析

Question

测试图中节点的可达性(有向)，可以使用cellualr Automata完成吗？实际上，我们考虑的是实现一个算法，该算法使用CA检查节点从指定顶点的可达性。这有可能吗？CA有能力做到这一点吗？

有什么想法吗？

Answer 1

第一个问题的答案是肯定的，因为Conway's Game of Life是turing complete。

我不熟悉证明的细节，但我假设它是基于某种方式将图灵机转变为生命游戏的实例。如果你能构造一个图灵机来解决这个问题，你就可以用这种技术把它变成一个细胞自动机。

我建议使用深度优先搜索作为底层算法，因为它比Dijkstra算法简单得多，而且细胞自动机可能不是解决问题的有效方法。

Answer 2

据我所知，在任意图中没有通用的元胞自动机可达性，但在20世纪90年代中期，有一些使用元胞自动机在矩形网格迷宫中求解迷宫的研究。可以在here上找到该技术的一个可访问的描述。如果你有ACM访问权限，你可以阅读原始的论文here。假设您的图是2D网格，将寻径算法调整为可达性应该不是特别困难。

我会继续寻找，看看是否能找到更通用的算法。

Answer 3

我不能肯定CA会做你想做的事。但是Dijkstra可以用来确定从一个节点到另一个节点的最短路径(如果存在路径的话)。不过，Dijkstra的复杂性很高。