längster weg bzw postkutsche programmieren

unbekannte · 3 Mai 2011

Hallo,

ich habe keine große Ahnung vom programieren möchte aber etwas entwickeln. Ich hab zur veranschaulichung mal in Excel was gestaltet

Rechts ist ein Wegnetz mit Bewertung angezeigt. Dieses habe ich links in den Gruppen dargestellt und die einzelnen Stufen farblich markiert.

Ziel ist es die größte (eigentlich kürzeste bzw niedrigst bewerteste) Strecke rauszugeben

Ich hab das wie schriftlich durchgerechnet indem ich die größten Teilschritte zum weiterrechnen benutzt habe,

Nun möchte ich aber ein Excelsheet haben wo ich das weitestgehend allgemein halten kann und es automatisiert abläuft und auch die einzelnen Teilschritte anzeigt.

Also sollte man die einzelnen Stufen variieren können so das auf jeder Stufe zb 1 oder auch 150 Stationen sein können. Auch die bewertungen also die Weggrößen sollten für alle Strecken variabel sein.

Wie kann man das als "Laie" gut durchsetzen oder gibt es evtl schon etwas was in diese richtung geht?

für tipps wär ich dankbar

der Unbekannte :jaa:

hellgrau · 3 Mai 2011

Beschreib die Aufgabe bitte nochmal etwas genauer.
Je nach dem, ist das entweder nur eine Frage von Excelfähigkeiten, oder aber (was ich vermute) Teil der schwierigsten/aufwändigsten Aufgaben die wir kennen.

unbekannte · 3 Mai 2011

Das Beispiel ist ein Postkutschenbeispiel

Typ will von A nach J und muss 3 mal irgendwo übernachten

welchen weg soll er nehmen um am meistne geld zu sparen oder respektiv was hat die höchste genauigkeit

die berechnung sagt wieviel die zwischenschritte kosten und sagt aus dass ein großer teilwert auch ein großer wert ist

am ende möchte ich versuchen das so zu gestalten das ich sagen kann es gibt evtl in stufe 2 zehn mögliche ziele mit jeweiligen bewertungen

da das irgendwann einen großen aufwand hat würd ich gerne die berechnung dann automatisieren und dann auslesen lassen das die kürzesten stationen von x nach y über z zu a war

ist das verständlicher?

Scavenger · 3 Mai 2011

Da ich keine Zyklen sehe und es so wenige Teilschritte sind würde ich das einfach mittels Rekursion machen. (VBA)
Sieht im Prinzip aus wie beim Routing was die Metriken angeht

hellgrau · 3 Mai 2011

Nein, wirklich klar ist es mir noch nicht.
Einer der Klassiker für die Berechnung kürzester Pfade ist
A*-Algorithmus ? Wikipedia
Den wirst Du so in Excel nicht unterbringen. Als Basic-Programm geht es. Vielleicht findest Du da etwas Fertiges, dass Du benutzen kannst.
Wie gut der skaliert, also wie schnell das bei 150 Stationen in Excel noch ist, kann ich nicht schätzen.

Vielleicht kannst Du Deine Aufgabe aber auch noch weiter eingrenzen und aus zusätzlichen Eigenschaften ein simpleres Verfahren ableiten.

Scavenger · 3 Mai 2011

A* wäre mit Kanonen auf Spatzen geschossen wenn ich mir den Beispiel Graphen anschaue. Eine einfache Rekursion ist zwar nicht so performant, aber dafür sehr viel einfacher und schneller zu implementieren. Was die Laufzeit angeht würde ich in etwa einen Sekunden Bruchteil schätzen.

hellgrau · 3 Mai 2011

Ich würde nicht sagen, dass der A* programmatisch komplexer ist. Und von der Laufzeit her ist er auch besser. Das kann bei 150 Stationen schon mal interessant werden, falls die Wege dann auch länger werden.
Aber da will ich mich nicht drüber streiten.

Was genau würdeset Du da rekursiv machen? Ein volles Backtracking, um sämtliche Pfade zu durchlaufen?

Fuchs · 4 Mai 2011

Hallo!

Kannst du dein Problem auch als Maximierungsproblem formulieren?

Sprich: Die Kutsche will in deinem Graphen von A nach J fahren und dabei möglichst viel Wert auf den einzelnen Wegen einsammeln?

Falls ja, hast du ein klassisches Problem der theoretischen Informatik: Das Max-flow-problem! Glücklicherweise ein Problem, was sich verhältnismäßig einfach und sogar effizient lösen lässt. Als Algorithmus würde ich den Algorithmus von Ford und Fulkerson empfehlen, da dieser sehr anschaulich und für einen Laien wohl noch am einfachsten zu programmieren wäre.

Falls du das zwangsläufig in Excel machen möchtest, wirst du mittels VBA ein Makro schreiben müssen. Ich halte das aber für möglich.

Ansonsten könnte eine Recherche über Flussprobleme helfen. Da das Problem wirklich sehr sehr klassisch ist, vermute ich, dass es irgendwo in den Weiten des Webs ein paar Applets gibt, welche dir erlauben dein Netzwerk zusammenzuklicken und dann den maximalen Fluss (resp. den Min cut) zu berechnen.

Nähere Infos zu Flussproblemen findest du bspw. hier: Flüsse und Schnitte in Netzwerken ? Wikipedia

:winkwink:

unbekannte · 4 Mai 2011

Wie gesagt geht es darum den längsten Weg mit verschiedenen möglichen Zwischenschritten zu kennen.

@ Fuchs ich hab mir das mal angesehen bin aber nicht sicher wie ich das anwenden kann

ich hab heute den dijkstra gefunden und denke das passt von der sache her. man müsste nur 100-X nehmen um aus den kleinsten die größten werte zu machen

ich frag mich nur ob es dafür evtl eine excel add in datei gibt?! weiß da jemand mehr?

oder gibt es beim ford und fulkerson evtl ein add in für excel das nach definierten knoten kanten und bewertungen funktioniert

Comparator · 4 Mai 2011

unbekannte schrieb:
ich hab heute den dijkstra gefunden und denke das passt von der sache her. man müsste nur 100-X nehmen um aus den kleinsten die größten werte zu machen

Das Erste, was mir bei dem Excelsheet einfiel, war der von dir angesprochene Dijkstra, ein klassischer Fall in der Graphentheorie.

Dieser ist relativ einfach zu implementieren, allerdings wirds dafür kein Excel-Add-In geben.

Von der Komplexität her ist der A* besser (logisch, eine Verbesserung von Dijjkstra) (O(abs(n)*log(abs(n))) als Dijkstra (O(n*log(n) + m)), aber wie oben schon geschrieben, ein bisschen oversized für das Problem hier.

Allerdings - wenn dein Problem wirklich das ist, den längsten Weg zu kennen (Sinn?), dann ist der von Fuchs vorgeschlagene Algorithmus die bessere Lösung - schon allein deswegen, weil A*/Dijkstra den kürzesten Weg suchen...

unbekannte · 4 Mai 2011

ich will die wege nach wahrscheinlichkeit in prozent bewerten. und hohe wahrscheinlichkeit ist natürlich besser als kleine

aber ich könnte ja ggf 100%-XX rechnen und nach kleinsten suchen

das müsste funktionieren

gibts bei dem von fuchs etwas wie ein add in? das wäre sehr fein finde ich

Comparator · 4 Mai 2011

unbekannte schrieb:
ich will die wege nach wahrscheinlichkeit in prozent bewerten. und hohe wahrscheinlichkeit ist natürlich besser als kleine

Das ist mir jetzt gar nicht klar.

Die Wahrscheinlichkeit ist bei einem kürzeren Weg doch größer? Der Weg von Berlin nach Potsdam über Dresden, Münschen, Stuttgart, Köln und Hamburg hat ziemlich genau die Wahrscheinlichkeit 0%?

unbekannte · 4 Mai 2011

es geht nicht um die wahrscheinlichkeit das der weg kurz ist sondern darum wie warscheinlich es ist das man als bestimmte person diesen weg nimmt

also zb geht milliardär zuerst zum schmuckladen im kaufhaus dann ins restaurant und dann zum parkhaus mit einer anderen wahrscheinlichkeit geht er erst zur bank dann zum schuhmacher und dann zum parkhaus

start das kaufhaus und ziel das parkhaus sind gleich und die wege dazwischen werden anhand der wahrscheinlichkeit gemessen

Fuchs · 4 Mai 2011

Es ist irgendwie schwierig dir zu helfen, wenn du dein Problem nur so vage beschreibst.

Zudem sehe ich in deinem Beispiel keine Wahrscheinlichkeiten. Grob gesprochen ist eine Wahrscheinlichkeit eine Zahl zwischen 0 und 1...

Zudem musst du klar unterscheiden, ob dich "der wahrscheinlichste" Weg in deinem Netzwerk interessiert (das wäre dann eher soetwas wie der Erwartungswert der Kosten/Gewinne über alle Wege) oder halt derjenige mit dem maximalen "Gewinn" sozusagen. Das sind verschiedene Dinge.

Ich wäre auch vorsichtig damit, die Werte 100% - X zu rechnen um aus einem Maximierungs- ein Minimierungsproblem zu machen. Unter Umständen kann das ins Auge gehen, gerade bei so kürzesten Weg-geschichten. Der Dijkstra-Algorithmus kann bspw. nicht so abgeändert werden, dass man mit ihm auch längste Wege finden kann, dafür verbürge ich mich.

edit: Das Finden eines längsten Weges in allgemeinen Graphen ist NP-vollständig, was in etwa so viel heißt wie das keine effizienten Algorithmen für die Lösung des Problemes bekannt sind. Ich hoffe für dich also nicht, dass du im großen Stil nach längsten Wegen suchen willst...

unbekannte · 4 Mai 2011

wenn ich mich ganz groß über das geheime projekt ausdrücke

ich soll menschen von ihren prozessen verfolgen

die prozesse sind fix und die reihenfolge auch allerdings ist je nach ort die anzahl oder der umfang unterschiedlich

verschiedene personengruppen nutzen aber verschiedene arten von diesen prozessen

meine aufgabe ist es abzuleiten, nachdem ich weis eine person ist diesen weg gegangen und daher personengruppe xy, dann wird diese person weiter so und so laufen mit einer wahrscheinlichkeit z

ich hab jetzt die prozessstationen als knoten genommen und die möglichen richtungen als kanten

die bewertungen sind die wahrscheinlichkeiten das man nach dem einen prozess den anderen nutzt in zusammenhang mit der personengruppe

meine idee ist halt das ich sage das die person am wahrscheinlichsten den weg mit der größten bewertung läuft

startpunkt ist der punkt an dem man die person zuletzt gesehen hat

zielpunkt ist zb ausgang

dadurch das die stationen von fall zu fall verschieden sind wollte ich auch variable möglichkeiten in der erarbeitung des programms haben

hab beim dijksta wikipedia gesehen wie das programm läuft anhand des beispiels suche kürzesten weg zwischen frankfurt und münchen über stationen x,y,z,...

von der berechnung müsste das doch klappen

außerdem sollte dieser ja so verbreitet sein, dass ich dachte dazu gibt es ein excel add in, so das man nur noch die knoten, kanten und bewertungen eingibt (in einer gewissen reihenfolge zur visualisierung) um sie dann auslesen zu lassen und einen wert präsentiert zu bekommen

ob das dann funktioniert muss sich dann ja rausstellen aber da ich keinerlei programierkenntnisse habe außer excelbefehle in den kästchen suche ich deswegen halt auch einfache und leicht anwendbare möglichkeiten der umsetzung

aber danke für die disskussion zur aufgabe

hellgrau · 4 Mai 2011

Es gibt immer zwei Möglichkeiten. Entweder Du legst die Karten auf den Tisch und erklärst jemandem, der sich mit den Verfahren auskennt, was Du genau erreichen willst,
oder Du schaffst Dir das KnowHow selbst drauf.
Aus Angst vor "Spionage und Kopien" eine Idee nur ungenau zu erklären, bei der man von der Materie selbst nur wenig Ahnung hat, funktioniert so gut wie nie.
Das was Du jetzt beschrieben hast, klingt schon wieder nach mehreren anderen Problemen und schneidet Themen wie "branch prediction", oder automatisiertes Lernen mit z.B. neuronalen Netzen, Klassifikation, Expertensysteme ...
Vielleicht machst Du erstmal für Dich weiter und wenn eine konkretere Problemstellung auftaucht, fragst Du nach.
Dann kann man Dir vielleicht auch ein paar Adressen nennen, wo Du damit besser aufgehoben bist.

Fuchs · 5 Mai 2011

Ich werde aus deiner Problembeschreibung leider auch nicht schlau, habe aber das Gefühl, dass es dein Problem (egal, wie es jetzt genau aussieht) bereits vor mindestens 20 Jahren gab und es gelöst wurde.

Auch wenn Excel mehr kann, als viele Leute meinen, wird dir Excel allein nie einen Algorithmus ausrechnen, selbst wenn er so simpel wie Dijkstra ist. Allerdings kannst du innerhalb von Excel Makros schreiben (in der Programmiersprache VBA), welche dir das dann ausrechnen und dir auch deine Tabelle füllen können.

Ich vermute aber, dass du da nicht drumrum kommen wirst, denn ich fände es schon eigenartig, wenn es sowas bereits als Add-on (Add-in???) geben würde (vermutlich ist da wenig Bedarf nach).

Was es aber massenweise gibt sind applets für Flussnetzwerke, Wegprobleme oder diesen ganzen anderen Krempel von dem man nicht weiß, was du da eigentlich machst. Da kannst du dir auf webseiten dann deine Graphen zusammenklicken, auf "Start" drücken, der Algorithmus rattert drüber und gibt dir dein Ergebnis.

Nur dafür müsste man halt wissen, was du überhaupt willst...