그래프에서 가장 긴 경로를 찾는 방법

Question

그래프에서 가장 긴 경로를 찾는데 내 솔루션에 하나의 문제점이 있습니다. 내 프로그램은 정점이 서로 가까울 때 매우 느리게 작동합니다. 여기 제 코드가 도와주세요. 찾는 경로

대한

테스트 클래스

public class GraphTest : MonoBehaviour { 

// Use this for initialization 
void Start() { 

    const int w = 5; 
    const int h = 4; 


    int[,] data = new int[h,w]{ 
     {0,0,0,1,0}, 
     {0,0,0,1,0}, 
     {0,0,1,1,0}, 
     {0,0,0,0,0}}; 

    Map map = new Map(data,w,h); 

    List<Node> longest = map.longestPath(); 
    Debug.Log("LONGEST " + longest.Count); 

    //INFO this doing for printing array with steps 
    int c = longest.Count-1; 
    foreach(Node n in longest) 
     data[n.r,n.c] = c--; 

    string st = ""; 
    for(int i = 0; i < h; i++) 
    { 
     for(int j = 0; j < w; j++) 
     { 
      st += data[i,j] + ","; 
     } 
     st += "\n"; 
    } 

    Debug.Log(st); 
} 
} 

노드 클래스

public class Node 
{ 
public int r,c; 
public int data; 
public Node[] neighbors; 

public Node(int r, int c, int data) 
{ 
    this.r = r; 
    this.c = c; 
    this.data = data; 
    neighbors = new Node[8]; 
} 
} 

지도 클래스

public class Map 
{ 
public static int[] xDir = {1,1,1,0,-1,-1,-1,0}; 
public static int[] yDir = {-1,0,1,1,1,0,-1,-1}; 

public Node[,] map; 
public int[,] mapData; 

private int width,height; 
private int[,] marks; 
public Map(int[,] mapData,int width,int height) 
{ 
    this.mapData = mapData; 
    this.width = width; 
    this.height = height; 

    createNodes(); 
    initNeighbors(); 
} 
//INFO create nodes 
private void createNodes() 
{ 
    map = new Node[height,width]; 
    for(int i = 0; i < height; i++) 
    { 
     for(int j = 0; j < width; j++) 
     { 
      map[i,j] = new Node(i,j,mapData[i,j]); 
     } 
    } 
} 
//INFO assign neighbor nodes 
private void initNeighbors() 
{ 
    for(int i = 0; i < height; i++) 
    { 
     for(int j = 0; j < width; j++) 
     { 
      for(int k = 0; k < 8; k++) 
      { 
       if(inRange(i+yDir[k],j+xDir[k])) 
       { 
        map[i,j].neighbors[k] = map[i+yDir[k],j+xDir[k]]; 
       } 
      } 
     } 
    } 
} 

private bool inRange(int r, int c) 
{ 
    return r < height && r >= 0 && c < width && c >= 0; 
} 

public List<Node> longestPath() 
{ 
    marks = new int[height,width]; 
    List<Node> nodes = new List<Node>(); 
    int c = dfs(map[0,0],nodes); 

    //INFO Iterasions count 
    Debug.Log("COUNT " + c); 
    return nodes; 
} 

private int dfs(Node node, List<Node> nodes) 
{ 
    int i = 1; 
    List<Node> longest = new List<Node>(); 
    List<Node> list = null; 
    marks[node.r,node.c] = 1; 

    for(int n = 0; n < 8; n++) 
    { 
     //INFO if the neighbor node is not null and same type with parent node do dfs for neighbor node 
     if(node.neighbors[n] != null && 
      marks[node.neighbors[n].r,node.neighbors[n].c] == 0 && 
      node.neighbors[n].data == node.data) 
     { 
      list = new List<Node>(); 
      i += dfs(node.neighbors[n],list); 
      //INFO if the found nodes count is more than previous nodes count set new nodes to best nodes 
      if(list.Count > longest.Count) 
       longest = list; 
     } 
    } 

    marks[node.r,node.c] = 0; 
    longest.Add(node); 
    nodes.AddRange(longest); 

    return i; 
} 
} 

Answer 1

언급 한대로 NP 완성 문제입니다. 효율적이고 최적의 솔루션을 찾을 수 없습니다. (그렇지 않으면 세계의 모든 프로그래머가 맥주를 사 줄 것입니다.)

그렇다고해서 아무 것도 할 수 없다는 것은 아닙니다. 특정 유스 케이스의 일반적인 모양과 특성에 중점을두고 처리 할 부정확 한 정도를 결정하십시오.

가장 먼저 수행 할 수있는 작업은 병목 현상을 찾는 것입니다. 인접한 통과 셀 쌍으로 직접 셀 이외의 경로가 없으며 시작 노드와 목표 노드가 쌍의 반대쪽에 있습니다 . 그리드 케이스의 경우 정확히 두 이웃이있는 셀을 살펴본 다음 두 이웃에 대한 병목 현상을 확인할 수 있습니다. 병목 현상을 발견하면 축하드립니다. 두 가지 하위 문제로 문제를 해결했습니다. 각각의 문제는 해결하기가 훨씬 빠릅니다.

simulated annealing과 같은 무작위 접근을 시도 할 수도 있습니다. 최단 경로로 시작한 다음 경로의 일부 노드와 두 노드가 모두 경로에서 사용되지 않으면 직선을 C 자 모양으로 변경하는 등 간단한 로컬 화 섭동을 수행하여 길게 만듭니다. 더 이상 만들 수 없을 때까지 그 일을 계속하고, 무작위로 경로에서 두 개의 노드를 선택하고, 그 사이의 경로를 최단 경로로 대체하고, 다시 연장하고,이를 새로운 경로로 간주하십시오.

궁극적으로 이것이 가장 이론적이고 일반적인 형식으로 해결할 수있는 문제는 아니라는 것을 기억해야합니다. 특별한 경우에만 집중할 수 있으며, 정확한 최적성에 대한 요구 사항을 완화 할 수 있습니다. 이론 CS가 당신을 버렸습니다. 대신 실용 공학으로 전환해야합니다.