如何用沃恩斯多夫规则改进奈特之旅？

Question

我知道有几个类似的线程，但即使在 SO 之外我也没有找到解决方案。 这是我的问题： 我针对 Knight's Tour 问题实现了 Warnsdorff 算法 http://en.wikipedia.org/wiki/Knight%27s_tour ，但在某些情况下它没有给出解决方案。在我读到的某些地方，经过一些更改，它可以更好地工作，但没有人指定哪些更改是这些更改。有人知道解决方案吗？我知道其他算法，但它们要复杂得多。

即使对于 8x8 的棋盘，有时也无法给出好的解决方案。我认为阅读我的代码没有意义，因为它是经典的 Warnsdorff 代码：检查可能的移动，并在下一步中选择可能移动最少的一个。

Answer 1

W+ 的链接不再存在，使得接受的答案不可用。

Warnsdorff 算法的改进是：

Arnd Roth 的命题：
罗斯认为沃恩斯多夫启发式的问题在于随机抢七规则。
提议是通过选择距棋盘中心欧氏距离最大的继任者来打破平局。

这里的问题是当多个后继者共享相同距离时会发生什么。
Arnd Roth 声称这种改进首先
在 428 行的主板上出现故障，并且所有主板上的故障率低于 1%
板数少于 2000 行。

Ira Pohl 的主张：
为了打破这种平局，波尔决定第二次应用沃恩斯多夫的规则。为了实现这一点，我们必须对所有未访问过的邻居、并列的后继者的度数进行求和，并选择总和最小的平方。

这里的问题之一是，无论我们应用 Warnsdorff 规则多少次，我们都会导致平局（两个相邻的
方格）如果我们从角方格开始。此外，如果我们申请
Warnsdorff 的启发式经过多次然后渐近
这相当于穷举搜索。

Pohl 还建议，如果我们在第二次应用 Warnsdorff 后未能产生后继者，可以通过使用固定的任意平方顺序来打破平局。他声称这成功地在 8*8 板上产生了解决方案。

通过使用这些增强功能之一，我们有更好的机会通过防止可能的锁定来系统地创建解决方案。

Answer 2

这是我发现的内容：

请注意，这仍然不是一个明确的答案，而且我也不是图论专家，所以这些只是观察结果。

我将经典的 Warnsdorff 启发式称为“W”。
http://mirran.web.surftown.se/knight/bWarnsd.htm< 的改进< /a> （缓存：http://web.archive.org /web/20120213164632/http://mirran.web.surftown.se/knight/bWarnsd.htm）将被调用“W+”。
https://github.com/douglassquirrel/warnsdorff/ 的改进blob/master/5_Squirrel96.pdf?raw=true 将是“W2”。
水平字段的数量将为“x”，垂直字段的数量将为“y”。

所以，这是我的观察。

简短版本：

W很简单，但在很多情况下它无法提供解决方案。一开始就引发了这个问题。 W+ 也很简单，并且提供了很大的改进，尤其是在大板上。 W2 的实现要复杂得多，而且与 W+ 相比，它似乎并没有给出更好的结果。所以我投票给W+。无论如何，这就是我将使用的变体。

长版：

W

优点：
与其他 Knights Tour 算法相比，简单。
和W+相比，确实没有什么优势。
与W2相比，它更容易实现。

缺点：
很多情况下有解决方案，但W无法提供解决方案
它往往会弄乱更大的板（50+）

W+

优点：
与其他 Knights Tour 算法相比，简单。
与W相比：它可以提供更多情况下的解决方案，并且几乎不比W复杂。
与W2相比，它更容易实现，并且W+也可以在非方板上工作。例如 10x20。

缺点：
与W相比，它没有缺点。
与其他骑士之旅算法相比，这个算法在某些情况下可能会卡住。 W+ 最难的是小板，如 5x5、6x6、7x7、9x9 等。正如 Wiki 上所述，当 x 和 y 均为偶数时，它会出现板问题。另一方面，当 x 和 y 为偶数但大于 9 时，W+ 似乎能够找到解决方案。
与W2相比，我并没有遇到劣势。

W2

优点：
与W相比，它提供了更多情况下的解决方案，特别是对于大板。
与 W+ 相比，我没有发现任何优势。

缺点：
与 W 和 W+ 的实施比较。

结论：

我认为W+实际上是最容易接受的。不要忘记它并不完美。我不得不说，我的实现不允许使用真正的大板。我测试了高达 90x90（8100 个节点）的 W+，它仍然提供了解决方案。不过，由于时间有限，我没有进行广泛的测试。我希望这可以帮助以前遇到过这个问题的人。
因为这不是一个确定的答案，我暂时不会接受，希望有人能给出完整的答案。
抱歉读了这么长。

Answer 3

以下是 Python 2 中的一个工作示例，它使用计时器来遍历电路板并说明解决方案。我找到最接近板边缘的节点作为平局断路器，如果两者相同，我只返回第一个。这似乎是一个自然的选择，因为如果棋盘是空的，靠近边缘的单元格的移动可能性就会较小。似乎运作良好，但正如 Panos 提到的，Arnd Roth 的提议有 1% 的失败率。可以轻松修改此代码以使用Ira Pohl 的提议。可以修改访问节点，以针对具有最小移动次数的节点再次运行 possible_unvisited_moves。如果出现平局，使用第一个应该可以。

class GNode(object):
    """ Used to represent a node in the graph """
    def __init__(self, value, row=None, col=None):
        self.row = row  # allows node to know its loc. in array
        self.col = col
        self.value = value

def setup_graph(n):
    """ Create x by x grid (graph inside an array). """
    graph = []
    for row in range(n):
        graph.append([])
        for col in range(n):
            graph[row].append(GNode(None,row=row, col=col))
    return graph

def possible_moves(graph_node, total):
    """ Find out all possible moves for the current node position. """
    moves = []
    move_patterns = [[-1,-2], [-1, 2], [-2, 1], [-2, -1], [1, -2], [1, 2], [2, 1], [2, -1]]
    for row, col in move_patterns:
        move_row = graph_node.row + row; move_col = graph_node.col + col
        if move_row >= 0 and move_col >= 0 and move_row < total and move_col < total:
            moves.append([move_row, move_col])
    return moves

def possible_unvisited_moves(graph_node, grid):
    """Get all possible moves and weed out the ones that are already visited. 
       visited means they have a value.
    """
    moves = possible_moves(graph_node, len(grid))
    unvisited = []
    for move in moves:
        if grid[move[0]][move[1]].value is None:
            unvisited.append(move)
    return unvisited


def closest_to_edge(pos1, pos2, total):  
    """ Find out which position is closest to the edge of board, and return it. 
        pos are 2 arrays [x,y], total is the board size (length)
    """
    total -= 1
    pos1_min = min(total - pos1[0], pos1[0], pos1[1], total-pos1[1])
    pos2_min = min(total - pos2[0], pos2[0], pos2[1], total-pos2[1])
    if pos2_min < pos1_min: return pos2
    return pos1  # default


def visit_node(graph_node, graph):
    """ Check possible unvisited moves from the pos & find next move to make """
    graph_node.value = "{}{}".format(graph_node.row, graph_node.col)  # visited
    p_moves = possible_unvisited_moves(graph_node, graph)
    next_move = None
    min_no_moves = 9 # highest can be 8 for knights move pattern
    for move in p_moves:
        next_moves = possible_unvisited_moves(graph[move[0]][move[1]], graph)
        if len(next_moves) < min_no_moves:
            next_move = move
            min_no_moves = len(next_moves)
        elif len(next_moves) == min_no_moves:
            min_move = closest_to_edge(next_move, move, len(graph))
            if min_move != next_move:
                next_move = min_move
                min_no_moves = len(next_moves)
    if next_move:
        os.system(clear_screen) 
        print "This Move: [",graph_node.row, ",",  graph_node.col, "]. Next Move: ", next_move, "Min Moves from next: ", min_no_moves
        display_graph(graph)
        import time
        time.sleep(.5)
        return visit_node(graph[next_move[0]][next_move[1]], graph)
    else:
        os.system(clear_screen) 
        display_graph(graph)
        return "Done"

def display_graph(graph):
    print ""
    for row in graph:
        row_vals = []
        for cell in row:
            row_vals.append(cell.value)
        print row_vals

import os
clear_screen = 'cls' if os.name == 'nt' else 'clear'

graph = setup_graph(8)

print visit_node(graph[4][4], graph)

玩得开心。 :)

Answer 4

我认为应用沃恩斯多夫规则时最容易被忽视的是正在构建的路径有两端。当对路径的两端应用两级平局决胜规则时，可以获得更好的结果。而且，作为额外的好处，产生的可重入旅行的数量大大增加。