php-resource



Zurück   PHP-Scripte PHP-Tutorials PHP-Jobs und vieles mehr > Scripts > Apps und PHP Script Gesuche
 

Login

 
eingeloggt bleiben
star Jetzt registrieren   star Passwort vergessen
 

 

 


Apps und PHP Script Gesuche Hier könnt ihr nach PHP Skripten und Programmen fragen. Postet eure Wünsche

Antwort
 
LinkBack Themen-Optionen Thema bewerten
  #1 (permalink)  
Alt 24-11-2006, 12:16
Astralkeks
 Newbie
Links : Onlinestatus : Astralkeks ist offline
Registriert seit: Nov 2006
Beiträge: 2
Astralkeks ist zur Zeit noch ein unbeschriebenes Blatt
Standard kürzeste (Rund-)Reise / nicht TSP

Hallo zusammen,

folgendes Problem stellt sich für mich:

Ich suche einen Algorithmus ähnlich einem, der das Travelling Salesman Problem löst. Nur muß in meiner Anforderung das Ende der Reise nicht mit dem Anfang übereinstimmen, ein kürzester Weg, der alle Orte (gegeben mit x,y-Koordinaten) besucht, und bei einem gegebenen (festen) Startpunkt beginnt, reicht.

Optimal wäre für mich (falls jemand dieses Problem bereits gelöst hat) ein realisierter Algorithmus in PHP. Ein nicht ausprogrammierter Algorithmus würde mir sicher auch weiterhelfen!

Gruß
Astralkeks
Mit Zitat antworten
  #2 (permalink)  
Alt 24-11-2006, 12:18
penizillin
 PHP Guru
Links : Onlinestatus : penizillin ist offline
Registriert seit: Feb 2004
Beiträge: 10.166
penizillin ist zur Zeit noch ein unbeschriebenes Blatt
Standard

meinst du vielleicht das mst-problem?
http://en.wikipedia.org/wiki/Minimum_spanning_tree
Mit Zitat antworten
  #3 (permalink)  
Alt 24-11-2006, 12:35
Astralkeks
 Newbie
Links : Onlinestatus : Astralkeks ist offline
Registriert seit: Nov 2006
Beiträge: 2
Astralkeks ist zur Zeit noch ein unbeschriebenes Blatt
Standard

Nein, denn das bildet keine günstige Reise ab, nur einen Spannbaum (wie der name schon sagt).
Ich suche die Lösung für Probleme wie:
Ich wohne in Hamburg, und möchte die Städte Dortmund, Berlin, Bonn, Stuttgart und München besuchen und möglichst wenig Spirit verfahren.
Das MST ist da ungeeignet.
Edit:
Um Missverständnisse zu vermeiden: Die Rückreise nach Hamburg ist unerheblich dabei (sonst wäre es ja wieder TSP)

Geändert von Astralkeks (24-11-2006 um 12:38 Uhr)
Mit Zitat antworten
  #4 (permalink)  
Alt 27-11-2006, 14:49
penizillin
 PHP Guru
Links : Onlinestatus : penizillin ist offline
Registriert seit: Feb 2004
Beiträge: 10.166
penizillin ist zur Zeit noch ein unbeschriebenes Blatt
Standard

dann nimm doch tsp und schmeiß die letzte kante ("nach hamburg zurück") einfach weg. dadurch wirst du nicht unbedingt _die_ kürzeste reise, aber _eine der_ kürzesten erwischen.
Mit Zitat antworten
  #5 (permalink)  
Alt 27-11-2006, 20:22
Marcusson
 Registrierter Benutzer
Links : Onlinestatus : Marcusson ist offline
Registriert seit: Jan 2006
Beiträge: 241
Marcusson ist zur Zeit noch ein unbeschriebenes Blatt
Standard

Genau _DIE_ kürzeste Reise kriegst du sowieso nicht, denn TSP ist AFAIK NP-vollständig. Eventuell bekommst du aber eine gute Näherung.
Mit Zitat antworten
  #6 (permalink)  
Alt 27-11-2006, 21:28
TobiaZ
  Moderator
Links : Onlinestatus : TobiaZ ist offline
Registriert seit: Jan 2001
Ort: MUC und MGL, Germany
Beiträge: 34.421
Blog-Einträge: 1
TobiaZ befindet sich auf einem aufstrebenden Ast
Standard

naja, das ganze geht ziemlich in diese Richtung allerdings musst du da noch die tatsächliche entfernung in Metern(?) mit reinbringen.
__________________
ERST LESEN: Unsere Regeln. | Ich hab schon Pferde kotzen sehn!

READ THIS: Strings richtig trennen/verbinden | JOINs, das leidige Thema | Wegwerf E-Mail Adressen

Ich werde keinen privaten 1:1 Support leisten, außer ich biete ihn ausdrücklich an.

Wenn man sich selbst als "Noob" bezeichnet, sollte man die Finger davon lassen.
Wenn man gewillt ist daran etwas zu ändern, lernt man Grundlagen!
Mit Zitat antworten
  #7 (permalink)  
Alt 27-11-2006, 22:10
Benutzerbild von onemorenerd onemorenerd
  Moderator
Links : Onlinestatus : onemorenerd ist offline
Registriert seit: Mar 2005
Ort: Berlin
Beiträge: 9.471
onemorenerd wird schon bald berühmt werdenonemorenerd wird schon bald berühmt werden
Standard

Ich kenne TSP als "nur" NP-hart, erst die Fragestellung "Gibt es eine Route, die kürzer ist als x?" ist -vollständig.

Und TSP wird normalerweise greedy implementiert, also mit einem Algorithmus, der in jedem Schritt das Optimum wählt, in der Annahme, dass das globale Optimum in der Nähe der Folge aller lokalen Optima liegt. Selbst wenn man das Lokalitätsprinzip etwas aufbohrt, in dem man das Optimum innerhalb eines Fensters der letzten x Kanten sucht - was die Komplexität direkt beeinflusst - bleibt es ein Greedy-Algorithmus.
Erst wenn das Fenster so groß ist wie der kürzeste Weg ist das lokale Optimum innerhalb des Fensters gleich dem globalen Optimum. Die dadurch gegebene Komplexität will man aber sicher nicht in Kauf nehmen.

Deshalb kann man nicht einfach TSP laufen lassen und am Ende die Rückreise zum Ausgangspunkt streichen. Denn dieser letzte Weg geht in den zu findenden kürzesten Pfad mit ein. Streicht man ihn einfach raus, ist der verbliebene Weg nicht mehr notwendigerweise der kürzeste.


Vielleicht wirds anhand eines Beispiels verständlicher:

Seien A, B, C, D Knoten mit folgenden Entfernungen:
A -> B = 1
A -> C = 2
A -> D = 3
B -> C = 4
B -> D = 3
C -> D = 6
Wir starten in A.
Die möglichen Rundreisen und ihre Längen sind:
A-B-C-D-A = 1-4-6-3 = 14
A-B-D-C-A = 1-3-6-2 = 12
A-C-B-D-A = 2-4-3-3 = 12
A-C-D-B-A = 2-6-3-1 = 12
A-D-B-C-A = 3-3-4-2 = 12
A-D-C-B-A = 3-6-4-1 = 14
Ein greedy TSP-Algorthmus hätte A-B-D-C-A als Lösung angegeben, was sogar tatsächlich eine der optimalen Lösungen ist. Aber läßt man von dieser Lösung den Rückweg C-A einfach untern Tisch fallen, bleibt A-B-D-C übrig. Das ist allerdings keine optimale Lösung mehr! Denn A-C-B-D und auch A-D-B-C wären kürzer (9).

Das war sicher mühselig zu lesen, aber hoffentlich leicht zu verstehen. Man kann nicht einfach eine TSP-Lösung ändern und behaupten, es wäre immernoch eine Lösung!

Das läßt sich auf die Unzulänglichkeit von Greedy für TSP reduzieren und beweist, dass Greedy für o.g. Problem nicht garantiert optimale Lösungen liefert. Wer hätte das gedacht...


@TO: Google mal nach AHOP, vielleicht hilfts weiter.

Geändert von onemorenerd (27-11-2006 um 22:20 Uhr)
Mit Zitat antworten
  #8 (permalink)  
Alt 02-12-2006, 02:58
penizillin
 PHP Guru
Links : Onlinestatus : penizillin ist offline
Registriert seit: Feb 2004
Beiträge: 10.166
penizillin ist zur Zeit noch ein unbeschriebenes Blatt
Standard

Marcusson: die zugehörigkeit zur klasse der NP-vollständigen sagt nichts über die lösbarkeit aus. triviales beispiel: ein graph mit zwei knoten und einer kante dazwischen.

onemorenerd: vollkommen richtig. was ich mir überlegt hatte, war der bezug zu einer realen aufgabe. wenn es tatsächlich um (groß-)städte in deutschland geht, betrachten wir 2 möglichkeiten für die letzte kante:

- letzte kante sehr lang (vielleicht 600 km)
da diese in der (angenäherten) lösung eines tsp-problems vorkam, wird sie höchstwahrscheinlich nicht umzugehen sein (beispiel: jemand kommt aus rostock und muss 15 orte in südbayern besuchen)

- letzte kante sehr kurz (z.b. wenige km)
ich starte z.b. in köln, fahre durch alle neuen bundesländer und der vorletzte knoten ist bonn. ob ich nach bonn oder nach köln zurückkomme, wird die "optimalität" der lösung minimal beeinflussen.

offensichtlich liegt die schwäche dieser überlegung in den mittellangen strecken... mit sicherheit lassen sich graphen konstruieren, deren rundreise sich dramatisch verändert, wenn man die letzte kante weglässt.
Mit Zitat antworten
Antwort

Lesezeichen


Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)
 

Themen-Optionen
Thema bewerten
Thema bewerten:

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are an


PHP News

ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlicht
ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlichtDie bekannte Marktplatzsoftware ebiz-trader ist in der Version 7.5.0 veröffentlicht worden.

28.05.2018 | Berni

Wissensbestand in Unternehmen
Wissensbestand in UnternehmenLebenslanges Lernen und Weiterbilden sichert Wissensbestand in Unternehmen

25.05.2018 | Berni


 

Aktuelle PHP Scripte

PHP Server Monitor

PHP Server Monitor ist ein Skript, das prüft, ob Ihre Websites und Server betriebsbereit sind.

11.09.2018 Berni | Kategorie: PHP/ Security
PHP WEB STATISTIK ansehen PHP WEB STATISTIK

Die PHP Web Statistik bietet Ihnen ein einfach zu konfigurierendes Script zur Aufzeichnung und grafischen und textuellen Auswertung der Besuchern Ihrer Webseite. Folgende zeitlichen Module sind verfügbar: Jahr, Monat, Tag, Wochentag, Stunde Folgende son

28.08.2018 phpwebstat | Kategorie: PHP/ Counter
Affilinator - Affilinet XML Produktlisten Skript

Die Affilinator Affilinet XML Edition ist ein vollautomatisches Skript zum einlesen und darstellen der Affili.net (Partnerprogramm Netzwerk) Produktlisten und Produktdaten. Im Grunde gibt der Webmaster seine Affilinet PartnerID ein und hat dann unmittelb

27.08.2018 freefrank@ | Kategorie: PHP/ Partnerprogramme
 Alle PHP Scripte anzeigen

Alle Zeitangaben in WEZ +2. Es ist jetzt 05:12 Uhr.