16
एक शब्दावली प्रश्न - क्या लालची सबसे अच्छी खोज सबसे पहले खोज से अलग है?क्या लालची सबसे अच्छी खोज सबसे पहले खोज से अलग है?
wiki page में लालची बीएफएस के बारे में एक अलग अनुच्छेद है लेकिन यह थोड़ा अस्पष्ट है।
मेरे समझ है कि लालची BFS बस है बीएफ जहां "खुली से सबसे अच्छा नोड" विकिपीडिया एल्गोरिथ्म में एक नोड के लिए एक अनुमानी समारोह एक की गणना करता है। तो यह लागू करने:
OPEN = [initial state]
CLOSED = []
while OPEN is not empty
do
1. Remove the best node from OPEN, call it n, add it to CLOSED.
2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
3. Create n's successors.
4. For each successor do:
a. If it is not in CLOSED: evaluate it, add it to OPEN, and record its parent.
b. Otherwise: change recorded parent if this new path is better than previous one.
done
"खुली से सबसे अच्छा नोड" के लिए अनुमान का समारोह का आकलन करने के कितने करीब नोड लक्ष्य है होने के साथ, वास्तव में लालची BFS है। क्या मैं सही हू?
संपादित करें: Anonymouse के जवाब पर टिप्पणी:
तो अनिवार्य रूप से एक लालची BFS एक "खुला सूची" की जरूरत नहीं है और केवल वर्तमान नोड पर अपने फैसलों का आधार होना चाहिए? इस एल्गोरिथ्म GBFS है:
1. Set START as CURRENT node
2. Add CURRENT to Path [and optinally, to CLOSED?]
3. If CURRENT is GOAL, exit
4. Evaluate CURRENT's successors
5. Set BEST successor as CURRENT and go to 2.
आप इसे प्रतिबिंबित करने के लिए उपरोक्त एल्गोरिदम कैसे बदलेंगे? – Alex
यह सभी समस्याओं पर लागू नहीं है। उदाहरण के लिए पथ खोज में, एक सच्चे लालची एल्गोरिदम अक्सर मृत सिरों में भागकर असफल हो जाता है। ए "प्राथमिकता गहराई पहले" को एक अच्छा रास्ता मिलेगा, लेकिन शुरुआती विकल्प खराब होने पर सबसे अच्छा याद आ सकता है। ए * एक सबसे अच्छी खोज है जो केवल तब समाप्त हो जाएगी जब यह सुनिश्चित हो कि कोई बेहतर रास्ता नहीं है। –
क्या आप मेरे प्रश्न में संपादन पर टिप्पणी कर सकते हैं? – Alex