Dag 3

Deze dag hebben wij het Thistlethwaite's Algorithm én een ZZ achtige methode geïmplementeerd.
Over het Thistlethwaite's Algorithm. Één cube kan in een bepaalde 'groep' worden gezet. Een willekeurige cube staat in de groep G0 = < L, R, F, B, U, D>. Dit betekent dat van iedere zijde iedere mogelijke beweging gemaakt worden mag. In het originele algoritme wordt er als volgt door de groepen gewerkt:

G0 = < L, R, F, B, U, D >

G1 = < L, R, F, B, U2, D2 >

G2 = < L, R, F2, B2, U2, D2 >

G3 = < L2, R2, F2, B2, U2, D2 >

G3 is duidelijk een hele kleine groep, hier zijn nog slechts 6 bewegingen mogelijk. Zouden wij 7 bewegingen diep kijken, en gebruik maken van next/2 of next/3 dan zou de complexiteit zijn: 76 441 ( 6 * 5 * ( 1/5 * 4 + 4/5 * 5 ) wat natuurlijk heel veel kleiner is dan de aller lompste methode (machten van 18) die 612 220 032 permutaties zou betekenen.

Voor de overige groepen is er een vergelijkbare berekening mogelijk, die zal ik aan jullie laten ;)

Wij hebben een kleine aanpassing op dit algoritme gemaakt, wij zetten de cube in de < L, R, F, B, U2, D2 > groep en dan meteen in de < L2, R2, F2, B2, U2, D2 > groep.

Voor ons project is dat voldoende want het plaatsen van die extra groepen tussendoor is een koud kunstje als je eenmaal door hebt hoe het werkt.

--- Even tussendoor; Sorry als de informatie in deze blog erg hard gaat, maar wij hebben nou eenmaal heel veel kennis in dit domein en tijdens dit project nog meer kennis opgedaan. Alles in detail uitleggen is geen optie omdat er voor sommige stukjes nou eenmaal wat kennis verondersteld wordt die wij niet 1,2,3 bij jou kunnen leveren. ---

Voor de ZZ methode van Zbigniew Zborowski hebben wij eveneens aanpassingen gedaan. Van de EO+line hebben wij EO gemaakt. Dit is de eerste fase.

Wij vervolgen in de < L, R, F, B, U2, D2 > groep om een 2x2x2 block te maken.

Daarna blijven wij de in de < L, R, F, B, U2, D2 > groep naar een oplossing zoeken.

Hierdoor hebben wij duidelijk een orient-first methode gecombineerd met een blockbuilding methode (denk aan de Ryan Heise methode).

Ons inziens zou het een goede methode zijn om EO+line te doen om vervolgens in een bijzondere groep te komen (en te blijven) namelijk < U, XD, XF, XB, R, L > ofwel < U, R, L >

Deze groep heeft 3 * 3 bewegingen, maar vanwege de manier waarop next/2/3 in elkaar zitten zou de complexiteit 9 * 6 * 4 * 4 * 4 * ... zijn ( (1 / 3 * 6 + 2/3 * 3) = 4 ) . Let natuurlijk dat een computer x,y,z neutraal is en dat EO+line geen diepe ruimte zal zijn.

Zou er genoeg tijd zijn dan zou het heel leuk zijn dit verder uit te werken.

Ná deze week begint onze vakantie en kunnen wij écht leuke dingen gaan doen!