優化的棋盤上騎士的旅遊

Question

我下面

我有一個小騎士巡遊問題，我試圖解決代碼：找到從A點上移動到B點的最小數量N * N棋盤。

我創建了一個板，並使用一個簡單的算法：

1. add point A to candidate list and start loop: 
2. pop first element in candidate list and check it: 
3. if end - return counter 
4. else - add the candidate 's "sons" to end of candidate list 
5. go to step 2 (counter is incremented after all previous level sons are popped) 

該算法的工作如我所料（用它在幾個測試案例），但它是非常緩慢：

通話f = Find_route(20, Tile(4,4), Tile(14,11))（20是電路板尺寸，瓷磚（4,4）和瓷磚（14,11）分別是開始&末端位置）檢查201590（!!）瓷磚到達答案之前。

我試着通過排序候選列表sorted(tiles, key = lambda e : abs(e.x - end.x)+abs(e.y - end.y))其中tiles是候選人列表來優化它。這適用於某些情況，但對於某些情況而言，這種方式毫無用處。

有用的情況：

• f = Find_route(20, Tile(1,4), Tile(1,10)) from 459 to 309 (~33% !!)
• f = Find_route(20, Tile(7,0), Tile(1,11)) from 87738 to 79524 (~10% :()

無益的情況：

• f = Find_route(20, Tile(4,4), Tile(14,11)): from 201891 to 201590
• f = Find_route(20, Tile(1,4), Tile(1,11)) from 2134 to 2111

我想最終有近端案件列表，從中算法會知道該怎麼做，（有點像一個5瓦半徑），我認爲這可以幫助，但我我更關心如何改進我的optimize_list方法。有小費嗎？

---

代碼

class Tile(object): 
    def __init__(self, x, y): 
     self.x = x 
     self.y = y 

    def __str__(self): 
     tmp = '({0},{1})'.format(self.x, self.y) 
     return tmp 

    def __eq__(self, new): 
     return self.x == new.x and self.y == new.y 

    def get_horse_jumps(self, max_x , max_y): 
     l = [(1,2), (1,-2), (-1,2), (-1,-2), (2,1), (2,-1), (-2,1), (-2,-1)] 
     return [Tile(self.x + i[0], self.y + i[1]) for i in l if (self.x + i[0]) >= 0 and (self.y + i[1]) >= 0 and (self.x + i[0]) < max_x and (self.y + i[1]) < max_y]   


class Board(object): 
    def __init__(self, n): 
     self.dimension = n 
     self.mat = [Tile(x,y) for y in range(n) for x in range(n)] 

    def show_board(self): 
     print('-'*20, 'board', '-'*20) 
     n = self.dimension 
     s = '' 
     for i in range(n): 
      for j in range(n): 
       s += self.mat[i*n + j].__str__() 
      s += '\n' 
     print(s,end = '') 
     print('-'*20, 'board', '-'*20) 


class Find_route(Board): 
    def __init__(self, n, start, end): 
     super(Find_route, self).__init__(n) 
     #self.show_board() 
     self.start = start 
     self.end = end 

    def optimize_list(self, tiles, end): 
     return sorted(tiles, key = lambda e : abs(e.x - end.x)+abs(e.y - end.y)) 

    def find_shortest_path(self, optimize = False): 
     counter = 0 
     sons = [self.start] 
     next_lvl = [] 
     num_of_checked = 0 

     while True: 
      curr = sons.pop(0) 
      num_of_checked += 1 
      if curr == self.end: 
       print('checked: ', num_of_checked) 
       return counter 
      else: # check sons 
       next_lvl += curr.get_horse_jumps(self.dimension, self.dimension) 
       # sons  <- next_lvl (optimize?) 
       # next_lvl <- [] 
       if sons == []: 
        counter += 1 
        if optimize: 
         sons = self.optimize_list(next_lvl, self.end) 
        else: 
         sons = next_lvl 
        next_lvl = [] 


optimize = True    
f = Find_route(20, Tile(7,0), Tile(1,11)) 
print(f.find_shortest_path(optimize)) 
print(f.find_shortest_path()) 

---

編輯

我添加了另一個優化級別 - 在新的候選瓦片任何插入優化列表，它似乎是一個工作魅力，對於一些情況：

 if optimize == 2: 
      if sons == []: 
       #counter += 1 
       sons = self.optimize_list(next_lvl, self.end) 
      else: 
       sons = self.optimize_list(sons + next_lvl, self.end) 
     else: 
      if sons == []: 
       counter += 1 
       if optimize == 1: 
        sons = self.optimize_list(next_lvl, self.end) 
       else: 
        sons = next_lvl 
       next_lvl = [] 

optimize = 2   
f = Find_route(20, Tile(1,4), Tile(8,18)) # from 103761 to 8 (optimal!!!) 
print(f.find_shortest_path(optimize)) 
print(f.find_shortest_path()) 

我在計算跳數時遇到了問題，因爲我不知道何時增加計數器（可能在每次檢查？），但似乎至少收斂得更快。另外，對於其他情況（例如f = Find_route(20, Tile(1,4), Tile(8,17))），它根本沒有改進（不知道它是否停止...）

Answer 1

不要重新發明輪子。

• 構建一個圖塊作爲頂點的瓷磚。如果一個騎士可以在一個步驟中從一個瓷磚到另一個瓷磚，就可以用瓷磚連接瓷磚。

• 使用標準路徑查找算法。廣度優先搜索看起來像是您在未加權圖中尋找最短路徑的最佳選擇。