使用元胞自动机对图中的顶点进行可达性分析
测试图中节点的可达性（有向），可以使用 cellualr 自动机来完成吗？实际上，我们的想法是实现一种算法，使用 CA 检查指定顶点的点头的可达性。有可能吗？ CA有能力做到这一点吗？
有什么想法吗？
Testing reachability of a node in a graph (directed), can be done using cellualr Automata? Actually what's in mind, is to implement an algorithm that checks reachability of a nod from a specified vertex, using CA. Is it even possible? Is CA capable of doing that?
Any idea?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我不能肯定地说 CA 会做你想做的事。但是 Dijkstra 可用于确定最短路径（如果存在路径）节点到另一个。 Dijkstra 的复杂性很高。
I cannot say for sure that CA will do what you want. But Dijkstra can be used to determine the shortest path (also if a path exists) from one node to another. The Complexity of Dijkstra is high though.
第一个问题的答案是肯定的，因为康威的生命游戏是图灵完备。这大致意味着元胞自动机（特别是生命游戏）可以计算您的 PC 可以计算的任何功能。
我不熟悉证明的细节，但我认为它是基于将图灵机转变为生命游戏实例的某种方式。如果您可以构建一台图灵机来解决该问题，您可能可以使用该技术将其转换为元胞自动机。
我建议使用深度优先搜索作为底层算法，因为它比 Dijkstra 算法简单得多，而且元胞自动机可能不是解决问题的有效方法。
The answer to your first question is yes, since Conway's Game of Life is turing complete. That roughly means that cellular automata (particularly the Game of Life) can compute any function your PC can.
I am not familiar with the details of the proof but I would assume that it is based on some way of transforming a Turing machine into an instance of the Game of Life. If you can construct a Turing machine to solve the problem you can probably transform it into a cellular automaton using that technique.
I would recommend using a depth first search as the underlying algorithm since it is much simpler than Dijkstra's Algorithm and a cellular automaton is probably not an efficient way of solving the problem anyway.
据我所知，还没有通用的元胞自动机能够实现任意图中的可达性，但在 20 世纪 90 年代中期，有一些关于使用元胞自动机在矩形网格迷宫中求解迷宫的研究。可以在此处找到该技术的一种易于理解的描述。如果您具有 ACM 访问权限，可以在此处阅读原始论文。假设您的图形是二维网格，那么将寻路算法调整为可达性应该不会特别困难。
我会继续寻找，看看是否能找到更通用的算法。
I know of no general cellular automaton for reachability in arbitrary graphs, but in the mid 1990s there was some research into maze-solving in rectangular grid mazes using cellular automata. One accessible description of the technique can be found here. If you have ACM access, you can read the original paper here. It should not be particularly difficult to adapt the algorithm for pathfinding to reachability, assuming that your graph is a 2D grid.
I will keep looking and see if I can find a more general algorithm.