두 그래프 노드 사이의 모든 경로 찾기

두 그래프 노드 사이의 모든 경로 찾기

---

나는 경로 네트워크에서 상호 연결된 노드 사이의 최단 경로를 검색하기 위해 Dijkstras 알고리즘 구현을 작업 중입니다. 나는 implentation이 작동합니다. 시작 노드를 알고리즘에 전달할 때 모든 노드에 대한 모든 최단 경로를 반환합니다.

내 질문 : 노드 A에서 노드 G까지 가능한 모든 경로를 검색하거나 노드 A에서 가능한 모든 경로를 검색하고 다시 노드 A로 돌아가는 방법은 무엇입니까?

---

기하 급수적 인 수의 단순 경로가 있기 때문에 가능한 모든 경로를 찾는 것은 어려운 문제입니다. k 번째 최단 경로 (또는 최장 경로)를 찾는 것조차 NP-Hard 입니다.

에서 [UP 특정 길이 또는 모든 경로] 모든 경로를 찾을 수있는 한 가지 가능한 솔루션 s으로는 t이다 BFS 유지하지 않고, visited세트를, 또는 가중 버전 - 당신이 사용할 수있는 균일 한 비용 검색

또한주기가있는 모든 그래프에는 [ DAG 가 아님 ] s~ 사이 에 무한한 경로가있을 수 있습니다 t.

---

가능한 한 시간 내에 이것을 할 수 없다는 과학적 증거의 (약간 작은) 버전을 (이해할 수 있지만, 제 생각에) 줄 것입니다.

내가 증명할 것은 임의의 그래프에서 두 개의 선택된 노드와 별개의 노드 (예 : sand t) 사이의 모든 단순 경로를 열거하는 시간 복잡도 G가 다항식이 아니라는 것입니다. 이러한 노드 사이의 경로 양에만 관심이 있으므로 에지 비용은 중요하지 않습니다.

물론 그래프에 잘 선택된 속성이 있으면 쉽게 할 수 있습니다. 그래도 일반적인 경우를 고려하고 있습니다.

---

s와 사이의 모든 단순 경로를 나열하는 다항식 알고리즘이 있다고 가정합니다 t.

G가 연결되어 있으면 목록이 비어 있지 않습니다. 경우 G아니며 s및 t다른 구성 요소에 아무도 없기 때문에, 그것은 그들 사이의 모든 경로를 나열하는 정말 쉽습니다! 동일한 구성 요소에있는 경우 전체 그래프가 해당 구성 요소로만 구성되어 있다고 가정 할 수 있습니다. 그래서 G실제로 연결되어 있다고 가정합시다 .

나열된 경로의 수는 다항식이어야합니다. 그렇지 않으면 알고리즘이 모든 경로를 반환 할 수 없습니다. 그것들을 모두 열거하면 가장 긴 것을 줄 것이므로 거기에 있습니다. 경로 목록이 있으면이 가장 긴 경로를 가리키는 간단한 절차를 적용 할 수 있습니다.

이 가장 긴 경로가의 모든 정점을 횡단해야한다는 것을 보여줄 수 있습니다 (일관되게 말할 수는 없지만) G. 따라서 우리는 다항식 절차를 사용하는 Hamiltonian Path 를 방금 찾았습니다 ! 그러나 이것은 잘 알려진 NP-hard 문제입니다.

그런 다음 P = NP가 아니면 우리가 가지고 있다고 생각한이 다항식 알고리즘이 존재할 가능성 이 매우 낮다 는 결론을 내릴 수 있습니다 .

---

기본적으로 한 노드에서 다른 노드로의 가능한 모든 경로를 찾는 버전을 구현했지만 가능한 '주기'를 계산하지 않습니다 (사용중인 그래프는 주기적 임). 따라서 기본적으로 하나의 노드는 동일한 경로 내에서 두 번 나타나지 않습니다. 그래프가 비순환 적이라면 두 노드 사이에서 가능한 모든 경로를 찾는 것 같다고 말할 수 있습니다. 잘 작동하는 것 같고 그래프 크기가 ​​~ 150 인 경우 거의 즉시 내 컴퓨터에서 실행되지만 실행 시간은 지수와 비슷해야하므로 빠르게 느려질 것입니다. 그래프가 커집니다.

다음은 내가 구현 한 것을 보여주는 자바 코드입니다. 더 효율적이거나 우아한 방법이 있어야한다고 확신합니다.

Stack connectionPath = new Stack();
List<Stack> connectionPaths = new ArrayList<>();
// Push to connectionsPath the object that would be passed as the parameter 'node' into the method below
void findAllPaths(Object node, Object targetNode) {
    for (Object nextNode : nextNodes(node)) {
       if (nextNode.equals(targetNode)) {
           Stack temp = new Stack();
           for (Object node1 : connectionPath)
               temp.add(node1);
           connectionPaths.add(temp);
       } else if (!connectionPath.contains(nextNode)) {
           connectionPath.push(nextNode);
           findAllPaths(nextNode, targetNode);
           connectionPath.pop();
        }
    }
}

---

다음 은 DFS 수정을 사용하여 s에서 t까지 모든 경로를 찾고 인쇄하는 알고리즘입니다. 또한 동적 프로그래밍을 사용하여 가능한 모든 경로의 수를 찾을 수 있습니다. 의사 코드는 다음과 같습니다.

AllPaths(G(V,E),s,t)
 C[1...n]    //array of integers for storing path count from 's' to i
 TopologicallySort(G(V,E))  //here suppose 's' is at i0 and 't' is at i1 index

  for i<-0 to n
      if i<i0
          C[i]<-0  //there is no path from vertex ordered on the left from 's' after the topological sort
      if i==i0
         C[i]<-1
      for j<-0 to Adj(i)
          C[i]<- C[i]+C[j]

 return C[i1]

---

찾기 _ 경로 [s, t, d, k]

이 질문은 이제 조금 오래되었습니다.하지만 반지에 모자를 던질 것입니다.

개인적으로 다음과 같은 형식의 알고리즘이 find_paths[s, t, d, k]유용합니다.

• s는 시작 노드입니다.
• t는 대상 노드입니다.
• d는 검색 할 최대 깊이입니다.
• k는 찾을 경로의 수입니다.

무한대의 프로그래밍 언어의 양식을 사용 d하고 k당신에게 모든 paths§을 줄 것이다.

§ 분명히 당신은 유향 그래프를 사용하고 모든 원하는 경우 방향성 사이의 경로를 s그리고 t이 두 가지를 실행해야합니다 :

find_paths[s, t, d, k] <join> find_paths[t, s, d, k]

---

도우미 기능

나는 개인적으로 재귀를 좋아하지만 때때로 어려울 수 있지만 어쨌든 먼저 도우미 기능을 정의하겠습니다.

def find_paths_recursion(graph, current, goal, current_depth, max_depth, num_paths, current_path, paths_found)
  current_path.append(current)

  if current_depth > max_depth:
    return

  if current == goal:
    if len(paths_found) <= number_of_paths_to_find:
      paths_found.append(copy(current_path))

    current_path.pop()
    return

  else:
    for successor in graph[current]:
    self.find_paths_recursion(graph, successor, goal, current_depth + 1, max_depth, num_paths, current_path, paths_found)

  current_path.pop()

주요 기능

그 과정에서 핵심 기능은 간단합니다.

def find_paths[s, t, d, k]:
  paths_found = [] # PASSING THIS BY REFERENCE  
  find_paths_recursion(s, t, 0, d, k, [], paths_found)

---

먼저 몇 가지 사항을 확인하십시오.

• 위의 의사 코드는 언어의 매시업이지만 가장 강하게 파이썬과 닮았습니다. 엄격한 복사-붙여 넣기는 작동하지 않습니다.
• [] 초기화되지 않은 목록입니다.이 목록을 선택한 프로그래밍 언어에 해당하는 것으로 바꿉니다.
• paths_found참조 로 전달됩니다 . 재귀 함수가 아무것도 반환하지 않는 것이 분명합니다. 이를 적절히 처리하십시오.
• 여기 graph에 어떤 형태의 hashed구조를 가정하고 있습니다. 그래프를 구현하는 방법에는 여러 가지가 있습니다. 어느 쪽이든, 방향성 그래프 graph[vertex]에서 인접한 정점 목록을 얻습니다 . 그에 따라 조정하십시오.
• 이것은 "버클"(자체 루프), 사이클 및 다중 에지를 제거하기 위해 사전 처리했다고 가정합니다.

---

사소하지 않은 그래프에는 지수 수가 있기 때문에 일반적으로 원하지 않습니다. 정말로 모든 (단순) 경로 또는 모든 (단순) 사이클을 얻으려면 하나를 찾은 다음 (그래프를 따라 이동하여) 다른 경로로 되돌아갑니다.

---

여러분이 원하는 것은 BFS를 기반으로하는 Ford–Fulkerson 알고리즘의 어떤 형태라고 생각합니다. 두 노드 사이의 모든 증가 경로를 찾아 네트워크의 최대 흐름을 계산하는 데 사용됩니다.

http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm

---

실제로 최단 경로에서 최장 경로로 경로를 정렬하는 데 관심이 있다면 수정 된 A * 또는 Dijkstra Algorithm을 사용하는 것이 훨씬 낫습니다 . 약간의 수정으로 알고리즘은 가장 짧은 경로를 먼저 순서대로 원하는만큼 가능한 많은 경로를 반환합니다. 그래서 당신이 정말로 원하는 것이 가장 짧은 것에서 가장 긴 것까지 순서가있는 모든 가능한 경로라면 이것이 갈 길이다.

가장 짧은 것에서 가장 긴 순서로 정렬 된 모든 경로를 반환 할 수있는 A * 기반 구현을 원한다면 다음을 수행합니다. 몇 가지 장점이 있습니다. 먼저 가장 짧은 것부터 가장 긴 것까지 정렬하는 것이 효율적입니다. 또한 필요한 경우에만 각 추가 경로를 계산하므로 모든 단일 경로가 필요하지 않기 때문에 일찍 중지하면 처리 시간이 절약됩니다. 또한 다음 경로를 계산할 때마다 후속 경로에 데이터를 재사용하므로 더 효율적입니다. 마지막으로 원하는 경로를 찾으면 조기에 중단하여 계산 시간을 절약 할 수 있습니다. 경로 길이별로 정렬하는 데 관심이 있다면 전반적으로 가장 효율적인 알고리즘이어야합니다.

import java.util.*;

public class AstarSearch {
    private final Map<Integer, Set<Neighbor>> adjacency;
    private final int destination;

    private final NavigableSet<Step> pending = new TreeSet<>();

    public AstarSearch(Map<Integer, Set<Neighbor>> adjacency, int source, int destination) {
        this.adjacency = adjacency;
        this.destination = destination;

        this.pending.add(new Step(source, null, 0));
    }

    public List<Integer> nextShortestPath() {
        Step current = this.pending.pollFirst();
        while( current != null) {
            if( current.getId() == this.destination )
                return current.generatePath();
            for (Neighbor neighbor : this.adjacency.get(current.id)) {
                if(!current.seen(neighbor.getId())) {
                    final Step nextStep = new Step(neighbor.getId(), current, current.cost + neighbor.cost + predictCost(neighbor.id, this.destination));
                    this.pending.add(nextStep);
                }
            }
            current = this.pending.pollFirst();
        }
        return null;
    }

    protected int predictCost(int source, int destination) {
        return 0; //Behaves identical to Dijkstra's algorithm, override to make it A*
    }

    private static class Step implements Comparable<Step> {
        final int id;
        final Step parent;
        final int cost;

        public Step(int id, Step parent, int cost) {
            this.id = id;
            this.parent = parent;
            this.cost = cost;
        }

        public int getId() {
            return id;
        }

        public Step getParent() {
            return parent;
        }

        public int getCost() {
            return cost;
        }

        public boolean seen(int node) {
            if(this.id == node)
                return true;
            else if(parent == null)
                return false;
            else
                return this.parent.seen(node);
        }

        public List<Integer> generatePath() {
            final List<Integer> path;
            if(this.parent != null)
                path = this.parent.generatePath();
            else
                path = new ArrayList<>();
            path.add(this.id);
            return path;
        }

        @Override
        public int compareTo(Step step) {
            if(step == null)
                return 1;
            if( this.cost != step.cost)
                return Integer.compare(this.cost, step.cost);
            if( this.id != step.id )
                return Integer.compare(this.id, step.id);
            if( this.parent != null )
                this.parent.compareTo(step.parent);
            if(step.parent == null)
                return 0;
            return -1;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Step step = (Step) o;
            return id == step.id &&
                cost == step.cost &&
                Objects.equals(parent, step.parent);
        }

        @Override
        public int hashCode() {
            return Objects.hash(id, parent, cost);
        }
    }

   /*******************************************************
   *   Everything below here just sets up your adjacency  *
   *   It will just be helpful for you to be able to test *
   *   It isnt part of the actual A* search algorithm     *
   ********************************************************/

    private static class Neighbor {
        final int id;
        final int cost;

        public Neighbor(int id, int cost) {
            this.id = id;
            this.cost = cost;
        }

        public int getId() {
            return id;
        }

        public int getCost() {
            return cost;
        }
    }

    public static void main(String[] args) {
        final Map<Integer, Set<Neighbor>> adjacency = createAdjacency();
        final AstarSearch search = new AstarSearch(adjacency, 1, 4);
        System.out.println("printing all paths from shortest to longest...");
        List<Integer> path = search.nextShortestPath();
        while(path != null) {
            System.out.println(path);
            path = search.nextShortestPath();
        }
    }

    private static Map<Integer, Set<Neighbor>> createAdjacency() {
        final Map<Integer, Set<Neighbor>> adjacency = new HashMap<>();

        //This sets up the adjacencies. In this case all adjacencies have a cost of 1, but they dont need to.
        addAdjacency(adjacency, 1,2,1,5,1);         //{1 | 2,5}
        addAdjacency(adjacency, 2,1,1,3,1,4,1,5,1); //{2 | 1,3,4,5}
        addAdjacency(adjacency, 3,2,1,5,1);         //{3 | 2,5}
        addAdjacency(adjacency, 4,2,1);             //{4 | 2}
        addAdjacency(adjacency, 5,1,1,2,1,3,1);     //{5 | 1,2,3}

        return Collections.unmodifiableMap(adjacency);
    }

    private static void addAdjacency(Map<Integer, Set<Neighbor>> adjacency, int source, Integer... dests) {
        if( dests.length % 2 != 0)
            throw new IllegalArgumentException("dests must have an equal number of arguments, each pair is the id and cost for that traversal");

        final Set<Neighbor> destinations = new HashSet<>();
        for(int i = 0; i < dests.length; i+=2)
            destinations.add(new Neighbor(dests[i], dests[i+1]));
        adjacency.put(source, Collections.unmodifiableSet(destinations));
    }
}

위 코드의 출력은 다음과 같습니다.

[1, 2, 4]
[1, 5, 2, 4]
[1, 5, 3, 2, 4]

Notice that each time you call nextShortestPath() it generates the next shortest path for you on demand. It only calculates the extra steps needed and doesnt traverse any old paths twice. Moreover if you decide you dont need all the paths and end execution early you've saved yourself considerable computation time. You only compute up to the number of paths you need and no more.

Finally it should be noted that the A* and Dijkstra algorithms do have some minor limitations, though I dont think it would effect you. Namely it will not work right on a graph that has negative weights.

Here is a link to JDoodle where you can run the code yourself in the browser and see it working. You can also change around the graph to show it works on other graphs as well: http://jdoodle.com/a/ukx

---

I suppose you want to find 'simple' paths (a path is simple if no node appears in it more than once, except maybe the 1st and the last one).

Since the problem is NP-hard, you might want to do a variant of depth-first search.

Basically, generate all possible paths from A and check whether they end up in G.

---

There's a nice article which may answer your question /only it prints the paths instead of collecting them/. Please note that you can experiment with the C++/Python samples in the online IDE.

http://www.geeksforgeeks.org/find-paths-given-source-destination/

참고URL : https://stackoverflow.com/questions/9535819/find-all-paths-between-two-graph-nodes