kürzester Weg für XY Tisch

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

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.

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

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

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.

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.

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.

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.

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.

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

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.

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

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

[ ] 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.

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!!!

<°)))o><

Wo ist das Popcorn?

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.

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".

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