12

今日、ラボで（2時間で）完了する課題がありました。質問は：

  • m*n行列が与えられます。
  • マトリックスには、「h」の寮と「b」の本館の入り口があります。
  • これらの「h」ホールと「b」入口の位置は既知です（（x、y）座標に関して）。
  • すべての寮が「b」の入り口の1つに到達するための少なくとも1つの方法を持つように経路を敷設する必要があります。
  • そのような切断された経路はせいぜい「b」である可能性があります。
  • 経路の長さは最小でなければなりません。
  • 上、下、左、または右にのみ移動できます。
  • 解決策はブルートフォース攻撃であってはなりません。

割り当ては終了しました。しかし、私はまだこれがどのように解決されるかを考えています。そのような問題の標準的な用語はありますか？何を読めばいいですか？

人々はそのようなアルゴリズムを都市に道路を敷設するためにも使用していますか？

4

5 に答える 5

3

これが私が思いついた解決策です。'b' 個の切断されたパスは生成されません。これは、すべての住居のホールと入口を通過する 1 つのパスを生成します。

  • ノードの各ペア間の距離を計算します (X 座標の差 + Y 座標の差)。これで完全なグラフができました。
  • この完全なグラフの MST を見つけます
  • MST の各傾斜エッジ (垂直でも水平でもないエッジ) は、水平と垂直の 2 つの部分に分割できます。
  • 各分割は 2 つの方法で行うことができます - 最初に水平方向に続いて垂直方向に、またはその逆のいずれかです。
  • そのような各順列を調べて、最小の長さのパスを計算します。これが答えです。
于 2010-11-29T07:08:19.437 に答える
2

ソリューションが何であるかはわかりませんが (推測では、最小コスト パス分析のようなものです)、道路モデリング ソフトウェアの経験があります。

規模の一端には、同様の (大まかに言えば) アプローチを使用する戦略モデリング システムがあります。それらは重力モデルのように考えることができます - 交通生成と需要の見積もりを使用して、例えば、町と都市の間、または工業地域と住宅地などの間の交通の流れを高レベルで予測します。計画されている大規模な開発、人口分布または土地利用ゾーンの変化のマクロ効果で..そのようなこと。

もう一方の端には、都市、町、インターチェンジなどの特定の領域のシミュレーション モデルがあります。これらは、攻撃性、道路の知識などの要素を持つ自律エージェントとして各車を扱う数値モデルです。これは非常に強引なアプローチですが、信号機やバスなどの機能を備えた複雑なネットワークでの実際のトラフィックの動作に関する有用な統計を提供する唯一の方法です。トラフィック モデラーは、たとえば、実際の交通管制データを取得するには、特定の設計ソリューションに対して特定の期間モデルを実行し、6 回または 7 回実行するように設定します。得られたデータは、特定のソリューションの別のソリューション (または現状) に対するパフォーマンスの非常に優れた評価を提供します。

これが有用なコンテキストを提供することを願っています。

于 2010-11-25T21:00:37.433 に答える
1

私には明確ではない問題の説明の側面があります。

  • 「道を敷く必要がある」というのは、「つながっている道は一つだけ」ということですか？または、複数の切断されたパスが存在する可能性がありますか? (例: ホール H1 から建物入口 B1 への経路と、ホール H2 から建物入口 B2 への別の経路)

しかし、私の質問にどのように答えても、これは非常にトリッキーな問題です。特殊なケースとして直線シュタイナー木問題が含まれているため (メインの建物の入り口が 1 つしかない場合)、NP 困難です。

したがって、一般的なケースで効率的に解決する方法は誰も知りません!

于 2010-11-25T21:34:50.633 に答える
1

検索問題です。2時間でやると思ってたでしょ？私ならDFSとpruneを使います。ヒューリスティックを使用して、より優れたソリューションをより迅速に取得できます。ただし、ヒューリスティックは最適なソリューションを保証できないため、すべての可能性を試す必要があることに注意してください。NP困難のようです。

于 2010-11-29T02:59:50.860 に答える
1

問題はもっと単純で、シュタイナー木でも最小全域木でもないと思います。

  1. 行列 M をグラフ G として表します。i <=m, j <= n}, E= {(Mi1j1,Mi2j2) : i1,i2 <=m, j1,j2<=n, |i1-i2| = 1 排他的 OR |j1-j2| = 2}

  2. 入口のセットB、ホールのセットHを取る

  3. H' = H/B、B' = B/H (入り口であるホールをマークします。深さ 0 で到達します。ホールであるため、これらの入り口をすべて削除します)

  4. 幅優先走査を行います。各深さで、すべてのホールがマークされるまで、B から到達できるホールをマークします。対応する経路を選択します。

于 2010-11-26T02:25:08.433 に答える