周期寻找算法

我需要找到一个循环开始和结束在给定点。不能保证它存在。我使用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;    
    }

但它不工作。它创建的路径包含两点：开始和它的第一个邻居。
我在做什么错？

编辑： 忘了提...横向连接后，必须有垂直，水平，垂直等... 更重要的是每行和每列有需要是最大的两个点（两个或没有）在周期中。但是这种情况与“周期必须是最短的周期”是一样的。

来源

2010-12-19 Miko Kronn

你所说的“循环”在图论中通常被称为“循环”（在我看过你的照片之前，“循环”的含义并不完全清楚）。我编辑了适当的问题，使其易于理解。仍然不清楚你的点如何存储在二维布尔数组中。 – 2010-12-19 14:25:20

编辑，以澄清我如何存储积分。 – 2010-12-19 14:34:48

这不是C＃的问题，仅仅是关于算法的问题。 – 2010-12-19 14:38:52

这就是我所做的。我不知道它是否经过优化，但确实能正常工作。我没有按照@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; 
    }

来源

2010-12-20 17:26:11 Ichibann

首先，您应该将您的表示更改为更高效的表示。你应该使顶点成为一个结构/类，它保留了连接顶点的列表。

更改了表示形式后，您可以使用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个点组成：红点，直接在上面的点和直接在下面的点。

来源

2010-12-19 14:36:20 Vlad

我不知道这被认为是“诡计”。大多数书籍（例如CLRS）中的示例总是标记访问的顶点。 – MAK 2010-12-19 17:57:10

@MAK：“窍门”是在找到标记的顶点时停止搜索，而当搜索到达根目录时则不是（天真的方式）。顺便说一句，严格来说，BF应该应用于树，我们的图很可能不是树（因为它有周期）。 – Vlad 2010-12-19 22:33:13

@Vlad：我指的是同样的事情。 – MAK 2010-12-20 03:51:59

我认为我会使用Dijkstra's algorithm的自适应变体，它会在第二次到达任何节点时停止并返回循环。如果这从来没有发生，你没有一个循环。

这种方法应该是多比广度优先或深度优先搜索更有效，特别是如果您有许多节点。保证你只会访问每个节点一次，因此你有一个线性运行时。

来源

2010-12-19 15:18:33 Lucero

为什么这应该更有效率？它的BF和DF搜索在'nodes + edges'中是线性的，Dijkstra至少也有一个'log'因子。 – IVlad 2010-12-19 15:28:11

没有你的“窍门”，BF和DF都会尝试每条可能的路径，如果B和C都连接到A，那么它将包括A-B-C和A-C-B。你的“诀窍”基本上实现了Dijkstra。并且在没有发现周期的情况下，Dijkstra将访问每个节点一次，使其在运行时呈线性，否？ – Lucero 2010-12-19 15:47:37

IVlad不是我:-) – Vlad 2010-12-19 15:53:27

如果执行得不好，您的积分移除步骤是最坏情况O（N^3），最坏的情况是在每次迭代中剥离单个点。而且，由于它并不总是能够为循环检测节省很多计算量，所以我会避免这样做，因为它还会给解决方案增加一层额外的复杂性。

首先从一组点中创建一个adjacency list。如果按X和Y（分开）对点进行排序，并按照X和Y的顺序遍历点，则可以在O（NlogN）中高效地执行此操作。然后，要查找最短周期长度（由点数确定），启动首先将所有点放在队列中，从每个点开始一个BFS。在遍历边时，将路径的源与当前点一起存储。然后你会知道BFS什么时候回到源头，在这种情况下我们找到了一个循环。如果在找到一个循环之前最终得到一个空队列，则不存在。注意不要立即追溯到前一个点，否则最终会出现由两个点形成的失效循环。例如，您可能还想避免由点(0, 0)，(0, 2)和(0, 1)形成的循环，因为这形成了一条直线。

BFS可能有一个最坏的情况是指数，但我相信这种情况可以被证明不存在或极其罕见，因为图的密度越快，你会发现一个周期越快，而图的稀疏你的队列就会越小。平均而言，它更可能与邻接列表构造更接近相同的运行时，或者在最坏的现实情况下O（N^2）。

来源

2010-12-19 16:52:47 marcog

周期寻找算法

回答

相关问题