पायथन idastar बनाम अस्थिर हल 8 पहेली

Question

मैंने अपने एआई ज्ञान को ताज़ा करना शुरू किया ताकि मैंने 8-पहेली को हल करने के लिए कुछ पथदर्शी एल्गोरिदम लागू किए।

• A*
• IDA*
• BFS
• IDFS

मैं सोच रहा था क्यों आईडीए * के अपने कार्यान्वयन एक लंबे समय तक मार्ग होता है। यह ए * की तरह इष्टतम होना चाहिए।

% python puzzle8.py -a idastar -d hard 
IDASTAR - RESULT in 161.6099: 
1 | 2 | 3 
4 | 5 | 6 
7 | 8 | N 

cost: 0 total_cost: 121 
... 
nodes 28 

% python puzzle8.py -a astar -d hard 
Max nodes 665 loops 1085 
ASTAR - RESULT in 0.3148: 
1 | 2 | 3 
4 | 5 | 6 
7 | 8 | N 

cost: 0 total_cost: 115 
... 
nodes 24 

कोड सार पर है https://gist.github.com/1629405

अद्यतन:

कोड अब संस्करण में काम कर रहे एक की ओर इशारा करते है।

% python puzzle8.py -a idastar -d hard 
IDASTAR - RESULT in 234.4490: 

1 | 2 | 3 
4 | 5 | 6 
7 | 8 | N 
... 
nodes 24 

लेकिन मैं अभी भी सोच रहा हूँ क्यों आईडीए * तो बहुत लंबे समय तक ए * से अजगर के तहत लेता है।

अद्यतन 2:

कोड बदल जाता है प्रिंट अब नोड्स का दौरा किया।

IDASTAR 4,184,368 ASTAR नोड्स पैदा करता है।

Answer 1

क्योंकि IDASTAR के आपके कार्यान्वयन में प्रत्येक पुनरावृत्ति के साथ 10 की सीमा बढ़ जाती है, जो केवल गारंटी देता है कि आपका समाधान इष्टतम से 9 से अधिक नहीं होगा। वृद्धि को 1 में बदलें, और आपको इष्टतम परिणाम प्राप्त करना चाहिए (लेकिन ऐसा करने में अधिक समय लगता है)।