同様のスレッドがいくつかあることは知っていますが、SOの外でも解決策が見つかりませんでした。ここに私の問題があります: Knight's Tour 問題http://en.wikipedia.org/wiki/Knight%27s_tourに対して Warnsdorff のアルゴリズムを実装しましたが、場合によっては解決策が得られません。私が読んだいくつかの場所では、いくつかの変更によりはるかにうまく機能する可能性がありますが、どの変更がそれらであるかを誰も指定していません. 誰かが解決策を知っていますか？私は他のアルゴリズムを知っていますが、それらははるかに複雑です。
8x8 のチェス盤であっても、適切な解が得られないことがあります。これは古典的な Warnsdorff のコードなので、コードを読んでも意味がないと思います。次のステップで可能な動きをチェックし、可能な動きが最も少ないものを選択します。
W+のリンクが存在しなくなったため、受け入れられた回答が使用できなくなりました。
Warnsdorff アルゴリズムの改善点は次のとおりです。
Arnd Roth の命題: Roth は、Warnsdorff のヒューリスティックの問題は、ランダムなタイブレーク ルールにあると判断しました。命題は、ボードの中心から最大のユークリッド距離を持つ後継者を選択することによって、関係を断ち切ることです。
ここでの問題は、複数の後継者が同じ距離を共有する場合に何が起こるかです。
Arnd Roth は、この改善は 428 行のボードで最初に失敗し、2000 行未満のすべてのボードで 1% 未満の失敗だったと主張しました。
Ira Pohl の命題: この関係を断ち切るために、Pohl は Warnsdorff の規則をもう一度適用することにしました。これを達成するには、すべての未訪問の隣人、同点の後継者の次数の合計を取り、合計が最小になる正方形を選択する必要があります。
ここでの問題の 1 つは、Warnsdorff のルールを何度適用しても、角の正方形から開始すると (隣接する 2 つの正方形の間で) 同点になることです。さらに、Warnsdorff のヒューリスティックを何度も適用すると、漸近的にこれは徹底的な検索に等しくなります。
Pohl はまた、Warnsdorff を 2 回目に適用した後に後継者を生成できなかった場合は、正方形の固定された任意の順序を使用して同点を解消することを提案しました。彼の主張は、これが 8*8 ボード上で問題なく解決策を生み出すというものです。
これらの拡張機能のいずれかを使用することで、ロックインの可能性を防ぎ、体系的にソリューションを作成できる可能性が高くなります。
これが私が見つけたものです：
これはまだ決定的な答えではなく、私はグラフ理論の専門家ではないので、これらは観察のみであることに注意してください。
古典的な Warnsdorff ヒューリスティックを「W」と呼びます。http://mirran.web.surftown.se/knight/bWarnsd.htmからの改善(キャッシュ: 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+ が最も受け入れられます。完璧ではないことを忘れないでください。そして、私の実装では非常に大きなボードは許可されていないと言わざるを得ません。W+ を最大 90x90 (8100 ノード) までテストしましたが、それでも解決策が得られました。ただし、時間が限られているため、広範なテストは行いませんでした。これが、以前にこの問題に直面した人に役立つことを願っています。確定的な回答ではないので、しばらくは受け付けませんが、完ぺきな回答をしてくれる人が現れることを期待します。長々と読んですみません。
これは、タイマーを使用してボードを通過し、ソリューションを示す Python 2 の実際の例です。タイ ブレーカーのボードの端に最も近いノードを見つけ、両方が同じ場合は、最初のノードを返します。ボードが空の場合、端に近いセルほど可能な移動が少なくなるため、これは自然な選択のように思われました。うまく機能しているように見えますが、Panos が言及しているように、Arnd Roth の命題には 1% の失敗率があります。このコードは、 Ira Pohl's Propositionを使用するように簡単に変更できます。Visit ノードを変更して、両方とも移動が最小のノードに対して 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)
楽しんで遊んでください。:)