पायथन

Question

में एक ग्राफ को मॉडलिंग करना मैं पाइथन में ग्राफ से संबंधित किसी समस्या को हल करने का प्रयास कर रहा हूं। इसकी एक संदिग्ध प्रोग्रामिंग समस्या के बाद से, मैं किसी अन्य तृतीय पक्ष पैकेज का उपयोग नहीं कर रहा हूं।

समस्या 5 X 5 वर्ग ग्रिड के रूप में एक ग्राफ प्रस्तुत करती है। एक बॉट ग्रिड पर उपयोगकर्ता द्वारा प्रदान की गई स्थिति पर माना जाता है। ग्रिड को नीचे बाईं ओर (0,0) पर नीचे दाईं ओर (4,4) पर अनुक्रमित किया गया है। ग्रिड में प्रत्येक सेल को निम्नलिखित 3 वर्णों में से किसी एक द्वारा दर्शाया जाता है। 'b' (एएससीआई मान 98) बॉट की वर्तमान स्थिति इंगित करता है, 'd' (एएससीआई मूल्य 100) एक गंदे सेल को इंगित करता है और '-' (एएससीआई मूल्य 45) ग्रिड में एक स्वच्छ सेल इंगित करता है।

b---d 
-d--d 
--dd- 
--d-- 
----d 

लक्ष्य चरण की न्यूनतम संख्या में, ग्रिड के सभी सेल साफ करने के लिए है: उदाहरण के लिए नीचे एक नमूना ग्रिड जहां बॉट 0 0 में है। एक कदम एक काम है, जहां या तो i) बॉट यह स्थिति ii) बॉट को घ से सेल (के राज्य में परिवर्तन में परिवर्तन के रूप में परिभाषित किया गया है -)

मान लें कि शुरू में स्थिति के रूप में चिह्नित b नहीं जरूरत साफ किया जाना चाहिए। बॉट को यूपी, नीचे, बाएं और दाएं स्थानांतरित करने की अनुमति है।

मेरे दृष्टिकोण

मैं रेखांकन पर ट्यूटोरियल की एक जोड़ी पढ़ा है, और कोई पथ का प्रतिनिधित्व करने के लिए 0 से 25 एक्स 25 के एक निकटता मैट्रिक्स के रूप में ग्राफ मॉडल करने के लिए फैसला किया, और मैट्रिक्स में 1 का प्रतिनिधित्व करने रास्तों (चूंकि हम केवल 4 दिशाओं में स्थानांतरित कर सकते हैं)। इसके बाद, मैंने फ़्लॉइड वॉर्सहेल के सभी जोड़े को सबसे कम पथ एल्गोरिदम लागू करने का निर्णय लिया, और फिर पथ के मानों को जोड़ दिया। लेकिन मुझे एहसास है कि यह काम नहीं करेगा। मैं एक डिलीमा में हूं कि समस्या या तो निम्न में से एक है:

i) एक न्यूनतम स्पैनिंग ट्री (जिसे मैं करने में असमर्थ हूं, क्योंकि मैं ग्रिड को मॉडल और स्टोर करने में सक्षम नहीं हूं ग्राफ)।

ii) ए * खोज (फिर एक जंगली अनुमान, लेकिन यहां एक ही समस्या है, मैं ग्रिड को ग्राफ के रूप में ठीक से मॉडल करने में सक्षम नहीं हूं)।

यदि आप इस तरह की समस्याओं पर एक अच्छा दृष्टिकोण सुझा सकते हैं तो मैं आभारी रहूंगा। इसके अलावा, ग्राफ़ आधारित समस्याओं (या उनसे लिंक) के विभिन्न रूपों के बारे में कुछ संकेत और psuedocode सहायक होंगे। धन्यवाद

Answer 1

मुझे लगता है कि आप यहां दो प्रश्न पूछ रहे हैं।

1. मैं इस समस्या को पायथन में ग्राफ के रूप में कैसे प्रस्तुत करूं?

जैसे रोबोट घूमता है, वह एक गंदे वर्ग से दूसरे में आगे बढ़ता जा रहा है, कभी-कभी रास्ते में कुछ साफ-सुथरे स्थान से गुजरता है। आपका काम गंदे वर्गों पर जाने के क्रम को समझना है।

# Code is untested and may contain typos. :-) 

# A list of the (x, y) coordinates of all of the dirty squares. 
dirty_squares = [(0, 4), (1, 1), etc.] 
n = len(dirty_squares)  

# Everywhere after here, refer to dirty squares by their index 
# into dirty_squares. 

def compute_distance(i, j): 
    return (abs(dirty_squares[i][0] - dirty_squares[j][0]) 
      + abs(dirty_squares[i][1] - dirty_squares[j][1])) 

# distances[i][j] is the cost to move from dirty square i to 
# dirty square j. 
distances = [] 
for i in range(n): 
    distances.append([compute_distance(i, j) for j in range(n)]) 

# The x, y coordinates of where the robot starts. 
start_node = (0, 0) 

# first_move_distances[i] is the cost to move from the robot's 
# start location to dirty square i. 
first_move_distances = [ 
    abs(start_node[0] - dirty_squares[i][0]) 
     + abs(start_node[1] - dirty_squares[i][1])) 
    for i in range(n)] 

# order is a list of the dirty squares. 
def cost(order): 
    if not order: 
    return 0 # Cleaning 0 dirty squares is free. 
    return (first_move_distances[order[0]] 
      + sum(distances[order[i]][order[i+1]] 
       for i in range(len(order)-1))) 

आपका लक्ष्य सूची (श्रेणी (एन)) को पुन: व्यवस्थित करने का एक तरीका ढूंढना है जो लागत को कम करता है।

2. इस समस्या को हल करने के लिए मुझे न्यूनतम संख्या में चाल कैसे मिलेंगी?

जैसा कि अन्य ने इंगित किया है, इस समस्या का सामान्यीकृत रूप अचूक (एनपी-हार्ड) है। आपके पास दो टुकड़े जानकारी हैं जो समस्या को सुलझाने में मदद करते हैं:

1. ग्राफ एक ग्रिड है।
2. 24 गंदे वर्ग हैं।

मुझे ए * का उपयोग करने के लिए आपकी वृत्ति पसंद है। खोज-न्यूनतम-संख्या-चाल की समस्याओं को हल करने के लिए अक्सर यह अच्छा होता है। हालांकि, ए * को उचित मात्रा में कोड की आवश्यकता होती है। मुझे लगता है कि आप शाखा-और-बाउंड दृष्टिकोण (कभी-कभी शाखा-और-प्रुन कहा जाता है) के साथ जाने के बेहतर होंगे, जो लगभग उतना ही कुशल होना चाहिए लेकिन इसे लागू करना बहुत आसान है।

# Each list represents a sequence of dirty nodes. 
    [] 
    [1] 
    [1, 2] 
    [1, 2, 3] 
    [1, 3] 
    [1, 3, 2] 
    [2] 
    [2, 1] 
    [2, 1, 3] 

हर बार जब आप कर रहे हैं के बारे में एक शाखा में recurse करने, अगर है कि शाखा है देखने के लिए जाँच:

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

यदि यह पर्याप्त कुशल नहीं है, तो शेष लागत पर निचले बाउंड की गणना करने के लिए एक फ़ंक्शन जोड़ें। फिर यदि लागत ([2]) + निचला_बाउंड (सेट ([1, 3])) अब तक के सबसे सस्ता समाधान से अधिक महंगा है, तो आप पूरी शाखा को छोड़ सकते हैं। कड़ा निचला_बाउंड() है, जितनी अधिक शाखाएं आप छोड़ सकते हैं।

Answer 2

समस्या निश्चित रूप से एक ग्राफ के रूप में संग्रहीत किया जा सकता है। नोड्स (गंदे कोशिकाओं) के बीच की लागत उनके Manhattan distance है। कोशिकाओं की सफाई की लागत को अनदेखा करें, क्योंकि कुल लागत वही होगी, चाहे कोई रास्ता न हो।

Answer 3

मान लें V={v|v=b or v=d}, और एक पूर्ण कनेक्टेड ग्राफ G(V,E) प्राप्त करें। आप में O(n^2) की समय जटिलता के साथ प्रत्येक किनारे की लागत की गणना कर सकते हैं। बाद में समस्या ठीक उसी तरह बन जाती है: निर्दिष्ट वर्टेक्स पर प्रारंभ करें, और G का एक छोटा रास्ता ढूंढें जो V को कवर करता है।

हम इस Traveling Salesman Problem(TSP) के बाद से 1832

Answer 4

यह समस्या Minimum Rectilinear Steiner Tree समस्या की तरह मुझे लग रहा है कहते हैं। दुर्भाग्यवश, समस्या एनपी कठिन है, इसलिए यदि आप सही हैं, तो आपको अनुमान के साथ एक अनुमान (मैनहट्टन दूरी के आधार पर न्यूनतम स्पैनिंग ट्री) के साथ आने की आवश्यकता होगी।