週期尋找算法

Question

我需要找到一個循環開始和結束在給定點。不能保證它存在。 我使用bool[,] points來指示哪個點可以在循環中。 Poins只能在網格上。 points指示網格上的給定點是否可以循環。 我需要使用最少的點數來找到這個循環。 一點只能使用一次。 連接只能是垂直或水平。

讓這成爲我們的點（紅色起點）：

去除死皮ImageShack的鏈接

我意識到，我可以這樣做：

while(numberOfPointsChanged) 
{ 
    //remove points that are alone in row or column 
} 

所以我有：

刪除死ImageShack鏈接

現在，我可以找到路徑。

去除死皮ImageShack的鏈接

但是，如果有不是由這個循環刪除，但不應該在路徑點？

我已經寫代碼：

class MyPoint 
{ 
    public int X { get; set; } 
    public int Y { get; set; } 
    public List<MyPoint> Neighbours = new List<MyPoint>(); 
    public MyPoint parent = null; 
    public bool marked = false; 
} 

    private static MyPoint LoopSearch2(bool[,] mask, int supIndexStart, int recIndexStart) 
    { 
     List<MyPoint> points = new List<MyPoint>(); 

     //here begins translation bool[,] to list of points 
     points.Add(new MyPoint { X = recIndexStart, Y = supIndexStart }); 

     for (int i = 0; i < mask.GetLength(0); i++) 
     { 
      for (int j = 0; j < mask.GetLength(1); j++) 
      { 
       if (mask[i, j]) 
       { 
        points.Add(new MyPoint { X = j, Y = i }); 
       } 
      } 
     } 

     for (int i = 0; i < points.Count; i++) 
     { 
      for (int j = 0; j < points.Count; j++) 
      { 
       if (i != j) 
       { 
        if (points[i].X == points[j].X || points[i].Y == points[j].Y) 
        { 
         points[i].Neighbours.Add(points[j]); 
        } 
       } 
      } 
     } 
     //end of translating 

     List<MyPoint> queue = new List<MyPoint>(); 
     MyPoint start = (points[0]); //beginning point 
     start.marked = true; //it is marked 
     MyPoint last=null; //last point. this will be returned 
     queue.Add(points[0]); 


     while(queue.Count>0) 
     { 
      MyPoint current = queue.First(); //taking point from queue 
      queue.Remove(current);   //removing it 

      foreach(MyPoint neighbour in current.Neighbours) //checking Neighbours 
      { 
       if (!neighbour.marked) //in neighbour isn't marked adding it to queue 
       { 
        neighbour.marked = true; 
        neighbour.parent = current; 
        queue.Add(neighbour); 
       } 
       //if neighbour is marked checking if it is startig point and if neighbour's parent is current point. if it is not that means that loop already got here so we start searching parents to got to starting point 
       else if(!neighbour.Equals(start) && !neighbour.parent.Equals(current)) 
       {       
        current = neighbour; 
        while(true) 
        { 
         if (current.parent.Equals(start)) 
         { 
          last = current; 
          break; 
         } 
         else 
          current = current.parent; 

        } 
        break; 
       } 
      } 
     } 

     return last;    
    } 

但它不工作。它創建的路徑包含兩點：開始和它的第一個鄰居。
我在做什麼錯？

編輯： 忘了提...橫向連接後，必須有垂直，水平，垂直等... 更重要的是每行和每列有需要是最大的兩個點（兩個或沒有）在週期中。但是這種情況與「週期必須是最短的週期」是一樣的。

Answer 1

這就是我所做的。我不知道它是否經過優化，但確實能正常工作。我沒有按照@marcog的建議對點進行排序。

private static bool LoopSearch2(bool[,] mask, int supIndexStart, int recIndexStart, out List<MyPoint> path) 
    { 
     List<MyPoint> points = new List<MyPoint>(); 
     points.Add(new MyPoint { X = recIndexStart, Y = supIndexStart }); 

     for (int i = 0; i < mask.GetLength(0); i++) 
     { 
      for (int j = 0; j < mask.GetLength(1); j++) 
      { 
       if (mask[i, j]) 
       { 
        points.Add(new MyPoint { X = j, Y = i }); 
       } 
      } 
     } 

     for (int i = 0; i < points.Count; i++) 
     { 
      for (int j = 0; j < points.Count; j++) 
      { 
       if (i != j) 
       { 
        if (points[i].X == points[j].X || points[i].Y == points[j].Y) 
        { 
         points[i].Neighbours.Add(points[j]); 
        } 
       } 
      } 
     } 

     List<MyPoint> queue = new List<MyPoint>(); 
     MyPoint start = (points[0]); 
     start.marked = true; 
     queue.Add(points[0]); 

     path = new List<MyPoint>(); 

     bool found = false; 

     while(queue.Count>0) 
     { 
      MyPoint current = queue.First(); 
      queue.Remove(current); 

      foreach (MyPoint neighbour in current.Neighbours) 
      { 
       if (!neighbour.marked) 
       { 
        neighbour.marked = true; 
        neighbour.parent = current; 
        queue.Add(neighbour); 
       } 
       else 
       { 
        if (neighbour.parent != null && neighbour.parent.Equals(current)) 
         continue; 

        if (current.parent == null) 
         continue; 

        bool previousConnectionHorizontal = current.parent.Y == current.Y; 
        bool currentConnectionHorizontal = current.Y == neighbour.Y; 

        if (previousConnectionHorizontal != currentConnectionHorizontal) 
        { 
         MyPoint prev = current; 

         while (true) 
         { 
          path.Add(prev); 
          if (prev.Equals(start)) 
           break; 
          prev = prev.parent; 
         } 

         path.Reverse(); 

         prev = neighbour; 

         while (true) 
         { 
          if (prev.Equals(start)) 
           break; 
          path.Add(prev);         
          prev = prev.parent; 
         } 

         found = true; 
         break; 
        }      
       } 
       if (found) break; 
      } 
      if (found) break; 
     } 

     if (path.Count == 0) 
     { 
      path = null; 
      return false; 
     } 
     return true; 
    } 

Answer 2

首先，您應該將您的表示更改爲更高效的表示。你應該使頂點成爲一個結構/類，它保留了連接頂點的列表。

更改了表示形式後，您可以使用breadth-first search輕鬆找到最短週期。

您可以使用以下技巧加速搜索：以廣度優先的順序遍歷圖，標記遍歷的頂點（並在每個頂點的根路上存儲「父頂點」編號）。只要找到已標記的頂點，搜索就完成了。通過回溯存儲的「父」頂點，您可以找到從找到的頂點到根的兩條路徑。

---

編輯：
你確定你的代碼是正確的？我試過如下：

while (queue.Count > 0) 
{ 
    MyPoint current = queue.First(); //taking point from queue 
    queue.Remove(current);   //removing it 

    foreach (MyPoint neighbour in current.Neighbours) //checking Neighbours 
    { 
     if (!neighbour.marked) //if neighbour isn't marked adding it to queue 
     { 
      neighbour.marked = true; 
      neighbour.parent = current; 
      queue.Add(neighbour); 
     } 
     else if (!neighbour.Equals(current.parent)) // not considering own parent 
     { 
      // found! 
      List<MyPoint> loop = new List<MyPoint>(); 
      MyPoint p = current; 
      do 
      { 
       loop.Add(p); 
       p = p.parent; 
      } 
      while (p != null); 
      p = neighbour; 
      while (!p.Equals(start)) 
      { 
       loop.Add(p); 
       p = p.parent; 
      } 
      return loop; 
     } 
    } 
} 

return null; 

，而不是在你的代碼的相應部分（我改變了返回類型List<MyPoint>，太）。它的工作原理和正確找到一個較小的循環，由3個點組成：紅點，直接在上面的點和直接在下面的點。

Answer 3

我認爲我會使用Dijkstra's algorithm的自適應變體，它會在第二次到達任何節點時停止並返回循環。如果這從來沒有發生，你沒有一個循環。

這種方法應該是多比廣度優先或深度優先搜索更有效，特別是如果您有許多節點。保證你只會訪問每個節點一次，因此你有一個線性運行時。

Answer 4

如果執行得不好，您的積分移除步驟是最壞情況O（N^3），最壞的情況是在每次迭代中剝離單個點。而且，由於它並不總是能夠爲循環檢測節省很多計算量，所以我會避免這樣做，因爲它還會給解決方案增加一層額外的複雜性。

首先從一組點中創建一個adjacency list。如果按X和Y（分開）對點進行排序，並按照X和Y的順序遍歷點，則可以在O（NlogN）中高效地執行此操作。然後，要查找最短週期長度（由點數確定），啓動首先將所有點放在隊列中，從每個點開始一個BFS。在遍歷邊時，將路徑的源與當前點一起存儲。然後你會知道BFS什麼時候回到源頭，在這種情況下我們找到了一個循環。如果在找到一個循環之前最終得到一個空隊列，則不存在。注意不要立即追溯到前一個點，否則最終會出現由兩個點形成的失效循環。例如，您可能還想避免由點(0, 0)，(0, 2)和(0, 1)形成的循環，因爲這形成了一條直線。

BFS可能有一個最壞的情況是指數，但我相信這種情況可以被證明不存在或極其罕見，因爲圖的密度越快，你會發現一個週期越快，而圖的稀疏你的隊列就會越小。平均而言，它更可能與鄰接列表構造更接近相同的運行時，或者在最壞的現實情況下O（N^2）。