Ankündigung

Einklappen
Keine Ankündigung bisher.

Das Problem des Handlungsreisenden

Einklappen
X
 
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

    Das Problem des Handlungsreisenden

    Schönen Abend Elite,

    ein mathematisches Problem an dieser Stelle...
    Versprochen wurden 14 Pkt bei Findung des kürzesten Weges...

    Google spuckt einiges aus, aber wollte die Elite mal mit einbeziehen...

    http://www.michael-unibonn.de/weg.jpg

    Auf dem Link findet ihr die Aufgabe...


    #2
    720 Möglichkeiten, hf..

    ich tippe

    AEFCDB ist am schnellsten bzw kürzesten.bzw der rückweg halt.
    weil das dann nahezu ein dreieck ist. und am wenigsten weg verschwendet wird. kann mich aber auch täuschen. nur so vom gefühl her.

    Kommentar


      #3
      Ich hab auf 0-F-C-D-B-E-A-0 bzw. 0-F-E-C-D-B-A-0 getippt.. aber kb zu rechnen.. da er jedem mit richtiger lösung 14 pkt versprochen hat vermute ich ist es unwahrscheinlich diese zu finden...

      Kommentar


        #4
        schnellster Weg durch gewichteten Graph

        http://de.wikipedia.org/wiki/Dijkstra-Algorithmus

        /e: Aufgabe falsch verstanden.

        Kommentar


          #5
          720 möglichkeiten. wird eine geben, die die beste ist. hf beim rechnen.

          Kommentar


            #6
            Schreib dir erstma die verbindungsvektoren auf und berechne die Länge, dann isses übersichtlicher, brauchst du ja sowieso um jedwaige Art von Algorithmus anzuwenden

            noobhans postete
            schnellster Weg durch gewichteten Graph

            http://de.wikipedia.org/wiki/Dijkstra-Algorithmus

            /e: Aufgabe falsch verstanden.
            Ist glaub ich falsch, du suchst den kürzesten Weg von A nach B, gesucht ist aber die Beste Route, alle Nodes zu besuchen.

            Kommentar


              #7
              erstelle/berechne ne tabelle wo alle entfernungen zueinander abgetragen sind. dann halt irgend ne heuristik anwenden. musste mal gucken ob es eine gibt die immer optimum liefert. hf

              edith glaubt das die best-neighbourhood methode am einfachste/effizientesten ist. nachteil is aller dings das sie glaube nich zwangsweise das optimum liefert. um optimum zu erreichen kommst du glaube um computergestützes rechnen nicht herum. wenn du die tabbelle erstell hast wie oben beschrieben, kannste ma googeln vllt gibs dafür sogar nen mathe tool um die tabelle dann einzugeben und ausrechnen zu lassen.

              p.s. : grüße an deinen lehrer den alten hochstapler. nur weil er ein bisschen OR kann brauch er nich gleich mit 14 puinkten um sich schmeißen ;)

              Kommentar


                #8
                mh danke bis hierhin schonmal :D

                werds ihm ausrichten b1rdman

                Kommentar


                  #9
                  Such einfach nach nem TSP Solver :D

                  http://students.ceid.upatras.gr/~miatidis/index.htm

                  Da der funzt... mach einfach 6 Vertices, das sind Start + A-F
                  Dann mach Random values, Save das File, gib in der Datei, wie quasi die tabelle enthält die Werte ein für die Entfernungen.

                  Die Tabelle ist quasi ne Matrix

                  A B C
                  A (entf A-A) (entf A-B) (entf A-C)
                  B (entf B-A) usw.
                  C

                  Musst halt auf der Diagonalen des -1 dastehen lassen und das du nur die Werte über bzw. unter der Diagonalen berechnen musst und dann spiegeln kannst ist ja klar.

                  Die kannste dann laden und dann go :D is 15 * Wurzel aus (x²+y²)

                  14 pts win!

                  Obwohl ich da noch nicht wirklich seh, was denn nu das Ergebniss ist :D

                  Ah Häkchen bei connected noch anmachen und dann auf Start

                  Kommentar


                    #10
                    auf wiki sind doch Lösungswege beschrieben

                    wiki meint:
                    Die Minimum-Spanning-Tree-Heuristik (MST) berechnet zunächst einen minimal aufspannenden Baum, also einen Graphen, in dem alle Punkte miteinander verbunden sind und der minimale Länge besitzt. Davon ausgehend wird eine Tour konstruiert, indem zunächst alle Baumkanten verdoppelt werden und danach eine „Eulertour“ in dem entstandenen eulerschen Graphen gesucht wird. Diese wird zuletzt durch direkte Kanten abgekürzt, falls Knoten doppelt besucht werden. Im Falle eines metrischen TSP kann man zeigen, dass die so konstruierte Tour höchstens doppelt so lang ist wie eine kürzeste Tour.
                    Kannst erstmal den minimalen Spannbaum aufstellen
                    http://de.wikipedia.org/wiki/Algorithmus_von_Kruskal
                    hier mit Beispiel, ist recht einfach und sieht für deinen Lehrer auch toll aus. Kantengewichte sind einfach die Vektorenlängen

                    Dann wie beschrieben alles verdoppeln und Eulertour durchführen, der Algorithmus dazu ist einfach und auch bei wiki zu finden. Kannst du alles schön aufmalen. 14 pkt inc.

                    Kommentar


                      #11
                      ok...die punkte hab ich jetz verbunden...aber was zum teufel sind vektoren und was haben die da zu suchen?

                      Kommentar


                        #12
                        genau wie #9 beschrieben hat meinte ich es auch. musst halt die entfernungsmatrix/tabelle aufstellen und dann computergestützt weitermachen, also wie schon gesagt nach nem tsp solver im inet suchen.

                        achso in der diagonalen muss natürlich 0 stehen und nich -1.

                        Kommentar


                          #13
                          DoppelToni postete
                          ok...die punkte hab ich jetz verbunden...aber was zum teufel sind vektoren und was haben die da zu suchen?

                          :D:D ich glab dir das zu erklären würde jetzt zu weit ausholen ^^

                          Kommentar


                            #14
                            Naja das mit der -1 ist halt theoretisch auch implementierungsabhängig, hab den halt mal n random Graph erzeugen lassen und dann in ne Textdatei exportiert, da hatte der überall -1 statt 0...
                            Hab bei dem Programm halt keine Möglichkeit gefunden die Werte direkt einzugeben, muss immer über die .txt gehen irgendwie

                            Kommentar


                              #15
                              14 Punkte nur??? das würde meinen tollen 15,0 schnitt ja runterziehen *hihi*

                              Kommentar

                              Lädt...
                              X