Käyttöympäristö tekstin ja numeerisen tiedon luovaan käsittelyyn |  |
Käyttöympäristö tekstin ja numeerisen tiedon luovaan käsittelyyn | |
Survo-ristikoiden ratkaiseminen reunasummien tulojen avulla
Tähänastiset kokemukset osoittavat, että Survo-ristikoiden
ratkaisemisessa ilman varsinaista ratkaisuohjelmaa
saatetaan käyttää hyvinkin erilaisia keinoja.
Useimmin toimitaan puhtaasti loogisten päätelmien avulla, mutta joskus
myös esim. Survon antama laskennallinen tuki on hyödyksi.
Normaalissa manuaalisessa ratkaisutavassa ristikkoa pyritään täyttämään
avointen ruutujen osalta vaihe vaiheelta parhaimmillaan
tiukan päättelyketjun avulla siten, että joka tilanteessa tehty
valinta on ainoa mahdollinen. Varsinkin helppoja ristikkoja
monet kuitenkin ratkovat myös osittain arvaamalla.
Esitän tässä erilaisen menettelyn, joka perustuu muutaman jo aikaisemmin
käytetyn keinon yhdistelemiseen ja muuntaa tehtävän hieman
shakkitehtävän tapaiseksi.
Tällä menetelmällä useat vaikeiksi koetut tehtävät saattavat ratketa
yllättävän helposti. Se ei kuitenkaan anna kätevää ratkaisua kaikille
Survo-ristikoille eikä sen avulla voi ainakaan toistaiseksi todeta
ratkaisun yksikäsitteisyyttä.
Tämä ratkaisutapa on toisaalta sukua alkuperäisen ratkaisuohjelmani
pääidealle, jossa
(satunnaisesti täytettyä) taulukkoa parannellaan vaihtamalla
lukujen paikkoja niin, että saadaan lopulta annetut ja
lasketut summat täsmäämään
ja toisaalta sille ilmeiselle piirteelle, että
pienet luvut sijoittuvat pienten summien risteyksiin ja
suuret suurten risteyksiin
sekä täsmällisemmin mm. Joonas Kauppisen ja Markku Verkasalon
esittämiin näkemyksiin siitä, että
reunasummien tulot osoittavat karkeasti lukujen oikean järjestyksen.
Reunasummien tulojen käytölle löytyy tilastollinen perustelu.
Jos tulkitaan Survo-ristikko kahden muuttujan otoksesta lasketuksi
frekvenssitaulukoksi ja muuttujat oletetaan toisistaan riippumattomiksi,
taulukon kussakin ruudussa odotettu frekvenssi on vastaavien reuna-
summien tulo jaettuna otoskoolla. Siis nuo tulot sellaisinaan ovat
verrannollisia odotettuhin frekvensseihin.
Kun nämä periaatteet yhdistetään (ja mietitään hieman lisää), ainakin
avoimet Survo-ristikot (olen ehtinyt vasta tarkastella lähemmin
4x4-tapausta) saa ratkaistuksi useimmiten yllättävän helposti hiukan
shakkitehtävien tyyliin esim. "matti kahdella siirrolla".
Näytän, miten se tapahtuu viime vuoden kesäkuun ensimmäisessä
kirjoituksessani (sivuilla 17-21) esitetyssä ja ratkaistussa tehtävässä
* * * * 14
* * * * 28
* * * * 44
* * * * 50
16 33 40 47
Reunasummien tulojen taulukko on silloin
224 462 560 658 14
448 924 1120 1316 28
704 1452 1760 2068 44
800 1650 2000 2350 50
16 33 40 47
ja kun luvut 1-16 pannaan taulukkoon näiden tulojen
suuruusjärjestyksessä, saadaan taulukko
1 3 4 5 14
2 8 9 10 28
6 11 13 15 44
7 12 14 16 50
16 33 40 47
joka ei sellaisenaan kelpaa, koska esim. ensimmäinen
rivisumma on 1+3+4+5=13 eikä 14, mutta summat ovat
silti lähellä oikeita seuraavasti:
Sum OK D
1 3 4 5 13 14 -1
2 8 9 10 29 28 1
6 11 13 15 45 44 1
7 12 14 16 49 50 -1
Sum 16 34 40 46
OK 16 33 40 47
D 0 1 0 -1 W=6
Tässä Sum vastaa laskettua summaa, OK oikeaa summaa ja D niiden erotusta
(virhettä) D=Sum-OK. Virheiden itseisarvojen summa on W=6.
Tavoitteena on nyt pienentää virhettä vaihtamalla sopivasti kahden luvun
paikkoja. Hyvältä näyttää tällöin vaihto (5,6), mikä johtaa tilanteeseen
Sum OK D
1 3 4 6 14 14 0
2 8 9 10 29 28 1
5 11 13 15 44 44 0
7 12 14 16 49 50 -1
Sum 15 34 40 47
OK 16 33 40 47
D -1 1 0 0 W=4
eli virhe on pudonnut arvoon W=4.
Tästä päästäänkin perille heti toisella siirrolla (7,8)
Sum OK D
1 3 4 6 14 14 0
2 7 9 10 28 28 0
5 11 13 15 44 44 0
8 12 14 16 50 50 0
Sum 16 33 40 47
OK 16 33 40 47
D 0 0 0 0 W=0
eli tehtävä ratkeaa todella helposti verrattuna vaikka alkuperäiseen
ratkaisuuni, jossa tosin pääteltiin samalla tuloksen yksikäsitteisyys.
Äskeisessä tehtävässä tarvittiin siis vain kaksi siirtoa.
Näin vähällä ei yleensä selvitä, mutta em. kirjoituksessani sivulla 24
esitetty ristikko, jolle nyt etsittiin mahdollisimman yksinkertaista
ratkaisua tehtävänä 65/2007
A B C D
1 * * * * 51
2 * * * * 36
3 * * * * 32
4 * * * * 17
51 42 26 17
ratkeaa sekin tällä "vaihtomenetelmällä" yllättävän sukkelasti eli
viidellä siirrolla. Ratkaisun olen saattanut Flash-demon muotoon.
Selvittääkseni, miten tämä menettely toimii yleisesti avoimilla,
yksikäsitteisesti ratkeavilla 4x4-ristikoilla, joita on 5327,
olen etsinyt niistä jokaiselle lyhimmän ratkaisun.
Siirtoja tarvitaan seuraavan taulukon mukaisesti
Siirtoja 0 1 2 3 4 5 6 7 8 9
frekvenssi 85 262 522 977 1271 1222 696 255 36 1
kumul. 85 347 869 1846 3117 4339 5035 5290 5326 5327
% 1.6 6.5 16.3 34.7 58.5 81.5 94.5 99.3 100.0
Summien tulot antavat siis suoraan ratkaisun 85 tapauksessa 5327:stä
ja 81.5 % näistä ristikoista ratkeaa alle 6 siirrolla.
Olen pyrkinyt ratkaisemaan (menettelyn alkuasetelmasta ja siirtojen
kirjanpidosta huolehtivan) sukron /SP_SWAP tuella useita näistä
tehtävistä ja kokemukseni viittaavat siihen, että jos siirtojen määrä
on korkeintaan 5, tehtävän saa selvitettyä suhteellisen helposti.
Ryhtyessään ratkomaan tehtävää ei kuitenkaan voi tietää etukäteen
tarvittavien siirtojen määrää. Jonkinlaisen ennusteen saa tehtävän
summien tulojen avulla muodostetun alkuasetelman virhesumman W avulla.
W vaihtelee nollasta arvoon 22 ja se kertoo tarvittavien siirtojen
määrästä mm. seuraavaa:
W siirtoja<6 W-arvojen frekvenssit
0-4 100.0 % 467
6 99.5 % 417
8 99.0 % 609
10 93.6 % 879
12 85.8 % 896
14 70.6 % 929
16 56.6 % 681
18 49.6 % 312
20 46.8 % 126
22 54.5 % 11
kaikki 81.5 % 5327
Jos siis virheiden lähtösumma on 10 tai pienempi, 4x4-ristikko ratkeaa
alle 6 siirrolla "93.6-prosenttisesti".
Siirtojen määrän keskiarvo on noin 4 (ja hajonta 1.6). Jos
aloitettaisiin aivan umpimähkään täytetystä ristikosta, keskiarvo
olisi olennaisesti suurempi eli noin 12.6 (ja hajonta 1.3),
mikä näytetään seuraavasti.
Menetelmän toimivuus (ainakin tässä 4x4-tilanteessa) perustuu paljolti
myös siihen, että jos lasketaan kaikista 5327 ristikosta (kuvitellen
ne frekvenssitaulukoiksi) khi^2-arvot, ne sijoittuvat välille
(0.25,8.25) eli suurinkin niistä on alle vapauasteiden 9 lukumäärän,
joka on riippumattomilla muuttujilla odotusarvo. Keskiarvo on nyt 3.95
ja keskihajonta 1.76. Niinpä näissä taulukoissa tuo "muuttujien
riippumattomuus" on siis jopa ylikorostunutta ja siksi summien tulot
ennustavat hyvin oikeaa ratkaisua.
Useimmiten ratkaisun pääjuonena on tehdä vaihdot niin, että virhesumma W
alenee jokaisessa siirrossa, koska tällöin "hyvän pelisilmän omaava"
näkee kussakin tilanteessa, mitkä vaikuttavat järkeviltä valinnoilta.
Toisinaan tilanne on hankalampi mm. siten, että W on heti alkuun niin
alhainen, ettei edellinen strategia pure, vaan on tehtävä "uhrauksia"
(hiukan shakkiongelmien tyyliin) eli valittava siirtoja, joissa W
väliaikaisesti kasvaa. Tällöin joutuu käyttämään myös muunlaisia
päättelyjä seuraavan esimerkin tapaan.
* * *
Jotta tässä kuvattua tekniikkaa olisi käytännössä mahdollisimman helppo
soveltaa, olen siis laatinut sukron /SP_SWAP, joka "esitäyttää" ristikon
summien tulojen mukaisesti ja antaa sitten käyttäjälle tilaisuuden tehdä
peräkkäin hiiren ja X-, Y-nappien avulla haluamiaan vaihtoja (swap).
Sukro päivittää jokaisen vaihdon jälkeen pelipöytäkirjan ja näyttää
siirtohistorian. Sukrolla on mahdollista käsitellä myös ei-avoimia
ristikoita, sillä esitäyttöohjelma (uusi pieni Survo-moduli SPGUESS)
käyttää silloin hieman yleistettyä summientulo-tekniikkaa. Näissä
tapauksissa valmiiksi annetut luvut näytetään sinisellä taustalla, jotta
pelaaja tietää varoa siirtelemästä noita "kiintopisteitä".
Sukron /SP_SWAP käyttö edellyttää täyttä SURVO MM -versiota.
Erikseen olen myöhemmin (vuoden 2008 alussa) tehnyt verkossa toimivan
Java-sovelman,
joka luo arpoen lukuisia Survo-ristikoita ratkaistavaksi vaihtomenetelmällä.
* * *
Sukro /SP_SWAP edellyttää, että ratkaistava Survo-ristikko talletetaan
Survossa matriisina. Esim. tehtävä
* * * * 14
* * * * 28
* * * * 44
* * * * 50
16 33 40 47
talletetaan muodossa
MAT SAVE AS A
0 0 0 0 14
0 0 0 0 28
0 0 0 0 44
0 0 0 0 50
16 33 40 47 0
ja sukro käynnistetään komennolla
/SP_SWAP A
Tässä on muutamia tehtäviä, joita voi yrittää ratkaista vaihtomenetelmällä:
Tehtävä S0: (ratkeaa suoraan)
MAT SAVE AS A
0 0 0 0 15
0 0 0 0 32
0 0 0 0 41
0 0 0 0 48
14 33 38 51 0
Tehtävä S1: (ratkeaa kolmella siirrolla)
MAT SAVE AS A
0 0 0 0 48
0 0 0 0 43
0 0 0 0 34
0 0 0 0 11
47 41 30 18 0
Tehtävä S2: (4 siirtoa)
MAT SAVE AS A
0 0 0 0 55
0 0 0 0 44
0 0 0 0 23
0 0 0 0 14
45 39 29 23 0
Tehtävä S3:
MAT SAVE AS A
0 0 0 0 0 27
0 0 0 0 0 37
0 0 0 0 0 56
9 17 24 31 39 0
Tehtävä S4:
MAT SAVE AS A
0 0 0 0 57
0 0 0 0 41
0 0 0 0 27
0 0 0 0 11
44 36 31 25 0
Tehtävä S5:
MAT SAVE AS A
0 0 0 0 56
0 0 0 0 38
0 0 0 0 31
0 0 0 0 11
45 37 32 22 0
* * *
Vaihtojen lukumäärän jakauman laskeminen satunnaiselle permutaatiolle
Vaihtojen lukumäärän jakaumaa ei yleisesti kannata lähteä laskemaan
määräämällä tuo lukumäärä kullekin permutaatiolla erikseen, koska
4x4-ristikoiden tapauksessa niitä on fact(16)=20922789888000 kappaletta.
Vaikka sekunnissa saisi laskettua miljoona tapausta, koko laskentaan
kuluisi yli puoli vuotta.
Näytän, miten Survon matriisi- ja "polynomi"-tulkin avulla jakauma
saadaan selville tarkkaan numeerisesti hyvin nopeasti. On hyvä
matemaattinen harjoitustehtävä osoittaa, miksi näin saadaan
haluttu tulos.
Tarkastellaan tuloa (x-1)*(x-2)*(x-3)*...*(x-15) ja kehitetään
se polynomiksi s0+s1*x+s2*x^2+...+s15*x^15.
Kertoimet s0,s1,s2,s3,...,s15 ovat tällöin ns. Stirlingin ensimmäisen
lajin lukuja ja niiden itseisarvot jaettuna luvulla 16! ilmaisevat
käänteisessä järjestyksessä vaihtojen lukumäärän jakauman pistetoden-
näköisyydet.
Laskenta tapahtuu tällöin Survolla esim. näin:
Muodostetaan tarvittavien polynomien (binomien) kerroinvektorit:
MAT SAVE AS P
-1
1
MAT SAVE AS P2
-2
1
MAT SAVE AS P3
-3
1
sama arvoilla 4-15 eli siis viimeisenä
MAT SAVE AS P15
-15
1
Lasketaan binomien tulo:
POL P=P*P2
POL P=P*P3
POL P=P*P4
POL P=P*P5
POL P=P*P6
POL P=P*P7
POL P=P*P8
POL P=P*P9
POL P=P*P10
POL P=P*P11
POL P=P*P12
POL P=P*P13
POL P=P*P14
POL P=P*P15
MAT TRANSFORM P BY abs(X#)
Tulostetaan kertoimien s0,s1,...,s15 itseisarvot, tarkistetaan
(kosketuslaskennalla) niiden summa (joka on siis 16!) ja jakamalla
sillä saadaan jakauman pistetodennäköisyydet:
MAT LOAD P,12345678901245,CUR+1
MATRIX P
Polynom
/// real todennäköisyys vaihtojen lukumäärä
0 1307674368000 0.06250000000000 15
1 4339163001600 0.20738931207681 14
2 6165817614720 0.29469385525189 13
3 5056995703824 0.24169796336407 12
4 2706813345600 0.12937153028299 11
5 1009672107080 0.04825704948933 10
6 272803210680 0.01303856761648 9
7 54631129553 0.00261108245341 8
8 8207628000 0.00039228171979 7
9 928095740 0.00004435812552 6
10 78558480 0.00000375468474 5
11 4899622 0.00000023417632 4
12 218400 0.00000001043838 3
13 6580 0.00000000031449 2
14 120 0.00000000000574 1
15 1 0.00000000000005 0
20922789888000
Tästä saadaan (edelleen kosketuslaskennalla) jakauman odotusarvo
ja hajonta:
m=12.619271006771 (odotusarvo)
S2=161.04238320212 (neliöiden painotettu summa)
s=sqrt(S2-m^2) s=1.3402919308079 (hajonta)
* * *
Esimerkki tehtävästä, joka edellyttää "uhrausta"
* * * * 49 vaikeusaste=1700
* * * * 39
* * * * 33
* * * * 15
49 43 29 15
Vaihtomenettelyn alkuasetelma on tällöin
C1 C2 C3 C4 Sum OK D
R1 16 15 11 7 49 49 0
R2 14 13 9 4 40 39 1
R3 12 10 8 3 33 33 0
R4 6 5 2 1 14 15 -1
Sum 48 43 30 15
OK 49 43 29 15 W=4
D -1 0 1 0
eli W on ainoastaan 4, mutta ristikko ei ratkea tästä suoraan
yhdellä tai parilla vaihdolla.
Koska minimisummat ovat molemmat suuruudeltaan 15, kannattaa
tarkastella niiden mahdollisia osituksia:
COMB P,CUR+1 / P=PARTITIONS,15,4 DISTINCT=1
Partitions 4 of 15: N[P]=6
1 2 3 9
1 2 4 8
1 2 5 7
1 3 4 7
1 3 5 6
2 3 4 6
Ainoat yhteensopivat ositusvaihtoehdot ovat silloin
8 4 2 1 - 6 5 3 1
7 5 1 2 - 6 4 3 2
ja näistä ensimmäinen pari on lähempänä alkuasetelmaa.
Kannattaa siis aloittaa vaihdoilla (2,3) ja (7,8), jolloin
viimeinen rivi ja sarake saadaan summiltaan oikeiksi, mutta
W kasvaa arvoon 6 (uhraus!)
C1 C2 C3 C4 Sum OK D
R1 16 15 11 8 50 49 1
R2 14 13 9 4 40 39 1
R3 12 10 7 2 31 33 -2
R4 6 5 3 1 15 15 0
Sum 48 43 30 15
OK 49 43 29 15 W=6
D -1 0 1 0
Nyt on helppo havaita, että vaihdot (12,13) ja (10,11)
vievät lopputulokseen
C1 C2 C3 C4 Sum OK D
R1 16 15 10 8 49 49 0
R2 14 12 9 4 39 39 0
R3 13 11 7 2 33 33 0
R4 6 5 3 1 15 15 0
Sum 49 43 29 15
OK 49 43 29 15 W=0
D 0 0 0 0
eli tehtävä on ratkaistu 4 siirrolla.