Egy volt kollégám és jó barátom hívta fel a topic-ra a figyelmem.
Azt kérdezte: "Nem lenne megoldás simán egy backtrack?"
A válaszom röviden: De!
Mint ahogy azt szemet felismerte ez felfogható CSP nek IS. Ami megoldható backtrack-kel IS. (Lásd 8 királynő probléma.)
Többen próbálták -feltehetően az analízis, lineáris algebra és hozzákapcsolódó tárgyak magas számának betudhatóan -lineáris egyenletrendszerre visszavezetni.
A használatához minimum azt kéne belátni, hogy az alaphalmaz egy számtest.
A testaxiómának teljesülni kellene amihez minimum két műveletre zártnak kellene lennie.
Ha a sima összeadást néznénk a topic indításban zártnak bizonyult szorzás mellé akkor nyilvánvalóan nem működne.
(-1) + 1 = 0 tehát kipukkad a lámpa és ugyan így hozható létre új.
Lehet ügyesen definiálni másik műveletet hozzá. Sok szerencsét! A 3 értékű logika úgyis hanyagolva van egy ideje.
A gráfos megoldásoknál az éllistás mátrix nem teljes itt is visszaüt a 3 értékű logika. És visszajutottunk az előző megoldáshoz.
(Ha telített a téglalap lámpával akkor 0 nem fordul elő és bool ÉS és VAGY műveletekkel kész a test.)
NagyZ helyében Én jól beletúrnék a formális nyelvek jegyzeteimbe.
"Igazán csodálatos bizonyítást találtam..."
Adott egy bizonyos számú lámpa. Legyen n a lámpák száma.
Ezek el vannak helyezve bárhogy. Fent úgyis le lett írva hogy az egymás melletti lámpák partíciókat alkotnak.
Én hozzáteszem, hogy partíciónként párhuzamosítható a megoldás.
Legalább egy partíció mindig létezik. Minden partíció megoldható ugyan úgy. Továbbá egy partíció megoldását írom le.
Egy lámpának a változása leírható a kiinduló állapotával, környezetével,a saját és környezete változásával. Ezek lesznek a szabályok.
(Állapot+ környezet -> Új állapot + új környezet)
Ez véges halmaz tekintve hogy véges az lámpa-állapotok száma és véges a szomszédok száma.
A partíció állapota az őt alkotó lámpák állapotai és a lámpák "összefüggései"(=helyzetei).
A partíció állapotai között csakis a fenti szabályokkal lehet átmeneteket képezni.
(Pl.: Átmenet = Állapot -> Egy tetszőleges lámpa átállítása és szomszédainak változása a régi állapotban)
Ez fent úgy hangzott el, hogy "...egy lámpa állapotát nem befolyásolja a saját, illetve élszomszédjain kívüli lápmák állapota és kapcsolása.".
A különböző állapotok száma véges a szabályok tulajdonságaiból fakadóan.
Az imént definiált struktúra egy környezet függő nyelvtan. Az ellenőrzés trivi.
Létező-e az állapot az adott szabályrendszerben = Szóprobléma.
A környezet függő nyelvtanok összes levezetés gráfja azon kívül hogy nagy még ciklizál is. Nem úgy mint a környezet függetleneké.
Enpassant verziója ott bukik hogy csak azt nézi hogy mit kapcsol le. Vannak lokális állapotok amik elrontják a monoton javulást.
Mint a Rubik kockánál. (Ott is függenek a környezetüktől a kis kockák.)
Eddig bőven polinomiális idő és táron belül vagyunk. Csakis a lámpák számától függ. (Mivel az egy lámpához tartozó szabályok száma korlátos.)
Kell konstruálni egy olyan normálformát ami bizonyítottan kiküszöböli a ciklusokat és az összes levezetések gráfjából fát csinál.
Nevezzük ezt "Penttonen" normálformának. Már csak azért is, mert létezik ilyen. :D
A nyelvtanunk epszilon mentes.
Bizonyított:
- Lehet ilyen normálformára hozni.
- Utána nem lesz benne ciklus.
Nagyon érdekes a bizonyítás végig lehet gondolni, el lehet olvasni. Itt nem tárgyalom.
Tárban és időben nem lép túl a polinomiális kereteken.
A fa alakú összes levezetések gráfjában környezet független esetén hagyományosan a CYK algoritmust használjuk.
Módosítható az algoritmus, hogy ciklus mentes környezet függő nyelvtanon működjön.
És így megkapható a legrövidebb út a végponthoz, azaz az összes leoltott lámpához.
Környezet független nyelvtan esetén O(n^3)-ös az algoritmus. Ami nem bonyolódik polinomiális fölé környezet független esetben sem.
Így a teljes megoldás polinomiális időben megoldható hasonló tár igénnyel kizárólag a lámpák számától függően. (Pontos számítást a fentiek alapján lehet végezni.)
Továbbá nyelvtani elemzőket is lehet alkalmazni.
A tekintett részalgoritmusok számítógéppel könnyen megvalósíthatóak.
Ha az utolsó lépésben nem CYK hanem backtrack-et használunk nagyobb művelet idővel ugyan úgy megkapjuk a sikeres levezetések számát amiből kiválasztható a legrövidebb.
Ha pedig feltételezzük a végtelen tár és végtelen idő rendelkezésre állását akkor bevprogon tanult módszerekkel bizonyítható backtrack helyessége:
Minden már egyszer meglátogatott élt megjelölve a ciklusok szűrhetők és minden levezetést megtalál a program utána leáll.
A levezetések költségeinek ismeretében egy minimum kereséssel kiválasztható a legrövidebb.
De ez utóbbi csak helyesség bizonyítási célokat szolgál. Amúgy favágás.
Természetesen ezek a változatok is totális eldöntő algoritmusok.
Ilyen módon az n királynő probléma is gyorsítható.
És végül: P = NP "..., de ez a margó túl keskeny, semhogy ideírhatnám."
Irodalom:
http://www.inf.unideb.hu/~fattila/hallgatoknak/dokumentumok/Varga.doc
--
Nálam a 'Tökéletes' csak egy 'Public Beta'...