कैटन गेम एल्गोरिदमिक

Question

के सेटलर में सबसे लंबी सड़क ढूंढना मैं कक्षा के लिए केटन क्लोन के एक सेटलर लिख रहा हूं। अतिरिक्त क्रेडिट सुविधाओं में से एक स्वचालित रूप से निर्धारित करता है कि किस खिलाड़ी के पास सबसे लंबी सड़क है। मैंने इसके बारे में सोचा है, और ऐसा लगता है कि गहराई पर कुछ मामूली बदलाव की तरह पहली खोज काम कर सकती है, लेकिन मुझे यह पता लगाने में परेशानी हो रही है कि चक्र का पता लगाने के साथ क्या करना है, किसी खिलाड़ी के दो शुरुआती सड़क नेटवर्क में शामिल होने को कैसे संभालना है, और कुछ अन्य minutiae। मैं यह एल्गोरिदमिक कैसे कर सकता हूं?

खेल से अपरिचित लोगों के लिए, मैं संक्षेप में और संक्षेप में समस्या का वर्णन करने की कोशिश करूंगा: मुझे एक अप्रत्यक्ष चक्रीय ग्राफ में सबसे लंबा संभव पथ खोजने की आवश्यकता है।

Answer 1

यह एक नहीं बल्कि आसान एल्गोरिथ्म लागू करने के लिए किया जाना चाहिए (प्रत्येक नोड के लिए एक get_neighbors समारोह मान लिया गया है)।

आरंभ करने के लिए, सड़कों को अलग-अलग सेटों में अलग करें, जहां प्रत्येक सेट में सभी सड़क खंड किसी भी तरह से जुड़े हुए हैं। ऐसा करने पर विभिन्न तरीकों है, लेकिन यहां से एक है:

1. , एक यादृच्छिक सड़क खंड उठाओ एक सेट में जोड़ने, और इस अनुभाग से
2. शाखा बाहर चिह्नित, यानी। दोनों दिशाओं में जुड़े सेगमेंट का पालन करें जो चिह्नित नहीं हैं (यदि वे चिह्नित हैं, हम पहले से ही यहां हैं)
3. यदि पाया गया कि सड़क सेगमेंट पहले से सेट में नहीं है, तो इसे जोड़ें और इसे
4. पर जाएं नए खंडों से जब तक आप वर्तमान में
5. में उन लोगों से जुड़े किसी भी अनमार्क किए गए सेगमेंट नहीं ढूंढ पा रहे हैं, यदि अनमार्क किए गए सेगमेंट शेष हैं, तो वे एक नए सेट का हिस्सा हैं, एक यादृच्छिक चुनें और 1 सेट पर एक और सेट के साथ शुरू करें

नोट: सरकारी Catan Rules के अनुसार, एक सड़क अगर Ano तोड़ा जा सकता है थर्म प्ले दो खंडों के बीच संयुक्त पर एक समझौता बनाता है। आपको निपटारे के पीछे शाखा का पता लगाने की जरूरत नहीं है।

नोट, उपरोक्त में, और निम्न चरणों में, केवल वर्तमान खिलाड़ियों के खंडों पर विचार करें। आप उन अन्य खंडों को अनदेखा कर सकते हैं जैसे कि वे मानचित्र पर भी नहीं थे।

यह आपको एक या एक से अधिक सेट देता है, जिनमें प्रत्येक एक या अधिक सड़क खंड होते हैं।

ठीक है, प्रत्येक सेट के लिए, निम्न कार्य करें:

1. सेट केवल एक ही जुड़ा सड़क खंड इसे से बाहर (यानी है कि में एक यादृच्छिक सड़क खंड उठाओ।आप एक अंतिम बिंदु)
2. आप ऐसा नहीं कर सकते हैं, तो पूरे सेट पाशन है (एक या अधिक) लेने, तो खंड आपके द्वारा चुने गए से अब इस मामले

में एक यादृच्छिक खंड लेने,, वर्तमान सड़क की लंबाई का ट्रैक रखते हुए, अब तक गहराई से पहली खोज में एक रिकर्सिव ब्रांचिंग करें। हमेशा सड़क सेगमेंट को चिह्नित करें, और पहले से चिह्नित सेगमेंट में शाखा न करें। यह एल्गोरिदम को रोकने की अनुमति देगा जब यह "अपनी पूंछ खाएगा"।

जब भी आपको बैकट्रैक की आवश्यकता होती है, क्योंकि वहां कोई और शाखा नहीं है, तो वर्तमान लंबाई का एक नोट लें, और यदि यह "पिछले अधिकतम" से अधिक लंबा है, तो नई लंबाई को अधिकतम के रूप में स्टोर करें।

सभी सेट के लिए यह करें, और आपको अपनी सबसे लंबी सड़क होनी चाहिए।

Answer 2

मुझे क्या करना चाहते हैं:

1. एक सड़क
2. पिक के साथ एक शीर्ष उठाओ सबसे दो सड़कों पर पालन करने के लिए
3. सड़क का पालन करें; अगर यह शाखाओं यहाँ पीछे, और कहा कि जो अब
4. था चुनते हैं, तो वर्तमान शिखर का दौरा सूची में है, 3
5. के लिए पीछे 3
6. से recurse दौरा सूची में शीर्ष जोड़ें, तो वहाँ कोई और अधिक सड़क है 3 पर, लंबाई
7. लौट आप सबसे अधिक 2 सड़कों पर का पालन किया है, तो उन्हें जोड़, लंबाई
8. अगर वहाँ प्रारंभिक शिखर पर 3 सड़कों थे ध्यान दें, करने के लिए 2.

क्षमा करें पीछे प्रोल-आश शब्दावली के लिए :)

Answer 3

मैं एक चौड़ाई पहली खोज का सुझाव दूंगा।

प्रत्येक खिलाड़ी के लिए:

• सेट 0

• की डिफ़ॉल्ट में जाना जाता है अधिकतम एक प्रारंभिक नोड उठाओ। छोड़ें यदि इसमें शून्य या एक से अधिक कनेक्टेड पड़ोसियों हैं और इसे पहले से शुरू होने वाले सभी खिलाड़ी के पथ मिलते हैं। पकड़: एक बार नोड को पार करने के बाद, यह उस मोड़ में छोड़ी गई सभी खोजों के लिए "निष्क्रिय" होता है। यही है, अब यह पार नहीं किया जा सकता है।

  इसे कैसे कार्यान्वित किया जा सकता है?

  1. इस प्रारंभिक नोड से कोई पथ, या एक से अधिक पथ देखते हैं, तो चिह्नित कर उसे निष्क्रिय और इसे छोड़: यहाँ एक संभव चौड़ाई-पहले एल्गोरिथ्म है कि इस्तेमाल किया जा सकता है।
  2. पथों की कतार रखें।
  3. एक पथ जोड़ें जिसमें केवल प्रारंभिक मृत-अंत नोड कतार में है। इस नोड को निष्क्रिय करें।
  4. कतार के पहले पथ को पॉप करें और इसे "विस्फोट" करें - यानी, सभी मान्य पथ खोजें जो वैध दिशा में पथ + 1 और चरण हैं। "वैध" द्वारा, अगला नोड सड़क से आखिरी बार से जुड़ा होना चाहिए, और इसे भी सक्रिय किया जाना चाहिए।
  5. अंतिम चरण के दौरान चरणबद्ध सभी नोड्स को निष्क्रिय करें।
  6. यदि पिछले पथ का कोई वैध "विस्फोट" नहीं है, तो ज्ञात अधिकतम तक उस पथ की उस लंबाई की तुलना करें। यदि इससे बड़ा है, तो यह अधिकतम अधिकतम है।
  7. सभी विस्फोटित पथ, यदि कोई हो, तो कतार में वापस जोड़ें।
  8. कतार खाली होने तक 4-7 दोहराएं।

• एक बार ऐसा करने के बाद, अगले सक्रिय नोड पर जाएं और फिर से प्रक्रिया शुरू करें। बंद करें जब सभी नोड्स निष्क्रिय हो जाते हैं।

• दिए गए प्लेयर के लिए अब आपके पास सबसे लंबी सड़क की लंबाई है।

ध्यान दें कि यह थोड़ा अक्षम है, लेकिन अगर प्रदर्शन कोई फर्क नहीं पड़ता है, तो इस कैमरून MacFarland को :)

महत्वपूर्ण नोट काम करेगा, धन्यवाद

• सभी नोड्स मान लें उन शहरों के साथ जो वर्तमान खिलाड़ी से संबंधित नहीं हैं हमेशा स्वचालित रूप से निष्क्रिय हो जाते हैं।

---

रूबी स्यूडोकोड

def explode n 
    exploded = n.get_neighbors    # get all neighbors 
    exploded.select! { |i| i.activated? } # we only want activated ones 
    exploded.select! { |i| i.is_connected_to(n) } # we only want road-connected ones 
    return exploded 
end 

max = 0 

nodes.each do |n|     # for each node n 
    next if not n.activated?  # skip if node is deactivated 
    if explode(n).empty? or explode(n).size > 1 
    n.deactivate     # deactivate and skip if 
    next       # there are no neighbors or 
    end        # more than one 

    paths = [ [n] ]     # start queue 

    until paths.empty?    # do this until the queue is empty 

    curr_path = paths.pop   # pop a path from the queue 
    exploded = explode(curr_path) # get all of the exploded valid paths 

    exploded.each { |i| i.deactivate } # deactivate all of the exploded valid points 

    if exploded.empty?     # if no exploded paths 
     max = [max,curr_path.size].max # this is the end of the road, so compare its length to 
             # the max 
    else 
     exploded.each { |i| paths.unshift(curr_path.clone + i) } 
             # otherwise, add the new paths to the queue 
    end 

    end 

end 

puts max 

Answer 4

आप डिजस्ट्रा का उपयोग कर सकते हैं और इसके बजाय सबसे लंबा रास्ता चुनने के लिए स्थितियों को बदल सकते हैं।

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

यह कुशल है, लेकिन हमेशा पथ प्राप्त नहीं कर सकेंगे वास्तविकता में कम से कम है कि/सबसे लंबे समय तक हालांकि यह समय की सबसे काम करेंगे।

Answer 5

एक साधारण बहुपद-समय गहराई-पहली खोज काम करने की संभावना नहीं है, क्योंकि समस्या एनपी-हार्ड है। आपको ऐसा कुछ चाहिए जो इष्टतम समाधान प्राप्त करने के लिए घातीय समय लेता है। चूंकि समस्या इतनी छोटी है, हालांकि अभ्यास में कोई समस्या नहीं होनी चाहिए।

संभावित रूप से सबसे सरल समाधान गतिशील प्रोग्रामिंग होगा: एक तालिका टी [वी, एल] रखें जो प्रत्येक नोड वी के लिए स्टोर करता है और प्रत्येक लंबाई एल पथों का सेट होता है जिसमें लंबाई एल और अंत में v होता है। स्पष्ट रूप से टी [वी, 1] = {[v]} और आप टी [डब्ल्यू, एल] को टी [डब्ल्यू, एल -1] से सभी पथ एकत्र करके एल> 1 के लिए भर सकते हैं, जहां डब्ल्यू वी का पड़ोसी है जिसमें पहले से ही वी नहीं है, और फिर v संलग्न कर रहा है। यह जस्टिन एल के समाधान के समान है, लेकिन कुछ डुप्लिकेट काम से बचाता है।

Answer 6

थोड़ा देर हो चुकी है, लेकिन अभी भी प्रासंगिक है। मैंने इसे जावा में कार्यान्वित किया, here देखें। एल्गोरिथ्म इस प्रकार है:

• मुख्य ग्राफ़ एक खिलाड़ी से सभी किनारों का उपयोग करने से एक ग्राफ प्राप्त, किनारों
• से जुड़े मुख्य ग्राफ़ के कोने जोड़ने (समाप्त होता है की एक सूची बनाएँ कोने जहां डिग्री == 1) और विभाजन (शिखर जहां डिग्री == 3)
• प्रत्येक छोर के लिए चेक (संभव रूट) के लिए एक मार्ग जोड़ें, और प्रत्येक दो किनारों के लिए + प्रत्येक चरम पर एक कशेरुका संयोजन मिला (3, डिग्री 3 है)
• हर मार्ग पर चलें। तीन चीजों का सामना किया जा सकता है: एक अंत, मध्यवर्ती या एक विभाजन।
• समाप्ति:, बर्खास्त possibleRoute पाया सूची
• मध्यवर्ती में जोड़ें: जाँच करता है, तो दूसरे किनारे करने के लिए कनेक्शन संभव है। यदि हां, तो किनारे जोड़ें। यदि नहीं, तो रूट को समाप्त करें और इसे मिली मार्गों में जोड़ें
• विभाजन: दोनों किनारों के लिए, मध्यवर्ती के रूप में करें। जब दोनों मार्ग कनेक्ट होते हैं, तो दूसरे मार्ग की प्रतिलिपि बनाएँ और इसे सूची में भी जोड़ें।
• कनेक्शन के लिए जांच दो विधियों का उपयोग करके किया जाता है: देखें कि नया किनारा संभवतः रूट रूट (कोई कनेक्शन नहीं) में मौजूद है, और नया किनारा पूछ रहा है यदि यह चरम और मूल वर्टेक्स को पैरामीटर के रूप में जोड़कर कनेक्ट कर सकता है।एक सड़क सड़क से जुड़ सकती है, लेकिन केवल तभी जब वर्टेक्स में किसी अन्य खिलाड़ी से शहर/निपटान नहीं होता है। एक सड़क एक जहाज से जुड़ सकती है, लेकिन केवल तभी जब कशेरुक उस खिलाड़ी से शहर या सड़क रखता है जिस पर मार्ग की जांच की जा रही है।
• लूप्स मौजूद हो सकते हैं। प्रत्येक सामने वाले किनारे को सूची में जोड़ा जाता है यदि पहले से मौजूद नहीं है। जब सभी संभव रूट चेक किए जाते हैं, लेकिन इस सूची में किनारों की मात्रा कम होती है तो खिलाड़ी के किनारों की कुल मात्रा, एक या अधिक लूप मौजूद हैं। जब ऐसा होता है, तो किसी भी गैर-जांच वाले किनारे को एक नया संभव मार्ग बनाया जाता है, और मार्ग के लिए फिर से जांच की जा रही है।
• सबसे लंबा मार्ग की लंबाई सभी मार्गों पर बसने के द्वारा निर्धारित की जाती है। पहले मार्ग का बराबर या अधिक 5 किनारों का सामना करना पड़ता है।

यह कार्यान्वयन केटन के अधिकांश प्रकारों का समर्थन करता है। किनारों अपना निर्णय स्वयं ले अगर वे दूसरे से कनेक्ट करना चाहते हैं, को देखने के

SidePiece.canConnect(point, to.getSidePiece()); 

एक सड़क, जहाज, पुल SidePiece इंटरफ़ेस कार्यान्वित हो सकता है। एक सड़क कार्यान्वयन के रूप में

public boolean canConnect(GraphPoint graphPoint, SidePiece otherPiece) 
{ 
    return (player.equals(graphPoint.getPlayer()) || graphPoint.getPlayer() == null) 
      && otherPiece.connectsWithRoad(); 
} 

Answer 7

यहाँ मैं अपने Catan एक्सेल VBA सिम्युलेटर में एक दिया खिलाड़ी ("उपयोगकर्ता") के लिए सबसे लंबे समय तक सड़क का निर्धारण करने के लिए उपयोग कोड का स्निपेट है है।

अभी मैंने महसूस किया कि यह ध्यान में बस्तियों के बारे में नियम नहीं ले करता है, लेकिन उस में परत के लिए कठिन नहीं होना चाहिए।

Private Frays As Dictionary 
Private RoadPths As Collection 
Public Function GetLongestRoad(g As Board, oUser As User) As Long 
    Dim oRoad As Road 
    Dim v, w 
    Dim fNum As Long 
    Dim rCount As Long 

    Set Frays = New Dictionary 
    Set RoadPths = New Collection 

    ' get list of roads that happen to be linked to other roads ("Frays") 
    For fNum = 55 To 126 
     If g.Roads(fNum).Owner = oUser.Name Then 
      For Each v In RoadLinks(g, fNum) 
       If g.Roads(v).Owner = oUser.Name Then Frays(fNum) = v 
      Next v 
     End If 
    Next fNum 

    ' begin recursion 
    For Each v In Frays 
     RecurSegmts g, v & ";" & Frays(v) 
    Next v 

    rCount = 0 
    For Each v In RoadPths 
     w = Split(v, ";") 
     If rCount < UBound(w) Then rCount = UBound(w) 
    Next v 

    GetLongestRoad = rCount + 1 
End Function 

Private Sub RecurSegmts(g As Board, Segmts As Variant) 
    Dim SegmtArr, NextRoad 
    Dim LoopsBack As Boolean 
    Dim i As Long 

    RoadPths.Add Segmts 
    SegmtArr = Split(Segmts, ";") 

    For Each NextRoad In RoadLinks(g, CLng(SegmtArr(UBound(SegmtArr)))) 
     LoopsBack = False 
     For i = 0 To UBound(SegmtArr) 
      If CLng(NextRoad) = CLng(SegmtArr(i)) Then LoopsBack = True 
     Next i 

     If LoopsBack = False Then Call RecurSegmts(g, Segmts & ";" & NextRoad) 

    Next NextRoad 
End Sub 

Answer 8

यहाँ मेरी संस्करण है, तो किसी को भी यह की जरूरत है। Typescript में लिखा गया।

longestRoadLengthForPlayer (खिलाड़ी: PlayerColors): नंबर { जाने longestRoad = 0

let mainLoop = (currentLongestRoad: number, tileEdge: TileEdge, passedCorners: TileCorner[], passedEdges: TileEdge[]) => { 
     if (!(passedEdges.indexOf(tileEdge) > -1) && tileEdge.owner == player) { 
      passedEdges.push(tileEdge) 
      currentLongestRoad++ 
      for (let endPoint of tileEdge.hexEdge.endPoints()) { 
       let corner = this.getTileCorner(endPoint)! 

       if ((corner.owner == player || corner.owner == PlayerColors.None) && !(passedCorners.indexOf(corner) > -1)) { 
        passedCorners.push(corner) 
        for (let hexEdge of corner.hexCorner.touchingEdges()) { 
         let edge = this.getTileEdge(hexEdge) 
         if (edge != undefined && edge != tileEdge) { 
          mainLoop(currentLongestRoad, edge, passedCorners, passedEdges) 
         } 
        } 
       } else { 
        checkIfLongestRoad(currentLongestRoad) 
       } 
      } 
     } else { 
      checkIfLongestRoad(currentLongestRoad) 
     } 
    } 

    for (let tileEdge of this.tileEdges) { 
     mainLoop(0, tileEdge, [], []) 
    } 

    function checkIfLongestRoad(roadLength: number) { 
     if (roadLength > longestRoad) { 
      longestRoad = roadLength 
     } 
    } 

    return longestRoad 
}