まず、これは宿題や関連するものではなく、(freeciv) という名前のゲームの問題であると言わなければなりません。
わかりました、ゲームでは通常「n」個の都市 (8 ～ 12) があり、各都市は通常「k」個 (4) の最大数の交易路を持つことができ、それらの交易路は「d」にする必要があります。 ' 距離以上 (8 マンハッタン タイル)。
問題は、(最大距離または最小距離) で k*n 貿易ルートを見つけることです。明らかに、この問題は力ずくのアルゴリズムで解決できますが、プレイヤーが 10 を超える都市を持っている場合は非常に遅くなります。プログラムは何度か反復する必要があります。グラフ理論を使って解こうとしましたが、私はその専門家ではありません。教師に尋ねたところ、誰もスマートアルゴリズムについて説明できませんでした。そのため、正確な解を見つけるためにここに来たわけではありませんが、私はこれを分析するためのアイデアまたは手順を取得する必要がありました。
この問題には次の 2 つの部分があります。
ダイクストラのアルゴリズムを実行するたびに、ある都市から他のすべての都市までの距離が得られるため、最初の部分はO(n·t) ( tはタイルの数)よりも速く計算できるとは思いません。しかし、私の理解が正しければ、2 つの都市間の距離は変わらず、左右対称です。したがって、新しい都市が建設されるたびに、そこからダイクストラのアルゴリズムを実行し、距離をキャッシュするだけで済みます。
2番目の部分では、貪欲なアルゴリズムが機能することを期待しています。都市のすべてのペアを適合性で並べ替え、各ステップで、都市ごとにkルートという制約に違反しない最初の都市を選択します。証明できるかどうかはわかりません (証明は、存在する場合、クラスカルの最小スパニング ツリー アルゴリズムの証明と同様になるはずです。しかし、理論的には機能しないことがわかったとしても、実際にはうまく機能すると思います (私はそれを証明しようとも反証しようともしていません; それはあなた次第です)
@Jan Hudecのやり方を続ける：
初期段階:
N 個の都市 (c1、c2、... cN) があるとします。リスト内の各エンティティの形式が (cX, cY, Distance) の場合 (X < Y、これは n^2/2 時間)、接続のリストを作成し、距離 (最大距離の降順) で並べ替える必要があります。または最小距離の昇順)、また、都市ごとの接続数 (cZ = W) を保持する配列/リストも必要です。これは、最初にすべてが接続されているため、N-1 で各都市に対して初期化されます。
反復: (cX、cY、D) ごとに接続のリストを反復し、(接続番号配列内の) 接続の数が cX > k および cY > k の場合、接続リストから (cX、cY、D) を削除します。また、接続配列の cX と cY の値を 1 ずつ決定します。
最後に、必要な値を含む接続リストが表示されます。