[vastaus aiempaan viestiin]
| Kirjoittaja: | Seppo Mustonen |
|---|---|
| Sähköposti: | - |
| Päiväys: | 3.5.2006 13:35 |
Seurasin aluksi 3x4-ristikoiden määrän laskemisessa täsmälleen niitä
polkuja, jotka Reijo esitti viestissään "3x3-ristikoiden analyysia"
19.4.2006 ja muunsin laskentaa tässä tilanteessa (juuri samalla
tavalla kuin Reijo kuvaa edellisessä viestissään) kiinnittämällä
yhden luvun (12) ristikon viimeiseen paikkaan.
Näin lähtökohtana on fact(11)=39916800 erilaista ristikkoa ja
Reijon 19.4.2006 kuvaamalla tavalla suodattui näiden joukosta
94896 ehdokasta.
Laskennassa keskeinen vaihe on aggregointia edeltävä lajittelu,
jossa FILE SORT:in nopeuttamiseksi kannattaa varata riittävästi
tilaa keskusmuistissa tapahtuvaan työskentelyyn ja
myös oletusarvoa suurempi määrä väliaikaisia tiedostoja.
Käytin tuossa lajittelussa asetuksia WORKSPACE=10000000 FILEMAX=12.
Tällöin havaintojen järjestäminen sujui koneellani alle tunnissa.
Oletusarvoilla WORKSPACE=65535 FILEMAX=4 se kestää huomattavasti
pitempään.
Näiden ristikoiden joukossa jokainen olennaisesti erilainen esiintyy
12 kertaa, sillä (luvun 12 paikan kiinnittämisestä huolimatta)
pystyriveillä on vielä fact(3)=6 eri järjestystä ja vaakariveillä
fact(2)=2 eri järjestystä. Näin olennaisesti erilaisia 3x4-ristikoita
olisi korkeintaan 94896/6/2=7908.
Näistä vähemmistö antaa yksikäsitteisen ratkaisun.
Esim. eräs ehdokkaista on
1 2 4 3 10
5 6 8 7 26
9 10 11 12 42
15 18 23 22
mutta Survo-ristikolla
* * * * 10
* * * * 26
* * * * 42
15 18 23 22
on toinenkin ratkaisu
1 2 3 4 10
5 6 8 7 26
9 10 12 11 42
15 18 23 22
jossa luku 12 ei ole enää viimeisessä paikassa vaan liukunut kolmanteen
sarakkeeseen ja liittyy nyt sarakesummaan 23 eikä summaan 22.
Näin jokainen em. seulotuista ristikoista tulee tarkastaa erikseen
ratkaisun yksikäsitteisyyden osalta.
Yksikäsitteisen ratkaisun antavien ristikoiden etsintään käytin
ratkaisuohjelmaani. Koska tuo ohjelma tarvitsee lähtötietonaan
ratkaistavan ristikon matriisitiedostona, laadin sukron, joka
käy läpi kaikki 12*7908=94896 ristikkoa poimien 94896 havainnon
datatiedostosta vuorollaan aina yhden ristikon ja muuntaen sen
matriisitiedostoksi sekä lopuksi tarkastaen ratkaisuohjelmalla,
määräytyykö tulos yksikäsitteisesti.
* * *
Ratkaisuohjelman yleisperiaate:
Ratkaisuohjelmani toimii hyvin alkeellisen "geneettisen" algoritmin
mukaisesti. Se aloittaa sijoittamalla puuttuvat luvut umpimähkään
taulukkoon (satunnaistettu ristikko) ja yrittää sitten systemaattisin
vaihdoin saada lasketut rivi- ja sarakesummat mahdollisimman lähelle
oikeita summia.
Menettely johtaa joko oikeaan ratkaisuun tai (kuten yleensä) se
päätyy pattitilanteeseen, jossa se ei enää pysty parantamaan
ratkaisuksi kelpaamatonta tulosta.
Jälkimmäisessä vaiheessa tapahtuu "mutaatio", jossa kaksi tai useampia
lukuja vaihtaa paikkojaan satunnaisesti.
Tämän jälkeen yritetään parantaa tulosta jälleen systemaattisesti,
kunnes joko päädytään ratkaisuun tai joudutaan turvautumaan uuteen
mutaatioon.
Ristikon vaikeutta kuvaavaksi tunnusluvuksi olen ottanut tarvittujen
mutaatiokertojen lukumäärän keskiarvon, kun ratkaisu toistetaan esim.
1000 kertaa lähtemällä joka kerran täysin satunnaistetusta ristikosta.
Mutaatioiden lukumäärä näyttää noudattavan (kuten sopii odottaa)
geometrista jakaumaa. Olen tarkkaillut joissain esimerkkiristikoissa,
mikä on kussakin mutaatiossa paras vaihtojen lukumäärä.
Kolme vaihtoa näyttää ainakin 5x5-ristikoilla antavan keskimäärin
nopeimmin ratkaisun ja ratkaisu on luokkaa kolme kertaa nopeampi
kuin lähdettäessä pattitilanteen jälkeen kokonaan uudelleen
satunnaistetusta ristikosta.
* * *
Olen sisällyttänyt ratkaisuohjelmaan myös option, jolla se tutkii
ratkaisun yksikäsitteisyyttä ratkaisemalla tehtävän korkeintaaan
k kertaa ja jos se havaitsee, että syntyy yksikin ensimmäisestä
ratkaisusta eroava tulos, tästä tulee ilmoitus.
Sukroni ja ratkaisuohjelmani avulla (arvolla k=5) annoin koneen
käydä läpi kaikki 94896 ristikkoa eli se joutui ratkomaan lähes
puoli miljoonaa kertaa 3x4-ristikkoja ja aikaa kului tähän
hieman yli 7 tuntia.
Tämä karsinta jätti jäljelle 94896 ristikosta vain 7609.
Se ei kuitenkaan ole lopullinen tulos, sillä olennaisesti
erilaisten ristikoiden määräksi tulisi 7609/12=634.08333333333
mikä ei ole kokonaisluku.
Päättelin, että jäljellä on vielä monikäsitteisiä ristikoita, joita
ratkaisuohjelma ei vain ole tunnistanut sellaiseksi eli joissakin
tapauksissa tällaisesta ristikosta on saatu sama ratkaisu
k=5 yrityskerrasta huolimatta.
Niinpä seuloin 7609 jäljelle jäänyttä ristikkoa vielä uudelleen
arvolla k=15, jolloin niistä karsiutui 613 ja jäljelle jäi siis
6996, mistä olennaisesti erilaisten ristikoiden määräksi tulee
6996/12=583.
Tämän kerroin eilisessä (2.5.2006) viestissäni ja se on mitä
ilmeisimmin lopullinen lukumäärä, sillä toistin seulonnan
vielä arvolla k=30 (melkein 2 tunnin ajo), mutta yhtään monikäsitteistä
ristikkoa ei enää löytynyt.
Periaatteessa ratkaisuun päästäisiin suoraan Reijon 3x3-ristikkojen
analysoinnin kaltaisesti (siis kiinnittämättä yhtä luvuista), mutta
seulottavia ristikkoja olisi silloin alunperin 12-kertainen määrä
fact(12)=479001600 ja käsiteltävät tiedostot tulisivat tällöin
valtavan suuriksi, jolloin aikaa ehkä kuluisi yhteensä enemmän
kuin mitä käytin kuvaamassani menettelyssä (noin 11 tuntia).
* * *
Kimmo ilmoitti ratkaisseensa Survo-ristikon 8.
Tässä on toinen ehkä hieman vaikeampi:
SURVO-ristikko 9: (vaikeusaste noin 1800)
* * * * 35
* * * * 17
* * * * 26
15 32 22 9
-Seppo
| Vastaukset: |
|---|
Survo-keskustelupalstan (2001-2013) viestit arkistoitiin aika ajoin sukrolla, joka automaattisesti rakensi viesteistä (yli 1600 kpl) HTML-muotoisen sivukokonaisuuden. Vuoden 2013 alusta Survo-keskustelua on jatkettu entistäkin aktiivisemmin osoitteessa forum.survo.fi. Tervetuloa mukaan!