今日、私たちはラボでの仕事を完了しました（2時間後）。問題は次のとおりです。通路/道路敷設の問題
割り当てが終了しました。しかし、私はまだこれがどのように解決されるか考えています。このような問題の標準用語はありますか？私は何を読むべきですか？
人々はこのようなアルゴリズムを使って都市に道路を敷設していますか？
ここに私が思いついた解決策があります。 'b'の切断されたパスは生成されません。すべての居住用のホールと入り口を通過する1つの経路を生成します。
ソリューションが何であるかを推測することはできませんでしたが、道路モデリングソフトウェアの経験があります。
スケールの一端には、同様の（広く言えば）アプローチを使用する戦略的モデリングシステムがあります。彼らは、重力モデルのように考えることができます - それは、トラフィックの発生の推定と、例えば都市と都市、または工業地域から住宅へのトラフィックフローの高いレベルの予測を使用する需要を使用します。これは、主要な計画的開発のマクロ的な影響、人口分布や土地利用の変化などがあります。
都市、町、インターチェンジなどの特定のエリアのシミュレーションモデルがあります。これは、各車を侵略、道路知識などの要因を持つ自律エージェントとして扱う数値モデルです。これは非常にブルートフォーススタイルのアプローチですが、複雑なネットワークの実際のトラフィック動作に関する有用な統計情報を、信号機やバスなどの機能と組み合わせて提供する唯一の方法です。トラフィックモデラーは、たとえば、実際の交通管理データ、特定の設計ソリューションの特定の期間のモデルを実行し、6または7回実行するように設定します。結果のデータは、特定のソリューションのパフォーマンス（または現状）に対する非常に優れた評価を提供します。
これは、役に立つコンテキストを提供します。私には明らかではないが、問題記述の側面があります
興味深い！どのようなソフトウェアを使用しましたか？私はそれを試してみたい –
：「？ちょうど1接続パスを」
あなたは「あなたが経路を築く必要がある」と言うしかし、あなたは私の質問に答えますが、これは非常に難しい問題です。特別なケースとしての問題（rectilinear Steiner tree）（メインの建物入り口が1つだけの場合）。
したがって、一般的なケースで効率的に解決する方法は誰も知りません！
私はちょうど質問を修正しました。複数のパスを持つことができます。 - Rectilinear Steiner Treeという言葉をありがとう...私はそれについて読むよ！ –
私は問題が簡単で、スタイナーツリーでも、最小スパニングツリーでもないと思います。
グラフGをV = {Mij | （i1、i2、i2）：i1、i2、i2、i3、i2、i3、i4、 = 1排他的論理和| j1-j2 | = 2}
は入口のセットBを取り、ホールのHに
H '= H/B、B' = B/Hを（入口であるホールをマークし、それらは、深さ0に達しますこれらの入り口をホールのようにすべて外します）
幅優先通過を行います。それぞれの深さには、Bから到達可能なホールに、すべてのホールがマークされるまで印を付けます。対応する経路を選択します。
これは経路の可能な限りの長さですか？例：H1 =（5,5）H2 =（6,9）B1 =（12,5）B2 =（10,10）。 H2はB2に非常に近いですが、経路はありません。 H1はB1に直接接続します。そしてH2はこの経路に接続します。 –
私はあなたの意見を見ます、私は最小限の意味 - ドアからの最小の長さの経路のセットを考えて答えました。しかしあなたのコメントを見てみましょう。あなたの長さの合計が最小であるような一連の経路を見つけようとしているようです。その場合、私は最初の考えであった – mho
を再試行しなければならないでしょう。これは一種の洪水充填アルゴリズムです。そして、私は問題が不明であることに同意する。 –
検索に問題があります。あなたは2時間後にそれをする予定でしたよね？私はDFSとプルーンです。より良いソリューションに素早くアクセスするには、ヒューリスティックを使用できます。しかしヒューリスティックは最適解を保証できないので、にすべての可能性を試してください。。 NP困難なようだ。
これは、多くの場合、最小パス長を指定できません（切断されたパスでは、より短い答えが得られる場合があります）場合によっては、パスの一部をジグザグにする方が効率的かもしれません。 –