Schaut mal, worüber Heise heute berichtet: http://www.heise.de/newsticker/meldung/Roboter-loest-Rubik-s-Cube-und-braucht-nur-gut-eine-Sekunde-3083732.html Das ist doch der Hammer, oder? Hat mit µC nicht sehr viel zu tun, aber ich finde es trotzdem interessant.
:
Verschoben durch User
Stefan U. schrieb: > Schaut mal, worüber Heise heute berichtet: > http://www.heise.de/newsticker/meldung/Roboter-loe... > > Das ist doch der Hammer, oder? > > Hat mit µC nicht sehr viel zu tun, aber ich finde es trotzdem > interessant. Stimmt. Daß die Berechnung der Lösung schnell genug ist, darüber wundere ich mich nicht. Aber die Drehungen so sauber hinzukriegen, daß sich nichts verkantet und alles sauber läuft, das ist das eigentliche Meisterwerk. Aber trotzdem frage ich mich immer wieder, wer den Blödsinn mit dem "Zauberwürfel" in die Welt gesetzt hat. Was hat das mit Zauberei zu tun?
Schade das er den Würfel dafür manipulieren musste (Löcher bohren). Sonst klasse...
> Aber trotzdem frage ich mich immer wieder, wer den Blödsinn mit dem > "Zauberwürfel" in die Welt gesetzt hat. Was hat das mit Zauberei zu > tun? Muggle werden das NIEMALS verstehen!
Technik wirkt oft wie Magie, bis man geschnallt hat, wie sie funktioniert.
Stefan U. schrieb: > Das ist doch der Hammer, oder? Hätten sie das Gestell nicht aus dem 3-Drucker sondern aus Aluprofilen zusammengeschraubt, hätten sie z.B. mit Gummifüssen oder Zahnscheiben genügend Druck auf die Aussenflächen des Cube ausüben können, um ihn auch ohne die Löcher zu greifen.
Stefan U. schrieb: > Schaut mal, worüber Heise heute berichtet: > http://www.heise.de/newsticker/meldung/Roboter-loest-Rubik-s-Cube-und-braucht-nur-gut-eine-Sekunde-3083732.html > > Das ist doch der Hammer, oder? Kalter Kaffee, schau dir mal einen montage robotor in ner chinafab an. Oder einen SMD-Bestücker: da fliegen x-Mal mehr Teile pro sekunde an die richtige Stelle als bei so nem lumpigen Spielzeugwürfel.
Michael B. schrieb: > genügend Druck auf die Aussenflächen des Cube ausüben können, um ihn > auch ohne die Löcher zu greifen. dann wird er (wahrscheinlich) recht schnell so klemmen, daß er sich entweder nicht mehr drehen läßt oder bei entsprechender Gewaltanwendung den Geist aufgibt.
Nein wie unprofessionell, angesteuert von einem Arduino, igitt! :-)
Jojo S. schrieb: > Nein wie unprofessionell, angesteuert von einem Arduino, igitt! Kein Arduino, war nur ein ATMega auf Lochraster. :-)
Jojo S. schrieb: > Nein wie unprofessionell, angesteuert von einem Arduino, igitt! :-) Wenn man mal bedenkt wie "lahm" der Arduino so ist (der µC kann ja bei weitem mehr) sieht man: Was besonderes ist das schnelle Lösen nicht. Aber dass sich nix verkantet, das ist, wie schon gesagt wurde, das wirkliche Meisterwerk.
Würde mich nicht wundern, wenn ein Mensch das genauso schnell könnte. 1. Man hat vorsichtshalber den Würfel Maschinengerecht gemacht. (Minuspunkte) 2. Man hat den Würfel - keine Ahnung wie lange das wirklich dauert - bereits eingespannt. (Sehr viele Minuspunkte, ungültiger Vorsprung) Also solide Programmierung und saubere Konstruktion.
Michael K. schrieb: > Wenn man mal bedenkt wie "lahm" der Arduino so ist (der µC kann ja bei > weitem mehr) Das verstehe ich nicht.
Michael K. schrieb: > Wenn man mal bedenkt wie "lahm" der Arduino so ist (der µC kann ja bei > weitem mehr) sieht man: Was besonderes ist das schnelle Lösen nicht. Der Mikrocontroller löst aber den würfel nicht, sondern steuert nur die Motoren an. Lösen tut ein linux rechner der auch die Bildauswertung zur ermittlung der Anfangsposition übernimmt. Wie lange das dauert steht nicht im text, da ist nur die Rede eigentlichen drehen das etwa eine sec dauert. Wenn man bedenkt das in jedem fall 20 Züge zur Lösung genügen und darunter auch doppelzüge und Züge über unverbundene Ebenen fallen hat man eine Zugdauer (Vierteldrehung) von so 50 ms - die Motoren drehen sich also mit r rps - nicht sonderlich viel.
Über Links gedacht schrieb: > Wenn man bedenkt das in jedem fall 20 Züge zur Lösung genügen und > darunter auch doppelzüge und Züge über unverbundene Ebenen fallen hat > man eine Zugdauer (Vierteldrehung) von so 50 ms - die Motoren drehen > sich also mit r rps - nicht sonderlich viel. nur würde man mehrere stunden brauchen um die schnellste Lösung zu finden.
Über Links gedacht schrieb: > Wenn man bedenkt das in jedem fall 20 Züge zur Lösung genügen und > darunter auch doppelzüge und Züge über unverbundene Ebenen fallen hat > man eine Zugdauer (Vierteldrehung) von so 50 ms - die Motoren drehen > sich also mit r rps - nicht sonderlich viel. Der rechnet doch nicht bei jedem Zug. Der schaut sich einmal die Ausgangssituation an, berechnet die erforderlichen Bewegungsverläufe und dann gehts los mit maximal (mechanisch) möglicher Geschwindigkeit.
Peter II schrieb: > nur würde man mehrere stunden brauchen um die schnellste Lösung zu > finden. Nein, der Algorithmus ist bekannt und relativ einfach. Sonst könnten Menschen den Würfel nicht blind lösen.
S. R. schrieb: > Peter II schrieb: >> nur würde man mehrere stunden brauchen um die schnellste Lösung zu >> finden. > > Nein, der Algorithmus ist bekannt und relativ einfach. Sonst könnten > Menschen den Würfel nicht blind lösen. nein, sonst hätte man nicht Jahre gebraucht es zu beweisen. Wenn man es nach "Handbuch" löst, dann ist das nicht die kürzeste weg.
?!? schrieb: >> Wenn man bedenkt das in jedem fall 20 Züge zur Lösung genügen und >> darunter auch doppelzüge und Züge über unverbundene Ebenen fallen hat >> man eine Zugdauer (Vierteldrehung) von so 50 ms - die Motoren drehen >> sich also mit r rps - nicht sonderlich viel. > > Der rechnet doch nicht bei jedem Zug. Der schaut sich einmal die > Ausgangssituation an, berechnet die erforderlichen Bewegungsverläufe und > dann gehts los mit maximal (mechanisch) möglicher Geschwindigkeit. Nö, alles vor der bewegung zu berechnen ist dumm. Man spekuliert ein paar Züge und schaut ob die enstehende Situation näher am Ziel ist. Während man diese Züge ausführt spekuliert man parallel die nächste Sequenz und schaut wiederum bei welcher man dem Ziel näher gekommen wäre/wird. Die Kunst ist wie beim Schach die Stellungsbewertung -> bin ich mit diesem Muster näher an der Ordnung oder entferne ich mich davon.
Über Links gedacht schrieb: > Nö, alles vor der bewegung zu berechnen ist dumm. Man spekuliert ein > paar Züge und schaut ob die enstehende Situation näher am Ziel ist. > Während man diese Züge ausführt spekuliert man parallel die nächste > Sequenz und schaut wiederum bei welcher man dem Ziel näher gekommen > wäre/wird. nein, das geht nicht. Die Bewertung ist fast nicht möglich. Ich denke sie Lösen es nach dem typischen Anleitungen im Netz. Also erst die 1.Ebende dann die nächste usw. Am ende gibt es gewisse Zugfolgen um die Ecken oder Seiten zu tauschen.
Über Links gedacht schrieb: > Nö, alles vor der bewegung zu berechnen ist dumm. Man spekuliert ein > paar Züge und schaut ob die enstehende Situation näher am Ziel ist. > Während man diese Züge ausführt spekuliert man parallel die nächste > Sequenz und schaut wiederum bei welcher man dem Ziel näher gekommen > wäre/wird. > Die Kunst ist wie beim Schach die Stellungsbewertung -> bin ich mit > diesem Muster näher an der Ordnung oder entferne ich mich davon. In einem vollständig vorhersagbaren System (und ein solches ist der Würfel) ist dieses Vorgehen für einen Computer einfach nur dämlich.
Peter II schrieb: > Über Links gedacht schrieb: >> Nö, alles vor der bewegung zu berechnen ist dumm. Man spekuliert ein >> paar Züge und schaut ob die enstehende Situation näher am Ziel ist. >> Während man diese Züge ausführt spekuliert man parallel die nächste >> Sequenz und schaut wiederum bei welcher man dem Ziel näher gekommen >> wäre/wird. > > nein, das geht nicht. Die Bewertung ist fast nicht möglich. Warum sollte sie unmöglich sein? Der Computer muss einfach nur schauen wie viel Cubies schon richtig liegen. nach dem vorletzten Zug sind zwei gegenüberliegenden Flächen und alle Ebenen korrekt, nach den vorvorletzten Zug ist mindestens eine 2x2x2 Ecke korrekt und so weiter. das ganze ist nur eine variante des Pfannkuchenproblems: https://de.wikipedia.org/wiki/Pfannkuchen-Sortierproblem
Über Links gedacht schrieb: > Warum sollte sie unmöglich sein? Der Computer muss einfach nur schauen > wie viel Cubies schon richtig liegen. nach dem vorletzten Zug sind zwei > gegenüberliegenden Flächen und alle Ebenen korrekt, nach den > vorvorletzten Zug ist mindestens eine 2x2x2 Ecke korrekt und so weiter. genau das ist aber nicht der Fall. Die Anzahl der richtige Cubies sagt wenig über die Anzahl der verbleibenden schritte aus. Da mit einen Zug sich sehr viel ändert, kann es schnell sein wenn mehre ecke nicht stimmen als wenn nur eine Ecke nicht stimmt.
Jan H. schrieb: > In einem vollständig vorhersagbaren System (und ein solches ist der > Würfel) ist dieses Vorgehen für einen Computer einfach nur dämlich. Nööhh heutistische Optimierungsalgos sind clever, bspw: https://de.wikipedia.org/wiki/Simulated_Annealing https://de.wikipedia.org/wiki/Monte-Carlo-Algorithmus
Über Links gedacht schrieb: > Nööhh heutistische Optimierungsalgos sind clever, bspw: doch, es macht keinen sinn. Es wird vorher ein möglichst kurzer weg gesucht (für den kürzesten fehlt die Zeit) und dann wird gelöst.
Ich sehe grade, ich hab deinen ersten Beitrag falsch verstanden. Ich dachte du willst am Würfel drehen und dabei dann kucken ob's besser oder schlechter wird. Was ziemlich langsam wird. Was du in der digitalen Welt machst, bis du anfängst den Würfel zu drehen, dabei dürften Über Links gedacht schrieb: > Nööhh heutistische Optimierungsalgos sind clever, bspw: > > https://de.wikipedia.org/wiki/Simulated_Annealing > https://de.wikipedia.org/wiki/Monte-Carlo-Algorithmus auch gerne mal kürzere Lösungen geben als das “Handbuch“.
Jan H. schrieb: > In einem vollständig vorhersagbaren System (und ein solches ist der > Würfel) ist dieses Vorgehen für einen Computer einfach nur dämlich. Aso. Vielleicht kommt es ja auch drauf an, was man will. Was wenn die Suche nach der optimalen Lösung länger dauert als nach einer nicht-optimalen Lösung? Hier kommt noch hinzu: Selbst wenn die optimale Lösung relativ schnell gefunden werden kann, steht in dieser Zeit der Würfel still. Könnte man in dieser Zeit nicht vielleicht schon ein paar sinnvolle Züge machen, die auf einer suboptimalen Lösung basieren?
Peter II schrieb: > genau das ist aber nicht der Fall. Die Anzahl der richtige Cubies sagt > wenig über die Anzahl der verbleibenden schritte aus. > > Da mit einen Zug sich sehr viel ändert, kann es schnell sein wenn mehre > ecke nicht stimmen als wenn nur eine Ecke nicht stimmt. Naja es ist eine Frage wie man richtig liegen definiert. Richtig in bezug auf seine nachbarn beispielsweise. Denk einfach rückwärts, je mehr du einen Würfel verdrehst desto weniger "Päärchen aus richtigen" nachbarn gibt es. Natürlich kann es zugfolgen geben bei denen es zwischendurch unordentlicher wird. deshalb permutiert man ja auch meherer Züge und bewertet alle entsandenen Möglichkeit bevor man sich für eine sequenz entscheidet. halt wie das Gambit beim Schach.
S. J. schrieb: > Vielleicht kommt es ja auch drauf an, was man will. Was wenn die Suche > nach der optimalen Lösung länger dauert als nach einer nicht-optimalen > Lösung? richtig, dazwischen muss man Abwegen. > Könnte man > in dieser Zeit nicht vielleicht schon ein paar sinnvolle Züge machen, > die auf einer suboptimalen Lösung basieren? genau das ist das Problem. Wenn dann die schnellste Lösung gefunden wurden ist, steht der Würfel dann nicht mehr so und man muss im Zweifelsfall zurückdrehen.
Über Links gedacht schrieb: > Denk einfach rückwärts, je mehr du einen Würfel verdrehst desto weniger > "Päärchen aus richtigen" nachbarn gibt es. warum haben sich wohl jahrelang Leute und Computer damit beschäftig rauszufinden wie viele schritte man minimal braucht, wenn man es einfach bewerten könnte? Die Bewertung ist - wie viele schritte braucht man zum Lösen. Dafür braucht man seeeehr viel Rechenleistung.
Jan H. schrieb: > Ich sehe grade, ich hab deinen ersten Beitrag falsch verstanden. Ich > dachte du willst am Würfel drehen und dabei dann kucken ob's besser oder > schlechter wird. Was ziemlich langsam wird. > > Was du in der digitalen Welt machst, bis du anfängst den Würfel zu > drehen, dabei dürften Genau, züge vorausberechnen und stellung bewerten und dann drehen. Kann natürlich ein Computer wunderbar, während ein mensch sich eher mit bekannten zugfolgen von bekannter Verbesserung zu bekannten Verbesserung hangelt. So machen es auch die Schachcomputer, Permutation der Ausgangsstellung durch durchspielen legaler Zugfolgen und bewertung der so erzielten stellungen.
Peter II schrieb: > Die Bewertung ist - wie viele schritte braucht man zum Lösen. Dafür > braucht man seeeehr viel Rechenleistung. Nö, die Bertung ist nur um man weniger schritte von der neuen position braucht als von der Ausgangsposition, wieviel ist wurscht. wie im Wald, hauptsache es wird heller, wie heller ist wurscht.
S. J. schrieb: > Hier kommt noch hinzu: Selbst wenn die optimale Lösung relativ schnell > gefunden werden kann, steht in dieser Zeit der Würfel still. Könnte man > in dieser Zeit nicht vielleicht schon ein paar sinnvolle Züge machen, > die auf einer suboptimalen Lösung basieren? Wieviele Züge wird der Linux-Rechner in einer Millisekunde berechnen können? Da fällt die "Stillstandszeit" des Würfels nicht ins Gewicht. Um einen einzigen Zug zu machen, brauchen die Schrittmotoren auf jeden Fall länger als die Lösung des gesamten Problems dauert.
@Über Links gedacht Was du da über Lösen des Cubes erzählst ist kompletter Unsinn. Offenbar hast du vom Cube(n) absolut keine Ahnung.
@ Johann So ist es. Um den Würfel zu lösen, brauch man nur einen einfacher Algorithmus zu programmieren. Ein 8035 ist hinreichend. --- Hier noch ein Artikel zum Zauberwürfel: http://www.spektrum.de/magazin/rubik-spiele-mit-einfachen-gruppen/995466
Frank G. schrieb: > Mal fragen wie er es macht:Youtube-Video "Rubik's Cube World > Record 5.25 sec Collin Burns Slow Motion" > ;) Der schaut ja während des Lösens den Würfel an! Hier geht es doch darum, ob man allein durch Betrachten der Ausgangsposition ALLE Züge vorausbestimmen kann. Hier ein Beispiel: https://www.youtube.com/watch?v=0RfJbcydNJ0
Die grundsätzliche Frage ist: Wie schnell kann die Mechanik Züge ausführen. Daraus leitet sich dann der Algorithmus ab. Ist die Mechanik sehr schnell, kann man irgendeinen der suboptimalen 100-Züge Algorithmen verwenden. Ist die Mechanik langsam, lohnt sich der zusätzliche Rechenaufwand für eine optimalere Lösung (man hat ja die Zeit während die Mechanik noch arbeitet). Peter II schrieb: >> Könnte man >> in dieser Zeit nicht vielleicht schon ein paar sinnvolle Züge machen, >> die auf einer suboptimalen Lösung basieren? > > genau das ist das Problem. Wenn dann die schnellste Lösung gefunden > wurden ist, steht der Würfel dann nicht mehr so und man muss im > Zweifelsfall zurückdrehen. Müßte man ihn dann nicht immer(!) zurückdrehen? lach Natürlich müßte die optimale Lösung die entstehende Zwischenstellung als Ausgangsbasis nehmen. Über Links gedacht schrieb: > So machen es auch die Schachcomputer... Jo. Und jetzt überlege Mal was hier der Unterschied ist... ?!? schrieb: > Wieviele Züge wird der Linux-Rechner in einer Millisekunde berechnen > können? Da fällt die "Stillstandszeit" des Würfels nicht ins Gewicht. Dann erzähl mal wieviel Züge er in einer Millisekunde berechnen kann. Und wie kommst du jetzt gleich auf deine Schlußfolgerung? Aus deiner Frage??
:
Bearbeitet durch User
S. J. schrieb: > Dann erzähl mal wieviel Züge er in einer Millisekunde berechnen kann. > Und wie kommst du jetzt gleich auf deine Schlußfolgerung? Aus deiner > Frage?? Schau dir mal das verlinkte Video im obigen Beitrag an. So viel kann der Linuxrechner allemal. Es geht hier nicht um das sture Durchprobieren aller möglichen Züge, sondern um einen Algorithmus, der alle Züge im Voraus berechnet. Und wenn das ein Mensch durch einfaches Anschauen des Ausgangszustandes kann, dann kann das eine Software allemal.
?!? schrieb: > Schau dir mal das verlinkte Video im obigen Beitrag an. So viel kann der > Linuxrechner allemal. Es geht hier nicht um das sture Durchprobieren > aller möglichen Züge, sondern um einen Algorithmus, der alle Züge im > Voraus berechnet. Und wenn das ein Mensch durch einfaches Anschauen des > Ausgangszustandes kann, dann kann das eine Software allemal. ein Mensch kann das nicht! Der Mensch und die meisten Computer lösen stück für stück den Würfel. Das ist nicht der optimale weg. Für den Optimalen weg braucht man ein Rechencluster und viel zeit - das ist nicht mit einen kleinen Linux PC zu machen. https://de.wikipedia.org/wiki/Zauberw%C3%BCrfel#Optimale_L.C3.B6sungen https://de.wikipedia.org/wiki/Gottes_Algorithmus
Nachtrag: http://www.zeit.de/wissen/2010-08/rubik-zauberwuerfel-mathematik [...] Für menschliche Spieler, die sich an Zugfolgen halten, die sie auswendig gelernt haben, mag das stimmen. Sie benötigen meist sogar mehr als 40 Züge. Ein [...]
Peter II schrieb: > ein Mensch kann das nicht! Na wenn du meinst... Ich habs selber schon gesehen, aber wenn ein Mensch das nicht kann, dann hab ich eben phantasiert.
Peter II schrieb: > ein Mensch kann das nicht! > > Der Mensch und die meisten Computer lösen stück für stück den Würfel. > Das ist nicht der optimale weg. Für den Optimalen weg braucht man ein > Rechencluster und viel zeit - das ist nicht mit einen kleinen Linux PC > zu machen. Selbst in dem von dir verlinkten Wikipedia-Beitrag ist beschrieben, daß ein Mensch das DOCH kann. Der Rekord liegt bei 21 Sekunden. https://de.wikipedia.org/wiki/Zauberw%C3%BCrfel#Blindfold_Cubing Behauptest du immer noch, daß ein Mensch das nicht kann?
Peter II schrieb: > Für den Optimalen weg braucht man ein > Rechencluster und viel zeit - das ist nicht mit einen kleinen Linux PC > zu machen. Möglicherweise ist dann der Weg, der auf einem kleinen PC in ein paar Millisekunden ermittelt werden kann, optimaler als der "Optimale Weg"?
?!? schrieb: > Ich habs selber schon gesehen, aber wenn ein Mensch das nicht kann, dann > hab ich eben phantasiert. was hast du gesehen? Das ein Mensch jeden Würfel in 20 Zügen lösen kann? Oder das ein Mensch den Würfen sehr schnell lösen kann?
?!? schrieb: > Selbst in dem von dir verlinkten Wikipedia-Beitrag ist beschrieben, daß > ein Mensch das DOCH kann. Der Rekord liegt bei 21 Sekunden. > https://de.wikipedia.org/wiki/Zauberw%C3%BCrfel#Blindfold_Cubing > > Behauptest du immer noch, daß ein Mensch das nicht kann? ich bin scheinbar zu blöd zu lesen - wo steht das?
J.-u. G. schrieb: > Möglicherweise ist dann der Weg, der auf einem kleinen PC in ein paar > Millisekunden ermittelt werden kann, optimaler als der "Optimale Weg"? was willst du jetzt damit sagen? Ja es macht sinn nicht den schnellsten weg zu suchen, dafür aber sehr schnell EINEN weg zu finden. Genau das wird ja vermutlich dort gemacht.
Peter II schrieb: > ?!? schrieb: >> Ich habs selber schon gesehen, aber wenn ein Mensch das nicht kann, dann >> hab ich eben phantasiert. > > was hast du gesehen? Das ein Mensch jeden Würfel in 20 Zügen lösen kann? > Oder das ein Mensch den Würfen sehr schnell lösen kann? Daß ein Mensch einen von mir persönlich beliebig verdrehten Würfel in kurzer Zeit BLIND lösen kann, nachdem er sich den verdrehten Ausgangszustand angesehen hatte und dann die Augen verbunden bekam. Und das mehrmals, also nachvollziehbar. Auch das Verdrehen wurde nicht nur von mir gemacht, sondern von verschiedenen Personen. So wie es im Video zu sehen ist...
?!? schrieb: > Daß ein Mensch einen von mir persönlich beliebig verdrehten Würfel in > kurzer Zeit BLIND lösen kann, nachdem er sich den verdrehten > Ausgangszustand angesehen hatte und dann die Augen verbunden bekam. Und > das mehrmals, also nachvollziehbar. Auch das Verdrehen wurde nicht nur > von mir gemacht, sondern von verschiedenen Personen. So wie es im Video > zu sehen ist... das bezweifelt auch niemand. Ich habe nur geschrieben, das ein Mensch nicht den optimalen weg zu Lösung findet und mehr Drehungen braucht als notwendig. Genauso wie ein Computer wenn er nicht viel zeit hat.
Peter II schrieb: > ich bin scheinbar zu blöd zu lesen - wo steht das? Einfach den Link anklicken und da bist du schon beim richtigen Abschnitt. "Blindfold Cubing"
?!? schrieb: > Peter II schrieb: >> ich bin scheinbar zu blöd zu lesen - wo steht das? > > Einfach den Link anklicken und da bist du schon beim richtigen > Abschnitt. > "Blindfold Cubing" und da steht nichts von optimaler Lösung.
?!? schrieb: > Einfach den Link anklicken und da bist du schon beim richtigen > Abschnitt. > "Blindfold Cubing" Die Diskrepanz besteht im unterschiedlichen Verständnis von "optimal" (z.B. geringste Anzahl von Zügen, schnellste Zeit, usw., usf.).
Peter II schrieb: > das bezweifelt auch niemand. Ich habe nur geschrieben, das ein Mensch > nicht den optimalen weg zu Lösung findet und mehr Drehungen braucht als > notwendig. Genauso wie ein Computer wenn er nicht viel zeit hat. Ich habe nirgends was vom optimales Weg geschrieben, sondern daß ein Mensch das in kurzer Zeit blind lösen kann. Daraufhin hast du geschrieben: "Ein Mensch kann das nicht!" Fazit: Wenn das schon ein Mensch nach einmaligem Anschauen der Ausgangsposition in 21s blind lösen kann, dann kann das doch eine Software auf einem heutigen Rechner allemal im Millisekunden-Bereich.
Peter II schrieb: > und da steht nichts von optimaler Lösung. Habe ich auch niemals behauptet, siehe meinen obigen Beitrag.
J.-u. G. schrieb: > Die Diskrepanz besteht im unterschiedlichen Verständnis von "optimal" > (z.B. geringste Anzahl von Zügen, schnellste Zeit, usw., usf.). die "geringste Anzahl von Zügen" ist übliche Frage bei dem Würfel. Man könnte auch jede Lösung speichern - leider reicht dafür nicht mal die Google und Amazon cloud aus.
?!? schrieb: > Habe ich auch niemals behauptet, siehe meinen obigen Beitrag. du hast geschrieben > Wieviele Züge wird der Linux-Rechner in einer Millisekunde berechnen > können? Da fällt die "Stillstandszeit" des Würfels nicht ins Gewicht. Um > einen einzigen Zug zu machen, brauchen die Schrittmotoren auf jeden Fall > länger als die Lösung des gesamten Problems dauert. wenn er den Optimalen weg berechnet, dann braucht er länger als die Motoren.
Laß doch mal den "optimalen Weg" beiseite. Davon war doch niemals die Rede und ich habe auch nichts davon geschrieben. Fakt ist doch, daß selbst ein Mensch nur 21s braucht...
Johann L. schrieb: > @Über Links gedacht > > Was du da über Lösen des Cubes erzählst ist kompletter Unsinn. Offenbar > hast du vom Cube(n) absolut keine Ahnung. Naja, mit ein bißchen guten Willen lassen sich schon Lösungsansätze für den Zauberwürfel auf basis heuristischer Suche finden: http://www.aaai.org/Papers/AAAI/1997/AAAI97-109.pdf Hier würde die Manhattan Distanz als Metrik benutzt um die Position zu bewerten. Auch die IDA* Suche als weiter informierte Suche wird auf den Zauberwürfel angewandt: http://kth.diva-portal.org/smash/get/diva2:816583/FULLTEXT01.pdf Die engl. WP kennt noch etliche andere Computer-Lösungsverfahren: https://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube Mit der Aussage "kompletter Unsinn" wäre ich äußerst vorsichtig. MfG,
Peter II schrieb: > die "geringste Anzahl von Zügen" ist übliche Frage bei dem Würfel. Mindestens genauso üblich ist die Lösung in der geringsten Zeit (darum geht es doch bei den ganzen "Weltrekorden"). Ich stimme Dir zu, dass das Finden der geringsten Anzahl von Zügen erheblichen Rechenaufwand erfordert. Es zeigt sich mal wieder: Ohne Angabe von Randbedingungen ist die ganze Streiterei über eine "optimale Lösung" fruchtlos.
Um 2010 hat wohl ein PC ("a good desktop PC") gut 3s für die optimale
Lösung gebraucht. Für eine gute Lösung (<= 20 Züge) weniger als eine
Millisekunde.
Daß das relativ schnell geht liegt einfach daran, daß nachgewiesen ist,
daß sich jede beliebige Stellung in maximal 20 Zügen lösen läßt.
guest schrieb: > Um 2010 hat wohl ein PC ("a good desktop PC") gut 3s für die optimale > Lösung gebraucht. Für eine gute Lösung (<= 20 Züge) weniger als eine > Millisekunde. > Daß das relativ schnell geht liegt einfach daran, daß nachgewiesen ist, > daß sich jede beliebige Stellung in maximal 20 Zügen lösen läßt. Kannst Du bitte den Link hirfür schreiben? Ich such auch nach der Dauer für eine Lösung, werd aber aus den Kociemba nicht ganz schlau, was er für hardware verwendet hat. Jedenfalls nicht in 5 Minuten: http://kociemba.org/cube.htm
schlussendlich sollte man sagen: Problem gelöst, nächstes. Oder wer hält es für sinnvoll, weiter Maschinen zu entwicklen und zu bauen, die genau dieses Problem in 0,8 oder 0,7 oder gar 0,5 sec. lösen können? Vielleicht kann man diese vorhandene Maschine noch auf Energieverbrauch/Größe/Kosten optimieren. Aber jedwede Bemühung der zeitlichen Optimierung halte ich für reine Resourcenverschwendung.
Mike B. schrieb: > schlussendlich sollte man sagen: > Problem gelöst, nächstes. > > Oder wer hält es für sinnvoll, weiter Maschinen zu entwicklen und zu > bauen, die genau dieses Problem in 0,8 oder 0,7 oder gar 0,5 sec. lösen > können? > > Vielleicht kann man diese vorhandene Maschine noch auf > Energieverbrauch/Größe/Kosten optimieren. Aber jedwede Bemühung der > zeitlichen Optimierung halte ich für reine Resourcenverschwendung. oder größer Würfel https://de.wikipedia.org/wiki/Professor%E2%80%99s_Cube
Mike B. schrieb: > Aber jedwede Bemühung der > zeitlichen Optimierung halte ich für reine Resourcenverschwendung. Schon Gottes Zahl zu finden war sogesehen Verschwendung. Eine Maschine, die den Würfel löst war sicher nicht notwendig. Gebaut hat man sie trotzdem und warum? Weil man es kann.
Mike B. schrieb: > Vielleicht kann man diese vorhandene Maschine noch auf > Energieverbrauch/Größe/Kosten optimieren. Aber jedwede Bemühung der > zeitlichen Optimierung halte ich für reine Resourcenverschwendung. Ja, eigentlich ist das Problem seit 2010 gelöst, seit nachgewiesen ist das die optimale Lösung max. 20 hat. Ein sich selbst lösender Würfel wäre vielleicht noch spannend. Beispielsweise mit Motoren in den Zentralsteinen.
Dass das System nur aus dem Anfangszustand einmal die nötigen Züge berechnet, wird im Video gesagt, ebenso, welcher Algorithmus verwendet wird. Und dass die Berechnung nicht schon im Vorfeld stattfindet, wird durch das Abdecken einer der Kameras illustriert. Übrigens glaube ich, dass der Würfel auch leichtgängiger gemacht wurde. Er verdreht sich einmal in der Hand bei geringster Kraft. Cooles Teil, vor allem wegen der simplen, billigen Hardware.
Ein Wuerfel eines Wuerfel-Profis ist auch auf superleichtgaengig getrimmt. Die koennen mit minimal Kraft gedreht werden. Man erreicht das mit Ausleiern, zb am Akkuschrauber, und mit Sand.
butsu schrieb: > Dass das System nur aus dem Anfangszustand einmal die nötigen Züge > berechnet, wird im Video gesagt, ebenso, welcher Algorithmus verwendet > wird. Etwa 01:40, "Kociemba algorithm" Damit ist wohl das gemeint: http://kociemba.org/math/imptwophase.htm produziert eine Lösung mit etwa 30 moves. Ob wirklich alle Züge vor dem Start des Motors berechnet werden, wird nicht gesagt. Im Video läuft die PC-Anzeige und Motoren gleichzeitig. Es kann gut sein, das nach Phase 1 (12 moves) die Motoren anlaufen und parallel Phase 2 (18 moves) berechnet wird. Und die 30 Züge Variante von 1992 hat Kociemba inzwischen auch verbessern können. > Und dass die Berechnung nicht schon im Vorfeld stattfindet, wird > durch das Abdecken einer der Kameras illustriert. Ja illustriert, bewiesen ist durch das Ab-/Auf-Decken einer von vier Kameras nichts. Gut möglich das Kamera 4 nur das Startsignal liefert. Bei den anderen Läufen startet die Maschienerei auf Knopfdruck. Peter II schrieb: > Für den Optimalen weg braucht man ein > Rechencluster und viel zeit - das ist nicht mit einen kleinen Linux PC > zu machen. Die Berechnung (Kociemba) selber ist wohl grösstenteils Table-Lookup, also keine Hexerei und wurde vor über 20 Jahren auf einen Homecomputer implementiert. Also nix mit SuperDuper Rechencluster. http://kociemba.org/math/imptwophase.htm MfG,
Angeblich kann man durch genügend langes Ansehen des Würfels eine Lösung finden, die maximal 24 Züge dauert und nur auf Rotationen von 5 Seiten beruhen. Bei allen 6 Seiten sind es maximal 21 Züge, die man deterministisch ermitteln kann. Optimiert waren es sogar unter 20 aber nicht mehr deterministisch. Ganz gute Arbeit trotzdem.
Fpga K. schrieb: > Peter II schrieb: >> Für den Optimalen weg braucht man ein >> Rechencluster und viel zeit - das ist nicht mit einen kleinen Linux PC >> zu machen. > > Die Berechnung (Kociemba) selber ist wohl grösstenteils Table-Lookup, > also keine Hexerei und wurde vor über 20 Jahren auf einen Homecomputer > implementiert. Also nix mit SuperDuper Rechencluster. > http://kociemba.org/math/imptwophase.htm das ist aber nicht der weg mit den wenigsten (optimale) schritten.
Peter II schrieb: > Fpga K. schrieb: >> Peter II schrieb: >>> Für den Optimalen weg braucht man ein >>> Rechencluster und viel zeit - das ist nicht mit einen kleinen Linux PC >>> zu machen. >> >> Die Berechnung (Kociemba) selber ist wohl grösstenteils Table-Lookup, >> also keine Hexerei und wurde vor über 20 Jahren auf einen Homecomputer >> implementiert. Also nix mit SuperDuper Rechencluster. >> http://kociemba.org/math/imptwophase.htm > > das ist aber nicht der weg mit den wenigsten (optimale) schritten. Den hat er dann später auf einem PC implementiert, der mehr Speicher hatte als das eine MB des Atari ST. Die Rechendauer blieb weiterhin im Sekundenbereich. Wobei die Tabellen fürs lookUp (sicher) vorher berechnet wurden. Das steht alles unter den genannten Links,auch die Quelltexte, für die Berechnung der optimalen Lösung einer Konfiguration brauchts wirklich nicht mehr. Für den Nachweis das der algo für jeden Verdreher nicht mehr als x Züge braucht, muss man aber alle (signifikanten) Verdrehmöglichkeiten austesten. Da addieren sich die Sekunden zu (ca. 90) Rechenjahren auf und da macht sich der google cluster nicht schlecht. Aber für einen einzelnen verdrehten Cube reicht der Linux-PC völlig. MfG,
Tiefbohrer schrieb: > Das steht alles unter den genannten Links steht da wirklich das er immer die Optimale Lösung findet? Ich konnte davon auf der Übersicht Seite nichts find. Kannst du mal bitte zeigen, wo steht das das Verfahren immer die kleinst mögliche Anzahl von Schritten ermittelt?
Fpga K. schrieb: > Ob wirklich alle Züge vor dem Start des Motors berechnet werden, wird > nicht gesagt. Im Video läuft die PC-Anzeige und Motoren gleichzeitig. Es > kann gut sein, das nach Phase 1 (12 moves) die Motoren anlaufen und > parallel Phase 2 (18 moves) berechnet wird. Das kann natürlich sein und wäre je nach Rechenzeit auch sinnvoll, ändert aber nichts daran, dass zwischendurch nicht mehr evaluiert wird, ob der Lösung näher gekommen wurde, womöglich gar durch weitere Auswertung der Kameras, wie weiter oben spekuliert wurde. >> Und dass die Berechnung nicht schon im Vorfeld stattfindet, wird durch >> das Abdecken einer der Kameras illustriert. > > Ja illustriert, bewiesen ist durch das Ab-/Auf-Decken einer von vier > Kameras nichts. Gut möglich das Kamera 4 nur das Startsignal liefert. > Bei den anderen Läufen startet die Maschienerei auf Knopfdruck. Ein Video beweist prinzipiell nichts. Die Jungs sagen explizit, dass es so ist. Muss man natürlich nicht glauben, dann kann man aber auch alles andere bezweifeln...Und der Lauf mit abgedeckter Kamera wird ebenfalls per Tastendruck gestartet.
Auf Lego Mindstorms NXT 2.0 wurde mal ein Algorithmus implementiert, der den Würfel in maximal ca 30 Zügen löst (die exakte Zahl weiss ich nicht mehr). Zur Berechnung brauchte das Script maximal eine Minute. Wobei man bedenken muss, dass der Script-Interpreter super lahm ist. In einer einfachen Schleife addiert er eine Integer Konstante zu einer Variable mit ca 10.000 Wiederholkungen pro Sekunde. Wenn man nun berücksichtigt, dass ein PC mit jeder gängigen Programmiersprache mindestens 10.000 mal schneller ist, erübrigt sich die ganze Diskussion, wie schnell der Algorithmus ist. Wir reden hier von einem kleinen Bruchteil einer Sekunde. Die Berechnung ist absolut kein Hexenwerk. Wirklich nicht.
Stefan U. schrieb: > Die Berechnung ist absolut kein Hexenwerk. Wirklich nicht. wie schon mehrfach geschrieben - wenn man den schnellsten weg haben will ist es ein Hexenwerk. Um es einfach nur lösen braucht man gar nicht großartig rechnen.
Peter II schrieb: > Tiefbohrer schrieb: >> Das steht alles unter den genannten Links > > steht da wirklich das er immer die Optimale Lösung findet? Ich konnte > davon auf der Übersicht Seite nichts find. Da steht das in der verbesserten vVriante bei suboptimalen Lösungen nicht abgebrochen wird: "As already mentioned above, the algorithm does not stop when a first solution is found but continues to search for shorter solutions by carrying out phase 2 from suboptimal solutions of phase 1." http://kociemba.org/math/imptwophase.htm Für Korf's algorithmus wird ausdrücklich gesagt, das er immer die optimale Lösung findet: "Although this algorithm will always find optimal solutions, there is no worst case analysis." https://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube#Korf.27s_algorithm Und er nutzt IDA* nutzt also die skizierte Vorgehensweise von Abschätzen des Abstands zur Lösung und verfolgt nur die Abfolgen die näher ans Ziel führen: "Da nur die Länge des Weges vom Startknoten bis zum aktuell untersuchten Knoten exakt bekannt ist, wird die Weglänge vom aktuell untersuchten Knoten bis zum Zielknoten mittels einer Heuristik geschätzt." https://de.wikipedia.org/wiki/IDA* Also so wie ich es gestern beschrieb: Über Links gedacht schrieb: > Genau, züge vorausberechnen und stellung bewerten und dann drehen. > > So machen es auch die Schachcomputer, Permutation der Ausgangsstellung > durch durchspielen legaler Zugfolgen und bewertung der so erzielten > stellungen. Der Trick dabei ist das Problem in die Graphentheorie zu überführen (über das Erstellen des Zustandsgraph) und dann den kürzesten Pfad zum Ursprungszustand zu finden. Dass ohne Brute-Force zu erreichen gibt es mehrere Ansätze. Folgend ein deutscher Artikel der mal in das Problem der "Kürzester Weg-Algos" einführt: http://www.gm.fh-koeln.de/~hk/lehre/ala/ws0506/Praktikum/Projekt/E_gelb/ALA-HeuristischeAlgorithmen-Jena-Liebelt.pdf Johann L. schrieb: > @Über Links gedacht > > Was du da über Lösen des Cubes erzählst ist kompletter Unsinn. Offenbar > hast du vom Cube(n) absolut keine Ahnung. Ich betrachte diese Aussage als komplett wiederlegt.
Peter II schrieb: > Stefan U. schrieb: >> Die Berechnung ist absolut kein Hexenwerk. Wirklich nicht. > > wie schon mehrfach geschrieben - wenn man den schnellsten weg haben will > ist es ein Hexenwerk. Sorry, aber dein Beharren auf deine mehrfach wiederlegte Privatmeinung wirkt langsam kindisch.
Über Links gedacht schrieb: > Für Korf's algorithmus wird ausdrücklich gesagt, das er immer die > optimale Lösung findet:... Und da steht auch: > Although this algorithm will always find optimal solutions, there is no > worst case analysis. It is not known how many moves this algorithm might > need. > For random positions, it seems to average about 2.5 hours for a complete > search through 17 face turns, 31 hours for a complete search through 18 > face turns on my hardware Wie hast du herausgefunden dass man mit Korf's Algorithm auf einen Linux PC eine mechanische Lösung in gut einer Sekunde herbeiführt? > Der Trick dabei ist das... Genau. Deine Aneinanderreihung von Zitaten und Referenzen ohne konkreten Bezug auf das Thema. Den Cube mit seinen 4E19 Zuständen in einen Graph zu zerlegen auf einen Linux PC und dann eine Wegfindung starten... Schöner Trick. ;-)
:
Bearbeitet durch User
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.