Sziasztok!

Én a következő optimalizációkat használtam:
1. a. sudoku szabályaira all_distinct
    b. távolságkorlátokra írtam saját felhasználói korlátokat
2. borotválás (könyvtári labeling használatával)
Redundáns korlátokat nem is csináltam. Kíváncsi lennék majd a végén, hogy ti milyen redundáns korlátokat csináltatok, én nem találtam olyat, amit egyszerűen meg lehetett volna írni.
Nekem az 1. megvalósítása esetén lefutott 9 tesztesetre, 1.+2. esetén mind a 10re.

üdv: Laci



> To: nhlp-l@cs.bme.hu
> From: szeredi@cs.bme.hu
> Date: Sun, 9 Jan 2011 21:36:06 +0100
> Subject: [NHLP-l] nagyhazi
>
>
> Egyikotok irta:
>
> > A gyorsítás viszont nem nagyon megy...Kipróbáltam minden trükköt, amit anno
> > deklapónál használtam, de csak lassítottak rajta.
> > Van egy olyan, hogy ha egy oszlopban (sorban stb.) csak egy elem domainjében
> > szerepel pl. a 4-es, akkor behelyettesíti arra. Ezt megírtam globális
> > korlátként, de csak lassított a futáson. Elképzelhető, hogy a clpfd (az
> > all_different hatására mondjuk) már észreveszi ezt az esetet?
>
> Az all_different csak akkor, ha megfelelo opciot adsz neki, de az
> all_distinct alapertelmezesben tartomanykonzisztenciat biztosit, tehat
> annak hasznalatakor biztosan felesleges ez a plusz globalis korlat.
>
> Ami fontos tehat:
>
> 1. Hasznaljatok tartomany-szukito korlatokat:
>
> a. all_distinct (es nem all_different)
>
> b. az s es w infoknak megfelelo tavolsag-korlatokhoz is erdemes egy
> tartomany-szukito megoldast talalni.
>
> 2. Hasznaljatok borotvalast.
>
> 3. Hasznaljatok redundans korlatokat.
>
> Az en viszonylag egyszeru megoldasom futasa a kovetkezokeppen alakul:
>
> 1. megvalositasa eseten (2. es 3. nelkul) lefut 6 teszteset (tehat mar boven
> ervenyes a nagyhazi).
>
> 1.+2. megvalositasa eseten lefut 8 teszteset.
>
> 1.+2.+3. megvalositasa eseten lefut mind a 10 teszteset.
>
> (A fenti "lefutott" tesztesetek eseten legalabb 3-szoros az en futasi
> idomhoz kepest a idokorlat.)
>
> Nikhazy Laci programjaval az osszes teszteset lefutott szumma 20 mp
> korul. Laci, nyugodtan ird meg a listara, hogy milyen *jellegu*
> optimalizaciokat hasznaltal (persze reszletek nelkul).
>
> Kicsit reszletesebben irok meg a 2. es 3. "tanacsokrol".
>
> A borotvalasban talan az a legosszetetebb, hogy hogyan agyazzuk be a
> cimkezesbe. Ket lehetoseg:
>
> - nem hasznaljuk a konyvtari labeling eljarast, helyette egy sajat cimkezot
> irunk. Ebben a cimkezoben minden n. cimkezesi lepes utan meghivjuk a
> borotvalast (ahol n egy kiserletileg megallapitando konstans -- az en
> programomnal 2 vagy 3 latszott a legjobbnak).
> Hatrany: elveszitjuk a konyvtari cimkezes elonyeit (pl. a hatekony
> valtozo-kivalasztas), vagy ezeket be kell programoznunk.
>
> - a konyvtari labeling eljarast hasznaljuk, es a myval opcioval vesszuk at
> a vezerlest minden cimkezesi lepes elott. Persze ilyenkor is erdemes csak
> minden n. cimkezesi lepesben hajtani vegre a borotvalast, de most ezt
> csak globalis valtozok hasznalataval tudjuk elerni (lasd bb_put, bb_get
> beepitett eljarasok).
> Hatrany: ezeket a speci dolgokat (myval, bb_*) fel kell deriteni.
>
> Maga a borotvalas ugye abbol all, hogy vegigmegyunk a sudoku tablan, es
> megprobalunk egyes -- meg be nem helyettesitett -- mezoket szukiteni oly
> modon, hogy kivalasztunk egy lehetseges erteket, es megnezzuk, hogy ha erre
> helyettesitunk, akkor ez meghiusulast okoz-e. Ha igen, akkor nyertunk, ezt
> az erteket kizarhatjuk az adott valtozo lehetseges ertekei kozul. Ha nem,
> akkor nem volt szerencsenk, es nem tudunk szukiteni (es a behelyettesites
> miatt felebresztett demonok munkaja karba veszett).
>
> A fenti eljarast erdemes lehet nem az osszes mezore elvegezni, mert az sok
> karbaveszett munkahoz vezethet. Egy lehetseges korlatozas, hogy csak azokat
> a mezoket borotvaljuk, ahol mar keves lehetseges ertek van. Ha pl. egy
> olyan mezot borotvalunk, ahol mar csak ket ertek van, es szerencsenk van,
> akkor be is tudjuk helyettesiteni az adott mezo erteket.
>
> Ami a redundans korlatokat illeti, szobajohetnek:
>
> - a klasszikus (tavolsagkorlatok nelkuli) sudokura vonatkozo redundans
> korlatok.
>
> - a tavolsaginfokra vonatkozo redundans korlatok.
>
> Nyugodtan kerdezzetek, ha valami nem vilagos.
>
> -Peter
>
> _______________________________________________
> NHLP-l mailing list
> NHLP-l@sziami.cs.bme.hu
> http://sziami.cs.bme.hu/mailman/listinfo/nhlp-l