Обход графа C# - отслеживание пути между любыми двумя узлами
Ищете хороший подход для отслеживания обхода в ширину между двумя узлами, ничего не зная о графе. По сравнению с Depth-First (где вы можете выбросить путь, если он не получается), у вас может быть довольно много «открытых» возможностей во время обхода.
Ответы 4
Наивный подход состоит в том, чтобы построить дерево с исходным узлом в качестве корня и всеми его соединениями в качестве его дочерних элементов. В зависимости от количества места, которое у вас есть, вам может потребоваться исключить циклы по мере продвижения. Вы можете сделать это с помощью растрового изображения, где каждый бит соответствует отдельному узлу в графе. Когда вы достигнете целевого узла, вы можете вернуться по родительским ссылкам к корню, и это ваш путь. Поскольку вы сначала идете вширь, вы уверены, что это кратчайший путь, даже если вы не исключаете циклы.
Для поиска в ширину вам нужно сохранить как минимум две вещи. Один - это набор уже посещенных узлов, а другой - набор узлов, которые напрямую доступны из посещенных узлов, но сами не посещаются. Затем вы продолжаете перемещать состояния из последнего набора в первый, добавляя к последнему новые достижимые состояния. Если вам нужен путь от корня к какому-либо узлу (узлам), вам также необходимо сохранить родительский узел для каждого узла (кроме корня) в вышеупомянутых наборах.
Обычно объединение набора посещенных узлов и набора непосещенных дочерних узлов (то есть набора видимых узлов) сохраняется в хеш-таблице. Это необходимо для того, чтобы иметь возможность быстро определять, было ли ранее обнаружено «новое» состояние, и игнорировать его, если это так. Если у вас действительно большое количество состояний, вам действительно может понадобиться битовый массив (как упоминал Джозеф Буй (57509), но если ваши состояния не могут использоваться (прямо или косвенно) в качестве индексов этого массива, вам нужно будет использовать хэш функция для сопоставления состояний с индексами. В последнем случае вы можете полностью игнорировать определенные состояния, потому что они сопоставлены с тем же индексом, что и другой (и видимый) узел, поэтому вы можете быть осторожны с этим. Кроме того, чтобы получить путь вам по-прежнему нужно хранить родительскую информацию, что в значительной степени сводит на нет использование битового массива.
Набор невидимых, но видимых узлов может быть сохранен в виде очереди. (Битовые массивы бесполезны для этого набора, потому что массив будет в основном пустым, а поиск следующего установленного бита относительно дорого.)
Я только что представил решение здесь, которое также применимо к этому вопросу.
По сути, я просто веду один список (на самом деле стек) посещенных узлов. Добавьте узел в список непосредственно перед повторением или сохранением решения. Всегда удаляйте из списка сразу после.
Если вы используете .NET 3.5, подумайте об использовании Hashset для предотвращения расширения повторяющихся узлов, это происходит, когда на вашем графике есть циклы. Если у вас есть какие-либо сведения о содержимом графа, подумайте о реализации Поиск, чтобы уменьшить количество расширяемых узлов. Удачи, и я надеюсь, что у вас все получится.
Если вы все еще являетесь поклонником древовидной архитектуры, существует множество отличных книг по теме графов и поиска по графам, например, «Искусственный интеллект: современный подход» Питера Норвига и Стюарта Рассела.
Ссылки в моем ответе содержат ошибку, это Hashset: http://msdn.com/en-us/library/bb359438.aspx и A * search: http://en.wikipedia.org/wiki/A*_search_algorithm