एक छवि

Question

दिए गए भूलभुलैया का प्रतिनिधित्व और हल करना किसी छवि को देखते हुए भूलभुलैया का प्रतिनिधित्व करने और हल करने का सबसे अच्छा तरीका क्या है?

एक JPEG चित्र (जैसा कि ऊपर देखा) को देखते हुए, में इसे पढ़ने के लिए कुछ डेटा संरचना में यह पार्स और हल भूलभुलैया का सबसे अच्छा तरीका क्या है? एक गैर सफेद पिक्सेल के लिए एक सफेद पिक्सेल के लिए True, और False (रंग खारिज किया जा सकता है): मेरी पहली वृत्ति पिक्सेल द्वारा पिक्सेल में छवि पढ़ सकते हैं और बूलियन मूल्यों की एक सूची (सरणी) में संग्रहीत करना है। इस विधि के साथ समस्या यह है कि छवि "पिक्सेल सही" नहीं हो सकती है। इसके द्वारा मेरा मतलब यह है कि अगर दीवार पर कहीं एक सफेद पिक्सेल है तो यह एक अनजान पथ बना सकता है। जो एक कैनवास पर तैयार रास्तों की एक सूची है -

एक अन्य विधि (जो सोचा था की एक बिट के बाद मेरे पास आया) एक एसवीजी फ़ाइल करने के लिए छवि परिवर्तित करने के लिए है। इस तरह, पथों को उसी प्रकार की सूची (बूलियन मान) में पढ़ा जा सकता है जहां True एक पथ या दीवार इंगित करता है, False एक यात्रा-सक्षम स्थान का संकेत देता है। इस विधि के साथ एक मुद्दा उत्पन्न होता है यदि रूपांतरण 100% सटीक नहीं है, और अंतराल को पूरी तरह से कनेक्ट नहीं करता है, अंतराल बना देता है।

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

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

फिर भूलभुलैया के हल आता है। अगर मैं पहले दो तरीकों में से किसी एक का उपयोग करता हूं, तो मैं अनिवार्य रूप से एक मैट्रिक्स के साथ समाप्त हो जाऊंगा। this answer के अनुसार, एक भूलभुलैया का प्रतिनिधित्व करने का एक अच्छा तरीका एक पेड़ का उपयोग कर रहा है, और इसे हल करने का एक अच्छा तरीका A* algorithm का उपयोग कर रहा है। छवि से पेड़ कैसे बनायेगा? कोई विचार?

टी एल; डॉ पार्स करने के लिए
सबसे अच्छा तरीका है? किस डेटा संरचना में? संरचना कैसे मदद/बाधा हल करने में कहा जाएगा?

अद्यतन
कार्यान्वयन के लिए मैं क्या @Mikhail पायथन में लिखा है, numpy का उपयोग कर, के रूप में @Thomas सिफारिश पर मेरे हाथ की कोशिश की है। मुझे लगता है कि एल्गोरिदम सही है, लेकिन यह उम्मीद के रूप में काम नहीं कर रहा है। (नीचे कोड।) पीएनजी लाइब्रेरी PyPNG है।

import png, numpy, Queue, operator, itertools 

def is_white(coord, image): 
    """ Returns whether (x, y) is approx. a white pixel.""" 
    a = True 
    for i in xrange(3): 
    if not a: break 
    a = image[coord[1]][coord[0] * 3 + i] > 240 
    return a 

def bfs(s, e, i, visited): 
    """ Perform a breadth-first search. """ 
    frontier = Queue.Queue() 
    while s != e: 
    for d in [(-1, 0), (0, -1), (1, 0), (0, 1)]: 
     np = tuple(map(operator.add, s, d)) 
     if is_white(np, i) and np not in visited: 
     frontier.put(np) 
    visited.append(s) 
    s = frontier.get() 
    return visited 

def main(): 
    r = png.Reader(filename = "thescope-134.png") 
    rows, cols, pixels, meta = r.asDirect() 
    assert meta['planes'] == 3 # ensure the file is RGB 
    image2d = numpy.vstack(itertools.imap(numpy.uint8, pixels)) 
    start, end = (402, 985), (398, 27) 
    print bfs(start, end, image2d, []) 

Answer 1

यहां एक समाधान है।

1. छवि को ग्रेस्केल (अभी तक बाइनरी) में कनवर्ट करें, रंगों के लिए वजन समायोजित करें ताकि अंतिम ग्रेस्केल छवि लगभग समान हो। आप छवि में फ़ोटोशॉप में स्लाइडर को नियंत्रित करके बस इसे कर सकते हैं -> समायोजन -> काला & व्हाइट।
2. छवि -> समायोजन -> थ्रेसहोल्ड में फ़ोटोशॉप में उपयुक्त थ्रेसहोल्ड सेट करके छवि को बाइनरी में कनवर्ट करें।
3. सुनिश्चित करें कि थ्रेसहोल्ड सही चुना गया है। 0 सहिष्णुता, बिंदु नमूना, संगत, कोई एंटी-एलियासिंग के साथ जादू वंड टूल का उपयोग करें। उन किनारों को जांचें जिन पर चयन ब्रेक गलत थ्रेसहोल्ड द्वारा पेश किए गए झूठे किनारे नहीं हैं। वास्तव में, इस भूलभुलैया के सभी आंतरिक बिंदु शुरुआत से ही सुलभ हैं।
4. यकीन है कि आभासी यात्री अपने पसंदीदा भाषा में चलना नहीं होगा चारों ओर यह :)
5. लागू breadth-first search (BFS) और शुरू से ही इसे चलाने बनाने के लिए भूलभुलैया पर कृत्रिम बॉर्डर जोड़ें। मैं इस कार्य के लिए MATLAB पसंद करता हूं। जैसा कि @ थॉमस पहले से ही उल्लेख किया गया है, ग्राफ के नियमित प्रतिनिधित्व के साथ गड़बड़ करने की कोई आवश्यकता नहीं है। आप सीधे बिनराइज्ड छवि के साथ काम कर सकते हैं।

यहाँ BFS के लिए MATLAB कोड है:

function path = solve_maze(img_file) 
    %% Init data 
    img = imread(img_file); 
    img = rgb2gray(img); 
    maze = img > 0; 
    start = [985 398]; 
    finish = [26 399]; 

    %% Init BFS 
    n = numel(maze); 
    Q = zeros(n, 2); 
    M = zeros([size(maze) 2]); 
    front = 0; 
    back = 1; 

    function push(p, d) 
    q = p + d; 
    if maze(q(1), q(2)) && M(q(1), q(2), 1) == 0 
     front = front + 1; 
     Q(front, :) = q; 
     M(q(1), q(2), :) = reshape(p, [1 1 2]); 
    end 
    end 

    push(start, [0 0]); 

    d = [0 1; 0 -1; 1 0; -1 0]; 

    %% Run BFS 
    while back <= front 
    p = Q(back, :); 
    back = back + 1; 
    for i = 1:4 
     push(p, d(i, :)); 
    end 
    end 

    %% Extracting path 
    path = finish; 
    while true 
    q = path(end, :); 
    p = reshape(M(q(1), q(2), :), 1, 2); 
    path(end + 1, :) = p; 
    if isequal(p, start) 
     break; 
    end 
    end 
end 

यह वास्तव में बहुत ही सरल और मानक है, वहाँ Python या जो कुछ भी में इस लागू करने पर कठिनाइयों नहीं होना चाहिए।

Answer 2

मै मैट्रिक्स-ऑफ-बूल विकल्प के लिए जाऊंगा। यदि आपको लगता है कि मानक पायथन सूची इसके लिए बहुत अक्षम हैं, तो आप इसके बजाय numpy.bool सरणी का उपयोग कर सकते हैं। 1000x1000 पिक्सेल भूलभुलैया के लिए संग्रहण केवल 1 एमबी है।

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

फिर इसे हल करने के लिए ए * एल्गोरिदम का उपयोग करें। दूरी हेरिस्टिक के लिए, मैनहट्टन दूरी का उपयोग करें (distance_x + distance_y)।

(row, column) निर्देशांक के एक tuple द्वारा नोड्स का प्रतिनिधित्व करें। जब भी एल्गोरिदम (Wikipedia pseudocode) "पड़ोसियों" के लिए कॉल करता है, तो यह चार संभावित पड़ोसियों (छवि के किनारों को ध्यान में रखकर) पर लूपिंग का एक साधारण मामला है।

यदि आपको लगता है कि यह अभी भी बहुत धीमी है, तो आप इसे लोड करने से पहले छवि को डाउनस्केल करने का प्रयास कर सकते हैं। प्रक्रिया में किसी भी संकीर्ण पथ को खोने से सावधान रहें।

शायद पाइथन में 1: 2 डाउनस्कलिंग करना संभव है, यह जांच कर कि आप वास्तव में किसी भी संभावित पथ को खो नहीं सकते हैं। एक दिलचस्प विकल्प है, लेकिन इसे थोड़ा और विचार चाहिए।

Answer 3

एक सीमा से निरंतर भरने के लिए एक कतार उपयोग करता है:

और यहाँ जवाब है। प्रवेश द्वार के पिक्सेल को कतार पर छोड़ देता है और फिर लूप शुरू करता है। यदि एक कतारबद्ध पिक्सेल पर्याप्त अंधेरा है, तो यह रंगीन हल्का भूरा (थ्रेसहोल्ड से ऊपर) है, और सभी पड़ोसियों को कतार पर धकेल दिया जाता है।

from PIL import Image 
img = Image.open("/tmp/in.jpg") 
(w,h) = img.size 
scan = [(394,23)] 
while(len(scan) > 0): 
    (i,j) = scan.pop() 
    (r,g,b) = img.getpixel((i,j)) 
    if(r*g*b < 9000000): 
     img.putpixel((i,j),(210,210,210)) 
     for x in [i-1,i,i+1]: 
      for y in [j-1,j,j+1]: 
       scan.append((x,y)) 
img.save("/tmp/out.png") 

समाधान ग्रे दीवार और रंगीन दीवार के बीच गलियारा है। ध्यान दें कि इस भूलभुलैया में कई समाधान हैं। इसके अलावा, यह केवल काम करने लगता है।

Answer 4

ट्री खोज बहुत ज्यादा है। भूलभुलैया समाधान पथ (पथों) के साथ निहित रूप से अलग है।

(रेडडिट से rainman002 को धन्यवाद, यह मुझे इंगित करने के लिए धन्यवाद।)

इस वजह से, आप भूलभुलैया दीवार के जुड़े अनुभागों की पहचान के लिए connected components का उपयोग कर सकते हैं। यह दो बार पिक्सल पर फिर से चलाता है।

यदि आप इसे समाधान पथ के अच्छे आरेख में बदलना चाहते हैं, तो आप प्रत्येक कनेक्टेड क्षेत्र के लिए "मृत अंत" मार्गों को भरने के लिए संरचना तत्वों के साथ बाइनरी परिचालनों का उपयोग कर सकते हैं।

MATLAB के लिए डेमो कोड निम्नानुसार है। यह परिणाम को बेहतर तरीके से साफ करने के लिए tweaking का उपयोग कर सकता है, इसे और अधिक सामान्य बनाने के लिए, और इसे तेजी से चलाने के लिए। (कुछ समय जब यह 2:30 नहीं हूँ है।)

% read in and invert the image 
im = 255 - imread('maze.jpg'); 

% sharpen it to address small fuzzy channels 
% threshold to binary 15% 
% run connected components 
result = bwlabel(im2bw(imfilter(im,fspecial('unsharp')),0.15)); 

% purge small components (e.g. letters) 
for i = 1:max(reshape(result,1,1002*800)) 
    [count,~] = size(find(result==i)); 
    if count < 500 
     result(result==i) = 0; 
    end 
end 

% close dead-end channels 
closed = zeros(1002,800); 
for i = 1:max(reshape(result,1,1002*800)) 
    k = zeros(1002,800); 
    k(result==i) = 1; k = imclose(k,strel('square',8)); 
    closed(k==1) = i; 
end 

% do output 
out = 255 - im; 
for x = 1:1002 
    for y = 1:800 
     if closed(x,y) == 0 
      out(x,y,:) = 0; 
     end 
    end 
end 
imshow(out); 

Answer 5

यहां कुछ सुझाव दिए हैं।

(1. इमेज प्रोसेसिंग :)

1.1 लोड के रूप में RGB पिक्सेल मानचित्र छवि। C# में system.drawing.bitmap का उपयोग करके यह छोटा है। इमेजिंग के लिए कोई आसान समर्थन नहीं वाली भाषाओं में, बस छवि को portable pixmap format (पीपीएम) (एक यूनिक्स टेक्स्ट प्रस्तुति, बड़ी फाइलें उत्पन्न करती है) या कुछ साधारण बाइनरी फ़ाइल प्रारूप को आसानी से पढ़ सकते हैं, जैसे कि BMP या TGA। विंडोज में यूनिक्स या IrfanView में ImageMagick या IrfanView।

1.2 जैसा कि पहले बताया गया है, आप प्रत्येक पिक्सेल के लिए ग्रे टोन के संकेतक के रूप में (आर + जी + बी)/3 ले कर डेटा को सरल बना सकते हैं और फिर काले और सफेद तालिका का उत्पादन करने के लिए मूल्य को थ्रेसहोल्ड कर सकते हैं। 200 के करीब कुछ मानते हैं 0 = काला और 255 = सफेद जेपीईजी कलाकृतियों को बाहर ले जाएगा।

(2. समाधान :)

2.1 गहराई-प्रथम खोज: आरंभ करने के स्थान के साथ एक खाली ढेर Init, उपलब्ध अनुवर्ती चाल इकट्ठा आकस्मिक एक का चुनाव और ढेर पर धक्का, आगे बढ़ना जब तक अंत तक पहुँच जाता है या एक मृतक। स्टैक पॉप अप करके डेडेंड बैकट्रैक पर, आपको ट्रैक रखने की आवश्यकता है कि मानचित्र पर कौन सी स्थितियों का दौरा किया गया था ताकि जब आप उपलब्ध चालें एकत्र करते हैं तो आप कभी भी दो बार एक ही रास्ता नहीं लेते। एनिमेट करने के लिए बहुत दिलचस्प है।

2.2 ब्रेड-फर्स्ट सर्च: ऊपर उल्लिखित, लेकिन केवल कतारों का उपयोग करके उल्लेख किया गया। एनिमेट करने के लिए भी दिलचस्प है। यह छवि संपादन सॉफ्टवेयर में बाढ़ भरने की तरह काम करता है। मुझे लगता है कि आप इस चाल का उपयोग कर फ़ोटोशॉप में एक भूलभुलैया हल करने में सक्षम हो सकते हैं।

2.3 वॉल अनुयायी: ज्यामितीय रूप से बोलते हुए, एक भूलभुलैया एक गुना/घुलनशील ट्यूब है। यदि आप दीवार पर अपना हाथ रखते हैं तो आपको अंततः बाहर निकलना होगा;) यह हमेशा काम नहीं करता है। कुछ धारणाएं हैं: परिपूर्ण मैज इत्यादि, उदाहरण के लिए, कुछ मैज द्वीपों में होते हैं। इसे देखो; यह आकर्षक है।

(3. टिप्पणियाँ :)

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

Answer 6

यह समाधान पायथन में लिखा गया है। छवि तैयारी पर पॉइंटर्स के लिए मिखाइल धन्यवाद।

एक एनिमेटेड चौड़ाई पहले खोज:

पूरे भूलभुलैया:

#!/usr/bin/env python 

import sys 

from Queue import Queue 
from PIL import Image 

start = (400,984) 
end = (398,25) 

def iswhite(value): 
    if value == (255,255,255): 
     return True 

def getadjacent(n): 
    x,y = n 
    return [(x-1,y),(x,y-1),(x+1,y),(x,y+1)] 

def BFS(start, end, pixels): 

    queue = Queue() 
    queue.put([start]) # Wrapping the start tuple in a list 

    while not queue.empty(): 

     path = queue.get() 
     pixel = path[-1] 

     if pixel == end: 
      return path 

     for adjacent in getadjacent(pixel): 
      x,y = adjacent 
      if iswhite(pixels[x,y]): 
       pixels[x,y] = (127,127,127) # see note 
       new_path = list(path) 
       new_path.append(adjacent) 
       queue.put(new_path) 

    print "Queue has been exhausted. No answer was found." 


if __name__ == '__main__': 

    # invoke: python mazesolver.py <mazefile> <outputfile>[.jpg|.png|etc.] 
    base_img = Image.open(sys.argv[1]) 
    base_pixels = base_img.load() 

    path = BFS(start, end, base_pixels) 

    path_img = Image.open(sys.argv[1]) 
    path_pixels = path_img.load() 

    for position in path: 
     x,y = position 
     path_pixels[x,y] = (255,0,0) # red 

    path_img.save(sys.argv[2]) 

नोट: मार्क्स एक सफेद पिक्सेल ग्रे का दौरा किया। यह किसी विज़िट की गई सूची की आवश्यकता को हटा देता है, लेकिन पथ को खींचने से पहले डिस्क से छवि फ़ाइल का दूसरा लोड आवश्यक होता है (यदि आप अंतिम पथ की समग्र छवि और सभी पथों को नहीं लेना चाहते हैं)।

A blank version of the maze I used.

Answer 7

मैं इस समस्या के लिए ए-स्टार खोज को लागू करने अपने आप की कोशिश की। बारीकी से ढांचे के लिए Joseph Kern द्वारा कार्यान्वयन और कलन विधि स्यूडोकोड दिया पीछा here: ए-स्टार के रूप में

def AStar(start, goal, neighbor_nodes, distance, cost_estimate): 
    def reconstruct_path(came_from, current_node): 
     path = [] 
     while current_node is not None: 
      path.append(current_node) 
      current_node = came_from[current_node] 
     return list(reversed(path)) 

    g_score = {start: 0} 
    f_score = {start: g_score[start] + cost_estimate(start, goal)} 
    openset = {start} 
    closedset = set() 
    came_from = {start: None} 

    while openset: 
     current = min(openset, key=lambda x: f_score[x]) 
     if current == goal: 
      return reconstruct_path(came_from, goal) 
     openset.remove(current) 
     closedset.add(current) 
     for neighbor in neighbor_nodes(current): 
      if neighbor in closedset: 
       continue 
      if neighbor not in openset: 
       openset.add(neighbor) 
      tentative_g_score = g_score[current] + distance(current, neighbor) 
      if tentative_g_score >= g_score.get(neighbor, float('inf')): 
       continue 
      came_from[neighbor] = current 
      g_score[neighbor] = tentative_g_score 
      f_score[neighbor] = tentative_g_score + cost_estimate(neighbor, goal) 
    return [] 

एक अनुमानी खोज एल्गोरिथ्म आप एक समारोह है कि शेष लागत का अनुमान है के साथ आने की जरूरत है (यहाँ: दूरी) लक्ष्य तक पहुंचने तक। जब तक आप एक उप-समाधान समाधान के साथ सहज न हों, तब तक इसे लागत को अधिक महत्व नहीं देना चाहिए। एक रूढ़िवादी विकल्प यहां manhattan (or taxicab) distance होगा क्योंकि यह प्रयुक्त वॉन न्यूमैन पड़ोस के लिए ग्रिड पर दो बिंदुओं के बीच सीधी रेखा दूरी का प्रतिनिधित्व करता है। (जो, इस मामले में, कभी भी लागत को अधिक महत्व नहीं देगा।)

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

import sys 
from PIL import Image 

def is_blocked(p): 
    x,y = p 
    pixel = path_pixels[x,y] 
    if any(c < 225 for c in pixel): 
     return True 
def von_neumann_neighbors(p): 
    x, y = p 
    neighbors = [(x-1, y), (x, y-1), (x+1, y), (x, y+1)] 
    return [p for p in neighbors if not is_blocked(p)] 
def manhattan(p1, p2): 
    return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1]) 
def squared_euclidean(p1, p2): 
    return (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2 

start = (400, 984) 
goal = (398, 25) 

# invoke: python mazesolver.py <mazefile> <outputfile>[.jpg|.png|etc.] 

path_img = Image.open(sys.argv[1]) 
path_pixels = path_img.load() 

distance = manhattan 
heuristic = manhattan 

path = AStar(start, goal, von_neumann_neighbors, distance, heuristic) 

for position in path: 
    x,y = position 
    path_pixels[x,y] = (255,0,0) # red 

path_img.save(sys.argv[2]) 

यहाँ परिणामों के एक दृश्य (एक Joseph Kern द्वारा पोस्ट की गई से प्रेरित) के लिए कुछ छवियों हैं:

कोड यह रहा। एनीमेशन मुख्य जबकि लूप के 10000 पुनरावृत्तियों के बाद प्रत्येक एक नया फ्रेम दिखाता है।

चौड़ाई पहले खोज:

ए-स्टार मैनहट्टन दूरी:

ए-स्टार Squared इयूक्लिडियन दूरी:

ए-स्टार मैनहट्टन दूरी चार से गुणा:

परिणाम बताते हैं कि भूलभुलैया के पता लगाया क्षेत्रों heuristics के लिए काफी भिन्न होते हैं इस्तेमाल किया जा रहा। इस प्रकार, स्क्वायर यूक्लिडियन दूरी अन्य मेट्रिक्स के रूप में एक अलग (उप-शीर्ष) पथ भी उत्पन्न करती है।

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

एक बात यह है कि के बारे में है या नहीं, (जैसे कि ए-स्टार के रूप में) एक सूचित खोज एल्गोरिथ्म एक संपूर्ण खोज (जैसे, BFS) की तुलना में बेहतर विकल्प हो सकता सामान्य रूप में कहा जा सकता है इस प्रकार है। भूलभुलैया के आयामों की संख्या के साथ, यानी, खोज पेड़ का शाखा कारक, एक संपूर्ण खोज का नुकसान (पूरी तरह से खोज करने के लिए) तेजी से बढ़ता है। बढ़ती जटिलता के साथ ऐसा करने के लिए कम और कम संभव हो जाता है और किसी बिंदु पर आप किसी भी परिणाम पथ से बहुत खुश हैं, चाहे यह (लगभग) इष्टतम हो या नहीं।

Answer 8

ये रहा: maze-solver-python (GitHub)

मैं मज़ा इस के साथ चारों ओर खेल रहे हैं और Joseph Kern के जवाब पर बढ़ाया था। इससे अलग नहीं होना; मैंने अभी किसी और के लिए कुछ मामूली जोड़ किए हैं जो इस के साथ खेलने में रुचि रखते हैं।

यह एक पायथन आधारित सॉल्वर है जो सबसे कम पथ खोजने के लिए बीएफएस का उपयोग करता है। मेरा मुख्य अतिरिक्त, समय में, कर रहे हैं:

1. छवि खोज से पहले साफ किया जाता है
2. कोई GIF स्वचालित रूप से उत्पन्न (यानी शुद्ध काला & सफेद में बदलने का।)।
3. स्वचालित रूप से एक एवीआई उत्पन्न करें।

जैसा कि यह खड़ा है, इस नमूना भूलभुलैया के लिए स्टार्ट/एंड-पॉइंट हार्ड-कोडेड हैं, लेकिन मैं इसे विस्तारित करने की योजना बना रहा हूं ताकि आप उचित पिक्सल चुन सकें।