www.mikrocontroller.net

Forum: Offtopic kürzester Weg für XY Tisch


Autor: Franz (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Wasser (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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>

Autor: Wasser (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hm theoretisch is ja beim Bohen nix im Weg. Warum nicht einfach die 
Differenz aus den positionen nehmen und los Bohren ?

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das lässt sich auf das traveling salesman Problem zurückführen, schau 
dir Lösungen dazu an.

Autor: Daniel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Wasser (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
<g> Er hat aber auch nicht gesagt das ein Mikrocontroller alles 
berechnen soll.

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wikipedia sagt, dass heutzutage auch exakte Methoden dafür zur Verfügung 
stehen.

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Legt man die Bohr-Reihenfolge nicht bereits auf dem PC beim Erstellen 
der Bohrdatei fest?

Autor: Daniel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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).

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
So, nu dauerts nur noch 1.7 Sekunden. Und mir sind noch einige 
brauchbare Sachen eingefallen, mit denen man's noch schneller bekommt.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
http://de.wikipedia.org/wiki/Backtracking - da steht, wieso es geht.

Für 20 Löcher braucht er nun noch 5.5 Sekunden.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jörg (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Matthias Lipinsky (lippy)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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!

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ü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.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
http://www.iwr.uni-heidelberg.de/groups/comopt/sof...

Das ist ein hübscher Link falls du dich eingehender über das Thema 
informieren willst.

http://www.informatik.uni-heidelberg.de/groups/com...

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.

Autor: 3357 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Optimierer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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)

Autor: Bernd L. (berndl)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ 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

Autor: Bernd L. (berndl)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ü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.

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Chris (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> O(exp(n)) = O(n!)

Vorsicht, O(n!) ist echt größer als O(exp(n)). Identisch sind diese 
beiden Groß-O-Mengen nicht.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
[ ] 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.

Autor: gespannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: I_ H. (i_h)
Datum:
Angehängte Dateien:
  • main (22,6 KB, 123 Downloads)

Bewertung
0 lesenswert
nicht lesenswert
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 %).

Autor: I_ H. (i_h)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Bernd L. (berndl)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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).

Autor: Bernd L. (berndl)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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).

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Bernd L. (berndl)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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...

Autor: Bernd L. (berndl)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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!

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Bernd L. (berndl)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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!!!

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
<°)))o><

Autor: Angemeldeter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Rufus Τ. Firefly (rufus) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wo ist das Popcorn?

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Chris (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Bernd L. (berndl)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Falls sich hier wirklich jemand dafür interessiert...

Nein, es interessiert sich hier keiner fuer weitere von deinen 
"Erklaerungen".

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dir hätt ich's eh nicht erklärt. Geh zurück auf deine Trollwiese.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail, Yahoo oder Facebook? Keine Anmeldung erforderlich!
Mit Google-Account einloggen | Mit Yahoo-Account einloggen | Mit Facebook-Account einloggen
Noch kein Account? Hier anmelden.