지시 된 그래프를 통해 경로를 찾기위한 재귀 람다 표현?

StackOverflow https://stackoverflow.com/questions/396296

  •  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);

누구든지 이것 (또는 비슷한 것을 구축 할 수있는 방법이 있습니까? 나는 과거에 재귀를했지만 어떤 이유로 든 이것에 대해 생각하는 뇌 방귀를 완전히 생각하고 있습니다. 내 질문은 람다 표현을 지정했지만 람다를 사용하는 것이 반드시 필요하지는 않습니다. 모든 해결책에 감사드립니다.

참고 사항 : Aku의 훌륭한 답변에서 수업을 들어 올렸습니다. 이 재귀 질문. 아래에 표시된 그의 우아한 솔루션은 트리 구조를 가로 지르지 만 필요한 것을 충분히 유연하게 수행 할 수있는 유연성을 허용하지 않는 것 같습니다 (예 : 원형 및 추적 경로를 기각하는 경로를 무시합니다).

Action<Node> traverse = null;
traverse = (n) => { Console.WriteLine(n.Value); n.Nodes.ForEach(traverse);};
traverse(root);  // where root is the tree structure

편집하다:

아래 주석과 답변의 입력을 기반으로 CodeProject에서 우수한 솔루션을 찾았습니다. A* 경로 찾기 알고리즘을 사용합니다. 여기 링크가 있습니다.

도움이 되었습니까?

해결책

문제가 Pathfinding과 관련이있는 경우 "A Star"또는 "A*"를 위해 Google을 원할 수 있습니다. 공통적이고 효율적인 경로 변형 알고리즘입니다. 보다 이 기사 문제와 직접 관련된 예는.

당신은 또한보고 싶을 수도 있습니다 dijsktra 알고리즘

다른 팁

의도 한 출력이 확실하지 않습니다 모두 목표로가는 길, 베스트 목표로가는 길 (일부 메트릭, 예를 들어 경로 길이) 또는 그냥 어느 목표로가는 길.

후자를 가정하면 Brann이 요약 한 방문 된 노드 추적을 포함한 재귀 전략으로 시작하고 다음을 변경합니다.

  1. 추구하는 목표, 성공적인 경로 수집 및 시작부터 현재 경로를 나타내는 매개 변수를 추가하십시오.

  2. 목표와 일치하는 노드에 들어가면 현재 경로 (현재 노드)를 성공적인 경로 목록에 추가하십시오.

  3. 현재 노드로 현재 경로를 확장하여 재귀 호출에 전달 된 경로를 만듭니다.

  4. 초기를 호출하십시오 ExploreGraph 빈 경로와 빈 경로의 빈 목록으로 전화하십시오.

완료되면 알고리즘이 전체 그래프를 통과했으며 목표에 대한 뚜렷한 경로가 캡처 될 것입니다.

그것은 단지 빠른 스케치 일 뿐이지 만 특정 요구에 맞게 살일 수 있어야합니다.

나는 당신이 무엇을 달성하고 싶은지 정확히 알지 못하지만,이 순환 참조 문제는 일반적으로 이미 방문한 노드를 태깅하여 해결됩니다. DictionNary를 사용하여 이미 방문한 노드를 추적하여 루프하지 않도록하십시오.

예시 :

  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);
                }
            }
        }
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top