साइकिल खोज एल्गोरिदम

Question

मुझे दिए गए बिंदु पर एक चक्र शुरू करने और समाप्त होने की आवश्यकता है। यह गारंटी नहीं है कि यह मौजूद है। मैं bool[,] points का उपयोग यह इंगित करने के लिए करता हूं कि कौन सा बिंदु चक्र में हो सकता है। सिक्के केवल ग्रिड पर हो सकता है। points इंगित करता है कि ग्रिड पर दिया गया बिंदु चक्र में हो सकता है या नहीं। मुझे इस चक्र को न्यूनतम अंक के रूप में उपयोग करने की आवश्यकता है। एक बिंदु केवल एक बार उपयोग किया जा सकता है। कनेक्शन केवल लंबवत या क्षैतिज हो सकता है।

मृत ImageShack को हटाने के लिंक

मैंने महसूस किया कि मैं यह कर सकता:

यह हमारे अंक (लाल बिंदु शुरू कर रहा है) हो

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

तो मेरे पास है:

मृत छविशैक लिंक को हटाने

अब, मैं पथ पा सकता हूं।

को हटाने मृत 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

आपके अंक हटाने का चरण सबसे खराब मामला ओ (एन^3) है यदि खराब तरीके से लागू किया गया है, तो सबसे खराब मामला प्रत्येक पुनरावृत्ति में एक बिंदु को अलग कर रहा है। और चूंकि यह आपको हमेशा चक्र पहचान में इतना गणना नहीं करता है, इसलिए मैं इसे करने से बचूंगा क्योंकि यह समाधान में जटिलता की एक अतिरिक्त परत भी जोड़ता है।

अंक के सेट से adjacency list बनाकर शुरू करें। यदि आप X और Y (अलग से) द्वारा अंक क्रमबद्ध करते हैं और एक्स और वाई के क्रम में बिंदुओं के माध्यम से इसे क्रमबद्ध करते हैं तो आप इसे कुशलता से ओ (एनएलओएनएन) में कर सकते हैं। फिर सबसे छोटी चक्र लंबाई (बिंदुओं की संख्या से निर्धारित) को खोजने के लिए, प्रारंभ करें शुरुआत में कतार पर सभी बिंदुओं को फेंककर प्रत्येक बिंदु से BFS। जैसे ही आप किनारे पर जाते हैं, वर्तमान बिंदु के साथ पथ के स्रोत को स्टोर करते हैं। तब आपको पता चलेगा कि बीएफएस स्रोत पर कब वापस आती है, इस मामले में हमें एक चक्र मिला है। यदि आप चक्र खोजने से पहले खाली कतार के साथ समाप्त होते हैं, तो कोई भी मौजूद नहीं है। सावधान रहें कि पिछली बिंदु पर तुरंत वापस नज़र डालें या आप दो बिंदुओं द्वारा गठित एक निष्क्रिय चक्र के साथ समाप्त हो जाएंगे। उदाहरण के लिए, आप (0, 0), (0, 2) और (0, 1) अंकों द्वारा गठित एक चक्र से बचने के लिए भी बच सकते हैं क्योंकि यह एक सीधी रेखा है।

बीएफएस संभावित रूप से घातीय होने का सबसे खराब मामला है, लेकिन मेरा मानना ​​है कि इस तरह का मामला या तो अस्तित्व में साबित नहीं हो सकता है या बहुत ही दुर्लभ हो सकता है क्योंकि जितना तेज़ होगा उतना ग्राफ जितना जल्दी आपको एक चक्र मिलेगा जबकि ग्राफर ग्राफ़ आपकी कतार छोटी होगी। औसतन यह निकटता सूची निर्माण के रूप में, या सबसे खराब यथार्थवादी मामलों ओ (एन^2) के समान रनटाइम के करीब होने की अधिक संभावना है।