बाइनरी भूलभुलैया में सबसे कम दूरी खोजने में मदद चाहिए, जो सूचियों मैट्रिक्स की एक सूची है, जहां 0 एक खाली सेल है और 1 एक दीवार है। भूलभुलैया में x, y शुरुआती निर्देशांक हैं जो डिफ़ॉल्ट रूप से 0,0 पर हैं और इसका अंतिम बिंदु हमेशा नीचे दाएं कोने में होता है। सबसे छोटी दूरी में हमेशा प्रारंभिक बिंदु शामिल होता है (अर्थात, यदि प्रारंभिक बिंदु से चार चरणों की आवश्यकता होती है, तो सबसे छोटी दूरी 5 होगी)

मुझे बैकट्रैकिंग एल्गोरिदम का उपयोग करने की आवश्यकता है। अब तक मैं एक ऐसे समारोह के साथ आ सकता हूं जो निर्धारित करता है कि कोई बचने का रास्ता है या नहीं। यह अच्छी तरह से काम करता है:

def is_solution(maze, x=0, y=0):

    n = len(maze)
    m = len(maze[0])

    if x == n - 1 and y == m - 1:
        return True
    
    maze[x][y] = 1
    result = False

    for a, b in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)]:
        if 0 <= a < n and 0 <= b < m and maze[a][b] == 0:
            result = result or is_solution(maze, a, b)
            
    maze[x][y] = 0
    return result


maze = [
      [0, 0, 1, 1],
      [1, 0, 0, 0],
      [1, 1, 1, 0]
    ]

is_solution(maze)

उपरोक्त का परिणाम सत्य होगा।

अब मैं वास्तव में सबसे छोटी दूरी खोजने के लिए संघर्ष कर रहा हूं। मुझे लगता है कि ऊपर दिए गए कोड को अपडेट करना अपेक्षाकृत आसान होना चाहिए, इसलिए अगर कोई रास्ता है और अगर कोई नहीं है तो यह दूरी दिखाता है। लेकिन मैं फंस गया। उपरोक्त उदाहरण में सबसे छोटी दूरी ६ होगी (शुरुआती बिंदु सहित) ), (0, 1), (1, 1), (1, 2), (1, 3), (2, 3)]]। इस मामले में केवल एक ही रास्ता है, लेकिन अगर दूरी छह में से दो थे, तो उस सूची में दूसरे सबसे छोटे पथ की सूची भी शामिल होगी।

धन्यवाद।

-1
Johnny smith 7 फरवरी 2021, 03:06
दूरी जोड़ने के लिए आपने स्वयं क्या प्रयास किया? बैकट्रैकिंग जोड़ने के लिए आपने क्या किया? आप कब पीछे हटेंगे? अब तक लिए गए रास्ते को याद करने की आपने क्या कोशिश की? कृपया समस्या को स्वयं हल करने का प्रयास करें और यदि आपके पास कुछ काम करने की उम्मीद है, तो मदद मांगने के लिए SO के पास आएं, लेकिन यह पता नहीं लगा सकते कि यह काम क्यों नहीं कर रहा है। SO को आपके लिए कोड लिखने के लिए न कहें।
 – 
Grismar
7 फरवरी 2021, 03:33
सबसे छोटे पथ एल्गोरिदम के लिए बैकट्रैकिंग एक कुशल दृष्टिकोण नहीं है। आप अपनी आवश्यकताओं की फिर से जाँच करना चाह सकते हैं - हो सकता है कि आपने कुछ गलत व्याख्या की हो।
 – 
user2357112 supports Monica
7 फरवरी 2021, 04:30
@ ग्रिस्मर, हमेशा की तरह क्षुद्रता के लिए धन्यवाद। हालांकि मैंने आधा प्रोग्राम पहले ही लिख लिया था। यह जाँचता है कि पथ मौजूद है या नहीं। मुझे नहीं पता कि इससे आगे कैसे बढ़ना है, इसलिए पूछ रहा हूं। मुझे केवल बीएफएस एल्गोरिदम मिले जो काम करते हैं। क्योंकि जाहिरा तौर पर यह ऊपर की टिप्पणी से क्या अनुसरण करता है - बैकट्रैकिंग कुशल नहीं है, इसलिए कोई भी इसका उपयोग नहीं करता है। इसलिए गीक्स या एसओ पर कोई कोड उदाहरण नहीं है।
 – 
Johnny smith
7 फरवरी 2021, 04:48
इसका "क्षुद्रता" से कोई लेना-देना नहीं है और स्टैक ओवरफ्लो के साथ क्या करना है। यह यहां प्रोग्रामिंग मुद्दों वाले लोगों के लिए है, लेकिन न केवल उनके मुद्दों को हल करने के लिए, बल्कि समान मुद्दों वाले अन्य लोगों के लिए एक मूल्यवान संसाधन प्रदान करने के लिए भी है। आपका प्रश्न वास्तव में सिर्फ "इस समस्या को हल करें" पूछ रहा है, भले ही यह काफी छोटा है (जो यह नहीं कहना है कि आपको कुछ हिस्सों को मुश्किल नहीं मिला)। न केवल मेरी राय, बल्कि SO नीति: stackoverflow.com/help/how-to-ask
 – 
Grismar
8 फरवरी 2021, 05:32

1 उत्तर

सबसे बढ़िया उत्तर

सबसे छोटा पथ ट्रैक करने के लिए अपने कोड में सरल परिवर्तन

सबसे छोटा रास्ता

def min_solution(maze, x = 0, y = 0, path = None):
    def try_next(x, y):
        ' Next position we can try '
        return [(a, b) for a, b in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)] if 0 <= a < n and 0 <= b < m]

    n = len(maze)
    m = len(maze[0])
    
    if path is None:
        path = [(x, y)]         # Init path to current position

    # Reached destionation
    if x == n - 1 and y == m - 1:
        return path
    
    maze[x][y] = 1              # Mark current position so we won't use this cell in recursion
    
    # Recursively find shortest path
    shortest_path = None            
    for a, b in try_next(x, y):
        if not maze[a][b]:
            last_path = min_solution(maze, a, b, path + [(a, b)])  # Solution going to a, b next
            
            if not shortest_path:
                shortest_path = last_path        # Use since haven't found a path yet
            elif last_path and len(last_path) < len(shortest_path):
                shortest_path = last_path       # Use since path is shorter
     
    
    maze[x][y] = 0           # Unmark so we can use this cell
    
    return shortest_path


maze = [
      [0, 0, 1, 1],
      [1, 0, 0, 0],
      [1, 1, 1, 0]
    ]

t = min_solution(maze)
if t:
    print(f'Shortest path {t} has length {len(t)}')
else:
    print('Path not found')

आउटपुट:

Shortest path [(0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 3)] has length 6

सभी पथ

def all_paths(maze, x = 0, y = 0, path = None):
    '''
        All paths through Maze as a generator
    '''
    def try_next(x, y):
        ' Next position we can try '
        return [(a, b) for a, b in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)] if 0 <= a < n and 0 <= b < m]

    n = len(maze)
    m = len(maze[0])
    
    if path is None:
        path = [(x, y)]

    # Reached destionation
    if x == n - 1 and y == m - 1:
        yield path
    else:
        maze[x][y] = 1              # Mark current position so we won't use this cell in recursion

        # Recursively find  pat          
        for a, b in try_next(x, y):
            if not maze[a][b]:
                yield from all_paths(maze, a, b, path + [(a, b)])  # Solution going to a, b next

        maze[x][y] = 0           # Unmark so we can use this cell
    

maze =  [[0, 0, 0], 
         [1, 0, 0], 
         [1, 1, 0]]

for t in all_paths(maze):
    print(f'path {t} has length {len(t)}')

उत्पादन

path [(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)] has length 5
path [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)] has length 5
1
DarrylG 15 अप्रैल 2021, 23:33
धन्यवाद। यह काम करता है! इसका विस्तार करने के तरीके भी सोच रहे हैं। भूलभुलैया मान लें = [ [0, 0, 0], [1, 0, 0], [1, 1, 0]]। क्या उस सूची में सभी छोटे पथ दिखाना संभव है? दो संभावित मार्ग हैं, दोनों लेन 5 के।
 – 
Johnny smith
7 फरवरी 2021, 04:55
1
@ जॉनीस्मिथ - सभी रास्तों को खोजना आसान है। मैंने उत्तर में दिखाए गए जनरेटर के रूप में इसे करने का सबसे अच्छा तरीका पाया है। एक विकल्प एक और तर्क यानी समाधान जोड़ना है, जिसे हम हर बार एक और रास्ता खोजने पर जोड़ते हैं।
 – 
DarrylG
7 फरवरी 2021, 06:00
बढ़िया समाधान, क्या आप ओ() सिंटैक्स में रन टाइम की व्याख्या कर सकते हैं? धन्यवाद।
 – 
user14025936
7 फरवरी 2021, 06:51
1
@ annie2020-- मुझे लगता है कि रन टाइम nm में घातीय है। यह तब देखा जा सकता है जब आप सभी शून्यों के k x k भूलभुलैया को समय देते हैं। समय बेतहाशा बढ़ता है। यह सच है क्योंकि आंशिक पथों की गणना दूसरे पथ के भाग के रूप में कई बार की जाती है। इसे फ़ंक्शन पर संस्मरण का उपयोग करके O(mn) तक कम किया जा सकता है, इसलिए आंशिक पथों की गणना केवल एक बार की जाती है।
 – 
DarrylG
7 फरवरी 2021, 07:32
बढ़िया जानकारी। आश्चर्य है कि यह इसे हल करने और अधिक कुशल होने के लिए डीएफएस प्रकार एल्गोरिदम लागू कर सकता है ... विश्लेषण के लिए धन्यवाद।
 – 
user14025936
7 फरवरी 2021, 14:12