Prijavi se z GoogleID

» »

Algoritem za rešitev Rubikovih kock vseh velikosti

Algoritem za rešitev Rubikovih kock vseh velikosti

New Scientist - Reševanje Rubikove kocke je priljubljeno opravilo, ki ni primerno le za kratkočasenje, ampak ima tudi povsem resne matematično-računalniške implikacije. O klasičnih Rubikovi kocki 3 x 3 x 3 je znano domala vse, saj obstoji tudi algoritem, ki za vsako legalno postavitev izračuna najhitrejše zaporedje korakov za rešitev kocke. Lani je bilo celo dokazano, da je vsako kocko mogoče rešiti v največ 20 potezah. Dokaz je bil zanimiv tudi zato, ker je šlo za surovo preverjanje vseh možnih permutacij (brute-force).

Pri kockah večjih razsežnosti to odpove, zato je treba problem reševati pametneje. Erik Demaine z MIT-a je poiskal splošni algoritem za reševanje Rubikove kocke s stranico n. Ugotovil je, da število korakov iskanja proporcionalno z n2 / ln n. Dosedanji rezultat O(n2) je temeljil na zaporednem premikanju skupin štirih polj (2 x 2), Demaine pa je ugotovil, da je mogoče hkrati premikati več takih skupin.

Tovrstne raziskave imajo poleg akademske zanimivosti tudi povsem uporabno vrednost, saj se temu problemu sorodni pojavljajo tudi pri sortiranju, razvrščanju ali iskanju nekaterih setov podatkov v računalništvu.

7 komentarjev

MrStein ::

Ugotovil je, da jih je v splošnem mogoče rešiti v največ n2 / ln n korakih.

Če vstavim n=3, dobim 8 cela nekaj, kar se ne sklada z omenjenimi 20 potezami.
Sem kaj spregledal?
Motiti se je človeško.
Motiti se pogosto je neumno.
Vztrajati pri zmoti je... oh, pozdravljen!

joebanana ::

Mogoče konstanto. V O notaciji se konstant ponavadi ne piše.

Nanthiel ::

Pisec novice ja naredil napako. V origialnem članku se uporablja "proportional to ..." = O notacija. Formule za točno število še niso uspeli odkriti.

lmfao ::

kr neki...kaj pa če je konstanta 1000?

Thomas ::

Tudi če je 1000, glavno da je konstanta. Tako tale O() notacija dela. Pa sploh ni to tako neumno, kakor morda zgleda laikom.

Pri kocki veliki kt Vesolje, s kubični milimeter velikimi subkockicami, se 1000 sploh ne pozna.
Man muss immer generalisieren - Carl Jacobi

Mavrik ::

lmfao je izjavil:

kr neki...kaj pa če je konstanta 1000?


Tudi če je konstanta 1.000.000 ti bo zahtevnost izvajanja naraščala kvadratično glede na vhod (pri dovolj velikem vhodu). Domače branje.

Hvala vsem za opozorila o napakah v novici.
The truth is rarely pure and never simple.

bMozart ::

1000x1000x1000

(pozor: nadležna muska zraven :D )
I NEED The Point of View Gun effectible on girls too! And then...


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Rubikova kocka (strani: 1 2 )

Oddelek: Loža
5414182 (2680) mailer
»

[Kje kupiti] Rubikova kocka

Oddelek: Loža
258125 (4159) DOOM_er
»

Patenti za vedno

Oddelek: Novice / Industrijska lastnina
132206 (2206) Tilen
»

Vprašanje glede Rubikove kocke

Oddelek: Loža
81410 (1113) GUFY

Več podobnih tem