路徑搜索：從A到B的星長不同於從B到A的星長

我正在爲8難題實現曼哈頓距離的A星算法。 [解決方法是在螺旋形式]路徑搜索：從A到B的星長不同於從B到A的星長

1 2 3 
8 0 4 
7 6 5

在一些情況下，從A到B不會採取相同數量的步驟從乙要A.

我認爲這是因爲它當它們具有相同的成本時，不會在打開的列表中選擇相同的狀態，因此不會展開相同的節點。

從

兩個都具有使用曼哈頓距離相同的值。我應該探索具有相同值的所有路徑嗎？或者我應該改變啓發式方法來打破某種局面嗎？

下面是代碼

def solve(self): 
    cost = 0 
    priority = 0 
    self.parents[str(self.start)] = (None, 0, 0) 
    open = p.pr() #priority queue 
    open.add(0, self.start, cost) 
    while open: 
     current = open.get() 
     if current == self.goal: 
     return self.print_solution(current) 
     parent = self.parents[str(current)] 
     cost = self.parents[str(current)][2] + 1 
     for new_state in self.get_next_states(current): 
     if str(new_state[0]) not in self.parents or cost < self.parents[str(new_state[0])][2]: 
      priority = self.f(new_state) + cost 
      open.add(priority, new_state[0], cost) 
      self.parents[str(new_state[0])] = (current, priority, cost)

來源

2016-11-22 Sequoya

我米不知道我明白你的例子中'A - > B'和'B - > A'的含義。你是否從目標搜索到你展示的「From」位置？其他圖表與這些搜索有什麼關係？我沒有看到你的A *代碼有什麼明顯的錯誤，但是由於它不是完全獨立的，我實際上不能運行它來查看是否有任何微妙的錯誤。只要它仍然[可接受]（https://en.wikipedia.org/wiki/Admissible_heuristic），啓發式中的關係就不應該成爲問題。如果有多種解決方案，它可能會找到任何解決方案，但它們都具有相同的長度。 – Blckknght

@Blckknght，是的，這就是我的意思。從目標到我展示的「從」位置。所以我不需要找到一種管理關係的方法，曼哈頓距離是可以接受的，然後我的代碼有什麼問題？我將清理代碼併發布項目的github鏈接。 – Sequoya

我已經嘗試過f = 0而不是曼哈頓距離，並且我嘗試刪除 if current == self.goal：return self.print_solution（current） to have all possible solution。兩者都沒有改變。我認爲問題在於發佈在問題中的函數，可能在self.parents中。以下是完整的代碼：https：//github.com/Sequoya42/automatic-waddle – Sequoya

相關的部分浪費那麼多時間重新寫我的「解決」的功能很多不同的方式，對什麼都沒有，我終於找到了問題之後。

def get_next_states(self, mtx, direction): 
    n = self.n 
    pos = mtx.index(0) 
    if direction != 1 and pos < self.length and (pos + 1) % n: 
     yield (self.swap(pos, pos + 1, mtx),pos, 3) 
    if direction != 2 and pos < self.length - self.n: 
     yield (self.swap(pos, pos + n, mtx),pos, 4) 
    if direction != 3 and pos > 0 and pos % n: 
    yield (self.swap(pos, pos - 1, mtx),pos, 1) 
    if direction != 4 and pos > n - 1: 
    yield (self.swap(pos, pos - n, mtx),pos, 2)

這是在這個功能。最後，如果使用的是「如果4和POS> N：」所以有未開發的狀態。對於爲期2天的「-1」

它會教我做更多的單元測試

來源

2016-11-24 22:17:06 Sequoya

路徑搜索：從A到B的星長不同於從B到A的星長

回答

相關問題