興味深い問題にぶつかりました。
無制限のチェス盤、N 人の騎士の開始位置、N の目標位置があります。
タスクは、すべてのナイトがすべてのターゲット位置に到達するための最小移動数を見つけることです。
1 人の騎士の最短経路問題は幅優先探索を使用して解決できることは知っていますが、複数の騎士の場合はどのように解決できるのでしょうか?
私の英語で申し訳ありませんが、めったに使用しません。
1611 次
4 に答える
2
Ricky が提案するように、幅優先検索を使用してコスト マトリックスを計算できます。したがって、cost[i][j] は、ナイト i を選択して終了位置 j に移動するコストを示します。次に、ハンガリーのアルゴリズムを使用して、O(N^3) の複雑さで計算できる最終的な答えを見つけることができます。
于 2011-10-19T18:33:19.707 に答える
2
1 つの Knigt に対してそれを行う方法を知っていると思います。
問題を線形計画法として再定式化できます。
次の表記法を使用します。
N 人の騎士と N 人の場所があります。
xij = 1騎士 i を選択して場所 j に移動する場合、それ以外の場合は 0
cijナイト i を位置 j に移動させる最小の長さ
次に、次の線形プログラムがあります。
変数:
[0,N] の ij に対する xij
コスト関数 :
C= SUM(cij.xij for (i,j) in [0,N]x[0,N])
制約:
SUM(xij for j in [1,N]) = 1 //ちょうど 1 つの knigt が i から j に移動します
SUM([1,N] の i に対する xij ) = 1
(行列(xij)は確率行列です)
X が (xij) の行列の場合、n! 可能なマトリックス。この問題はNP 困難である可能性があります (このシステムには簡単な解決策はありません。システムを解決することは、考えられるすべての解決策をテストすることとかなり似ています)。
編集：
この問題は代入問題と呼ばれ、多項式時間で解くアルゴリズムが複数存在します。（例については@puravの回答をご覧ください）
@Purav で言及されているように、この種の問題は NP 困難になる可能性がありますが、この場合は O(n^3) で解決できます
@j_random_hacker が提起した問題について:
問題
騎士がエンドポイントにいる場合、次のナイトはこのエンドポイントを通過できないはずです。そのため、騎士が移動するたびに Cij を更新する必要がある場合があります。
備考 ：
1. 複数の最適パス :
チェス盤の側 (制限されたチェス盤) には制約がないため、最短経路を達成するために移動する順序は関係ありません。ここでは組み合わせ論）。
騎士が 2 人の場合の例
2 K と 2 つのエンドポイント (「x」) があるとします。最適なパスが描画されます。
-x | | x | K-- --K
右の K を最初のポイントに移動します (1 回の移動)。2 番目のポイントは最適なパスを使用できません。
-x | | K | K-- --:
しかし、2 つ右 1 つ上に 2 つ上 1 つ右に移動する代わりに、新しい最適なパスを簡単に作成できます。1 は 2 を上に 1 を右に 1 を上に 2 を右に移動できます (ちょうど逆)
--K | - | K | | : --:
パスの任意の組み合わせが機能します：
1 U 2 R その後 2 U 1 R など... UP LEFT DOWN と RIGHT の同じ数の移動を維持し、それらが有効である限り。
2. 騎士の移動順序:
2 つ目は、自分の移動順序を選択できることです。
例：
前の例で、左の騎士から始めて上のエンドポイントに行くことを選択した場合、エンドポイントの制約はもうありません。
-K | | x | :-- --K -K | | K | :-- --:
これら 2 つの注意事項を使用して、計算された下限が最適でない状況が存在しないことを証明できる可能性があります。
于 2011-10-19T09:29:51.157 に答える
1
BFS はここでも機能します。状態を少し調整する必要がありますが、それでも機能します。
可能Sな状態のセットになります。
S={((x1,y1),(x2,y2),...,(xn,yn))|knight i is in (xi,yi)}
S の各 s について、次を定義します。
Successors(s)={all possible states, moving 1 knight on the board}
ターゲット状態はもちろん、ターゲット ポイントのすべての順列です [これらの順列を実際に作成する必要はありません。すべての四角形が「塗りつぶされた」状態に達したかどうかを確認するだけで、簡単に確認できます]
start=(start_1,start_2,...,start_n)ここで、start_i はナイト i の開始位置です。
[各騎士の初期位置]からの BFS の実行は、start[BFS が完了しているため] 存在する場合、解決策を見つけることが保証されています。また、可能な限り最短のソリューションであることが保証されています。
(*)単一の騎士の場合は、このソリューションのプライベート インスタンスであり、n=1 であることに注意してください。
BFS は機能しますが、かなり時間がかかります。ここでの分岐係数は 4n であるため、アルゴリズムはO((4n)^d)頂点を作成する必要があります。n は騎士の数、d は解に必要なステップ数です。
可能な最適化:
- スペース: BFS は多くのメモリ
O((4n)^d)を使用する [ ] ため、BFS のように動作しますが、消費するメモリははるかに少なく [O(nd)] 実行に時間がかかります。 - 時間:解決策の検索を加速するために、 A Starを 許容ヒューリスティック関数と共に使用できます。また、解が存在する場合は解を見つけることが保証され、見つかった解が最適であることも保証されます。また、おそらく [適切なヒューリスティックを使用して] BFS よりも少ない頂点を開発する必要があります。
于 2011-10-19T15:25:17.000 に答える
0
だから、私は解決策を見つけました。
BFS は無制限のチェス盤ではうまく機能しません。最短経路アルゴリズムを使用しても意味がありません -- 位置 a から位置 b への騎士の移動回数は O(1) 時間で計算できます -- M. Deza, Dictionary of Distances, p. 251
http://www.scribd.com/doc/53001767/Dictionary-of-Distances-M-Deza-E-Deza-Elsevier-2006-WW
割り当ての問題は、mincost-maxflow アルゴリズム (例: Edmonds-Karp) を使用して解決できます。
于 2012-02-09T11:55:07.550 に答える