Re: Uusi Survo-ristikoiden ratkaisuohjelma

[vastaus aiempaan viestiin]

Olen viime päivinä pystynyt vielä tehostamaan uuden Survo-ristikkojen
ratkaisuohjelman SP_SOL toimintaa karsimalla turhia rönsyjä.
Tällä ohjelmalla käsitellään toistaiseksi avoimia ristikkoja
(pelkät rivi- ja sarakesummat annettuna) ja sitä voidaan soveltaa paitsi
yksittäisten ristikkojen ratkaisujen määräämiseen ja ratkaisujen
lukumäärän (0,1,2,...) laskentaan myös (mikä on tärkeämpää) kaikkien
olennaisesti erilaisten, yksikäsitteisesti ratkeavien mxn-ristikkojen
luettelointiin ja niiden lukumäärän S(m,n) laskemiseen.
Jälkimmäinen tehtävä vaikeutuu mielettömän nopeasti dimensioiden m ja n
kasvaessa ja on yhä ilmeistä, ettei nykytiedoilla luvun S(5,5)
laskeminen näytä olevan mahdollista missään kohtuullisessa ajassa.
Kuitenkin luku S(4,5), suuruusluokaltaan 250000, on ehkä selvitettävissä
uusimpien tehostusten jälkeen.

Näiden parannusten kuvaamiseksi on syytä toistaa periaate, jolla
kaikki mahdolliset vaihtoehdot käydään läpi. Jo yli vuosi sitten
määrätessäni luvun S(3,4) en suinkaan yrittänyt tutkia kaikkia
mahdollisia tapauksia, joita on 12!=479001600 kpl. vaan pääsin
paljon vähemmällä tarkastelemalla ristikoita pelkästään kaikkien
mahdollisten reunasummien kautta. 3x4-ristikossa reunasummayhdistelmiä
on sarakkeittain 519 ja riveittäin 128 eli yhteensä 519*128=66432,
minkä Survossa saa selville seuraavilla COMB-kaavioilla:
............................
COMB P,CUR+1 / P=PARTITIONS,78,3 DISTINCT=1 MIN=10 MAX=42 RESULTS=0
Partitions 3 of 78: N[P]=128
............................
COMB P,CUR+1 / P=PARTITIONS,78,4 DISTINCT=1 MIN=6 MAX=33 RESULTS=0
Partitions 4 of 78: N[P]=519
...........................
Tutkittavien tapausten määrä 66432 on häviävän pieni 12-kertomaan
verrattuna eli hieman yli kymmenestuhannesosa.
Kuitenkin silloinen ratkaisuohjelmani tarvitsi parisen tuntia tehtävään
ja sain tulokseksi S(3,4)=583.
Tapaus S(4,4)=5327 olisi jo ollut erittäin työläs tuolle ohjelmalle,
mutta Petteri Kaski laski sen muutamassa tunnissa -
lähtien samalla tavalla reunasummayhdistelmistä mutta muuntaen tehtävän
ns. täsmällisen peitteen ongelmaksi ja käyttäen nopeita algoritmejaan.
Omalla koneellani S(4,4):n selvittäminen Kasken ohjelmalla vie lähes
neljä tuntia.
Uusi SP_SOL käyttää (edellisessä viestissäni kuvaamallani tavalla)
paremmin tehtävän erityisominaisuuksia ja sen tarvitsema aika luvun
S(4,4) laskentaan oli (pari viikkoa sitten) 160 sekuntia.
Viime päivinä olen kuitenkin saanut ohjelmaa nopeutettua niin paljon,
että aikaa kuluu vain neljäsosa eli noin 40 sekuntia.

Nopeutus perustuu olennaisesti siihen, että huomattava osa
reunasummayhdistelmistä, joita 4x4-tapauksessa on 2980*2979/2=4438710,
voidaan karsia ilman varsinaisen ratkaisualgoritmin soveltamista.
Tämä koskee erityisesti ratkeamattomia tapauksia, joita alunperin
olisi 1837169 (41.4 %), mutta niistä valtaosa saadaan mitätöidyksi niin,
että lukumääräksi jää "vain" 193695 (4.4 %).

Survolla (täsmennys POINT_COLOR on tässä hyödyksi) piirtämäni kuva

http://www.survo.fi/tmp/sol3x4.pdf 

kertoo miten monta ratkaisua kullakin reunasummayhdistelmällä
on 3x4-tapauksessa. Kuvassa eri tapaukset on esitetty värillisin
pistein seuraavasti:

väri       pisteitä  tulkinta

musta       22821    0 ratkaisua suoraan reunasummaehtojen nojalla
punainen      583    1 ratkaisu
vihreä      32505    2 tai useampia ratkaisuja
keltainen    2843    0 ratkaisua (ei todettavissa reunasummien avulla)
yhteensä    58752

Tästä kuvasta on karsittu valmiiksi sellaiset sarakeositukset (60 kpl),
jotka eivät voi antaa minkäänlaisia ratkaisuja alla kuvattavien
ehtojen (1) perusteella, jolloin kuvassa esiintyy yhteensä
(519-60)*128=58752 reunasummayhdistelmää.
Kuva antaa mielestäni hyvän yleiskäsityksen ongelman luonteesta ja
siitä, mihin SP_SOL pystyy viimeaikaisten tehostusten jälkeen.
Kuvaa katsellessa sitä kannattaa suurentaa riittävästi, jotta
saa käsityksen mm. siitä, miten häijysti tärkeät punaiset pisteet
lymyävät etupäässä vihreiden ja keltaisten seassa.

Ehdot, jotka sulkevat pois "turhat yritykset" ovat kuvattavissa näin:

Tarkastellaan (avointa) m x n -ristikkoa, jonka reunasummat ovat
r_1 < r_2 < ... < r_m ja c_1 < c_2 < ... < c_n.
Näistä muodostetut kumulatiiviset summat olkoot

  R_i = r_1 + ... + r_i, i = 1,2,...,m,
  C_j = c_1 + ... + c_j, j = 1,2,...,n.

Tällöin ristikolla ei ole ratkaisua, jos kumulatiiviset summat ovat
"liian pieniä" eli ainakin yksi ehdoista

      R_i <  2in(2in+1)/2, i=1,2,...,m,
(1)
      C_j <  2im(2im+1)/2, j=1,2,...,n.

toteutuu.
Nämä rajoitukset pudottavat esim. 4x4-tapauksessa vaihtoehtojen
määrän kummassakin suunnassa 2980:sta 2636:een.

Tästä päästään vielä huomattavasti alaspäin havaitsemalla, että
ristikolla ei ole yhtään ratkaisua, jos yksikin ehdoista

(2)   (jm+in-ij)(jm+in-ij+1)/2+ij(ij+1)/2 < R_i + C_j,

                                          i=1,...,m-1, j=1,...,n-1,

toteutuu. Ehdot on pääteltävissä melko helposti. Yleisen todistuksen
asemasta havainnollistan ehtoja (2) tapauksessa i=j=2, jolloin
ehto (2) saa muodon

(2a)     (2m+2n-4)(2m+2n-3)/2+10 < r_1+r_2+c_1+c_2

Tarkastelen mahdollista "ratkaistua" ristikkoa

      1   2   *   *     *  r_1
      3   4   *   *     *  r_2
      *   *
      *   *

      *   *
     c_1 c_2

Summa r_1+r_2+c_1+c_2 on pienin mahdollinen siten, että
ristikon vasemmassa yläkulmassa ovat pienimmät neljä lukua 1,2,3,4
(jossain järjestykseesä) ja sekä kahdessa ensimmäisessä rivissä
että kahdessa ensimmäisessä sarakkeessa ovat muissa paikoissa lukua 4
suuremmat, mahdollisimman pienet luvut. Näin näillä riveillä ja
sarakkeilla (2m+2n-4 paikkaa) voisivat pienimmillään sijaita luvut
1,2,...,2m-2n-4. Niiden summa on (2m+2n-4)(2m+2n-3)/2 ja koska summaan
r_1+r_2+c_1+c_2 luvut 1,2,3,4 (summa 10) tulevat kahteen kertaan
alarajaksi saadaan juuri ehdon (2a) mukainen (2m+2n-4)(2m+2n-3)/2+10.
Yleinen ehtojen (2) oikeiksi päättely menee luonnollisesti aivan
samalla tavalla.

Se, että ehdot (2) eivät karsi pois kaikkia mahdottomia yhdistelmiä
(eli kuvan keltaisia pisteitä)
johtuu mm. siitä, että esim. rivisumman r_1 ollessa minimaalinen eli
rivillä ovat luvut 1,2,3,4,..,n, vasemmassa 2x2-ylänurkassa
eivät voi olla pienimmät luvut 1,2,3,4 vaan esim. 1,2,5,6, jolloin
ehdosta (2a) saa rankemman.
Tällä tavalla "turhia" pisteitä saattaisi saada vielä lisää
karsituksi. Ratkaisuohjelman tehokkuuden kannalta on ehkä vielä
tärkeämpää (jos ajattelee sitä edelleen kehitettäväksi), että
monikäsitteisesti ratkeavia tapauksia, joita on eniten, pystytään
havaitsemaan vielä nykyistä paremmin.

Seppo Mustonen

Luettelo keskustelunaiheista

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!