Ankündigung

Einklappen
Keine Ankündigung bisher.

Das Problem des Handlungsreisenden

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

    #16
    0 c d b f e a 0

    Kommentar


      #17
      Glaube nicht, dass er für ne computergezauberte Lösung 14 pkt kassiert.

      Kommentar


        #18
        ok, hier nochmal ne alternative variante, ohne pc.

        ausgangpunkt is wieder die entfernungsmatrix. durch anwenden des best-neighbourhood verfahren (alternativ: verfahren der sukzessiven einbeziehung) eine erste lösung generieren. die versuchen durch das k-opt verfahren sukzessive zu verbessern. auch wenn dies nur heuristiken sind ist die chance denke ich sehr groß (subjektive einschätzung) bei nur 7 städten die optimale lösung zu erhalten.
        die funktionsweise der verfahren musst du dir schon selber beibringen. ich empfehle dir aber dies an beispielen zu erlernen und nicht an allgemeinen erklärungen.

        Kommentar


          #19
          #4 hat insofern Recht, als dass die Aufgabe per Graphentheorie gelöst werden kann. Die Aufgabe kann aber so nur durch ausprobieren / logisches Denken gelöst werden, da es schwierig wird die Punkte in einen Algorythmus einzugeben. Grundsätzlich funktioniert das ähnlich wie die Algorythmen in Navigationssystemen.

          Kommentar


            #20
            slayer postete
            #4 hat insofern Recht, als dass die Aufgabe per Graphentheorie gelöst werden kann. Die Aufgabe kann aber so nur durch ausprobieren / logisches Denken gelöst werden, da es schwierig wird die Punkte in einen Algorythmus einzugeben. Grundsätzlich funktioniert das ähnlich wie die Algorythmen in Navigationssystemen.
            Bis auf das, was du nur wiederholt hast und das mitm Navi völliger Mist.
            Das einzige was zählt sind die Entfernungen der Punkte untereinander, dann kann man den ganzen Scheiss in jegliche Art von Heuristik/Algorithmus eingeben.

            Kommentar


              #21
              nein der djikstra ist für strecken und nicht für routen!
              für np-schwere probleme ist er nicht geeignet.

              Kommentar


                #22
                Ich hätte da ein Programm in haskell, aber leider keine Lust die Daten einzuhexxen. Sry Bru. :P

                Kommentar


                  #23
                  also nochmal zusammenfassend. wenn du das ernsthaft angehen willst, wirst du an wie in #18 beschrieben nicht vorbeikommen. es gibt außerdem kein rechenverfahren (meines wissens) das zu 100% auf die optimale lösung kommt, außer natürlich alle möglichkeiten auszuprobieren, aber ich hoffe das hast du nich vor ;)

                  Kommentar


                    #24
                    nein hab nicht vor alles auszuprobieren.. :D

                    Kommentar


                      #25
                      Wie er einfach drauft wartet das ihm jemand die Tipparbeit abnimmt anstatt das kurz selber zu machen...

                      Kommentar

                      Lädt...
                      X