12

クラス用にカタンの入植者のクローンを書いています。追加のクレジット機能の 1 つは、どのプレーヤーが最長の道路を持っているかを自動的に決定することです。考えてみたところ、深さ優先検索のわずかなバリエーションが機能するように思えますが、サイクル検出をどうするか、プレイヤーの 2 つの最初の道路ネットワークの結合を処理する方法を理解するのに苦労しています。と他のいくつかの細目。どうすればアルゴリズム的にこれを行うことができますか?

このゲームに慣れていない人のために、問題を簡潔かつ抽象的に説明しようと思います。無向巡回グラフで可能な最長パスを見つける必要があります。

4

7 に答える 7

7

これは、実装するのがかなり簡単なアルゴリズムになるはずです。

まず、道路を別個のセットに分けます。各セットのすべての道路セグメントは何らかの方法で接続されています。これにはさまざまな方法がありますが、ここではその 1 つを示します。

  1. ランダムな道路セグメントを選択してセットに追加し、マークを付けます
  2. このセグメントから分岐します。マークされていない接続されたセグメントを両方向にたどります（マークされている場合は、すでにここにいます）
  3. 見つかった道路セグメントがまだセットにない場合は、追加してマークを付けます
  4. 現在セット内にあるセグメントに接続されているマークされていないセグメントが見つからなくなるまで、新しいセグメントから続けます。
  5. マークされていないセグメントが残っている場合、それらは新しいセットの一部であり、ランダムなセグメントを選択して別のセットで 1 から開始します

注: 公式のカタン ルールに従って、別のプレイが 2 つのセグメント間のジョイントに和解を構築すると、道路が壊れる可能性があります。これを検出し、集落を越えて分岐しないようにする必要があります。

上記および以下の手順では、現在のプレーヤー セグメントのみを考慮することに注意してください。それらの他のセグメントは、マップ上にさえないかのように無視できます。

これにより、1 つまたは複数の道路セグメントを含む 1 つまたは複数のセットが得られます。

各セットについて、次の操作を行います。

  1. 接続された道路セグメントが 1 つだけあるセット内のランダムな道路セグメントを選択します (つまり、エンドポイントを選択します)。
  2. それができない場合は、セット全体が (1 つ以上) ループしているため、この場合はランダムなセグメントを選択します

ここで、選択したセグメントから再帰的に分岐する深さ優先検索を実行し、これまでに見つけた現在の道路の長さを追跡します。道路セグメントも常にマークし、既にマークされているセグメントに分岐しないでください。これにより、「自分の尻尾を食べた」ときにアルゴリズムを停止できます。

分岐がなくなったためにバックトラックする必要があるときはいつでも、現在の長さをメモし、それが「以前の最大値」よりも長い場合は、新しい長さを最大値として保存します。

これをすべてのセットで行うと、最長の道路ができあがります。

于 2010-07-07T07:33:30.817 に答える
2

少し遅れていますが、それでも関連性があります。私はJavaで実装しました。ここを参照してください。アルゴリズムは次のようになります。

  • プレーヤーのすべてのエッジを使用してメイン グラフからグラフを導出し、エッジに接続されたメイン グラフの頂点を追加します。
  • 端 (次数==1 の頂点) と分割 (次数==3 の頂点) のリストを作成します。
  • すべての端点、およびすべての分割で検出された 2 つのエッジ + 1 つの頂点の組み合わせ (次数が 3 であるため 3) ごとにチェックするルート (possibleRoute) を追加します。
  • すべてのルートを歩きます。エンド、インターミディエイト、スプリットの 3 つに遭遇する可能性があります。
  • End : possibleRoute を終了し、見つかったリストに追加します
  • 中間: 他のエッジへの接続が可能かどうかを確認します。その場合は、エッジを追加します。そうでない場合は、ルートを終了し、見つかったルート リストに追加します。
  • 分割: 両方のエッジに対して、中間として行います。両方のルートが接続されたら、2 番目のルートをコピーしてリストに追加します。
  • 接続の確認は、次の 2 つの方法を使用して行われます。新しいエッジが possibleRoute に既に存在するかどうか (接続なし) を確認する方法と、頂点と元の頂点をパラメーターとして指定して接続できるかどうかを新しいエッジに問い合わせる方法です。道路は道路に接続できますが、頂点に別のプレイヤーの都市/居住地が含まれていない場合に限ります。道路は船に接続できますが、ルートがチェックされているプレイヤーからの都市または道路が頂点にある場合に限ります。
  • ループが存在する可能性があります。検出されたすべてのエッジは、まだリストにない場合はリストに追加されます。すべての可能なルートがチェックされているが、このリスト内のエッジの量がプレーヤーのエッジの合計量よりも少ない場合、1 つ以上のループが存在します。この場合、チェックされていないエッジは新しい possibleRoute から作成され、ルートについて再度チェックされます。
  • 最長ルートの長さは、すべてのルートを単純に反復することによって決定されます。5 つ以上のエッジを持つ最初のルートが返されます。

この実装は、Catan のほとんどのバリアントをサポートします。エッジは、別のエッジに接続するかどうかを自分で決定できます。

SidePiece.canConnect(point, to.getSidePiece());

道路、船、橋には SidePiece インターフェイスが実装されています。道路は実装として持っています

public boolean canConnect(GraphPoint graphPoint, SidePiece otherPiece)
{
    return (player.equals(graphPoint.getPlayer()) || graphPoint.getPlayer() == null)
            && otherPiece.connectsWithRoad();
}
于 2011-02-12T19:29:33.253 に答える
2

幅優先検索をお勧めします。

各プレーヤーについて:

  • デフォルトの既知の最大値を 0 に設定します

  • 開始ノードを選択します。接続された隣人がゼロまたは複数の場合はスキップし、そこから始まるプレーヤーのすべてのパスを幅優先の方法で見つけます。キャッチ: ノードがトラバースされると、そのターンに残されたすべての検索に対して「非アクティブ化」されます。つまり、通過できなくなる可能性があります。

    これはどのように実装できますか？使用可能な幅優先アルゴリズムの 1 つを次に示します。

    1. この最初のノードからのパスがない場合、または複数のパスがない場合は、非アクティブ化のマークを付けてスキップします。
    2. パスのキューを保持します。
    3. 最初の行き止まりノードのみを含むパスをキューに追加します。このノードを無効にします。
    4. キューから最初のパスを取り出し、それを「展開」します。つまり、有効な方向へのパス + 1 ステップであるすべての有効なパスを見つけます。「有効」とは、次のノードが最後のノードに道路で接続されている必要があり、アクティブ化されている必要があります。
    5. 最後のステップでステップしたすべてのノードを非アクティブにします。
    6. 前のパスの有効な「爆発」がない場合は、そのパスの長さを既知の最大値と比較します。それより大きい場合は、新しい最大値です。
    7. 展開されたパスがあれば、すべてキューに追加します。
    8. キューが空になるまで 4 ～ 7 を繰り返します。

  • これを一度実行したら、次にアクティブ化されたノードに移動し、プロセスを最初からやり直します。すべてのノードが非アクティブになったら停止します。

  • 現在の最大値は、指定されたプレーヤーの最長道路の長さです。

これは少し効率が悪いことに注意してください。ただし、パフォーマンスが問題にならない場合は、これでうまくいくでしょう :)

重要な注意事項、Cameron MacFarland に感謝

  • 現在のプレイヤーに属していない都市を持つすべてのノードが常に自動的に非アクティブ化されると仮定します。

get_neighborsRuby 疑似コード (ノードごとに関数を想定)

def explode n
  exploded = n.get_neighbors             # get all neighbors
  exploded.select! { |i| i.activated? }  # we only want activated ones
  exploded.select! { |i| i.is_connected_to(n) } # we only want road-connected ones
  return exploded
end

max = 0

nodes.each do |n|                 # for each node n
  next if not n.activated?        # skip if node is deactivated
  if explode(n).empty? or explode(n).size > 1
    n.deactivate                  # deactivate and skip if
    next                          # there are no neighbors or
  end                             # more than one

  paths = [ [n] ]                 # start queue

  until paths.empty?              # do this until the queue is empty

    curr_path = paths.pop         # pop a path from the queue
    exploded = explode(curr_path) # get all of the exploded valid paths

    exploded.each { |i| i.deactivate }  # deactivate all of the exploded valid points

    if exploded.empty?                  # if no exploded paths
      max = [max,curr_path.size].max    # this is the end of the road, so compare its length to
                                        # the max
    else
      exploded.each { |i| paths.unshift(curr_path.clone + i) }  
                                        # otherwise, add the new paths to the queue
    end

  end

end

puts max
于 2010-07-07T07:06:36.060 に答える
2

この問題は NP 困難であるため、単純な多項式時間の深さ優先検索は機能しそうにありません。最適解を得るには、指数関数的な時間がかかるものが必要になります。ただし、問題は非常に小さいため、実際には問題にならないはずです。

おそらく、最も簡単な解決策は動的計画法です。ノード v ごと、長さ l ごとに、長さ l で v で終わるパスのセットを格納するテーブル T[v, l] を保持します。明らかに T[v, 1] = { [v]} そして、T[w, l-1] からすべてのパスを収集することにより、l > 1 の T[v, l] を埋めることができます。ここで、w は、v をまだ含まない v の隣人であり、v をアタッチします。 . これは Justin L. のソリューションに似ていますが、作業の重複を避けることができます。

于 2010-07-07T08:52:53.207 に答える
0

私がすること：

  1. 道路のある頂点をピック
  2. たどる道を 2 つまで選択してください
  3. 道をたどってください。分岐する場合はここでバックトラックし、長い方を選択します
  4. 現在の頂点が訪問済みリストにある場合は、3 に戻ります
  5. 頂点を訪問済みリストに追加し、3 から再帰します
  6. 3 でこれ以上道路がない場合は、長さを返します
  7. たどった道が 2 本以下になったら、それらを合計し、長さに注意してください
  8. 最初の頂点に道路が 3 つある場合は、2 つに戻ります。

プロローグっぽい用語でごめんなさい:)

于 2010-07-07T02:25:54.723 に答える
-1

Dijkstra を使用して条件を変更し、代わりに最長パスを選択することができます。

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

効率的ですが、ほとんどの場合は機能しますが、実際には最短/最長のパスが常に見つかるとは限りません。

于 2010-07-07T07:37:07.297 に答える