Hallo, ich habe einen Bohrtisch mit Motoren für.X Y. Bekannt sind die zu bohrenden Positionen. (x1,y1) (x2,y2) (x3,y3) ...... In welcher Reihenfolge sollen nun die Bohrungen ausgeführt werden, damit ein möglichst kurzer Weg mit dem XY-Tisch zu fahren ist. Wie kann die Reihenfolge der Punkte berechnet werden? Gruß Franz
Schau dir Verfahren an die Autorouter verwenden. z.b. Um Position XY werden Einsen gezeichnet um die Einsen dann zweier usw. erreicht eine Zahl Position X2Y2 wird eine Verbinung gezogen. Es gibt aber X verschiedene, die hab ich aus der Vorlesung nur behalten weil es eine simple war <fg>
hm theoretisch is ja beim Bohen nix im Weg. Warum nicht einfach die Differenz aus den positionen nehmen und los Bohren ?
Das lässt sich auf das traveling salesman Problem zurückführen, schau dir Lösungen dazu an.
lol, die Lösung zu Travaling Salesman^^ nun ja für ein Mikrokontroller einwenig viel Rechnerei, wenn die Anzahl der Löcher 8 übersteigt. Mach es dir nicht übermässig kompliziert. Ich würde erstmal die Platine in Bereiche aufspalten, sodass in einem Bereich 5-8 Löcher sind und mit dann über Permutation aller Wege die absolut günstiste Lösung nehmen. Solange Bohrer läuft, können andere Bereiche berechnet werden.
<g> Er hat aber auch nicht gesagt das ein Mikrocontroller alles berechnen soll.
Daniel wrote: > lol, die Lösung zu Travaling Salesman^^ > nun ja für ein Mikrokontroller einwenig viel Rechnerei, > wenn die Anzahl der Löcher 8 übersteigt. Quatsch. Das kommt auf den Algorithmus an. Außerdem muss ja die Reihenfolge der Punkte nur einmal vorm Bohren festgelegt werden und nicht zum Beispiel 1000 mal pro Sekunde. Ich bin mir sicher, dass es auch vor 30 Jahren schon Bohrtische gab, die haben auch funktioniert.
Das von I_ H. genannte "traveling salesman Problem" ist zwar nicht optimal lösbar (sog. NP-Problem, d.h. exp. Berechnungsaufwand), aber ein guter Hinweis zur Internetsuche. In vielen Büchern zum Thema Algorithmentechnik gibt's brauchbare Lösungen in Form von Heuristiken. Such aber einfach mal im Internet (Stichworte "Traveling..." + evtl. "Bohren", vieleicht in Wikipedia. Gruss Jörg
Wikipedia sagt, dass heutzutage auch exakte Methoden dafür zur Verfügung stehen.
Alle Verfahren zu diesem Problem sind exakt (d.h. alle Löcher abfahren), aber eben nicht optimal. Für einen uC-Einsatz bleibt bei vielen Löchern nur eine Heuristik, da gibt's aber genug brauchbare (auc für uC's). Gruss Jörg
Legt man die Bohr-Reihenfolge nicht bereits auf dem PC beim Erstellen der Bohrdatei fest?
so eine Aufspaltung in Bereiche wäre zum Beispiel auch eine Heuristik. Es könnte sich dabei die kürzeste Gesamtstrecke ergeben, muss es allerdings nicht. (und die Wahrscheinlichkeit dafür ist ehrlich gesagt auch sehr sehr klein) Das ist ein NP Problem => Globales Optimum nur durch Durchprobieren aller Wege! Und das läuft auf die Permutation hinaus. Letztes Endes braucht man keine Optimale Lösung das war das was ich oben sagen wollte. Auch starke CPU würde nicht mehr als 15 Punkte schaffen. So unglaublich das klingen mag. Grüsse
Mit ein paar Optimierungen schaffen starke CPUs deutlich mehr als 15 Löcher. 15! ist eine Größenordnung die man mit modernen CPUs durchaus bearbeiten kann, das sind gerade mal 1.3Mrd Kombinationen.
Also bei 15 Bohrungen kommt man schon auf 1.3 Billionen Kombinationen. Jede muss dann noch untersucht werden, also viel zu aufwendig (selbst für einen schnellen PC); und falls doch, kann man ja 20 Löcher als (noch relativ kleines) Problem nehmen: dann sind es 2.4 Trillionen, d.h. sehr/zu langes Rechnen (beim Platinenlöcherbohren sind's aber viel mehr als 20 Löcher). Einfacher Ansatz: Im ersten Schritt wird die Liste der Bohrlöcher als einfacher Weg interpretiert (ein sogenanter Graph). Im nächsten Schritt wird aus diesem Graph ein sog. Minimaler Spannender Graph (MST) berechnet (z.B. Kruskal- oder Prim-Algorithmus, Aufwand O(V log V ) mit V = #Bohrungen). Im Dritten Schritt wird dann aus dem MST ein einfacher Durchlauf bestimmt. Der Durchlaufaufwand dieser Heuristik ist maximal doppelt so lange wie der optimale Pfad (der ist aber mit praktisch unendlichem Rechenaufwand bestimmbar). Dieses Verfahren läuft selbst auf uCs akzeptabel schnell. Gruss Jörg
Also ich hab auf die schnelle jetzt mal was zusammengeschrieben, das für 15 (zufällig angeordnete) Löcher 11 Sekunden rechnet... mit wirklich einfachstem backtracking (wurde schon eine Lösung kürzer als der aktuelle Stand gefunden, brich ab).
So, nu dauerts nur noch 1.7 Sekunden. Und mir sind noch einige brauchbare Sachen eingefallen, mit denen man's noch schneller bekommt.
Nu dauert's noch 0.5 Sekunden, für 17 Punkte braucht er 5.5 Sekunden (vorher ~35). Und ich seh immernoch eher das was ich noch nicht umgesetzt hab, als das was ich umgesetzt hab. Also 15 Punkte sind wirklich kein Problem, wenn man mit Verstand rangeht.
Also für 15 Bohrlöcher bekommt man ca. 1.3 Billionen Kombinationen. Die optimale(n) (es kann mehrere geben!!) rauszufinden heisst, alle Möglichkeiten zu untersuchen und und die (bzw. eine) minimale Lösung auszuwählen. Um die 1.3 Billionen (15 Fakultät) kommt man dabei nicht rum, sonst hätte man ja NP = P, was zu bezweifeln ist. Du hast sicherlich eine gute Lösung gefunden, aber ob das (rein zufällig) das Optimum ist, lässt sich allgemein nicht rausfinden. Der von mir oder der von Daniel vorgeschlagene Ansatz lieft ebenfalls gute und brauchbare Lösungen. @I_ H. Kannst du mal den Code posten? Gruss Jörg
Es ist zu 100% das Optimum - es gibt keine bessere Variante. Das liegt daran, dass der Algorithmus effektiv (!) alle Varianten betrachtet hat. Für 20 hat er übrigens 1m45s gebracht. Ich bin aber noch am Verbessern.
Das kann unmöglich sein: nur mal angenommen, für 15 Löcher brauchst du 0.5 sec, dann sind für 16 Löcher schon das 16-fache erforderlich, also ungefähr 8 sec, für 17 dann 136 sec = 1 min,16 sec usw. Für 20 Löcher somit 930240 sec ~= 258.4 h. Also 1m45s können unmöglich sein, wobei noch zu bemerken ist, dass das Optimum bei 15 Bohrungen auch nicht in 0.5 sec zu finden ist. Gruss Jörg
http://de.wikipedia.org/wiki/Backtracking - da steht, wieso es geht. Für 20 Löcher braucht er nun noch 5.5 Sekunden.
Nur weil du es nicht verstehst, ist es nicht unmöglich. Sorry, aber das musste jetzt mal sein. Stell dir die Lösungen in einem Baum vor, jede Ebene korrespondiert mit einem Schritt. Bei 15 Bohrungen hast du 15 Ebenen, jeder Knoten hat 15 Kinder (jedes mögliche Bohrloch/jede mögliche Stadt/wasauchimmer). Den Baum kannst du einfach abarbeiten, indem du 15 verschachtelte Schleifen von 1 bis 15 laufen lässt (bzw. 0 bis 14). Ein Großteil der Blätter ist jetzt schon ungültig, nämlich wenn Orte 2mal vorkommen. Also nimmt man ein Array her, speichert für jeden Ort ob er schon besucht wurde, und wenn man beim Durchlaufen vom Baum einen Knoten evaluieren will, der schonmal besucht wurde, kann man den Knoten und alle Kinderknoten auslassen. Der nächste Punkt ist dann das Mitrechnen der zurückgelegten Strecke. Man findet sehr schnell irgendeine Lösung. Wenn man nun auf der Suche nach einer anderen den Baum durchläuft, und dabei unterwegs schon mehr Weg angesammelt hat, als die schon berechnete (nicht optimale) Lösung an Weg hat, dann kann man den Knoten mit all seinen Kindern auslassen. So funktioniert Backtracking.
Nu sind's 0.5 Sekunden für 20 Löcher. Für 25 sind's 11 Sekunden, für 28 sind's 50 Sekunden.
Danke für den Link. Backtracking liefert nicht das Optimum, sondern EINE Lösung, und wie gut die ist, lässt sich schwer sagen. Bei dem von mir angegebenen Verfahren (Standardverfahren aus Algo-Buch) hat man maximal die doppelte Wegstrecke. Ich habe nur mal eben so ein kleines C++-Programm geschrieben, das nichts anderes tut als für jede Kombination eine einzige Operation auszuführen (hier: Inkrementierung einer Integer Variable). Für n=7 fast nicht messbar (Zeitauflösung: Milisec.), für n=8 0.03sec, für n=9 1.1sec, für n=10 19.1 sec., man erkennt schon gut den exp. Verlauf. Für die Suche nach dem Optimum hast du jetzt aber nicht eine Operation sondern viele (u.U. hunderte), so dass schon 10 Bohrungen in den zeitproblematischen Bereich hineinreichen. Gruss Jörg
Och mensch... Backtracking liefert entweder eine GUTE, oder eine OPTIMALE Lösung! In meinem Fall die optmiale. Ich will jetzt bitte nicht nochmal schreiben müssen, dass das die optimale Lösung ist grmpf Btw. 34 Sekunden für 28. Denk mal nach: Du hast eine Lösung mit Weg x (irgendeine, nicht optimal) und bist auf der Suche nach einer besseren. Ist absehbar, dass ein ganzer Zweig nur Lösungen mit Wegstrecke > x liefert, kannst du den vollständig auslassen.
Schau einfach mal in einem Buch über Algorithmentechnik nach (ich habe mehrere gute). Darin findest du die allgemein bekannte Aussage, das Probleme wie Trav.Sel.Prob, das Rucksackproblem etc. sogenannte NP-Vollständige Probleme sind, und die sind nunmal nur in exp. Zeit lösbar. Die gesammte weltweite Algorithmenforschung hat es bis heute nicht gechafft, NP = P zu beweisen/wiederlegen. Mit deinem Ansatz wäre dir das aber gelungen, was wohl zu bezweifeln ist. backtracking ist als Suchverfahren wohlbekannt, liefert bei solchen Problemen praktisch gesehen niemals die optimale Lösung und ist auch kein Beweis für NP=P!! Gruss Jörg
Nur mal zur Info - man hat schon Probleme mit mehreren 10'000 Orten optimal gelöst. Die ganzen Komplexitätsaussagen gelten nur für n gegen unendlich, für kleine n kannst du das in die Tonne treten.
Das ist absolut falsch: selbst bei kleinem n eschlagt dich schon die Exponential-Funktion; benutzt einfach mal einen Taschenrechner und lass dich überrachschen. Gruss Jörg
Also... ich hab ein Prog das die optimale Lösungen findet, ich verdiene Geld damit Programme zu optimieren und hab schon einige lustig Probleme auf quasi 0 Zeit optimiert, und das trotz korrekter Lösung. Wenn dein Programm es schafft Lösungen für 10 Orte zu errechnen können wir auch gern vergleichen, ich nehm für die Orte x:y Koordinaten und errechne daraus ein Array das die Distanz von jedem zu jedem Ort bereithält (es muss sich also nicht auf 2D darstellbare Orte beschränken, 10 Punkte sind aber schneller vorgegeben als ein 10x10 Array). Es reicht also, wenn du mir die x:y Koordinaten gibst. Aber wenn ich jetzt noch einmal höre, dass das unmöglich wär, werd ich unfreundlich. Du hast einfach nur keine Ahnung wie das gehen kann - ist wohl zu hoch für dich.
Kein Grund unfreundlich zu werden. Ich habe selbst Informatik und Mathematik studiert (parallele und graphische Algos als Schwerpunkt) und bin mit der Komplexitätstheorie vertraut genug um zu wissen, dass das einfach unmöglich ist. Schau einfach mal bei Wikipedia etc. unter NP-Problem vorbei. Gruss jörg
Denkst du, ich hab davon keine Ahnung? Mir stößt grad übel auf, dass du mich für blöd erklären willst. Andere Leute kommen ja vielleicht (aber nur vielleicht!) auch aus dem Umfeld... Ich versuche auch nicht dir das 1*1 zu erklären, und tu so als hättest du keine Ahnung davon...
Mensch Leute...
Wie im Kindergarten mal wieder...
Wie wärs, wenn ihr das einfach testet?
>Es reicht also, wenn du mir die x:y Koordinaten gibst.
Geht los!
Also ich erkläre hier keinen für blöd (deine Wortwahl), ich habe nur wie bereits Oben Daniel dir versucht zu erklären, dass dieses Problem von Rechenaufwand her betrachtet einen exp. Aufwand hat. Es gibt aber Verfahren (sog. Heuristiken), die gute (teils sogar sehr gute) Lösungen liefern. Dazu gehöhren die von Daniel und mir vorgeschlagenen Verfahren genau so wie deins. Aber ein Verfahren zum Bestimmen der Optimalen Lösung ist nunmal praktisch nicht möglich (praktisch heisst hier nicht in angemessener Zeit). Gruss Jörg
Du hast ganz am Anfang geschrieben, dass man mehr als 15 Punkte mit modernen Rechnern nicht machen kann - ich hab denke ich sehr deutlich das Gegenteil bewiesen (und nochmal, es ist die optimale Lösung). Ich versuch's jetzt noch ein letztes mal: 15 Punkte macht 15 ineinander verschachtelte Schleifen. In jeder Schleife testest du, ob der aktuelle Zählerstand schon in einer vorherigen Schleife vorkommt (dann hättest du einen Ort 2mal besucht), ist dem so überspringst du den Schleifeninhalt. Mit der Methode würdest du alle möglichen Kombinationen ablaufen. Ich denke mal das ist soweit klar. Du findest also jede Lösung, und musst die mit dem geringsten Weg auswählen. Nun errechnest du in jeder Schleife den bisherigen Weg. Also in der 3. Schleife hast du 3 Orte besucht, da berechnest du bei jedem Durchlauf den Weg bis hierhin - die 4. Schleife bestimmt dann quasi den nächsten Ort. Wenn du nun feststellst, dass du schon mehr Weg für die 3 Orte brauchst, als für eine andere Lösung die alle 15 Orte einschließt, kannst du die 3. Schleife direkt eins weiterzählen. Eine Lösung kann nunmal nicht optimal sein, wenn eine kürzere existiert. Und alle Lösungen die mit den 3 gegebenen Orten anfangen sind länger. Das ist die einfachste Variante da Möglichkeiten auszulassen die eh zu keiner Lösung führen. Eine weitere wäre: Wenn du in der 3. Schleife bist, hast du noch 14-2=12 Wege vor dir. Ein Weg kann nicht kürzer sein als die geringste Distanz zwischen 2 Orten - also kannst du schonmal eine untere Schranke für den restlichen Weg angeben, die größer 0 ist. Beispiel: (0:0), (1:0), (1:1), (10:1), (10:0) Irgendeine Variante: (0:0)-(1:0)-(1:1)-(10:1)-(10:0), macht Weglänge 1+1+9+1=12. Nun gehst du deine Schleifen durch, und hast bisher (0:0)-(10:0)-(1:0). Allein die 3 Orte haben schon Weglänge ~19. Du brauchst also für die letzten beiden Orte garnix einsetzen, kommt eh >12 raus. qed. Wenn du vor praktischen Optimierungsproblemen stehst, musst du dich zuallererst immer fragen, wieviele Lösungen du betrachten musst. Da nutzt dir deine theoretische Informatik erstmal so ziemlich garnix. In dem Fall hier suchst du eine bestimmte Lösung aus einer Menge die zu groß ist um sie vollständig zu betrachten. Die eine Lösung hängt aber nicht mit anderen Lösungen zusammen. Im Idealfall "kennst" du die Lösung, dann ist der Aufwand O(1). Kennst du die Lösung nicht, und hast du auch keine Möglichkeit vorher auszusortieren, ist der Aufwand O(n!). In der Praxis schaffst du es häufig einen Großteil vorher auszusortieren. Du hast nicht genug Informationen um in O(1) einfach direkt die richtige auszuwählen, aber du hast auch genug um nicht alles durchprobieren zu müssen. Dazu eine theoretisch korrekte Komplexitätsbetrachtung zu machen ist einmal nahezu unmöglich weil zu kompliziert, zum anderen aber auch nicht zweckdienlich - weil es in der Praxis um Durchschnittswerte für bestimmte Eingabewerte geht, und nicht um den worst case.
Übrigens, wenn ich mich richtig erinnere ist n!/10^n auch in O(n!). Nu überleg mal, was das für die Zeiten bedeutet (umgeschrieben: Produkt(i=1..n) (n/10)). Die Aussage das ein Problem in O(n!) liegt, sagt dir - wie schon gesagt - nur was über's Unendliche aus.
http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ Das ist ein hübscher Link falls du dich eingehender über das Thema informieren willst. http://www.informatik.uni-heidelberg.de/groups/comopt/software/TSPLIB95/STSP.html Das bringt's auf den Punkt: "When I published TSPLIB more than 10 years ago, I expected that at least solving the large problem instances to proven optimality would pose a challange for the years to come. However, due to enormous algorithmic progress all problems are now solved to optimality!!" Man beachte, dass da Teile mit über 10k Punkten rumschwirren. Kannst ja mal ausrechnen, wie lang die deiner Erklärung nach benötigen würden... Leider ist das Format in den die Daten vorliegen teils etwas komisch, die für ulysses16 angegebene Lösung stimmt nicht, wenn man das als Koordinaten in der Ebene interpretiert (komme auf eine kürzere). Steht zwar dabei, dass das GEO Daten sind (wahrscheinlich Länge/Breite), hab aber keinen Plan wie man die interpretieren muss... und auch keine Lust mich damit zu beschäftigen. Nochwas zu der n!/10^n Geschichte: Natürlich ist das nicht in O(n!), aber auch nicht polynomial. Kein Widerspruch also.
Der Exponentialansatz fuer das Problem ist duemmlich. Um bei 25 Punkten den 26. zu nehmen, muss man nicht alle 26, sondern nur die naechsten, 2-5 betrachten
In einem früheren Job hatte ich genau dieses Thema, und es war keine Zeit für große und langwierige Berechnungen / Optimierungen. Außerdem kam jedes Problem nur ein einziges Mal. Also: der jeweils nächste Punkt war der jeweils nächstliegendste. Das war sicher nicht die optimalste Lösung, aber eigentlich immer eine sehr gute und vom Rechenaufwand superfast. Witzig dabei: Häufig wurde ein Punkt nicht berücksichtigt, so dass die Maschine für den letzten Punkt noch einmal quer über den Tisch fahren musste. Wir hatten mehrere Optimierungsmethoden ausprobiert, diese schien uns am Ende die günstigste. Damals waren die Rechner auch noch deutlich langsamer als heute (ganz wenige 100MHz)
Schon lustig. Da streiten sich zwei, die in ihrer Jugend mal Rechnen oder Programmieren gelernt haben (ok, man kann es auch Mathe oder Informatik "studieren" nennen) und meinen, sie haetten die Weisheit mit Loeffeln gefressen. Meint ihr, ihr habt recht, wenn ihr eure vermeintlichen Argumente oefter wiederholt als der andere? Joerg hat immerhin recht, aber weiss nicht, wieso. Und I_H hat zwar nicht recht, hat aber trotzdem ein gutes Mittel gegen Minderwertigkeitskomplexe - andere geben mit der Groesse ihres was-auch-immer an, I_H haelt mit der Geschwindigkeit "seiner" Algorithmen dagegen. I_H, mach dir mal klar, dass es beim Traveling-Salesman-Problem nicht um die optimale Loesung fuer 99.999% aller praktisch auftretenden Aufgabenstellungen geht (das beherrscht per Backtracking -wie du- jeder Schueler, der Informatik in der Schule belegt), sondern es geht um einen Algorithmus, der alle denkbaren Aufgabenstellungen effizient loest. Also beweist du gar nichts, wenn du nach xy-Datensaetzen fragst, die du dann loest. Andersrum wird ein Schuh draus: poste deinen Algorithmus, und ich gebe dir einen Datensatz mit 30 Punkten, fuer den der Algorithmus zu deiner Lebzeit nicht nachweisen kann, welches der optimale Weg ist. Ich erwarte nicht, dass du dies einsehen willst. Aber bevor du deine Position zum 101. Mal wiederholst, tu einfach, was ich dir sage, poste deinen Algorithmus, und du wirst ganz schnell an deinen Faehigkeiten zweifeln. Bernd
@ I_ H. (i_h), hatte in der Mittagspause mal Zeit, die Links anzuklicken. Es war, wie ich mir das schon dachte: Es geht um einen Wettbewerb um die besten TSP-Heuristiken, gestaffelt nach verschiedenen Gruppen. Wenn du man auf den Link/Seite von Bill Cook gehst, findest du ein in der Litheratur bekanntes Problem: Die optimale Tour durch Schweden. Schau dir einfach mal an, welcher Aufwand hinter der optimalen Lösung steht. Das gleiche gilt übrigens auch für die anderen Beispiele. Die auf der Heidelberger Seite genannten optimalen Lösungen beziehen sich nicht auf allgemeine Probleme, sondern auf von vornherein festgelegte. Das wird in der Algorithmenthechnik bzw. deren Wettbewerbe um Algorithmen häufig so gemacht. Gibst du dagegen einen neuen Datensatz vor, kannst du lange warten, bis jemand ein Optimum findet. @ Bernd L. (berndl), wieso soll ich nicht wissen, wieso TSP NP-vollständig ist. All diese Probleme lassen sich in polynomieller Zeit aufeinander abbilden, einen Beweis für NP=P hab ich natürlich auch nicht, wie dann auch. Aber das habe ich glaube ich schon direkt bzw. indirekt ausgeführt. Das ich nicht sagen kann, wieso das Verfahren von I_ H. nicht funktioniert, liegt ja daran, dass ich das Verfahren nicht kenne. Aber rein aus dem Wissen um die Komplexitätstheorie heraus weiss ich, dass entweder der Algo nicht optimal arbeitet oder aber O(exp(n)) = O(n!) Rechenaufwand hat. Gruss Jörg
>Das ich nicht sagen kann, wieso das Verfahren von I_ H. nicht funktioniert, >liegt ja daran, dass ich das Verfahren nicht kenne. Naja, wenn er die Wahrheit sagt, hat er doch ein funktionierendes Verfahren fuer seine Testdaten, und Backtracking sagt genug, um zu erkennen, warum es funktioniert. Fuer so kleine, zufaellige Datensaetze, ist Backtracking fast immer effizient. >Aber rein aus dem Wissen um die Komplexitätstheorie heraus weiss ich, dass >entweder der Algo nicht optimal arbeitet Wenn du seinen unbeholfenen Erklaerungen folgen wuerdest, muesstest du das nicht anzweifeln >oder aber O(exp(n)) = O(n!) Rechenaufwand hat. Genau, das merkt er aber nicht, da er keine worst-case Daten verwendet. Genau wie bei diesen sogenannten TSP-Wettbewerben. Dies ist ein gutes Beispiel, was herauskommt, wenn man Programmierern oder Ingenieuren ein mathematische Problem gibt. Sie loesen nicht das Problem, sondern dessen Projektion auf alltaegliche Situationen. Die Loesung des modifizierten Problems kann durchaus brauchbar sein (und ja, die Loesungen des TSP-Wettbewerbs sind optimal), aber die eigentliche Fragestellung wird man solchen Leuten nicht verstaendlich machen koennen.
I_ H. wrote: > Also ich hab auf die schnelle jetzt mal was zusammengeschrieben, das für > 15 (zufällig angeordnete) Löcher 11 Sekunden rechnet... mit wirklich > einfachstem backtracking (wurde schon eine Lösung kürzer als der > aktuelle Stand gefunden, brich ab). Sorry, wer nicht liest ist selber schuld. Da steht eindeutig, wie die Löcher angeordnet sind. Das es hier nur um eine Teilmenge aller möglichen Probleme geht habe ich nie bestritten, genausowenig hab ich behauptet eine Lösung für das allgemeine Problem gefunden zu haben, die schneller als O(n!) ist. Ich habe behauptet, mein Algorithmus/Programm arbeitet auf diese oben angegebenen Daten mit den Zeiten die ich angegeben hab! In der Praxis braucht man oft die Lösung für praxisbezogene Werte, ich bin auch nochmal extra auf den worst-case Fall eingegangen, der in der Praxis schlicht nicht von Interesse ist, weil er bei 99% der Probleme nie und nimmer auftritt. Wenn man sich bei jedem Problem hinstellt und sagt "nein, das ist in NP, das lässt sich nicht in brauchbarer Zeit lösen" und garnicht erst weitersucht kommt man nicht vom Fleck. @Jörg Gib doch einfach mal zu, dass du nicht genau gelesen hast. Die ganze Diskussion hier dreht sich darum, dass du mir schlicht nicht geglaubt hast, dass mein Algorithmus so schnell ist. Die Dinger die auf der verlinkten Seite angegeben wurde, wurden übrigens sehr wohl optimal gelöst. So steht es jedenfalls da... @Bernd. L. Du hast auch nicht ordentlich gelesen. Setzen, 6.
Übrigens - mit verlaub - ihr seid daran schuld, dass Akademiker (zu denen ich auch gehöre) so einen schlechten Ruf haben. 0 Praxisorientierung, anderen gegenüber erstmal lauter Theoriegewäsch loslassen, das zudem 0 Praxisbezug hat. Und dann daran scheitern, ordentlich zu lesen. PS: Richtig programmieren lernt man nicht an Universitäten.
So, Mittagspause ist gleich vorbei.. Den Ausführungen zu folgen ist aber schwer: einerseits verwendet er Backtracking (ist ja auch Auswertmechanismus in PROLOG, einfach zu implementieren), andererseits werden Zeitangaben gemacht, die bei Backtracking unmöglich auf das Problem zutreffen können. Von daher (ohne den Code zu kennen) kann ich ja nur Metaaussage treffen. Gruss jörg
> O(exp(n)) = O(n!)
Vorsicht, O(n!) ist echt größer als O(exp(n)). Identisch sind diese
beiden Groß-O-Mengen nicht.
[ ] du hast verstanden was Backtracking ist Sorry, aber der Verdacht drängt sich mir einfach auf. Backtracking allein hilft dir noch garnix. Wenn du die Lösung kennst, kommst du mit Backtracking bei NP Problemen zu einer Lösung O(log n). Auf jeder Baumebene kannst du alle bis auf einen Pfad ausschließen, weil du weist, dass die Lösung auf dem einen Pfad liegt. Backtracking braucht einen Algorithmus der Zweige zuverlässig ausschließen kann, ohne den Zweig komplett betrachten zu müssen. Und mit diesen Algorithmen steht und fällt die Effizienz von Backtracking. Ich hab vor 'ner Weile mal weil mir langweilig war ein Programm geschrieben, das Sudokus berechnet (wir hatten zum Zeitvertreib welche gemacht, und ich war zu faul jedesmal neu zu denken). Prinzipiell macht der auch nix anderes als alle Kombinationen durchzuprobieren, das Backtracking ist aber so effektiv, das bei Vorgaben mit wenig Lösungen das Ergebnis in quasi 0 Zeit rauskommt. Macht man keine Vorgaben fängt er an alle möglichen Sudokus auszugeben, was einige Zeit (so etwa 123.45e67 Jahre) dauern dürfte - die meisten Backtracking Algorithmen schließen dann nix mehr aus. Im Moment kennt mein TRS Programm 2 Algorithmen, der eine schlägt mit einer Effizienz von >90% zu (der Zweig kann also weggelassen werden) und wird auf jeder Ebene ausgeführt, der andere mit 20..40% ab Ebene 6. Den Code zu posten würde übrigens wenig Sinn machen, weil du wahrscheinlich nicht durchblicken würdest.
Also auch wenn der ein oder andere den Code nicht verstehen würde, bitte poste ihn. Dann kann vielleicht noch jemand (u.a. ich) davon was lernen...
Na ok, aber ich hab euch gewarnt. Der Code ist nicht schwer verständlich weil er besonders komplex ist oder sowas, sondern weil er gestern evolutionär gewachsen ist und ich wenig Lust hatte zu kommentieren, und schnell was sehen wollte. Der normale Weg wär das nach dem proof of concept nochmal schön sauber umzusetzen, wobei man gleich mit Templates loshauen könnte (brächte sicher nochmal ein paar %).
Mist, das war die executable... hier nun der Code. Mir fällt grad auf, dass einige der Kommentare schon obsolete sind (zB. bei cmpminp2p). Aber ich hab euch gewarnt...
>Wenn du die Lösung kennst, kommst du mit Backtracking bei NP Problemen zu einer Lösung O(log n). Haeh? Wenn ich die Loesung kenne, ist die Komplexitaet O(1). Und ich dachte, du wuerdest beginnen zu verstehen, dass das, was du geschrieben hast, ziemlich wenig Sinn ergibt, es sei denn du drehst dir selbst du Worte im Mund um, so dass das Gegenteil von dem herauskommt, was jeder andere in deinen Beitraegen liest. >Im Moment kennt mein TRS Programm 2 Algorithmen, der eine schlägt mit >einer Effizienz von >90% zu (der Zweig kann also weggelassen werden) und >wird auf jeder Ebene ausgeführt, der andere mit 20..40% ab Ebene 6. Oh Herr, deine Worte sind unergruendlich.
> Oh Herr, deine Worte sind unergruendlich.
So hat die Bevölkerung vor 300 Jahren auch auf die Wissenschaft
reagiert...
Wenn du das Problem in einem Baum darstellst (was bei vielen NP
Problemen funktioniert) und den nun abläufst, erreichst du mit
Backtracking und bekannter Lösung O(log n).
Sinn der Aussage ist zu zeigen, dass die Effizienz von Backtracking von
den dahinterstehenden Algorithmen abhängt. Aber das hast du scheinbar
nicht verstanden.
PS: Wenn du die Lösung kennst, ist der beste Algorithmus O(1). Hast du
einen Algorithmus der die bekannte Lösung verwurstet, ist der aber nicht
zwangsweise O(1).
>PS: Wenn du die Lösung kennst, ist der beste Algorithmus O(1). Hast du >einen Algorithmus der die bekannte Lösung verwurstet, ist der aber nicht >zwangsweise O(1). Stimmt. Und wenn ich nichts zu tun habe und mir trotzdem eine Frikadelle ans Knie nagele, kostet mich das auch O(Frikadelle+Nagel+Hammer+Arztbesuch).
Du hast es immernoch nicht verstanden - es geht darum zu zeigen wie sehr Backtracking von den dahinterstehenden Algorithmen abhängt. Wenn du die Lösung kennst kannst du auch eine Aussage treffen, ob du einen bestimmten Zweig auslassen kannst, oder nicht - die Aussage ist in dem Fall sogar optimal, also alles was du auslassen kannst, sagt dir der Algorithmus aus. Das zeigt, wo die maximale Effizienz von Backtracking liegt. Das Minimum auf der anderen Seite hast du, wenn du garnix ausschließen kannst. Dann ist Backtracking wirkungslos. Der Fall das du die Lösung kennst ist nur ein Beispiel zur Demonstration! Wenn 2 Leute hergehen und sich tolle Algorithmen mit Backtracking ausdenken, kann der Algorithmus von Person A trotzdem in einer anderen Komplexitätsklasse als der von Person B liegen, weil die Backtrackingalgorithmen von A und B unterschiedlich sind. Backtrackingalgorithmen haben nur die blöde Angewohnheit häufig (nicht immer) von den Eingabedaten abzuhängen, also bei "guten" Eingaben fast alle unnötigen Fälle ausschließen zu können, bei "schlechten" Eingaben aber nur noch sehr wenig ausschließen zu können. Desswegen nutzt es dir garnix zu wissen, dass ein Programm Backtracking benutzt. Daraus kannst du noch keine Aussage zur Komplexität ableiten - geht einfach nicht. Genau das hat Jörg oben aber gemacht. Dabei ist zwar sehr wahrscheinlich, dass ich keinen Backtrackingalgorithmus finde der die Gesamtzeit für alle Eingaben auf P drückt, aber darum ging es auch nie.
Ih, es ist nicht erkennbar, wem du mit deinen Beitraegen antwortest. Widersprichst du gerade meiner Aussage, dass es moeglich ist, das TSP fuer kleine zufaellige Punktanordnungen in den meisten Faellen effizient zu loesen, wie du es getan hast? Oder willst du gerade deinen alleinigen Anspruch auf die Loesung des TSP per Backtracking sicherstellen? Mit der Begruendung, dass Backtracking an sich noch keine Loesung des Problems ist, solange kein Ih daherkommt und zeigt, dass er Experte fuer Sudokus und Bohrwege ist? Ich verstehe immer weniger, worauf du eigentlich hinauswillst, denn du hast ja schon deine Spielereien ja schon in Relation zu 300 Jahre alter Wissenschaft gesetzt. Willst du dem, was uns allen selbstverstaendlich ist, noch etwas Neues hinzufuegen, oder willst du bloss beweisen, dass man Altbekanntes auch kompliziert ausdruecken kann?
> Widersprichst du gerade meiner Aussage, dass es moeglich ist, das TSP fuer kleine zufaellige Punktanordnungen in den meisten Faellen effizient zu loesen, wie du es getan hast? Das war meine Aussage, du hast sie nur nochmal wiederholt. Ich hab's aber nicht nur eine Vermutung abgegeben, sondern praktisch belegt (praktisch beweisen geht ja leider net). Mein Beitrag oben ist die Reaktion auf > Stimmt. Und wenn ich nichts zu tun habe und mir trotzdem eine Frikadelle ans Knie nagele, kostet mich das auch O(Frikadelle+Nagel+Hammer+Arztbesuch). weil du offensichtlich nicht verstanden hast, wieso ich den Beitrag geschrieben hab. Fassen wir nochmal zusammen: - "Ein Algorithmus benutzt Backtracking"; diese Aussage erlaubt keinerlei Rückschlüsse auf die Laufzeit, was Jörg gemacht hat - Die Effizienz von Backtracking hängt davon ab, wie gut die Ausschlussalgorithmen funktionieren; wenn optimal, wird aus O(n!) mal eben O(log n). - Das TRS Problem hab ich für zufällig angeordnete Punkte durchgerechnet, und dabei ergaben sich bis n=30 brauchbare Laufzeiten; darüber steigt die Laufzeit irgendwann fakultativ - Komplexitätsaussagen wie "das kann nicht sein, weil das in O(n!) liegt!" sind für praktische Belange nur begrenzt brauchbar, siehe Punkt drüber - für n in 1..30 läuft es nicht mit n!, für n gegen unendlich schon (bzw. wahrscheinlich). Das Sieve of Pritchard ist auch der schnellste Siebalgorithmus für Primzahlen, obwohl auch O(n) Varianten existieren (Pritchard: O(n*log log n)... unter der Annahme, dass Rechenoperationen konstant sind). - aus Zeitangaben für 3 gerechnete Punktmengen eine Komplexitätsklasse ermitteln zu wollen ist ausgeschlossen Wenn du das jetzt wieder nicht verstehst, bitte lies den Thread nochmal in Ruhe durch. Btw. hier kommt nicht zufällig jemand aus Ilmenau? Da kenn ich jemanden, mit dem sich ähnlich sinnfreie Diskussionen führen lassen. Und macht euch bitte klar, wie Backtracking funktioniert. Ich hab den Wikipedia Artikel nicht umsonst gepostet...
>Fassen wir nochmal zusammen: >- "Ein Algorithmus benutzt Backtracking"; diese Aussage erlaubt >keinerlei Rückschlüsse auf die Laufzeit, was Jörg gemacht hat wo? >- Die Effizienz von Backtracking hängt davon ab, wie gut die >Ausschlussalgorithmen funktionieren Wenn ich mal rate, was du mit Ausschlussalgorithmen meinst, schraenkst du das Backtracking auf eine triviale Untergruppe von Algorithmen ein. Und natuerlich hast du recht: jeden Algorithmus kannst du durch zufuegen von unnoetigen Zwischenschritten beliebig ineffizient machen. >- Das TRS Problem hab ich für zufällig angeordnete Punkte >durchgerechnet, und dabei ergaben sich bis n=30 brauchbare Laufzeiten; >darüber steigt die Laufzeit irgendwann fakultativ Das ist uebel. Ich dachte, du haettest einen effizienten Algorithmus gefunden. Kann es sein, dass deine Implementierung ein Memory-Leak hat? >- Komplexitätsaussagen wie "das kann nicht sein, weil das in O(n!) >liegt!" sind für praktische Belange nur begrenzt brauchbar, siehe Punkt >drüber - für n in 1..30 läuft es nicht mit n!, ok, ich frag mich jetzt nicht mehr, ob du was verstehst oder nicht. Halten wir einfach fest: wenn du dich anstrengst, kannst du so tun, als ob. >- aus Zeitangaben für 3 gerechnete Punktmengen eine Komplexitätsklasse >ermitteln zu wollen ist ausgeschlossen Wie bitte? Ermitteln zu wollen ist doch das, was du die ganze Zeit willst, aber nicht tust. Immerhin hast du belegt ohne zu beweisen. Eine eindrucksvolle Leistung!
Sag jetzt nicht du kommst wirklich aus Ilmenau... Bernd L. wrote: >>Fassen wir nochmal zusammen: >>- "Ein Algorithmus benutzt Backtracking"; diese Aussage erlaubt >>keinerlei Rückschlüsse auf die Laufzeit, was Jörg gemacht hat > > wo? Zum Beispiel da: Jörg: >Den Ausführungen zu folgen ist aber schwer: einerseits verwendet er >Backtracking (ist ja auch Auswertmechanismus in PROLOG, einfach zu >implementieren), andererseits werden Zeitangaben gemacht, die bei >Backtracking unmöglich auf das Problem zutreffen können. >>- Die Effizienz von Backtracking hängt davon ab, wie gut die >>Ausschlussalgorithmen funktionieren > > Wenn ich mal rate, was du mit Ausschlussalgorithmen meinst, schraenkst > du das Backtracking auf eine triviale Untergruppe von Algorithmen ein. > Und natuerlich hast du recht: jeden Algorithmus kannst du durch zufuegen > von unnoetigen Zwischenschritten beliebig ineffizient machen. Extra für dich aus der Wikipedia kopiert: "Backtracking geht nach dem Versuch-und-Irrtum-Prinzip (trial and error) vor, d. h. es wird versucht, eine erreichte Teillösung schrittweise zu einer Gesamtlösung auszubauen. Wenn absehbar ist, dass eine Teillösung nicht zu einer endgültigen Lösung führen kann, wird der letzte Schritt bzw. die letzten Schritte zurückgenommen, und es werden stattdessen alternative Wege probiert." Man beachte: "Wenn absehbar ist, dass eine Teillösung nicht zu einer endgültigen Lösung führen kann, wird der letzte Schritt bzw. die letzten Schritte zurückgenommen" (niemand sagt, dass alle Schritte schon berechnet worden sein müssen) Dieses "Wenn absehbar ist" ist der Schlüssel zur Effizienz von Backtracking. Mehr schreibe ich zu dem Thema Backtracking nicht mehr, es ist für mich offensichtlich, dass du noch nie einen Backtrackingalgorithmus umgesetzt hast. >>- Das TRS Problem hab ich für zufällig angeordnete Punkte >>durchgerechnet, und dabei ergaben sich bis n=30 brauchbare Laufzeiten; >>darüber steigt die Laufzeit irgendwann fakultativ > > Das ist uebel. Ich dachte, du haettest einen effizienten Algorithmus > gefunden. Kann es sein, dass deine Implementierung ein Memory-Leak hat? Ehrlich gesagt sind die Zeiten geschätzt, ich habe kaum Rechnungen über 30 gemacht. Die Funktionsweise vom Ausschlussalgorithmus legt es aber nah, wahrscheinlich etwas der Form f(n)+(n/2-30)!, wobei f(n) kleiner O( (n/2)!) ist. >>- Komplexitätsaussagen wie "das kann nicht sein, weil das in O(n!) >>liegt!" sind für praktische Belange nur begrenzt brauchbar, siehe Punkt >>drüber - für n in 1..30 läuft es nicht mit n!, > > ok, ich frag mich jetzt nicht mehr, ob du was verstehst oder nicht. > Halten wir einfach fest: wenn du dich anstrengst, kannst du so tun, als > ob. Nochmal extra für dich: f(n) ist in O(g(n)) wenn gilt: lim sup (n->unendlich) f(n)/g(n) divergiert nicht gegen unendlich. Nun nimm dir mal die Funktion f(n)=n!-n^10 her (ok, blödes Beispiel, das wird negativ... egal). Die liegt in O(n!). Beweis: n^10/n! geht gegen 0, fällt also weg. Bleibt n!/n!, was offensichtlich nicht gegen unendlich geht. Wenn du dir die Funktion für kleine n anschaust, bekommst du aber nix auch nur annährend n! entsprechendes raus (die fällt anfangs sogar). Das hast du erst für n->unendlich. Es ist also offensichtlich, dass man aus einigen wenigen praktisch ermittelten Laufzeiten nicht auf die Komplexität zurückschließen kann, so wie Jörg es hier: Jörg: >Das kann unmöglich sein: nur mal angenommen, für 15 Löcher brauchst >du 0.5 sec, dann sind für 16 Löcher schon das 16-fache erforderlich, >also ungefähr 8 sec, für 17 dann 136 sec = 1 min,16 sec usw. getan hat. Jörg war auch der Meinung Backtracking liefere nur eine, nicht aber die optimale Lösung, was auch falsch ist: Jörg: >Danke für den Link. Backtracking liefert nicht das Optimum, sondern >EINE Lösung, und wie gut die ist, lässt sich schwer sagen. Bei dem >von mir angegebenen Verfahren (Standardverfahren aus Algo-Buch) >hat man maximal die doppelte Wegstrecke. >>- aus Zeitangaben für 3 gerechnete Punktmengen eine Komplexitätsklasse >>ermitteln zu wollen ist ausgeschlossen > > Wie bitte? Ermitteln zu wollen ist doch das, was du die ganze Zeit > willst, aber nicht tust. Immerhin hast du belegt ohne zu beweisen. Eine > eindrucksvolle Leistung! Siehe Zitate oben drüber - ICH hab mein Programm nicht für fehlerhaft erklärt, weil die Zeiten bei den 3 Rechnungen nicht n! entsprachen. ICH hab aber auch nie gesagt, dass das für allgemeine Lösungen immer diese Zeiten liefert. So, ich hab jetzt noch'n paar andere Sachen zu tun.
>So, ich hab jetzt noch'n paar andere Sachen zu tun.
Sag nicht, du schreibst ein Backtracking-Programm fuer Schach! Du waerst
DER Kandidat dafuer, denn in den letzten 300 Jahren hat es keiner
geschafft. Aber es gab ja auch noch keine solchen Experten, die das
ganze Wikipedia mit all seinen Fehlern sogar mehrfach zu zitieren in der
Lage sind.
Jeder normale Mensch sagt bei offensichtlichen Fehlern: wenn der Satz so
stimmen wuerde, waeren NP und P aequivalent. Nicht so du. Du sagst: wenn
es so in Wikipedia steht, kann der grosse Ih jedes Problem loesen, und
wenn es 10 Minuten spaeter immer noch so in Wikipedia steht, dann muss
es richtig sein.
Bitte, bitte, bitte oh Herr! Loese die jahrtausendealte Frage nach einer
Schachstrategie!!!
oh my god! warum nennt jemand wie i_ h. das stichwort traveling-salesman-problem, wenn er ganz offensichtlich nicht weiß worum es dabei geht, oder er weiß es und schreibt dann zu einem ganz anderen thema? warum können typen wie er nicht einfach zugeben, daß sie sich geirrt haben? dann hätte er sich nur 1-2 postings lang lächerlich gemacht, so aber merkt er, wie er sich immer tiefer reinreitet, und versucht verzweifelt, da wieder rauszukommen. das ist nicht schön mit anzusehen.
Ihr seid ja vielleicht 'n paar Stumpfnasen. Es lässt sich sogar beweisen, dass sich das allgemeine symmetrische TRS Problem mit Länge n (teilbar 3) in f(n):=n!/(n/3-1)! lösen lässt (auch mit Backtracking), mit O(f(n)) != O(n!) aber trotzdem NP. Es geht sicher noch besser, aber dann ist der Beweis nicht mehr so einfach. Verdient mit solchem Wissen erstmal Geld, dann reden wir weiter. Mit eurer Wortklauberei kommt ihr da nicht besonders weit, wenn ihr die Bildungselite Deutschlands sein sollt, ist klar wieso's uns so schlecht geht.
Einer der besseren Algorithmen für exakte Lösungen schafft übrigens O(n^2*2^n) (auch NP, was sonst), was auch deutlich besser als n! ist (Michael Held & Richard M. Karp, A Dynamic Programming Approach to Sequencing Problems). Der und der Beweis dazu ist nicht auf meinem Mist gewachsen, verifiziert aber meine Aussage oben, dass es besser als O(n!) geht. Ich weis nach wie vor nicht wieso ihr hier so einen Aufstand gemacht habt (es ist mir inzwischen auch egal). Einzige Erklärung wäre, dass ihr gedacht habt NP ist ausschließlich O(n!). Damit ist das Thema für mich erledigt.
Nur mal als Einwurf: "NP" enthält keine Algorithmen, sondern Probleme. Ein Algorithmus kann also niemals "in NP" sein. Achtet man darauf nicht, verwechselt man schnell Komplexitätsklassen mit Laufzeitklassen und wirft völlig verschiedene Konzepte durcheinander. Genau genommen enthält NP sogar nur Entscheidungsprobleme, also Ja/Nein-Fragen. Die Frage "was ist der kürzeste Weg durch alle Punkte?" liegt also auch nicht in NP.
Wenn man es eng sieht hast du Recht. Ich formulier die Aussage von oben so um, dass es passt: Die Tatsache, dass ein Algorithmus besser O(n!) für ein Problem existiert, impliziert nicht, dass dieses Problem in P liegt. Selbst wenn mein Programm von oben das TRS Problem in O(n^2*2^n) lösen würde (was zweifelsohne möglich wäre), bedeutet das nicht, dass das TRS Problem in P liegt. In O(n!) liegt es (mein Prog/Alg) übrigens auch nicht, auch für das allgemeine TRS Problem mit allen Eingabewerten nicht. Eher etwas der Form O(n!/(an)!) mit relativ kleinem 0<a<1. Falls sich hier wirklich jemand dafür interessiert reiße ich auch nochmal an wie man auf einen Algorithmus (mit Backtracking) besser O(n!) kommt, und wie sich zeigen lässt, dass er wirklich besser O(n!) ist.
>Falls sich hier wirklich jemand dafür interessiert...
Nein, es interessiert sich hier keiner fuer weitere von deinen
"Erklaerungen".
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.