4

米国の州のように、州のリストが与えられた場合、州が連続しているかどうかを判断するアルゴリズムを作成しようとしています。順序は関係なく、状態を再訪することができます。

例:

  • AZ, CA, OR, WA隣接している
  • AZ, CA, NM, UT隣接している
  • AZ, NM, OR, WA連続していない

仮定:

  1. 州を表す文字列のコレクションがあります。

  2. 状態接続のコレクションがあります。

    class StateConnection
{
    public string OriginState { get; set; }
    public string ConnectingState { get; set; }
}

このコレクションには両方向のレコードがあります。

  • OriginState = AZ, ConnectingState = CA
  • OriginState = CA, ConnectingState = AZ

私は何を試しましたか？

試行 1: コレクション内の各状態について、リスト内に別の状態を持つ StateConnection が少なくとも 1 つあることを確認します。

なぜうまくいかなかったのですか？ これにより、2 つの別個の連続した範囲が渡される 3 番目の例が可能になります。

試行 2: 状態をチェックした後、候補接続状態のリストから状態を削除します。これには、すべての状態に 1 回触れる完全なパスが必要になります。

なぜうまくいかなかったのですか？ これは、1 つの州が複数の州のハブとして機能する 2 番目の例を許可しません。

私はグラフ理論の問題をしばらく解いていないので、少しさびています。

最短経路や巡回セールスマンのようなものは求めていません。どのパスが取られるか、または何回の移動が使用されるかは気にしません。隙間があるかどうかだけが気になる。

私はこれをC＃で書いていますが、他の言語で自由に答えてください。

4

3 に答える 3

4

グラフ理論のフラッドフィリングをご覧ください。ツリー内の接続されている各ノードを「ペイント」し、最後に、状態のいずれかが接続されていないままであるかどうかを確認します。グラフをトラバースしてペイント（BFSまたはDFS）を実行する方法は重要ではありませんが、これによりギャップ（または接続されていないノード）が強調表示されます。

于 2012-07-27T15:02:41.977 に答える
2

最良の解決策は、状態のグラフを介した幅優先検索であるように思えます。次のようなもの (例として最初のリストを使用):

  • 調べる状態のキューを作成します。まず、空です。
  • リストから状態を選択します。たとえばCA、キュ​​ーに追加します。

次に、次のようにループします。

  • キューから状態をデキューします。訪問済みとしてマークします。
  • そのすぐ隣 (訪問されていないもの) がリストに含まれているかどうかを確認します。はいの場合は、それらをキューに追加します。
  • たとえば、 の場合CA、リストに次の 2 つのナイトバーが見つかりましORたAZ。それらを次の状態のキューに追加して調べます。後で を調べると、とがその隣にあり、リストに載っているORことがわかります。すでに訪問済みなので、訪問する州のリストにのみ追加します。WACACAWA

デキューする状態がなくなるまで続行します。その時点までに最初のリストのすべての州を訪問した場合、リストは連続しています。そうでなければそうではありません。

于 2012-07-27T15:04:45.830 に答える
2

問題の状態のサブセットの接続性マトリックスを作成します (N*Nサブセット内の各状態の行と列を含み、状態とが互いに隣接しているm[i,j]==true場合のみ)。ij

次のアルゴリズムを実行します。

for (int k=0 ; k != N ; k++)
    for (int i=0 ; i != N ; i++)
        for (int j=0 ; j != N ; j++)
            m[i,j] |= (m[i,k] && m[k,j]);

3 つのループが終了した後、 のすべての要素がm[i,j]に設定されていることを確認します。trueいずれかの要素がfalseである場合、状態は連続していません。

「あの 3 ループのこと」とは何かを忘れた方のために説明すると、それはグラフの推移閉包を見つけるための有名なFloyd-Warshall アルゴリズムです。

于 2012-07-27T15:04:48.773 に答える