如何找到在图形

最长路径我有一个问题，我的解决方案，在图中寻找最长路径。当顶点彼此靠近时，我的程序工作非常缓慢。这里是我的代码，请帮助我。如何找到在图形

测试类

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

Node类

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; 
} 
}

来源

2014-09-21 haksist

我很好奇你正在尝试做什么？你能否详细说明一下。这是为了一场比赛吗？ – Postlagerkarte 2014-09-22 09:35:14

如前所述BRZ，这是一个NP完全问题;您将无法找到既高效又保证最佳的解决方案。（或者，如果你这样做，世界上每一个程序员你买啤酒。）

这并不是说你不能做任何事情。专注于您的特定用例的一般形式以及任何特性，并决定您愿意处理多少错误。

你可以做的第一件事就是寻找一个瓶颈 - 一对相邻的可穿越单元，这样除了直接单元之外，它们之间不存在路径，并且起始节点和目标节点位于该对的相对侧。对于网格情况，您可以查看刚好有两个邻居的单元，然后检查这两个邻居是否存在瓶颈。如果你发现瓶颈，恭喜你 - 你已经将你的问题分解为两个子问题，每个子问题解决起来要快得多。

您也可以尝试随机的方法，如simulated annealing。从最短路径开始，然后对其执行一些简单的局部扰动以使其更长，例如，如果路径的一部分的两个节点都未被路径使用，则将直线改变为C形。继续这样做，直到你不能再做它，然后随机从你的路径中选择两个节点，用最短路径替换它们之间的路径，重新拉长它，并考虑将它作为新路径。

最后，你必须记住，这不是你能在最理论，一般的形式解决问题。您可以专注于特殊情况，并且可以放松您对精确最佳性的要求。理论CS已经抛弃了你;你需要转向实际工程。

来源

2014-09-21 19:56:32 Sneftel

谢谢，我会试试 – haksist 2014-09-21 20:26:14

+1：“理论CS已经抛弃了你，你需要转向实际工程。”我必须记住这一点，这是一种相当有趣的投放方式。 – Nuclearman 2014-09-21 20:44:15

如何找到在图形

回答

相关问题