Willkommen auf Planet-Liebe

diskutiere über Liebe, Sex und Leidenschaft und werde Teil einer spannenden Community! :)

jetzt registrieren
  • unbekannte
    unbekannte (34)
    Verbringt hier viel Zeit
    298
    113
    20
    Verlobt
    3 Mai 2011
    #1

    längster weg bzw postkutsche programmieren

    Hallo,

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

    [​IMG]

    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
    Gast
    0
    3 Mai 2011
    #2
    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
    unbekannte (34)
    Verbringt hier viel Zeit Themenstarter
    298
    113
    20
    Verlobt
    3 Mai 2011
    #3
    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
    Verbringt hier viel Zeit
    162
    113
    38
    nicht angegeben
    3 Mai 2011
    #4
    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 :grin:
     
  • hellgrau
    Gast
    0
    3 Mai 2011
    #5
    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
    Verbringt hier viel Zeit
    162
    113
    38
    nicht angegeben
    3 Mai 2011
    #6
    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
    Gast
    0
    3 Mai 2011
    #7
    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
    Planet-Liebe-Team
    Moderator
    5.601
    398
    3.434
    Single
    4 Mai 2011
    #8
    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. :smile:

    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. :zwinker:

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

    :winkwink:
     
    • Danke (import) Danke (import) x 1
  • unbekannte
    unbekannte (34)
    Verbringt hier viel Zeit Themenstarter
    298
    113
    20
    Verlobt
    4 Mai 2011
    #9
    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
     
  • User 98295
    User 98295 (28)
    Meistens hier zu finden
    134
    128
    123
    nicht angegeben
    4 Mai 2011
    #10
    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
    unbekannte (34)
    Verbringt hier viel Zeit Themenstarter
    298
    113
    20
    Verlobt
    4 Mai 2011
    #11
    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 :smile2:
     
  • User 98295
    User 98295 (28)
    Meistens hier zu finden
    134
    128
    123
    nicht angegeben
    4 Mai 2011
    #12
    Das ist mir jetzt gar nicht klar. :hmm:

    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
    unbekannte (34)
    Verbringt hier viel Zeit Themenstarter
    298
    113
    20
    Verlobt
    4 Mai 2011
    #13
    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
    Planet-Liebe-Team
    Moderator
    5.601
    398
    3.434
    Single
    4 Mai 2011
    #14
    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... :zwinker:
     
  • unbekannte
    unbekannte (34)
    Verbringt hier viel Zeit Themenstarter
    298
    113
    20
    Verlobt
    4 Mai 2011
    #15
    wenn ich mich ganz groß über das geheime projekt ausdrücke :tongue:

    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
    Gast
    0
    4 Mai 2011
    #16
    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
    Planet-Liebe-Team
    Moderator
    5.601
    398
    3.434
    Single
    5 Mai 2011
    #17
    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...
     

  • jetzt kostenlos registrieren und hier antworten