Weg / Straße Problem Verlegung

Question

Heute haben wir einen Auftrag im Labor abzuschließen (in zwei Stunden). Die Frage war:

• Sie sind eine m * n-Matrix gegeben.
• Die Matrix hat 'h' Wohn-Hallen und 'b' Hauptgebäude Eingänge.
• Die Lage dieser 'h' Hallen und 'b' Eingängen ist bekannt (in Bezug auf die (x, y) Koordinaten).
• Sie müssen Wege legen, so dass jeder Wohnhalle mindestens eine Art und Weise hat eine der ‚b‘ Eingänge zu erreichen.
• Es höchstens 'b' solche getrennte Wege sein kann.
• Die Länge des Weges sein Minimum muss.
• Sie können nur nach oben, unten, links oder rechts.
• Die Lösung darf nicht zu einem Brute-Force-Versuch sein.

Die Zuordnung ist vorbei. Aber ich denke immer noch, wie diese gelöst werden würden. Gibt es ein Standardbegriff für solche Probleme? Was soll ich lesen,?

Do Menschen nutzen solche Algorithmen auf Straßen in den Städten als auch die Verlegung?

Answer 1

Hier ist eine Lösung, die ich mit aufkommen. Es erzeugt keine ‚b‘ getrennt Wege. Es erzeugt einen Pfad, der durch alle Wohnräume und Eingänge geht.

• Berechnen der Abstand zwischen jedem Paar von Knoten (Differenz der Koordinaten X + Differenz der Y-Koordinaten). Jetzt haben Sie einen vollständigen Graphen.
• Finden Sie die MST für dieses vollständigen Graphen
• jeder geneigten Kante der MST (diejenigen, die nicht vertikal oder horizontal) kann in zwei Teile geteilt werden. - die horizontale und die vertikale
• Jede Spaltung kann auf zwei Arten erfolgen -. Entweder horizontal erste kehrt durch die vertikale oder umge gefolgt
• Gehen Sie durch jede solche Permutation und berechnen Sie den Pfad mit der geringsten Länge. Dies ist die Antwort.

Answer 2

Könnten Ihnen nicht sagen, was die Lösung ist (eine Art Least-Cost-Pfad-Analyse, bei einer Vermutung), aber ich habe einige Erfahrung mit Straßen-Modellierungs-Software.

An einem Ende der Skala Sie strategische Modellierungssysteme haben, die einen ähnlichen (im weitesten Sinne) Ansatz. Sie können wie ein Gravitationsmodell gedacht werden - es Schätzungen der Verkehrserzeugung nutzen und fordert hohe Vorhersagen machen den Verkehr zwischen fließt, beispielsweise Städte oder Industriegebiete bis hin zu Wohn usw. Dies ist vor allem nützlich für die Suche bei den Makro Auswirkungen der wichtigsten geplanter Entwicklungen, Veränderungen in der Bevölkerungsverteilung oder Landnutzungszonen .. diese Art der Sache.

Am anderen Ende Sie Simulationsmodelle von bestimmten Bereichen einer Stadt, in der Stadt, Austausch haben, usw. Diese sind numerische Modelle, die jedes Auto als autonome Agenten mit Faktoren wie Aggression, Straßen Wissen behandeln, und so weiter. Das ist sehr viel ein Brute-Force-Stil Ansatz, aber es ist die einzige Möglichkeit, nützliche Statistiken über die tatsächliche Verkehrsverhalten in einem komplexen Netzwerk mit Funktionen wie Ampeln, Busse usw. Einem Verkehr Modellierer kann, zum Beispiel zu liefern, stecken Sie sie in die tatsächliche Verkehrssteuerdaten, führen das Modell für einen bestimmten Zeitraum für eine bestimmten Konstruktionslösungen und setzten es 6 oder 7-mal auszuführen. Die resultierenden Daten gibt Ihnen eine sehr gute Beurteilung der Leistung einer bestimmten Lösung gegen einen anderen (oder den Status quo).

Hope dies bietet einigen nützlichen Kontext.

Answer 3

Es ist ein Aspekt des Problems Beschreibung, die mir nicht klar ist:

• Wenn Sie sagen: „Sie müssen einen Weg legen“, soll das heißen „ nur ein verbundenen Weg?“ Oder kann es mehrere getrennte Pfade sein? (Beispielsweise ein Pfad von Hall-H1 zu Eingang B1 und einen separaten Weg von der Halle zu H2 Eingang B2)

Aber wie Sie meine Frage beantworten, ist dies ein äußerst kniffliges Problem: es ist NP-schwer, wie es die geradlinige Steiner Baum Problem als Spezialfall (wenn es nur ein Hauptgebäude Eingang).

So niemand weiß, wie es im allgemeinen Fall effizient zu lösen!

Answer 4

Ich denke, das Problem ist einfacher und nicht Steinerbaum oder nicht einmal minimale Spanning Tree.

1. Sie sind Matrix M als Graph G mit V = {Mij | i <= m, j <= n}, E = {(Mi1j1, Mi2j2): i1, i2 <= m, j1, j2 <= n, | i1-i2 | = 1-Exklusiv-ODER | j1-j2 | = 2}

2. Nehmen Sie Satz B Eingänge, Satz H von Hallen

3. H '= H / B, B' = B / H (die Hallen markieren, die Eingänge sind, werden sie in der Tiefe 0 erreicht, sind alle diese Eingänge entfernen, wie jene, Hallen sind)

4. Starten Sie eine Breite-first Traversal. An jeder Tiefe durch die Hallen markieren, die von B erreicht werden kann, bis alle Hallen gekennzeichnet sind. Wählen Sie entsprechende Wege.

Answer 5

Es ist ein Suchproblem. Sie wurden erwartet, es in 2 Stunden zu tun, nicht wahr? Ich würde DFS und prune . Sie könnten Heuristik schneller zu den besseren Lösungen zu erhalten. Aber bedenken Sie Heuristik kann nicht optimale Lösungen garantieren, so dass Sie müssen versuchen, alle Möglichkeiten . Scheint NP-hart.