Welcher Algorithmus? < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:43 Di 04.02.2014 | | Autor: | katil |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo allezusammen,
Ich habe die Aufgabe innerhalb einer Karte(z.B. Goolge Maps) Stationen zu setzen. Von diesen Stationen aus soll jeder Punkt innerhalb der Karte in max. einer halben Stunde zu erreichen sein. Die Anzahl der Stationen soll dabei möglichst gering gehalten werden.
Nun zu meiner Frage:
Gibt es einen Algorithmus der Ansatzweise das kann?
Würde mich freuen, wenn jemand ne idee dazu hätte.
lg
Engin
|
|
| |
|
> Ich habe die Aufgabe innerhalb einer Karte(z.B. Google
> Maps) Stationen zu setzen. Von diesen Stationen aus soll
> jeder Punkt innerhalb der Karte in max. einer halben Stunde
> zu erreichen sein. Die Anzahl der Stationen soll dabei
> möglichst gering gehalten werden.
> Gibt es einen Algorithmus der ansatzweise das kann?
Hallo Engin,
ich denke, dass die Aufgabenstellung präzisiert werden
müsste.
Falls man zum Beispiel mit einem Helikopter unterwegs
ist, der in jede beliebige Richtung mit einer bestimmten
Geschwindigkeit fliegen kann, wird aus der Aufgabe eine
relativ einfache geometrische Aufgabe mit der Lösung,
dass die Stationen die Gitterpunkte einer regelmäßigen
Pflasterung der Ebene aus kongruenten gleichseitigen
Dreiecken sein sollen.
Ich nehme aber an, dass man für die zu befahrenden
Wege nur ein gewisses Straßennetz zur Verfügung hat,
auf dessen Strecken man auch unterschiedliche mittlere
Fahrgeschwindigkeiten einhalten muss. Entsprechende
Algorithmen wurden bestimmt schon entwickelt, sind
aber vermutlich nicht ganz so einfach.
Das Problem gehört im weitesten Sinne in eine Kategorie
mit dem ![[]](/images/popup.gif) Travelling Salesman Problem
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 15:29 Di 04.02.2014 | | Autor: | katil |
Entschuldigt bitte,
deine Annahme ist richtig gewesen, das Strassennetz muss beachtet werden. Den TSP-Algorithmus habe ich mir schon vorher angeschaut. Das Problem ist, dass der TSP-Algorithmus schon von bestehenden Stationen(Lagern) ausgeht. In meinem Fall müssen die Stationen aber erst gesetzt werden. Ich sollte nochmal erwähnen, das Stationen an jedem Punkt auf der Karte gesetzt werden kann. Ich habe mich schon durch einige Operation Research Bücher gekämpft, fand aber leider keinen Ansatz. Würde mich um jede weitere Idee freuen.
lg
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:51 Di 04.02.2014 | | Autor: | felixf |
Moin!
> Entschuldigt bitte,
>
> deine Annahme ist richtig gewesen, das Strassennetz muss
> beachtet werden. Den TSP-Algorithmus habe ich mir schon
> vorher angeschaut. Das Problem ist, dass der
> TSP-Algorithmus schon von bestehenden Stationen(Lagern)
> ausgeht. In meinem Fall müssen die Stationen aber erst
> gesetzt werden. Ich sollte nochmal erwähnen, das Stationen
> an jedem Punkt auf der Karte gesetzt werden kann. Ich habe
> mich schon durch einige Operation Research Bücher
> gekämpft, fand aber leider keinen Ansatz. Würde mich um
> jede weitere Idee freuen.
Ich gehe mal davon aus, dass du nicht eine optimale Loesung suchst, sondern eine "recht gute"?
Ich vermute das Problem eine optimale Loesung zu finden ist NP-schwer (und moeglicherweise nicht in NP, da das Verifizieren einer Loesung ebenfalls schwer ist). Insofern wirst du nur exponentielle Algorithmen finden (also mit einer Laufzeit exponentiell in der Anzahl der Gesamtknoten des Strassennetzes).
Insofern benoetigst du approximative Algorithmen. Ich wuerde das ganze erstmal auf ein (etwas vereinfachtes) Graphenproblem zurueckfuehren. Das Strassennetz kannst du dir als gewichteten Graphen vorstellen (Gewichte = Zeit wie lange man fuer den Strassenabschnitt braucht). Das ganze Problem kannst du jetzt mit dieser Notation ausdruecken.
Du wirst jede Zusammenhangskomponente des Graphes unabhaengig voneinander betrachten koennen/muessen. Nehmen wir also an der Graph ist zusammenhaengend. Du kannst nun recht fix (siehe hier) die Laenge aller kuerzesten Wege bestimmen. Mit diesen kannst du das Problem versuchen anzugreifen.
Du koenntest etwa einen Greedy Algorithm verwenden, der zuerst den Knoten waehlt, dessen 30-Minuten-Radius am meisten andere Knoten abdeckt. Danach entfernst du diese und suchst unter allen Knoten denjenigen, der von den verbleibenden Knoten am meisten abdeckt. Damit faehrst du fort, bis alle Knoten abgedeckt sind. Wie gut/schlecht dieser Algorithmus ist musst du in der Praxis ausprobieren, es kann sein dass er in manchen Faellen katastrophal ist, man ihn in diesen aber verbessern kann indem man z.B. Strassen in kleinere Abschnitte aufteilt bzw. die Aufteilung etwas homogenisiert, so dass die Anzahl der Strassenknoten pro Flaecheneinheit in etwa konstant ist.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Do 06.02.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:58 Do 06.02.2014 | | Autor: | wieschoo |
Deine Aufgabe entspricht in etwa dem Preprocessing
von Single-Sink-Shortest-Path-Problem.
Du kannst dich mal über Quadtrees und Dissections bei TSP erkundigen. Da "baut" man sich ebenfalls ein Gitter.
|
|
|
|
