Анализ достижимости вершины в графе с использованием клеточных автоматов

Question

Проверка достижимости узла в графе (направленном) может быть выполнена с помощью cellualr Automata?На самом деле, имеется в виду реализовать алгоритм, который проверяет достижимость узла из указанной вершины, используя CA.Это вообще возможно?CA способен сделать это?

Есть идеи?

Answer 1

Ответ на ваш первый вопрос - да, поскольку Игра жизни Конвея завершена . Это примерно означает, что сотовые автоматы (особенно Game of Life) могут вычислять любую функцию, которую может выполнять ваш компьютер.

Я не знаком с деталями доказательства, но предположил бы, что оно основано на каком-то способе превращения машины Тьюринга в экземпляр Игры Жизни. Если вы можете построить машину Тьюринга для решения этой проблемы, вы, вероятно, сможете превратить ее в клеточный автомат, используя эту технику.

Я бы рекомендовал использовать поиск в глубину в качестве основного алгоритма, поскольку он намного проще, чем алгоритм Дейкстры, и клеточный автомат, вероятно, в любом случае не является эффективным способом решения проблемы.

Answer 2

Я не знаю ни одного общего клеточного автомата для достижимости в произвольных графах, но в середине 1990-х годов было проведено некоторое исследование решения лабиринтов в прямоугольных сетчатых лабиринтах с использованием клеточных автоматов. Одно доступное описание техники можно найти здесь . Если у вас есть доступ к ACM, вы можете прочитать оригинал статьи здесь . Не должно быть особенно сложно адаптировать алгоритм поиска пути к достижимости, предполагая, что ваш график является двумерной сеткой.

Я буду продолжать искать и смогу найти более общий алгоритм.

Answer 3

Не могу с уверенностью сказать, что CA будет делать то, что вы хотите. Но Dijkstra можно использовать для определения кратчайшего пути (также если путь существует) от одного узла к другому. Сложность Дейкстры высокая, хотя.