python idastar vs astar çözme 8 bulmaca

Question

Benim ai bilgimi yenilemeye başladım, böylece 8-Puzzle'ı çözmek için bazı pathfind algoritmalarını uyguladım.

IDFS

IDA * benim uygulanması daha uzun bir yol vardır neden merak ediyorum IDA*

BFSA*

• . A * gibi optimal olmalı.

  % 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 
  

  Kod özünden üzerindedir https://gist.github.com/1629405

  Güncelleme:

  Kod şimdi versiyonunu çalışan bir işaret ediyor.

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

  Ama IDA * böylece çok daha uzun A * den piton altında sürer neden ben hala merak ediyorum.

  Güncelleme 2:

  Kod değiştirilir baskılar artık düğümleri ziyaret etti.

  IDASTAR Astar düğümleri oluşturur.

Answer 1

IDASTAR uygulamanız her yineleme ile sınırı 10 artırdığından, yalnızca çözümünüzün en iyi 9'dan fazla olamayacağını garanti eder. Artışı 1 olarak değiştirin ve en uygun sonucu almalısınız (ancak bunu yapmak için daha uzun sürün).