优化骑士在棋盘上的游览

Question

下面是我的代码

我有一个小night's tour问题，我正在尝试解决：在 N* 上找到从 A 点到 B 点的最小步数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是棋盘尺寸，Tile(4,4)和Tile(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

不要重新发明轮子。

构建一个以图块为顶点的图形。如果骑士可以一步从一个瓷砖走到另一个瓷砖，则用边连接瓷砖。
使用标准路径查找算法。广度优先搜索看起来是您在未加权图中寻找最短路径的最佳选择。

优化骑士在棋盘上的游览

optimizing Knight's tour on a chess board

python

algorithm

knights-tour