経路/道路敷設の問題

Question

今日、私たちは実験室で完了するための割り当てを受けました（2時間で）。質問は次のとおりです。

• m*nマトリックスが与えられます。
• マトリックスには、「H」住宅ホールと「B」メインビルディングの入り口があります。
• これらの「H」ホールと「B」入り口の位置は（（x、y）座標の観点から）知られています。
• すべての住宅ホールには、「B」入り口の1つに到達するための少なくとも1つの方法があるように、経路を築く必要があります。
• せいぜい、そのような切断された経路を「b」することができます。
• 経路の長さは最小でなければなりません。
• 上に移動することしかできません。
• 解決策は、ブルートフォースの試みであってはなりません。

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

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

Answer 1

これが私が思いついた解決策です。 「B」切断されたパスは生成されません。すべての住宅と入り口を通過する1つのパスを生成します。

• ノードの各ペア間の距離を計算します（x座標の差 + y座標の差）。これで、完全なグラフができました。
• この完全なグラフのMSTを見つけてください
• MSTの各傾斜エッジ（垂直または水平ではないもの）は、水平と垂直の2つの部分に分割できます。
• 各分割は、最初に水平に続く垂直またはその逆のいずれかの2つの方法で作成できます。
• そのような順列それぞれを通過し、最小の長さでパスを計算します。これが答えです。

Answer 2

ソリューションが何であるか（推測では、ある種の最小コストパス分析）を伝えることができませんでしたが、道路モデリングソフトウェアの経験があります。

スケールの一端には、同様の（広く話す）アプローチを使用する戦略的モデリングシステムがあります。彼らは重力モデルのように考えることができます - それは交通量の推定値を使用して、たとえば町や都市、または住宅から産業エリアなどの交通フローを高レベルの予測するために使用します。主要な計画開発のマクロ効果、人口分布または土地利用ゾーンの変化..そのようなこと。

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

これがいくつかの便利なコンテキストを提供することを願っています。

Answer 3

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

• あなたが「あなたは道を築く必要がある」と言うとき、それは意味します」一つだけです 接続された道？

しかし、あなたが私の質問に答えても、これは非常に難しい問題です。 直線的なシュタイナーツリー 特別なケースとしての問題（メインの建物の入り口が1つしかない場合）。

そのため、一般的なケースで効率的に解決する方法を誰も知りません！

Answer 4

問題はよりシンプルで、シュタイナーツリーではなく、最小スパニングツリーでさえないと思います。

1. マトリックスMをv = {mij |でグラフgとして表します。 i <= m、j <= n}、e = {（mi1j1、mi2j2）：i1、i2 <= m、j1、j2 <= n、| i1-i2 | = 1-独占的または| j1-J2 | = 2}

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

3. h '= h/b、b' = b/h（入り口であるホールをマークし、深さ0で到達し、これらすべての入り口を削除します。

4. 幅最初のトラバーサルを行います。各深度マークで、すべてのホールがマークされるまで、Bから到達できるホールをマークします。対応する経路を選択します。

Answer 5

検索の問題です。あなたは2時間でそれをすることが期待されていましたよね？私は...するだろう DFS と プルーン. 。使用できます 経験則 より良いソリューションをより速く進めるために。しかし、ヒューリスティクスは最適なソリューションを保証できないことに留意してください。 すべての可能性を試してください. 。 NPハードのようです。