algorithm - 使用元胞自动机对图中的顶点进行可达性分析

Question

测试图中节点的可达性（有向），可以使用 cellualr Automata 来完成吗？实际上要考虑的是实现一种算法，使用 CA 检查从指定顶点到节点的可达性。甚至可能吗？CA有能力做到这一点吗？

任何想法？

Answer 1

你的第一个问题的答案是肯定的，因为康威的生命游戏已经完成。这大致意味着元胞自动机（尤其是生命游戏）可以计算您的 PC 可以执行的任何功能。

我不熟悉证明的细节，但我认为它是基于将图灵机转换为生命游戏实例的某种方式。如果您可以构建图灵机来解决问题，您可能可以使用该技术将其转换为元胞自动机。

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

Answer 2

我知道在任意图中没有通用元胞自动机可达到，但在 1990 年代中期，有一些研究使用元胞自动机解决矩形网格迷宫中的迷宫问题。可以在此处找到该技术的一种易于理解的描述。如果您有 ACM 访问权限，则可以在此处阅读原始论文。假设您的图形是 2D 网格，使寻路算法适应可达性应该不是特别困难。

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

Answer 3

我不能肯定地说 CA 会做你想做的事。但是Dijkstra可用于确定从一个节点到另一个节点的最短路径（如果存在路径）。不过 Dijkstra 的复杂性很高。