A lámpagyújtogató dilemmája

Algoritmusok

Kevésbé formálisan:

Adott egy téglalap alapú terem, mely függőlegesen négyzetalakú cellákra van osztva. E cellák némelyikében (akár az összesben) lámpák vannak. Minden olyan cellában, amelyben van lámpa, van egy kapcsoló is. E kapcsoló e lámpához tartozik, viszont viselkedése nem szokványos: az aktuális lámpa állapotán kívül mind a négy élszomszédjának állapotát is megfordítja (ha az adott élszomszéd cellában van lámpa, illetve ha beszélhetünk négy élszomszédról, azaz nem falnál, illetve sarokban vagyunk).

A lámpák kezdetben fel és le is lehetnek kapcsolva (adott egy kapcsolási állapot). A cél az, hogy az összes lámpát lekapcsolt állapotba helyezzük.Formálisan:

Adott egy n×m-es { -1 ; 0 ; 1 } feletti mátrix. A mátrix egyes mezői 0 értékűek, ha az adott cellában nincs lámpa, -1 értékűek, ha van lámpa, és az le van kapcsolva, 1 értékűek, ha van lámpa, és az fel van kapcsolva.
Egy lámpa állítása a következő módosítást eszközöli a mátrixon: legyen a lámpa két koordinátája i és j. A lámpa kapcsolásának hatására az (i;j), (i;j-1), (i+1;j), (i;j+1), (i-1;j) cellák értéke (-1)-szeresére változik, ezek létezése esetén (azaz kivéve: i ∈ { 1 ; n } V j ∈ { 1 ; m } ).

A dilemma:

- Döntsük el, hogy lekapcsolható-e az összes lámpa!
- Adjunk olyan kapcsolási sort, amely az összes lámpát lekapcsolja!
- Adjuk meg ezek közül a legrövidebbet, ha több ilyen van, akkor azok közül valamelyiket.

Amire eddig jutottam:

Könnyen belátható, hogy a { -1 ; 0 ; 1 } a hagyományos Z-n értelmezett * (szorzás) műveletre zárt: hiszen -1 * 0 = 0 * 0 = 0 * 1 ; 1 * 1 = 1 ; -1 * -1 = 1 ; 1 * -1 = -1 . (Következésképpen ha a mátrix sorait vagy oszlopait { -1 ; 0 ; 1 } -beli vektorral szorozzuk, akkor { -1 ; 0 ; 1 } -beli mátrixot kapunk eredményül. Az is könnyen belátható, hogy { -1 ; 0 ; 1 } jólrendezett a Z-n értelmezett jólrendezésre, ami triviális, hiszen { -1 ; 0 ; 1 } részhalmaza Z-nek. Tehát a * szorzás műveletet teljes nyugodtsággal használhatjuk multiplikatív műveletnek, a > relációt pedig jólrendezési relációnak.

Én úgy látom, hogy a kapcsolgatást egy másik mátrixszal lehetne "nyilvántartani", modellezni. Legyen adott így egy n×m-es { 0 ; 1 } feletti mátrix, mely kezdetben nullmátrix. Egy (i;j) lámpa kapcsolása a mátrixban az (i;j) cellán hajtja végre a + műveletet, definiáljuk +(0) := 1 ; +(1) := 0 módon. Triviális, hogy ha a kapcsolási folyamat során egy kapcsolóhoz többször (kétszer) is hozzányúlunk, az a végeredmény szempontjából olyan, mintha egyszer sem nyúltunk volna hozzá, azaz ekkor csináltunk két fölösleges lépést. (Mivel a végső cél a legrövidebb út megkeresése, érdemes így szűrni a biztosan fölösleges lépéseket.)

A lámpák ( M(i;j) ∈ { -1 ; 1 } ) számának maximuma m*n (ekkor mindenhol van lámpa), tehát a lehetséges különböző kapcsolási utak (bárhová is vezetnek) maximuma 2^(m*n), ami banális. Azonban ezeknek igen csekély számú interpretációja fog az "összes lámpa lekapcsolásához" vezetni. Ezek közül aztán pedig talán ki lehetne választani a legrövidebbet (aminek maximális hossza n*m).

  • 7724 megtekintés

( erdohegr | 2009. 01. 20., k – 10:42 )

> Triviális, hogy ha a kapcsolási folyamat során egy kapcsolóhoz többször (kétszer) is hozzányúlunk, az a végeredmény szempontjából olyan, mintha egyszer sem nyúltunk volna hozzá, azaz ekkor csináltunk két fölösleges lépést.

Na várjál, ha egy kapcsoló a szomszédos lámpákat is átbillenti, akkor ez nem teljesen igaz így szerintem. Mert a szomszédos lámpákat azok szomszédos lámpái is kapcsolgatják, így ha te bekapcsolod mondjuk a szomszédos lámpákat, majd azok szomszédos lámpáival valamelyiket lekapcsolod, akkor az első lámpád lekapcsolásával a most lekapcsolt lámpa ismét felgyullad.
Vagy eltévedtem a logikában? :)

Szerintem igaza van. Igazabol azt akarja ez mondatni, hogy ha ugyanazt a mezot ketszer atkapcsolod (es a tobbi mezot is valahanyszor), akkor ugyanazt az eredmenyt kapod, ha ezzel a mezovel semmit nem csinaltal volna, a tobbbi mezon pedig ugyanazokat a muveleteket vegezted el.

Persze mindebbol az kovetkezik, hogy egy mezot legfeljebb egyszer kell atkapcsolni.

Oké, bizonyítom. Vegyünk egy tetszőleges kapcsolót. E kapcsoló végállapota öt dologtól függ, miszerint attól, hogy őt hányszor kapcsolták, illetve, hogy az élszomszédjait. Mivel az állapotok száma kettő, így konkrétan csak ezek összegének kettes kongruenciájú maradékától függ. Azaz egyértelműen látszik, 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. És mivel tetszőleges lámpát vettünk, ezért ezt kiterjeszthetjük mindre. Ahol nincs lámpa, azzal meg nem kell foglalkozni. Voilá.

:: by BRI.
:: config :: Acer TravelMate // Ubuntu Intrepid
:: tothab [a] gmail [pötty] kom
:: black rose immortal's weblog

Na várjál, ezzel gyakorlatilag nem mondtál semmit, minden esetben páratlan lesz az összeg, ha páratlan lámpa van, és páros, ha páros a lámpák száma, mert:
Ha van x = n + m lámpa, ahol n felkapcsolt lámpák és m lekapcsolak, akkor az összeg n - m lesz.
Ha x páros, akkor vagy n és m is páros vagy mindkettő páratlan. Ekkor n - m mindenképp páros lesz.
Ha x páratlan, akkor vagy n páros és m páratlan, vagy fordítva, ekkor n - m szintén páratlan lesz.

Hm-hm várjunk csak, ezzel valami gond van.

Tegyük fel, hogy adott egy páros értékösszegű lekapcsolható n×m-es mátrix. Vegyük akkor azt a mátrixot, mely úgy keletkezik, hogy az előzőhöz hozzáírunk először egy csupa 00..00, majd egy 100..00 sort. A lámpák kezdeti értékösszege ettől eggyel nő, azaz páratlan lesz. A konstrukció továbbra is lekapcsolható a következőképpen: az utolsó két sor kivételével kapcsoljuk le a lámpákat a már ismert módon, majd kapcsoljuk le az utolsó sor egyetlen lámpáját.

:: by BRI.
:: config :: Acer TravelMate // Ubuntu Intrepid
:: tothab [a] gmail [pötty] kom
:: black rose immortal's weblog

Az üres helyek befolyásolják.

Szét kell vágni a teret komponensekre, olyan részterületekre amik nem befolyásolják egymást.

Aztán minden lámpára külön megnézni az hogyan befolyásolja saját komponensében a paritást, majd komponensenként összegezni hogy adott komponensben megvalósítható-e a páros paritás. És intuicióm szerint még ez sem elég, de hirtelen nem jut eszembe mi kell még! :)

A szétvágás elmélete nem hülyeség. Az tuti, hogy ha a mátrixban van egy csupanulla sor vagy oszlop, akkor annak mentén kettévágható. Az is belátható, hogy ha van olyan "navigáció", ami egy falmenti 0 mezőtől egy másik falmenti 0 mezőig tart (navigáció alatt értsük azt, hogy fel-le-jobbra-balralépés, de csak ugyanolyan értékű, azaz 0 mezőre léphetünk), akkor annak mentén is szétvágható. Következésképpen a lekapcsolhatóság ekvivalens a két új kisebb mátrix lekapcsolhatóságával, valamint a legrövidebb út, a két mátrix legrövidebb útjának tetszőleges sorrendű konkatenációja.

Teljes indukcióval beláthatjuk, hogy így bármely véges lépésben szétvágott mátrix megoldható "elemenként", és a legrövidebb út megkonstruálható az elemek legrövidebb útjainak konkatenációjaként.

A feladatunk már csak az elemi (vágásra alkalmas navigációt nem tartalmazó) "szobák" megoldása.

:: by BRI.
:: config :: Acer TravelMate // Ubuntu Intrepid
:: tothab [a] gmail [pötty] kom
:: black rose immortal's weblog

Viszont ha nincsenek markans hatarok, akkor minden lampa befolyasol minden lampat. amig ugyanis nincs olyan lampa, ami nem valt at egy masik (tetszolegesen valasztott) lampa allapotatol fuggoen, addig egy lampa az egesz matrixot kapcsolja. Amennyiben viszont talalunk egy olyan teruletet, amely 0-kal korul van veve (vagy olyan, reszben a matrix szelei altal hatarolt teruletet, mely 0-kbol alkotott hatarvonala ket ponton erintkezik valamely szellel), az a terulet fuggetlen lesz a matrix tobbi reszetol, vagyis ott nem ervenyesul a gordulo hatas sem.

Legalabbis igy poren, nem-matekos szemmel. A feltevesem egyik hibaja az, hogy ugy vettem, hogy minden cellaban egy lampa van, ugyanis nem ertem kristalytisztan, hogy ha a gordules egy olyan mezobe fut, ahol tobb lampa is van, akkor mi tortenik. Ha ugyanis minden lampat lekapcsol az adott mezoben, akkor teljesen mindegy, vehetjuk ugy, hogy 1 darab lampa van. Ha nem, akkor valik erdekesse a dolog, mert ez esetben csak p-vel csokkenti az adott mezoben ego lampak szamat (p>=1)
Ha viszont nincsenek markans hatarok, akkor a dolog nagyon erdekesse valik, ugyanis barmely mezo, amiben a lampak szamara l<4 a szomszedokra pedig n>=l ugyanugy lekapcsolodik az osszes lampa (ugye nincsenek hatarok, vagyis ebben az esetben minden lampa valamilyen hatassal van az egesz matrixra).
-- 


()=() Ki oda vagyik,
('Y') hol szall a galamb
C . C elszalasztja a
()_() kincset itt alant.

Így van. Például a

000XX
XX0XX
XX00X
XXX0X
XXX0X
X000X

tábla a 0-k mentén kettévágható. Az X-ek helyébe tetszőleges { 1 ; -1 }-beli elemet kell látni. Ekkor szemben állunk kettő legfeljebb feleakkora mátrixszal. Ami a lentebb említett "kapcsolási-reláció mátrix" szempontjából egyáltalán nem hasztalan, ugyanis annak az összméretét legalább negyedeli, ha jól gondolom.

Az is igaz még, hogy az olyan 0 mezőkkel sem kell foglalkoznunk, melyek minden élszomszédja 0. Vágáskor az ilyen elem "hulladék".

Az is értelemszerű továbbá, hogy a teljes szoba pontosan akkor kapcsolható le, ha az összes "kis szoba" lekapcsolható, valamint a legrövidebb lekapcsolás is ekvivalens (azonos hosszú, azaz ugyanúgy jó) lesz azzal, amit a "kis szobák" legrövidebb lekapcsolásainak egymásutánjával kapunk. Egyszóval ez egy optimalizációs megoldásnak kifejezetten jó.

A feladatot pedig innen pontosíthatjuk: feltételezhetjük, hogy bármely két lámpát összeköt valamilyen "folyosó". Definiálja, aki szeretné, szerintem érthető, miről van szó.

A feladat tehát az olyan szoba lekapcsolása, amely már nem szabdalható tovább.

:: by BRI.
:: config :: Acer TravelMate // Ubuntu Intrepid
:: tothab [a] gmail [pötty] kom
:: black rose immortal's weblog

-zsákutca a probléma példányától függő megoldás keresése, mert általánosan akarod megoldani
-egy kis súgás: nem árt tisztázni, hogy lehet-e több megoldás (rájöhet az ember hogy a "mátrixműveletek" nem működnek ha több van), (azt már látom hogy rájöttél hogy mindegy hogy egy adott lámpát mindegy hogy milyen párosságúan kapcsolgatjuk, de ha két szoba van egymás mellett akkor is mindegy hogy mindkettőben felkapcsolom-e vagy nem, tehát két megoldás van, és minél nagyobb az épület annál több lesz)

"de ha két szoba (lámpa) van egymás mellett akkor is mindegy hogy mindkettőben felkapcsolom-e vagy nem"

No ebbe most gondoltam bele. Akkor az világos, hogy ha két szomszédos "szeparált" lámpát kapcsolunk, akkor lényegében nem tettünk semmit. De mi a helyzet akkor, ha vannak további élszomszédjaik? Akkor már nem igaz, hogy bármely két szomszédos kapcsolt lámpa nincs befolyással a többire (a további élszomszédjaikra).

Amit te mondtál, abból az következne, hogy ha bármely két szomszédos kapcsolóhoz hozzányúltunk, az lényegében ekvivalens a végeredmény szempontjából azzal, mintha egyiket se kapcsoltuk volna át, nem igaz? Ez pedig nagyon nem kóser. Pl.:

122 az 1. és 2. lámpa kapcsolásakor: 122 -- 212 -- 121 , ami még véletlenül sem ekvivalens az 122-vel.

:: by BRI.
:: config :: Acer TravelMate // Ubuntu Intrepid
:: tothab [a] gmail [pötty] kom
:: black rose immortal's weblog

-1, 1 -gyel jelölve ezzel még csak annyit mondtál, hogy ha kapcsolsz akkor is értelmezhető értéktartományon marad az érték...

Ilyen párospáratlan változás összefüggést itt nem lehet felállítani, mert egy kapcsolásra 9, 6 vagy 4 változás van (attól függően hogy a szélen, sarkon vagy belül van-e a mező). Ezeket pluszminusz kombinálva minden egész szám kijön.

Szerk: elnéztem, élszomszéd van, tehát a változások száma 3, 4 és 5

( bri | 2009. 01. 20., k – 10:49 )

Egy egyszerű példa: Adott a következő 3×3-as mátrix: (a -1 helyett 2-t írok)

0 1 0
0 1 0
1 0 2

A cél:

0 2 0
0 2 0
2 0 2

A helyes kimenet: (1;2) ; (3;1)

Ekkor

0 1 0     0 2 0     0 2 0
0 1 0     0 2 0     0 2 0
1 0 2     1 0 2     2 0 2

a mátrixsorozat. A segédmátrixunk a következőképpen alakul:

0 0 0     0 1 0     0 1 0
0 0 0     0 0 0     0 0 0
0 0 0     0 0 0     1 0 0

Ebből könnyen megadható a kimenet.

:: by BRI.
:: config :: Acer TravelMate // Ubuntu Intrepid
:: tothab [a] gmail [pötty] kom
:: black rose immortal's weblog

( lzrd | 2009. 01. 20., k – 11:30 )

"A cél az, hogy az összes lámpát lekapcsolt állapotba helyezzük."
Akkor ez nem is lámpagyújtogató, hanem lámpaoltogató.
--
unix -- több, mint kód. filozófia.
Life is feudal

( szemet | 2009. 01. 20., k – 11:38 )

Triviális lesz amit írok... Ugye nem formális megoldás kell, hanem algoritmus?

Ez egy egyszerű CSP (Constraint Satisfaction Problem), minden erre vonatkozó általános eszköz kipróbálható.

Egy mező értékét max 5 kapcsoló befolyásolja. Azaz max. 2^5/2=2^4=16 eset adhat jó megoldást. A szomszédos mezőket egy adott megoldás éppúgy korlátozza mint pl. a 8 királynő problémában (ami a CSP állatorvosi lova...).

Persze nem álltatlak a CSP-k alá beletartozik néhány NP teljes probléma is, illetve annyi CSP megoldó algoritmus van mint égen a csillag, szóval jó próbálkozást hátha valamelyik bejön! :)

:) Tegyük fel 1000×1000-es mátrixokra akarom számolni. Az én procim ha 100%-on teljesít és nem foglalkozik semmi mással, az univerzum várható életkorát alig meghaladó időegység alatt végezne. Ne gondolkodj kicsiben.

:: by BRI.
:: config :: Acer TravelMate // Ubuntu Intrepid
:: tothab [a] gmail [pötty] kom
:: black rose immortal's weblog

Amúgy ezen a szálon elindulva akár Turing-gépet is lehetne konstruálni a feladatra, illetve legalább arra, hogy eldöntsük, egy adott szoba teljesen lekapcsolható-e. Az időigénye sajnos vészes lenne, de nem ez az egyetlen problémám vele: esztétikailag nem tartom kielégítő megoldásnak. Favágás.

:: by BRI.
:: config :: Acer TravelMate // Ubuntu Intrepid
:: tothab [a] gmail [pötty] kom
:: black rose immortal's weblog

( tomaza | 2009. 01. 20., k – 11:47 )

gondolom a lényeg megoldani a problémát, nem maga a megoldás, de talán segít:
jaaps
:)

( imp | 2009. 01. 20., k – 13:29 )

Csak egy átfogalmazás:
Ábrázoljuk a termet egy gráffal, aminek annyi csúcsa van, ahány lámpa van a szobában. Két csúcs között van él, ha a teremben szomszédosak. Címkézzük az éleket 0-val, ha a két végpontjának megfelelő (szomszédos) lámpák fordított állásúak, és 1-el, ha azonos állásúak. Egy lámpa átkapcsolása egy pontban az adott pontból kiinduló élek szomszédos éleinek a címkéit változtatják meg. A cél, hogy minden él 1-es címkéjű legyen.
(azzal most nem foglalkozunk, hogy le vagy fel van kapcsolva az összes lámpa)

Pl.: 


A mátrix:
0 2 0
2 1 1*
2 2 0


A gráf:
    .
    0!
. 0!. 1 *
1   0!  
. 1 .

A *-gal jelölt pontot átkapcsolva a felkiáltójeles élek változnak.

Készítsünk most egy mátrixot, aminek a sorai az éleknek felelnek meg, oszlopai pedig a csúcsoknak. A mátrix egy (ij) tagja legyen 1, ha a j-edik csúcs átkapcsolása változtatja az i-edik élet. 


A gráf, eljelölve az éleket kisbetűkkel, a csúcsokat nagybetűkkel, illetve a kiinduló érték mégegyszer:
    A             A
    p             0
B q C u F     B 0 C 1 F
r   s         1   0
D t E         D 1 E

Az ehhez tartozó M mátrix:
  A B C D E F
p   1     1 1
q 1     1 1 1
r     1   1
s 1 1   1   1
t   1 1
u   1     1

A kiinduló k állapotot az élek állapotával jellemezhetjük, jelen esetben:
p 0
q 0
r 1
s 0
t 1
u 1

A cél egy olyan x vektor megtalálása, hogy Mx = -k legyen, ahol az M és k is (mod 2) felett értelmezett. Innen látható, hogy
1) a kapcsolgatási sorrend lényegtelen
2) minden kapcsolót legfeljebb egyszer kell átkapcsolni

Ezt nekem még mátrix általánosított inverzeként tanították, bár kétségtelen, hogy a Moore-Penrose sokkal komolyabban hangzik ;)

szerk:

Hogy érdemben is hozzászóljak: ha az "M^-1" jelölést a szokásos konvenciók szerint használjuk, akkor az állítás tényleg csak nxn-re igaz. Az általános inverz definícióját általában (szándékosan) máshogy jelölik, pl.: AA'A=A, ahol A' az A (mxn-es) általánosított inverze.

Khm, nem -k, hanem [1...1]^T - k. Lehet hogy szerencsésebb fordítva választani az állapotok jelölését (ha különbözik két szomszédos lámpa, akkor ahhoz az élhez 1-et rendelünk, különben 0-t; az M mátrix jelölése viszont jó), és akkor Mx = k -t kell megoldani.

Egyébként az is elég, ha csinálsz egy NxN-es négyzetes mátrixot, ahol N a lámpák száma, és M(i,j) = 1, ha a j-edik kapcsoló megváltoztatja az i-edik lámpát. Ekkor lesz egy szimmetrikus négyzetes mátrixod, és szintén Gauss-eliminációval megoldod Mx=k -t Z(2) felett, ahol k a lámpák kezdeti állapota: 1, ha ég a lámpa, és 0, ha nem. Ennek megvan az az előnye, hogy k-val pontosan meg tudod adni, hogy milyen végállapotot szeretnél.

Ez nagyon favágásnak tűnik. Ennyi erővel az is lehetne megoldás, hogy vegyük az összes legfeljebb N-hosszú kapcsolási lehetőséget (ismétlés nélküli variációt?), keressük ki ezek közül azokat, amelyek lekapcsolnak minden lámpát (itt is rengetek triviális eset kizárható), és keressük meg ezek közül a legrövidebbet. Ez nem reális megoldás, hanem ágyúval sortűz legyekre.

:: by BRI.
:: config :: Acer TravelMate // Ubuntu Intrepid
:: tothab [a] gmail [pötty] kom
:: black rose immortal's weblog

Ugyan múlt héten vizsgáztam belőle, de őszintén megmondom, nem tudom, hogyan ugranék neki a kérdésnek. Vélhetően ekvivalens problémákat keresnék, amelyeknél ezt meg tudom határozni. Annyi viszont biztos, hogy nem szebb megoldás, mint az összes lehetőség közül a jók kiválogatása, azok közül pedig a legrövidebb megkeresése. Az eleganciát hiányolom belőle.

Szerk.: Az eleganciát, mint matematikus, nem mint informatikus; de a feladatra matematikai jellegű megoldást keresek.

:: by BRI.
:: config :: Acer TravelMate // Ubuntu Intrepid
:: tothab [a] gmail [pötty] kom
:: black rose immortal's weblog

Konkrétan annak a legszűkebb előfeltétele kéne először, hogy egy szoba lekapcsolható legyen. Ezzel a dilemma három részéből az első megoldódna, és el tudunk indulni az ösvényen a második és harmadik rész megoldása felé. Ha azt mondjuk, hogy csináljunk rá Turing-gépet, kétverem-automatát, közvetlen hozzáférésű gépet, számlálós gépet, vagy bánom is én micsodát, az nem visz közelebb a másik két probléma matematikai megoldásához.

:: by BRI.
:: config :: Acer TravelMate // Ubuntu Intrepid
:: tothab [a] gmail [pötty] kom
:: black rose immortal's weblog

Na jó, kapható vagyok a probléma teljesen formális megoldására, de nem fogom tudni teljesen formálisan megoldani egyedül. Gyakorlatilag fogalmam sincs, hogy kezdjek hozzá. Talán nyelvtant kéne írni hozzá valahogy...?

:: by BRI.
:: config :: Acer TravelMate // Ubuntu Intrepid
:: tothab [a] gmail [pötty] kom
:: black rose immortal's weblog

:)

Úgy értettem, hogy kíváncsi lennék, hogy hogyan lehet megoldani ezt a feladatot egy Turing-géppel vagy egy kétverem-automatával, de sajnos elképzelésem sincs, hogy olyat hogyan kéne, mert sosem csináltam még. Szóval ha megcsinálod és elmagyarázod, azt nagyon megköszönöm, ha nem, akkor meg elfogadom, hogy úgy megoldható.

:: by BRI.
:: config :: Acer TravelMate // Ubuntu Intrepid
:: tothab [a] gmail [pötty] kom
:: black rose immortal's weblog

+1

mennyi hulyeseget osszehordtal itt.. ilyen feladathoz ketverem automata meg turing gep, OMFG.

szakadj mar el a rohadt formnyelvek meg bevprog targyaktol. konkret algohoz (es annak implementaciojahoz) nem fog elvezetni egyik se. formalisan megoldani meg nem fogod, leven, ha jol emlekszem elsos vagy kb: a matematikai apparatus is hianyzik hozza. egy programhelyessegbizonyitas azert nem trivi dolog. (egy quicksortot ha megirsz mondjuk adaban, bizonyithatoan jora, arra ra fog menni eleg sok idod, hogy bebizonyitsd - egy absztrakt automatat kodra szintetizalni meg nem mindig trivi)

( enpassant v | 2009. 01. 26., h – 20:38 )

Elsőre egy ilyen algoritmus jut az eszembe:
Megkeressük azokat a lámpákat, amelyek lekapcsolásával a mellette levő lámpák is lekapcsolódnak. Ezek közül a legtöbb lámpát lekapcsolót választjuk (ha több van, akkor mindegy melyiket). Ez elvileg egyre közelebb visz a megoldáshoz az optimális úton.
A kérdés már csak az, mi van akkor, ha már nincs ilyen eset, de még van felkapcsolt lámpa.
Ebben az esetben megkeresném azt a lámpát, amelyik lekapcsolásával a legkevesebb lámpa kapcsolódik fel és azt választanám.
Mindkét részben azokat a kapcsolókat, amiket már kapcsoltam azokat nem használnám.
Ha elfogynak a kapcsolók, akkor vagy kész vagyunk, vagy ez az algoritmus nem vezet eredményre :-)
A sejtésem az, hogy ez az algoritmus működik, már csak egy ügyes embernek igazolnia kell :-)
Ez Enpassant első sejtése! :-)

Igazolás helyett cáfolat:

"Megkeressük azokat a lámpákat, amelyek lekapcsolásával a mellette levő lámpák is lekapcsolódnak. Ezek közül a legtöbb lámpát lekapcsolót választjuk (ha több van, akkor mindegy melyiket)."

Ha több van, akkor mindegy.
Mi van, ha nincs ilyen? Ez esetben a feladat megoldható, de az algoritmus el sem indul.

Triviális példa: A szoba 3×1-es, a következőképpen fest:

212

Ez a következő három kapcsolással lekapcsolható:

212 -- 121 -- 211 -- 222 (a 2., 1., 3., lámpákat kapcsoljuk)

:: by BRI.
:: config :: Acer TravelMate // Ubuntu Intrepid
:: tothab [a] gmail [pötty] kom
:: black rose immortal's weblog

Ezt az én algoritmusom is megoldja. A második rész írja le, hogy mi van akkor, ha nincs olyan, hogy csak lekapcsolunk lámpát. Ilyenkor olyat választ, ami minél kevesebbet kapcsol fel.
Tehát az én algoritmusom először az 1.-et v. 3.-at kapcsolná (mivel azok csak egyet kapcsolnak fel), legyen mondjuk az 1. Utána a 3.-at, végül a 2.-at.
Tehát:
212 -- 122 -- 111 -- 222
vagy 3,1,2-őt választ, akkor:
212 -- 221 -- 111 -- 222

Nekem valami még mindig azt súgja, hogy ez csak parciális megoldás, azaz van olyan szoba, ami megoldható, de ez az algoritmus nem oldja meg. De most keltem, szóval kávé, cigi, és meggondolom.

:: by BRI.
:: config :: Acer TravelMate // Ubuntu Intrepid
:: tothab [a] gmail [pötty] kom
:: black rose immortal's weblog

( joco01 v | 2009. 01. 27., k – 09:34 )

Felejtsd el azt, hogy a termet mátrixként ábrázolod. Csak szobák vannak egy vektorban.

Nézzünk egy ilyet (L):

10
X1
X1

Ez egy 2x3-as szoba, 1=felkapcsolt lámpa, 0=lekapcsolt lámpa, X=nincs lámpa.

Az ezt megoldó kapcsolás (K):

10
X1
X0

1=átkapcsoljuk a lámpát, 0=nem nyúlunk hozzá, X=nincs lámpa.

Ezek után az X-ekkel nem is kell foglalkozni. Nevezzük el a szobákat:

AB
CD
EF

Modulo 2-vel számolva:

KA+KB=LA
KA+KB+KD=LB
KB+KD+KF=LD
KD+KF=LF

Itt lesz bal oldalon egy 4x4-es kapcsolómátrixod (M), ennek egy sora megadja, hogy a sorhoz tartozó lámpa melyik kapcsolóktól függ.

Tehát az algoritmus: fogod a lámpás szobákat valamilyen sorrendben, felírod a kapcsolómátrixot, és innen kezdve nem foglalkozol a topológiával, mint ahogy fent is írtam. Amit előbb felírtam: M*K=L. Ez abból jött ki, hogy M*K+L=0, vagyis a kapcsolómátrixot beszorzod valamilyen kapcsolással, és ha ezt ráereszted a kiindulási állapotra, akkor kimenetként minden lámpa le lesz kapcsolva. K-t keressük. Szép lineáris egyenletrendszer, kijön belőle minden K, akár nem létezik, akár egyértelmű, akár több megoldása van.

--
joco voltam szevasz

Varjal, nekem valami nem vilagos (meg nem kapcsoltam fel a lampat, csak felteteleztem :D )
Ez a dolog mukodhet a 2x3-as szoba eseteben, de mi a helyzet egy mondjuk paratlan szamu lampat tartalmazo szobaban (teszem fel 3x3)? Es mi a helyzet, ha a X-ek elhelyezkedese sokkal randomabb?
Amennyire en latom, eloallhat olyan helyzet, hogy nem lehet megoldani a kerdest.

A masik pedig, hogy te itt arra epitesz, hogy egy cellaban egy lampa van (vagy ugy lehet venni, hogy egy cellaban egy lampa van), ez viszotn a feladat ertelmeben nem feltelten igaz. Azt a feladat ugyanis nem definialja, hogy mi a viselkedes 1-nel tobb lampat tartalmazo cellak eseteben - ha ugyanis csak csokkenti az ego lampak szamat a szomszedjanak az atvaltasa, es csak akkor indit hatast a szomszedjara, ha 0 lampa van a cellaban felkapcsolva, akkor tokmas a megoldas modszere.
Itt specifikalni kellene, hogy a cellankenti random mennyisegu lampa relevans-e a megoldasban (azaz mi a gordulo hatas viselkedese 1-nel tobb lampat tartalmazo cellakban).
-- 


()=() Ki oda vagyik,
('Y') hol szall a galamb
C . C elszalasztja a
()_() kincset itt alant.

Röviden: WTF?

Ha az én algoritmusom azt mondja, hogy nem lehet megoldani, akkor nem lehet megoldani.

Mi a fenéért ne működne páratlan szám esetén? 3x3-as mátrix az csak valami legenda?

És egy cellában maximujm egy lámpa van, nem tudom, honnan szedted ezt a hülyeséget...

--
joco voltam szevasz

He?

Egy cellában legfeljebb egy lámpa lehet. Praktikusan: ha kettő (vagy több, indukcióval) lenne, akkor
1) azok kezdetben azonos állásúak, ekkor ugyanúgy viselkednek, mintha egy lámpa lennének (vagy mind ég, vagy mind alszik)
2) azok kezdetben különböző állásúak, ekkor nincs megoldás, hiszen a kapcsolás után is különböző lesz az állásuk.

:: by BRI.
:: config :: Acer TravelMate // Ubuntu Intrepid
:: tothab [a] gmail [pötty] kom
:: black rose immortal's weblog

( Beka v | 2009. 01. 27., k – 10:26 )

Sziasztok,

A probléma algoritmizálásához bölcsészként teljesen hülye vagyok, de szerintem ez a feladat szerepel a Neverwinter Nights (I): Infinite Dungeons c. kiegészítőjében, amihez megoldási javaslatokat ezen a fórumon tettek:

http://nwn.bioware.com/forums/viewtopic.html?topic=483126&forum=86&sp=30

Itt említenek többek között egy puzzle-t (Flip), ami alkalmazza az algoritmust:

http://www.chiark.greenend.org.uk/~sgtatham/puzzles/

Nem tudom, közelebb visz-e a megoldáshoz, bocs, ha nem.

Béka

Amit itt látunk, az egy nagyságrendekkel egyszerűbb probléma. Ebben a verzióban szerepelnek olyan mezők, ahol nincs lámpa, azaz üres mező. A linkelt Flip alapján mondjuk úgy kell elképzelni, hogy az ilyen mezőre kattintani sem lehet, és nem is kell megváltoztatni a színét (nem befolyásol semmit, és őt sem befolyásolja semmi).

:: by BRI.
:: config :: Acer TravelMate // Ubuntu Intrepid
:: tothab [a] gmail [pötty] kom
:: black rose immortal's weblog

( samuf v | 2009. 01. 27., k – 11:36 )

Ennek van valami köze Neumann-hoz és a Celluláris automatákhoz?

( dlazesz | 2009. 07. 09., cs – 02:04 )

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'...

( sebist v | 2009. 07. 09., cs – 07:23 )

A kovetkezo algoritmust gondolom.

Epits a lampak allapotabol fat, igy:
A fa csucsa: az osszes lampa le van kapcsolva.
Egy csucsbol ugy kapjuk, a gyereket, hogy egy-egy lampat atkapcsolunk. De ha ennek az atkapcsolasnak a hatasara olyan allapotba jutunk, amely allapotot a fa valamelyik csucsa mar tartalmazza, akkor ertelemszeruen nem hozzuk letre az uj gyereket. Egy csucsnak maximum kapcsolok szamu gyereke lehet.
A fa epitesenek vege van ha:
1. megtalaltuk a megadott allapotot (ilyenkor a fa magassaga az atkapcsolasok szama)
2. nincs uj gyerek, csak olyan allapotba jutunk, ami mar volt. Ez esetben nincs megoldas.

Udv:
Istvan

Aham. Viszont ez csak algoritmikusan jo, programba nem a leggyorsabb megoldas, leven le kell definialni, hogy az allapotokat hogy hasonlitod ossze. En nem vagyok matektudos, de szerintem az allapotok osszehasonlitasa a lampak szamaval aranyosan no (nem mondom, hogy egyenes aranyban, mert az ide vago szamitasokat nem ismerem), es szerintem van olyan megoldas, amivel gyorsabban meg lehet ennek a feladatnak a vegeredmenyet mondani.
-- 


()=() Ki oda vagyik,
('Y') hol szall a galamb
C . C elszalasztja a
()_() kincset itt alant.

Konnyen lehet, hogy van jobb algoritmus, de szerintem nem az allapotok osszehasonlitasa lesz a gond.

Az allapotokat ugy reprezentalnam, hogy megsorszamoznam a lampakat. Egy allapotot egy N bithosszusagu sorozat reprezental, ahol az i-edik biten az i-edik lampa allapotat tarolom. Ekkor ket allapot osszehasonlitasa memcmp -vel tortenhet.
Ha tul nagy a fa es lassu egy allapotrol eldonteni, hogy szerepelt-e, akkor a kovetkezoket lehet tenni.
Keszitunk egy 2^N elemu bool tombot, amelyet ezen allapotok szerint indexelunk. Az elejen a tomb minden eleme hamis. Ha talalunk uj allapotot, akkor az ehhez tartozo elemet is atallitjuk igaz-ra. Ekkor egyetlen 'if' segitsegevel eldonthetjuk, hogy uj allapotrol van-e szo.