matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Hochschulmathe
  Status Uni-Analysis
    Status Reelle Analysis
    Status UKomplx
    Status Uni-Kompl. Analysis
    Status Differentialgl.
    Status Maß/Integrat-Theorie
    Status Funktionalanalysis
    Status Transformationen
    Status UAnaSon
  Status Uni-Lin. Algebra
    Status Abbildungen
    Status ULinAGS
    Status Matrizen
    Status Determinanten
    Status Eigenwerte
    Status Skalarprodukte
    Status Moduln/Vektorraum
    Status Sonstiges
  Status Algebra+Zahlentheo.
    Status Algebra
    Status Zahlentheorie
  Status Diskrete Mathematik
    Status Diskrete Optimierung
    Status Graphentheorie
    Status Operations Research
    Status Relationen
  Status Fachdidaktik
  Status Finanz+Versicherung
    Status Uni-Finanzmathematik
    Status Uni-Versicherungsmat
  Status Logik+Mengenlehre
    Status Logik
    Status Mengenlehre
  Status Numerik
    Status Lin. Gleich.-systeme
    Status Nichtlineare Gleich.
    Status Interpol.+Approx.
    Status Integr.+Differenz.
    Status Eigenwertprobleme
    Status DGL
  Status Uni-Stochastik
    Status Kombinatorik
    Status math. Statistik
    Status Statistik (Anwend.)
    Status stoch. Analysis
    Status stoch. Prozesse
    Status Wahrscheinlichkeitstheorie
  Status Topologie+Geometrie
  Status Uni-Sonstiges

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenOperations ResearchWelcher Algorithmus?
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Operations Research" - Welcher Algorithmus?
Welcher Algorithmus? < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Operations Research"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Welcher Algorithmus?: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

        
Bezug
Welcher Algorithmus?: Antwort
Status: (Antwort) fertig Status 
Datum: 15:00 Di 04.02.2014
Autor: Al-Chwarizmi


> 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 []Travelling Salesman Problem

LG ,   Al-Chw.

  


Bezug
                
Bezug
Welcher Algorithmus?: Frage (überfällig)
Status: (Frage) überfällig Status 
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

Bezug
                        
Bezug
Welcher Algorithmus?: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                        
Bezug
Welcher Algorithmus?: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:20 Do 06.02.2014
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
        
Bezug
Welcher Algorithmus?: Begriffe
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Operations Research"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.unimatheforum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]