P R E S E K
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652 Letnik 18 (1990/1991) Številka 2 Strani 90-93
Janez Žerovnik:
PROBLEM TRDNJAV NA ŠAHOVNICI IN POŽREŠNA METODA
Ključne besede: računalništvo, matematika, problem trdnjav, požrešna metoda.
Elektronska verzija: http://www.presek.si/18/1032-Zerovnik.pdf
© 1990 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali posameznih delov brez poprejšnjega dovoljenja založnika ni dovoljeno.
PROBLEM TRDNJAV NA ŠAHOVNICI IN POŽREŠNA METODA
Nedavno sem naletel na zanimiv problem. K!jub temu, da je na prvi pogled videti enostaven, gaje v splošnem težko rešiti.
Začnimo v dveh dimenzijah. Imejmo šahovnico velikosti 3x3. Poskusimo postaviti nanjo kar najmanj trdnjav, tako da bo vsako polje napadeno vsaj po enkrat.
Prepričajmo se, da potrebujemo vsaj 3 trdnjave.
1.	če postavimo v vsaki vrstici vsaj eno trdnjavo, potem so v rešitvi gotovo vsaj 3 trdnjave.
2.	Pa recimo, da v rešitvi obstaja vrstica brez trdnjave. Ker so v vrstici 3 polja, morajo biti v ostalih dveh vrsticah vsaj 3 trdnjave, če hočemo, da bodo napadena vsa polja v vrstici brez trdnjave.
označuje položaj trdnjave
Slika 1. Skica ene od optimalnih rešitev za n = 2
če ne bi šlo drugače, bi lahko poskusili vse mogoče postavitve trdnjav, vendar tega ne priporočam. Vseh postavitev je namreč kar
23' = 29 = 512
saj je polj na šahovnici 32 = 9, na vsako polje pa lahko trdnjavo postavimo, ali pa ne.
Posplošimo zdaj primer na več dimenzij! V n dimenzijah imejmo rt— dimenzionalno "šahovnico" s3x3x- x3 = 3" polji. Vsako polje šahovnice
lahko opremimo s koordinatami. Ker smo se omejili na dolžino šahovnice 3. je koordinata eno od števil 0, 1, 2. Poljubno polje 3-dimenzionalne šahovnice tedaj enolično opišemo s trojico (/, j, , na primer (0, 0. 0), (0, 2, l), (2. 2, 0) itd. Položaj trdnjave opišemo s poljem, na katero je postavljena. Trdnjava na dvodimenzionalni šahovnici napada vsa polja, ki se od njenega položaja razlikujejo v natanko eni koordinati. In posplošimo: trdnjava na n-dimenzionalni šahovnici napada vsa polja, ki se od njenega položaja razlikujejo v natanko eni koordinati. Povzemimo:
	X	
		X
	X	
K
Problem trdnjav: Za dani n poišči minimalno število trdnjav, ki jih lahko postavimo na n-dimenzionalno šahovnico (s stranicami dolžine 3) tako, da bodo vsa polja šahovnice napadena.
Za kasnejšo rabo se dogovorimo, da bomo vsako postavitev trdnjav na šahovnico, pri kateri so vsa polja napadena, imenovali (približna) rešitev problema. Rešitev, pri kateri je uporabljeno minimalno število trdnjav pa imenujmo optimalna rešitev.
V angleščini problem imenujejo "the Football-Pool problem", kar bi lahko za silo prevedli kot "pro6/em športne napovedi'. Velja namreč naslednje: vsako rešitev problema (množica n-teric ničel, enic in dvojk) lahko uporabimo za športno napoved z n-pari. Rešitev ima lepo lastnost: vnaprej vemo, da bomo gotovo (vsaj enkrat) zadeli drugo nagrado (zgrešili bomo največ en izid). Ker plačamo prt športni napovedi vsak stolpec (torej vsako n-terico), je optimalna rešitev najcenejša rešitev z lastnostjo, da vedno zadane vsaj drugo nagrado.
Kljub temu, da na prvi pogled problem ni videti prezahteven, je povzetek znanega kaj skromen. S kombinatorično analizo so uspeli poiskati optimalne rešitve v dimenzijah 2,3,4 in 5. Dokaz, da je dobljena rešitev za dimenzijo 5 res optimalna, je dolg kar 10 strani! Za večje dimenzije je znanih nekaj zgornjih mej za optimalne rešitve, toda nič več. Dokazov, da so rešitve zares najboljše, torej optimalne, ni. Za računalnikarje bo zanimivo, da so doslej najboljše rešitve (in s tem najboljše zgornje meje za optimalno rešitev) v dimenzijah 6,7 in 8 našli z računalnikom. Algoritem, ki so ga uporabili, je popularno "ohlajanje" (angleško " Simulated Annealing" ) in je sam po sebi zanimiv, vendar njegov opis presega namene tega članka. Morda kdaj drugič, tukaj pa povejmo le to, da je algoritem za rezultate na Sliki 2 porabil veliko (ure in ure) časa na velikih računalnikih.
n	2 3 4 5 6 7 8
število trdnjav	3 5 9 27 < 73 < 136 < 468
Stika 2. Optimalne rešitve alt na]boljie ocene zanje
Poglejmo si enostavni poskus računanja rešitev po "požrešni metodi'. Opišimo na kratko idejo požrešne metode. Rešitev gradimo postopoma. Na vsakem koraku dodamo tisti element, ki največ prispeva h " kriterijski funkciji'. Sprejmemo ga le, če je s tem elementom razširjena množica še " dopustna". Kako deluje požrešna metoda na različnih problemih, st
lahko preberete na primer v knjigi Jerneja Kozaka Podatkovne strukture in algoritmi.
Naš program postopa preprosto: izbere si polje, ki še ni napadeno, in ga pokrije s trdnjavo, ki poleg izbranega pokrije ie kar največ novih polj. To ponavlja, dokler niso vsa polja napadena.
V našem konkretnem primeru je rešitev poljubna množica trdnjav. Kri-terijska funkcija je vsota števila trdnjav v rešitvi in števila še nenapadenih polj; optimalna je torej rešitev, ki napada vsa polja z najmanj trdnjavami. Dopustna je vsaka delna rešitev, ki jo je mogoče dopolniti do prave rešitve. V primeru problema trdnjav so vse delne rešitve dopustne, v splošnem pa utegnemo potrebovati nekaj več pazljivosti.
Požrešna metoda je enostavna, zato ne moremo pričakovati, da bo optimalna za vse probleme. Res se izkaže, da je za nekatere probleme mogoče dokazati, da je požrešna metoda "prava", za mnoge probleme pa velja, da s požrešno metodo ne bomo dobili optimalnih rešitev. Videli bomo, da to zadnje velja tudi za problem trdnjav na Šahovnici.
če algoritem poženemo, za n = 2, 3. 4, 5 dobimo optimalne rešitve! Ali to pomeni, da je problem tako enostaven? Na žalost ne, pri n — 6 je rezultat algoritma že 90 trdnjav, kar je precej slabše od enostavne rešitve, ki jo dobimo, Če sestavimo skupaj tri rešitve za n = S (Premisli, da taka konstrukcija pri vsakem n vedno da rešitev za n + 1 s trikratnim Številom trdnjavi). Če pogledamo na Sliko 2, vidimo, da je med n = 4 in n = 5 konstrukcija, ki sestavi tri manjše rešitve, celo optimalna, nasploh pa to seveda ni res.
n	2 3 4 5 6 7 8
število trdnjav	3 5 9 27 90 248 679
Slika 3. Reiitve. dobljene 5 požrešnim algoritmom
Kaj pa če bi način izbire trdnjav, ki naj pokrijejo izbrano polje nekoliko spremenili? Izdam vam, da sem nekaj različnih strategij preizkusil, pa se niso izkazale za dobre. Na primer: postavil sem trdnjavo kar na izbrano polje ali pa (slučajno) nekam na okolico, itd.
Morda bi se splačalo poskusiti s programom sestavljati (delne) rešitve za manjše dimenzije? Če je vašemu računalniku kdaj dolgčas, pa poskusite še vi! Še enkrat opozorimo, da je zelo malo možnosti, da bi hitro lahko našli kakšno 'doslej najboljšo rešitev'. Zelo zanimivo bi že bilo imeti algoritem (program), ki bi dajal boljše rešitve od požrešne metode.
Za konec pa še tole. Na n—dimenzionalni Šahovnici trdnjava napada (s poljem na katerega je postavljena) natanko 2n + 1 polj. Ker je na 4-dimenzionalni Šahovnici 34 = 81 polj, velja
3 : (2 - 4 H- l) = 81 : 9 = 9
In res obstaja rešitev z 9 trdnjavami za n = 4 (glej sliko 4), pri kateri je vsako polje napadeno natanko po enkrat!
22
21
20
1 1
1 0
02 01
00
K

Z
Z
K
£
H
£

00 0102 10 11 12 2021 22 Stika 4. Skica rešitve za n — 4
Povzemimo, Na videz enostavni problem trdnjav na šahovnici je zahteven. Požrešna metoda je dobra za n < 5, za n > 5 pa so rešitve, dobljene s požrešno metodo, slabe.
Janez Zerovnik