Рекурсивное лямбда-выражение для нахождения пути (путей) через ориентированный граф?
-
29-08-2019 - |
Вопрос
Мне нужно найти путь или пути вниз по сложной структуре графа.График построен с использованием чего-то подобного этому:
class Node
{
public string Value { get; set;}
public List<Node> Nodes { get; set;}
public Node()
{
Nodes = new List<Node>();
}
}
Что усложняет это, так это то, что узлы могут ссылаться на более ранний узел.Например,
A -> C -> E -> A
Что мне нужно сделать, это получить список стеков, которые представляют пути через узлы, пока я не доберусь до узла с определенным значением.Поскольку возможно, что может быть доступно несколько очень больших путей, у нас может быть максимальное количество узлов, которые мы можем попробовать.
List<Stack<Node>> paths = FindPaths(string ValueToFind, int MaxNumberNodes);
У кого-нибудь есть способ создать это (или что-то подобное)?Я делал рекурсию в прошлом, но у меня по какой-то причине от одной мысли об этом совсем мозги пукают.В моем вопросе указано лямбда-выражение, но использование лямбда-выражения необязательно.Я был бы благодарен за любое решение.
Боковое примечание:Я поднял класс из отличного ответа аку на этот вопрос о рекурсии.Хотя его элегантное решение, показанное ниже, пересекает древовидную структуру, оно, похоже, не обеспечивает достаточной гибкости для выполнения того, что мне нужно (например, отклонять циклические пути и отслеживать успешные пути).
Action<Node> traverse = null;
traverse = (n) => { Console.WriteLine(n.Value); n.Nodes.ForEach(traverse);};
traverse(root); // where root is the tree structure
Редактировать:
Основываясь на приведенных ниже комментариях и ответах, я нашел отличное решение в CodeProject.Он использует алгоритм поиска пути A *. Вот ссылка.
Решение
Если ваша проблема связана с поиском пути, вы можете поискать в Google "звездочку" или "А *".Это распространенный и эффективный алгоритм поиска пути.Видишь эта статья приведу пример, непосредственно связанный с вашей проблемой.
Возможно, вы также захотите взглянуть на Алгоритм Дейсктры
Другие советы
Я не уверен, является ли ваш предполагаемый результат ВСЕ пути к цели, к Лучшие путь к цели (по некоторому показателю, напримердлина пути), или просто Любой путь к цели.
Предполагая последнее, я бы начал с рекурсивной стратегии, включая отслеживание посещенных узлов, как описано Бранном, и внес эти изменения:
Добавьте параметры для представления искомой цели, набора успешных путей и текущего пути с самого начала.
При вводе узла, соответствующего цели, добавьте текущий путь (плюс текущий узел) в список успешных путей.
Расширьте текущий путь с помощью текущего узла, чтобы создать путь, передаваемый при любых рекурсивных вызовах.
Вызовите начальный
ExploreGraph
вызов с пустым путем и пустым списком успешных путей.
По завершении ваш алгоритм пересечет весь график, и будут зафиксированы отдельные пути к цели.
Это всего лишь краткий набросок, но вы должны быть в состоянии дополнить его в соответствии с вашими конкретными потребностями.
Я не знаю точно, чего вы хотите достичь, но эта проблема с циклическими ссылками обычно решается путем пометки уже посещенных узлов.Просто используйте Словарь для отслеживания узлов, которые уже были посещены, чтобы не зацикливаться.
Пример :
public void ExploreGraph(TreeNode tn, Dictionary<TreeNode, bool> visitednodes)
{
foreach (Treenode childnode in tn.Nodes)
{
if (!visitedNodes.ContainsKey(childnode))
{
visitednodes.Add(childnode);
ExploreGraph(childnode, visitednodes);
}
}
}