메모리 부족 최단 경로 알고리즘

Question

나는 지침이있는 가중치가없는 그래프로 생각할 수있는 전역 고유 경로 테이블을 가지고 있습니다. 각 노드는 제어중인 실제 하드웨어의 일부 또는 시스템의 고유 한 위치를 나타냅니다. 테이블은 각 노드에 대해 다음을 포함

1. 고유 경로 ID (INT) 성분 (문자 - 'A'또는 'L')의
2. 타입의 콤마 분리 된리스트를 포함
3. 문자열 해당 노드가 연결된 경로 ID (char [])

시작과 끝 노드를 지정하고 두 노드 간의 최단 경로를 찾는 함수를 만들어야합니다. 일반적으로 이것은 매우 간단한 문제이지만 여기에 제가 가지고있는 문제가 있습니다. 매우 제한된 양의 메모리/리소스가 있으므로 동적 메모리 할당 (예 : 대기열/연결된 목록)을 사용할 수 없습니다. 재귀 적이 아니라면 좋을 것입니다. (실제로는 테이블/그래프 자체가 너무 작 으면 큰 문제는 아니지만 현재 26 개의 노드가 있으며 그 중 8 개는 절대 적중되지 않습니다. 최악의 경우 총 약 40 개의 노드가 있습니다).

나는 함께 모으기 시작했지만, 항상 최단 경로를 찾지는 못합니다. 의사 코드는 다음과 같습니다 :

bool shortestPath(int start, int end) 
    if start == end 
    if pathTable[start].nodeType == 'A' 
     Turn on part 
    end if 
    return true 
    else 
    mark the current node 
    bool val 
    for each node in connectedNodes 
     if node is not marked 
     val = shortestPath(node.PathID, end) 
     end if 
    end for 

    if val == true 
     if pathTable[start].nodeType == 'A' 
     turn on part 
     end if 
     return true 
    end if 
    end if 

    return false 

end function 

사람은 방법이 코드를 수정하거나, 나는 그것이 작동되도록하는 데 사용할 수있는 다른 뭔가를 알고하는 방법 중 어떤 아이디어가?

----------------- 편집 -----------------

이 Aasmund의 조언을 복용, 내가 들여다 폭 넓은 우선 검색을 구현합니다. 아래에는 내가 온라인에서 찾은 의사 코드를 사용하여 빠르게 던진 C# 코드가 몇 개 있습니다.

는 입력 : 그래프 G와 G의 루트 (V)가이 코드를 사용하여 작성

procedure BFS(G,v): 
     create a queue Q 
     enqueue v onto Q 
     mark v 
     while Q is not empty: 
      t ← Q.dequeue() 
      if t is what we are looking for: 
       return t 
      for all edges e in G.adjacentEdges(t) do 
       u ← G.adjacentVertex(t,e) 
       if u is not marked: 
        mark u 
        enqueue u onto Q 
     return none 

C# 코드는 :

 public static bool newCheckPath(int source, int dest) 
     { 
      Queue<PathRecord> Q = new Queue<PathRecord>(); 
      Q.Enqueue(pathTable[source]); 
      pathTable[source].markVisited(); 

      while (Q.Count != 0) 
      { 
       PathRecord t = Q.Dequeue(); 
       if (t.pathID == pathTable[dest].pathID) 
       { 
        return true; 
       } 
       else 
       { 
        string connectedPaths = pathTable[t.pathID].connectedPathID; 
        for (int x = 0; x < connectedPaths.Length && connectedPaths != "00"; x = x + 3) 
        { 
         int nextNode = Convert.ToInt32(connectedPaths.Substring(x, 2)); 

         PathRecord u = pathTable[nextNode]; 
         if (!u.wasVisited()) 
         { 
          u.markVisited(); 
          Q.Enqueue(u); 
         } 

        } 
       } 
      } 

      return false; 
     } 

이 코드를 실행

의사 코드는 온라인을 발견 그러나 그것은 단지 경로가 존재 하는지를 알려주는 것입니다. 그게 내게는별로 효과가 없다. 이상적으로 내가하고 싶은 것이 "if (t.pathID == pathTable [dest] .pathID)"블록에서 무엇을 얻으려고 통과해야 하는지를 알 수있는 목록이나 방법을 원합니다. 다른 곳에서 처리 할 목록을 반환하는 대신 해당 노드를 처리 할 수 ​​있도록 원본과 대상을 지정해야합니다. 어떻게 그 변화를 만들 수있는 아이디어?

Answer 1

가장 효과적인 솔루션, 당신은 (의 고정 크기 int 배열을 선언하는 것입니다 (나는 용어입니다 ++은 C는 것을 기억하는 것 같이, 또는 자동) 정적 메모리 할당을 사용하고자하는 경우 노드 41의 개수가 결코 40을 초과하지 않을 것이라는 것을 확신한다면, 크기 41 큐의 시작과 끝을 나타내는 두 개의 인덱스를 사용하면이 배열을 너비 우선 탐색에서 큐로 작동 할 수있는 링 버퍼로 사용할 수 있습니다.

다른 방법 : 노드 수가 너무 적기 때문에 Bellman-Ford이 충분히 빠를 수 있습니다.알고리즘은 구현하기 쉽고 재귀를 사용하지 않으며 필요한 추가 메모리는 노드 당 거리 (int 또는 심지어 byte)와 노드 당 선행 ID (int)입니다. 실행 시간은 O(VE), 또는 O(V^3)입니다. 여기서 V은 노드 수이고 E은 에지 수입니다.