尋找最佳啓發式，A *搜索，吃豆子

（所有的電路板開始的每一個角落點）

如果我有吃豆子板這樣

*--------------------* 
---------------------- 
---------------------- 
---------------------- 
---------------------- 
---------------------- 
---------------------- 
P--------------------* 
----------------------

什麼是最好的啓發式讓他吃所有的點（*）？我正在使用A *搜索。我曾嘗試使用曼哈頓距離，但一旦將牆壁扔進混合物中，它不會達到與BFS相同的效果，因此不是最佳選擇。我期待它是最優的，同時擴展更少的節點，然後BFS。

來源

2015-11-03 Jordan

這僅僅是旅行商問題的一個例子，有幾個算法有關這方面的論點和啓發。找到兩個點之間的距離， pacman和點，可以使用某種洪水填充算法來完成。 –

我已經看過旅行商問題，常見的主題是使用曼哈頓距離。另外，我相信BFS是一種洪水填充算法。 – Jordan

是的，在這種情況下，BFS和洪水填充意味着同樣的事情。無論如何，主要的問題是找到點的最佳順序吃。尋找距離點之間的最短路徑相對容易。 –

好，我發現一種解決方案：

（MAX（X，Y）到最遠角落

childXY =狀態[0] cornersLeft =狀態[1]

maxDistance = 10000 
minDistance = 0 
farthestCorner = 0 
nearestCorner = 0 


for corner in cornersLeft: 

    if util.manhattanDistance(childXY, corner) > minDistance: 
     minDistance = util.manhattanDistance(childXY, corner) 
     farthestCorner = minDistance - min((childXY[0]-corner[0]),(childXY[1]-corner[1])) 


heuristic = farthestCorner 

print "heuristic is: ", heuristic 
return heuristic

距離我的A *搜索出現問題，最終導致我的啓發式問題無法正常工作

來源

2015-11-03 06:17:07 Jordan

尋找最佳啓發式，A *搜索，吃豆子

回答

相關問題