Lehet kezdeni azzal valamit, hogy 128 darab tetszülegesen kiválasztott elemből ( 2 sarok, 28 oldal, 95-96 közép + 2-3 kulcs ) a tábla fele csak 1:10^35 eséllyel rakható? Ezzel viszonylag "gyorsan" szűrhető, hogy mely csoport nem illik az adott táblafélre. Persze kérdéses, hogy mennyire lehet lecsökkenteni egy-egy ilyen csoport méretét. Kívánatos az lenne, ha akár egy-egy elemről is megmondható lenne, hogy illik vagy nem illik az adott félre...
Az viszont még reménytelenebb, hogy kiderítsd mi a hatása egy puzzle-nak 10-20 él távolságra. Az esetek kb. 95%-ban már azt is képtelenség bebizonyítani, hogy két, egymástól 1 egység távolságra lévő tetszőleges puzzlenek van-e hatása egymásra. Abban a maradék 5%-ban meg leginkább olyan szituációk vannak példul, hogy két sarokelemet teszel le úgy, hogy a szürke részükkel forgatod egymás felé. Természetesen ilyenkor nem találsz közéjük illő elemet.
Én úgy érzem backtrack-el reménytelen, mégha bele is írunk ilyen shortcut-okat.
Vagy valami olyan módszer kell bele szerintem, ami ha egy elemet lerakunk, hatással van az összes elemre valamilyen módon. A sima backtrack csak azt nézi, hogy tud e még lerakni, vagy sem, de nem használ fel információt arról, hogy a többi elem "mit csinál" éppen. Erre kéne valamit kitalálni.
Hm... olyasmin nem gondolkodtatok, hogy hogyan lehetne csökkenteni a backtrack módszerrel bejárandó lépések számát? Ugyanis akármennyire rossz a backtrack, még nem találtam nála használhatóbb módszert. Viszont egyértelműen bizonyítható, hogy ha nem alkalmaz az ember valamiféle redukciót, akkor nincs az a számítási kapacitás amivel megoldható lenne a feladat. Példaképp valami ilyesmire gondolok:
A sárgával jelölt mezők jelzik, hogy az algoritmus hová pakolt le darabokat. Az utoljára lerakott darab éppen az 56-os. A darab lerakása után ugyan tudna még a program rakni az 57-es, 58-as, 59-es stb. mezőkre is egy-egy puzzle-t, de ennél a pontnál mégis visszafordul, mert ellenőrizte a piros kereszt által fedett élek színkombinációját. Az pedig tiltott, ugyanis a kék terület nem kitölthető ha a közepén ez az élkombináció szerepel. Ehhez a módszerhez, természetesen némi előkaluláció szükséges. Viszont így részszámításokra is lehet támaszkodni és legalább néhány esetben elkerülhető, hogy ugyanazt a csapdát újra és újra bejárja a program.
A fenti négy élből álló alakzat akár 34 mezővel korábban is visszafordíthatja a keresést. Persze csak elméletileg, sajnos ez nem túl hatékony figura. De ezt most csak példának szántam. Egyébként nagyon könnyen megvalósítható és lépésenként rendkívül kevés időt pazarló eljárás. A memóriaigénye sem túl vészes, legalábbis a fenti figurának. Mert ugye 225 ilyen "kereszt" írható fel és mindegyikhez max 83521 (17^4) kombináció tartozhat. Ez olyan 2,5MB memóriát igényel. Sajnos a komolyabb, hatékonyabb, több élből álló figurák már több helyet foglalnak. Cserébe a nem csak több esetben fordítanak vissza, hanem messzebbre is látnak.
Előkalkulációként a "kereszt" esetében elég minden egyes lehetséges ellenőrzési pozíciónál a kékkel jelölt 6x6-os területen a 83521 kombináció kirakhatóságát ellenőrizni. A területen kívül eső további puzzle-ok illesztgetése már nincs hatással a használható élek számára.
Érdekes ez a fehérjeláncos módszer. Én is azon töprengtem, hogy van e olyan kémiai/fizikai módszer, ami megfeleltethető a problémának (azonos minták vonzák, ellentétesek taszítják, 23 különböző vonzástípus és egy elemnek 4 pólusa van), de nem tudok ilyenről.
Keresünk egy szabályrendszert, ami azt tudja, hogyha két elemet egy véletlen elrendezésben közelítünk egymáshoz, akkor az összes többi elem állapota (mondjuk helyzete) is valamiképpen megváltozik. Ezt tudja pl. az a kis egyszerű dinamikai modell, amit leírtam. Az a kérdés, hogy van e olyan szabályrendszer, ami úgy tudja módosítani az összes elem állapotát, hogy a bekövetkezett változásokból következtetni lehet arra, hogy a két elem, amit közelítettünk egymáshoz, az a teljes megoldásban szomszédos e, vagy sem. Mert ha van egy ilyen szabályrendszerünk, akkor meg van a megoldás is. De hogy valójában létezik e ilyen szabályrendszer, arról fogalmam sincsen.
Hat ja, a kerdes tenyleg az, hogy tudunk-e jol valogatni, van-e ra modszer (ott a Hamilton-kornel is kell hogy kulonbozok legyenek, es valami utalas volt hogy lehet). Raadasul a cikk lanckepzesrol szolt, itt meg halo kellene...
Ötletes elképzelés a számítási kapacitás növelésére. Rengeteg fehérjével rengeteg műveletet lehetne párhuzamosítani. Azért vannak kétségeim az elképzelést illetően. Legalábbis, nekem úgy tűnik, mintha olyasmiről lenne szó, hogy rázzunk össze több millió doboznyi Eternity II puzzle-t, majd öntsük ki egy rendező asztalra és megkapjuk a megoldást. Mi van, ha egyforma elemek is lesznek az adott képletben?
Azert a 240 lerakasa nem ugyanaz, mert ott nem veszed figyelembe a tobbi elem tavolsagat, csak az elso 240-et. De teny, hogy gyanus, hogy "magatol" nagyon messze lenne az elso stabil minimum is a keresettol. [Na igen, erre az eternitys problemara az a kb. 10 eve hallott modszer lenne jo, amelyik valami biologiai reszecskekkel manipulalt. A leiras valamelyik NP-teljes grafos problemara volt, talan a Hamilton-kor keresesere. Bar nem hiszem, hogy hasznaltak, lehet hogy csak elmelet volt. Szoval feherjelancokra epult, es a feherjelancokat tudtak valami modszerrel tulajdonsagokra szurni. Eloszor is olyanokat kell keresni, hogy barmely ket feherje pontosan akkor tudjon kapcsolodni, ha az elek amiket reprezentalnak egy csucsban talalkoznak. Ezekbol a reprezentalo izekbol kell rengeteget gyartani, osszekeverni, aztan kapcsolodjanak ahogy akarnak, ez kb. konstans ido. Aztan a kapott lancokbol allitottak, hogy lehet szurni: pont megfelelo hosszuakat vagy levagdosni megfelelo hosszura, elejen-vegen osszekapcsolhatoakat, csak kulonbozoket tartalmazoakat stb. megtartani, es a vegen csak "le kell olvasni", hogy amelyik megmaradt, az mint minden feltetelre illeszkedo az megoldas, na az mit reprezental. Sajnos csak egy angol nyelvu fenymasolatom volt a dologrol, es azt se tudom hol van most mar, igy eleg homalyos emlekeim vannak csak rola.] Mondjuk gyanithato, hogy ha ez a gyakorlatban megoldhato lenne, mar biztos eszebe jutott volna valakinek es lenne megoldas...
Az a probléma az Eternity II-nél, hogy ezek a "hegyek-völgyek" elképzelhetetlenül nagyok. A táblára lerakható akár 240 puzzle is úgy, hogy minden illeszkedik mindennel mégis az összes rossz helyen van. Vagyis szinte teljesen előlről kell kezdeni a mókát.
Tehet olyan algoritmus kell ami garantáltan képes bejárni az összes hegyet-völgyet. Ehhez jó a véletlen mutációs dolog, de ettől még bőven előfordulhat, hogy ugyanazt a völgyet járod be sokadszor, míg egy csomó másikat még nem is láttál. A másik lehetőség, hogy nyílvántartjuk, legalább részben, hogy mely völgyek voltak már bejárva. Ez viszont iszonyatosan sok RAM-ot igényel. A sok adat átböngészése meg nagyon sok időt... Nem jó ez így. :)
Ja! Akkor ott tevedtem el, hogy azt hittem, egyesevel pakolgatsz. En elsore ugy nezem, hogy rengeteg szuboptimalis lokalis szelsoertek lehet, akar ugy is, hogy azok (egy resze) stabil: kis kimozdulas ugyanoda visz vissza. (Mint egy golyo egy nagyon hegyes-volgyes asztalon a legmelyebb lyukba igyekezne, de barmelyik eleg szeles lyukbol kis valtozassal nem tudsz kijonni.) Nem biztos, hogy ilyen tipus, de ha igen, ilyenkor szoktak veletlenszeru mutaciot hozzaadni (1 nagy valtozas) a helyi szelsoertekre beallaskor, es azt hiszem egyutt vizsgaljak par lepesig, amelyik jobb lesz, az marad meg a kovetkezo mutacioig.
Úgy képzeld el a dolgot, hogy kiszórod az asztalra az összes puzzle darabkát jó szellősen, majd megpróbálod elképzelni, hogyha hirtelen az azonos minták vonzanák egymást, a különbözők pedig taszítanák, akkor mi történne az asztalon. Elvileg ekkor a puzzle-k mindaddig mozognának, amíg az összes táblán található erő ki nem egyenlíti egymást. De ez (azt gondolom) egy instabil állapot lesz, mert bármilyen kis "külső" változtatástól az egész felborul és átrendeződik.
A helyesen kirakott táblát azért gondolom stabilnak, mert ekkor minden elemet a 4 irányból 4 másik határol, így ezek között a vonzerők kiegyenlítik egymást. Ez tehát valamiféle egyensúlyi állapot, amin (talán) az elemek felett mozgó "átmágnesező" minta sem tud változtatni.
Az lenne a jó, ha az átmágnesezéssel valahogy azt lehetne elérni, hogy az összes elem által határolt terület nagysága folyamatosan csökkenjen. A legkisebb lehetséges terület ugye maga a 16x16-os négyzet, mivel ekkor nincs "tér" az elemek között.
(Azt nem látom még, hogy a puzzle-ek mozgásakor megengedhető e, hogy a puzzle-k egymásra csússzanak (átlapolódjanak), vagy csak síkban tudjanak mozogni és úgy taszigálnák egymást.)
Valoszinuleg nem ertem jol, mert ezt nem latom igazolva abbol, amit erteni velek: "Elvileg a helyesen kirakott tábla stabil állapot, amin a próbaminták nem változtatnak." Tegyuk fel, hogy a jol kirakott tablabol fenthagysz 32 darabot. Veszel egy tetszoleges 33. darabot. A 33.-nak a tablara gyakorolt hatasat nezed, vagy a tablan levo 32 hatasa alapjan keresed a 33.-nak a legvaloszinubb helyet? En egyik esetben se latom, hogy mi es miert lenne stabil (de hangsulyozom, valamit en nem ertek vszinu). Mi lenne ha kiprobalnad az algot a kulcspuzzle-okon? Vagy egy sajat magad altal generalt kicsi (de a nagyhoz hasonlo tulajdonsagu: nincs ismetles, szinek eloszlasa a "legnehezebb") palyan?
Én úgy képzelem, hogy egy kis változás (egy elem arrébb mozgatása) is elég kaotikusan módosítaná a tábla állapotát, úgyhogy ismétlődés valószínűleg nem lenne. Inkább az a kérdés, hogy konvergálna e valahova a dolog, vagy tök összevissza módosulna a tábla a végtelenségig.
Dolgozik még valaki a kirakóson?;-) Valami ilyesmin gondokoztam, valszeg nincs túl sok értelme: Az elemek kezdetben véletlenszerűen helyezkednek el a táblán (a fix elemek, belértve a keretet, a helyükön vannak). Az azonos minták vonzó erőt jelentenek két elem között, és az erő nagysága fordítottan arányos az elemek távolságának négyzetével. A különböző minták taszítják egymást. E szabályok alapján az elemek elfordulnak, gyorsulni kezdenek, és egy instabil poziciót vesznek fel a táblán. Ez még nem a kirakott állapot. Veszünk egy "próbamintát", és a tábla felett körözni kezdünk vele állandó sebességgel, aminek hatására a táblán az elemek folyamatosan átrendeződnek. (Valahogy úgy, mint amikor a régi képcsöves tv elmágneseződik, és egy mágnessel körözve eltüntetjük a képhibát). Egyszerre több próbamintával is körözhetünk véletlenszerűen. Elvileg a helyesen kirakott tábla stabil állapot, amin a próbaminták nem változtatnak. Eddig jutottam a gondolatmenettel;-) Talán annyit tesz hozzá a különböző próbálgatós módszerekhez, hogy itt egy kis változtatás az összes elemre hatással van, és az egész tábla állapotát megváltoztatja.
"Szerencsére" az Eternity II magyar honlapját még ritkábban frissítik, mint az angolt viszont továbbra is elérhető. Itt nyugodtan vissza lehet keresni az eredeti ajánlott árakat...
Eternity II: 8.990,-
72 darabos kulcs: 5.290,-
36 darabos kulcs: 4.190,-
Egyébként nekem is olyan 9 ezer körüli ár rémlik a 256 darabosra. Egy hazai on-line játékboltból rendeltem... és valami 2-3 ezer volt még a postaköltség.
Miert nem nyilvanvalo ebbol, hogy akik honapokkal ezelott azt allitotta, hogy kiraktak, azok csak kamuztak? Szerintem azt senki nem fogja bevenni, hogy nem akartak bekuldeni, vagy bekuldtek de nem ert oda. Legfeljebb bekuldtek, de hibas volt, de ez azert valoszinutlen, mert egyszeru az ellenorzes.
Sajnos nem lehet tudni biztosan, hogy az ELTE csapata valóban kirakta mint ahogy azt sem, hogy másnak sikerült-e. Mindenesetre az EternityII hivatalos honlapján ( http://www.eternityII.com ) a legutolsó hír az, hogy 2009. december 31-ig még nem küldtek be teljes megoldást. 2010 december 31-ig biztosan él még a díj.
Üdv! Már lehet tudni biztosan, hogy az ELTE csapata valóban kirakta? És még az érdekel, hogy honnan lehet megtudni sikerült-e valakinek, iletve ha nem, akkor hosszabítanak az eddigi határidőn?
A hétvégén megírtam a tanító algoritmust a kirakósomhoz, és egész érdekes dolgot tapasztaltam: 2 különböző gépen indítottam el a programot úgy, hogy csak adatokat gyűjtsenek: azt vizsgálják, hogy a random kirakózás során melyik elemek szeretnek legtöbbet egymás mellett lenni ("szimpátia"). Sajnos a programom elég lassú, mert java-ban írtam, és az adatgyűjtés is lassít rajta, így egy éjszaka kb. 300000000 lépést tud végrehajtani (szóval tényleg lassú:) Viszont amikor elemeztem a két gépen az adatokat, azt találtam, hogy meglepően hasonló az egymásnak "szimpatikus" elemek eloszlása! Pl. 1. gép: <piece num="131"> <friend num="199" sympathy="0,05" time="14313308"/> <friend num="122" sympathy="0,04" time="13003119"/> <friend num="103" sympathy="0,04" time="12657861"/> <friend num="104" sympathy="0,04" time="11329099"/> <friend num="169" sympathy="0,04" time="10516926"/> (...)
A két xml részleten az látszik, hogy a 131-es elem melyik elemek mellett szeretett leginkább felbukkanni. Látszik, hogy az első 5 elemből 3 ugyanaz úgy, hogy amúgy a "friend" lista több mint 100 elemet tartalmaz! És ez kb. az összes elemre így van!
Persze biztos nem jelent ez sem túl sokat a teljes kirakás szempontjából, esetleg az is lehet, hogy rossz a programom:) De legalább valami új érdekesség.;-)
Nem akarlak lebeszélni a tanítgatós algoritmusról, de talán érdemes megjegyezeni, hogy ez a módszer is csak lokális maximum keresést végez. Vagyis segít abban, hogy minél több jól lerakott darab legyen a táblán, de semmi nem garantálja, hogy ez egyben a globális maximum ( teljesen kirakott tábla ) része. Ugye, hiába rakosgat le a program 240 darabot jól a táblára, ha a maradék 16-ot akárhogy is variálja nem tudja kirakni az egészet.
Sajnos a backtrack-re épülő módszerek nem elég hatékonyak. Szerintem, ha egyszer lesz is megoldása ennek a játéknak, akkor azt egy olyan módszerrel fogják megtalálni ami úgymond egyszerre dobja ki a jó megoldásokat. Gondolok itt pl. valamiféle faktorizáción alapuló eljárásra vagy olyan egyenletrendszerre, mátrixra, aminek az elemei leírják az összes puzzle lehetséges rotációit, pozícióit és azok kapcsolatait.
Egyébként a generátor oldali megközleítés ( mikor a program generál egy táblát és ott próbálja úgy cserélgetni a színeket, hogy minél jobban hasonlítson az eredeti puzzlera ) is ugyanezt a backtrack-es csapdát rejti. A Yahoo Groups eternity_two topikjában régebben felmerült pár ötlet a globális maximum keresésre, de sajnos mindegyikről kiderült, hogy olyan erőforrásigényes ( memória, számítási kapacitás ) amit nem lehet biztosítani.
Azért remélem, hogy valakinél előbb-utóbb csak lángra kap egy isteni szikra. :-)
Csak a kirakós algoritmust írtam meg régen, az fut szépen: http://huzoka.atw.hu/eternity A tanítót kéne megírni hozzá, de már azt se tudom hol a kód. Lehet, hogy majd megkeresem:)
Szia, Tesztelted az algoritmusodat? Készítesz egy E2-höz hasonló kirakott táblát. Elemeire bontod, és megnézed, hogy az algoritmusod az elemilleszkedésre jó eredményt ad-e? Üdv
Még annyit talán hozzá, hogy nem teljesen légből kapott ötlet az együtt töltött idő szerint osztályozni a szomszédos elemeket. A kirakó algoritmus szabályából következik, hogy: 1. Minél több időt tölt egyhuzamban a táblán két szomszédos elem, annál nagyobb valószínűséggel van lent sok elem a táblán. (Azért, mert valószínűleg egy nagyobb blokk belsejében van éppen mindkettő). 2. Minél tovább van a táblán két szomszédos elem, annál nagyobb valószínűséggel szereti a többi elem, hogy ők együtt vannak:) Tehát ha sokáig vannak együtt, az azt jelenti, hogy több nagyobb blokk alakul ki/át folyamatosan a táblán. Ha nem lennének nagyobb blokkok, akkor a kirakó algoritmus nagy valószínűséggel gyorsan szétszedné a szomszédos elemeket.
Én egy "öntanítós" kirakón törömtem régen a fejem, leírom, hátha valaki ihletet kap belőle. Kirakó algoritmus: Az első lépés kész van, azt már rég megírtam. Ez egy random kirakó, ami dobálja le a táblán a szabad helyekre az elemeket úgy, hogy ne legyenek hibásan érintkező szomszédok. De rakhat le elemet olyan helyre is, ami nem érintkezik még semmivel. Ha nem tud már több elemet lerakni, akkor kisorsolja, hogy melyik elemet vegye fel a tábláról, de azzal a szabállyal, hogy nagyobb valószínűséggel vesz le olyan elemet, amelyik minél kevesebb éllel érintkezik a többivel. Utána megint próbál lerakni a "talon"-ból új elemet, és így tovább. Ezzel az egyszerű szabállyal viszonylag gyorsan sikerül 230-240 elemet helyesen lerakni a táblára.
Tanitó algoritmus: A kirakó algoritmust futtatjuk x. napig úgy, hogy közben rögzítjük minden elemre, hogy mely szomszédos elemekkel szeretnek leginkább "párosodni":). Tehát pl. vesszük a 193-mas elemet, és letároljuk, hogy a 152-es elem állt időben a legtöbbet mellette, az utána a 164-es elem volt a leggyakoribb, stb. Ezt minden elemre megcsináljuk. Abban reménykedhetünk, hogy ez az időbeni eloszlás a szomszédos elemekre szór valamennyire, azaz vannak elemek, amik többet szeretnek egymás mellett lenni, mint a többiek. Ha ez tényleg így van, akkor az 1. lépés kirakóját úgy módosítjuk, hogy belevesszük lerakó szabálynak, hogy olyan elempárokkal ne is próbálkozzon, amik legkevésbé szeretnek egymás mellett lenni. Utána megint futtatjuk a kirakót x. napig, aztán megint módosítjuk a szabályokat, stbstb.
És közben reménykedhetünk, hogy az egész konvergál valahova:)
Körkörös megközelítés? Ez egy útvonalmódosítást takar?
Én annak idején úgy írtam meg a programot, hogy egy fájlból olvassa be az útvonalat ( min.: 1, max.: 256 pozíció ) és a megoldó rutin azt adta vissza, hogy hányféle módon tudta bejárni az adott útvonalat az útvonalban szereplő mezőkre alkalmazható darabokkal. Természetesen a teljes, 256 elemű útra sosem kaptam választ ( hi-hi ). De a kisebb 1-25 elemű részletek összes kombinációit képes volt tűrhető időn belül ( kevesebb mint 1 nap ) kiszámolni.
