Kiwiki - Príspevky používateľa [sk]

Problém 8-mich dám

2010-05-07T18:41:11Z

Pa3k:

== O čo vlastne ide? ==

Problém ôsmich dám je šachová úloha, resp. kombinatorický problém kde treba umiestniť na šachovnicu osem dám tak, aby sa podľa pravidiel šachu navzájom neohrozovali.

== História úlohy ==
Problém ôsmich dám bol prvý krát zverejnený v berlínskom časopise Schachzeitung v roku 1848 Maxom Bezzelom. V ďalších rokoch sa problémom zaoberalo veľa slávnych matematikov vrátane Carla Friedricha Gaussa. Zovšeobecnenie problému na n dám navrhol v roku 1850 Franz Nauck, ktorý tiež správne stanovil počet všetkých riešení pôvodného problému. V roku 1874 navrhol Siegmund Günther metódu riešenia úlohy pomocou determinantov, ktorú neskôr vylepšil James Whitbread Lee Glaisher.

== Počet riešení ==
Problém má 92 riešení (uvažujú sa kombinácie). Riešenia sa získavajú aj pomocou symetrie (zrkadlovým otáčaním). Je 12 základných riešení: 11 má osem symetrií, 1 iba štyri lebo je samo stredovo symetrické.
Počet všetkých riešení problému n dám, započítaním symetrie aj bez nej je pre malé n takýto: pre n=1 existuje jediné triviálne riešenie, pre n=2 a n=3 neexistuje riešenie. Je domnienka, že počet riešení sa asymptoticky chová ako n!/c*n, kde c je okolo 2,54.

== Tabuľka počtu riešení ==
{| class=wikitable border=1 cellpadding=5
|-
! n
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
| 9
| 10
| 11
| 12
|-
! unikátne
| 1
| 0
| 0
| 1
| 2
| 1
| 6
| 12
| 46
| 92
| 341
| 1785
|-
|-
! všetky
| 1
| 0
| 0
| 2
| 10
| 4
| 40
| 92
| 352
| 724
| 2680
| 14200
|-
|}

== Niektoré základné riešenia pre n <4,7> dám ==
[[Súbor:4.jpg]] [[Súbor:5.jpg]] [[Súbor:6.jpg]] [[Súbor:7.jpg]]

== Niektoré riešenia pre 8 dám ==
[[Súbor:8_1.jpg]] [[Súbor:8_2.jpg]] [[Súbor:8_3.jpg]] [[Súbor:8_4.jpg]] [[Súbor:8_5.jpg]]

== Metóda riešenia – backtracking ==
Spôsob hľadania riešenia pre rôzne všeobecné problémy je tzv. metóda Backtracking (metóda pokusov a opráv, prehľadávanie s návratom, prehľadávanie do hĺbky). Jedná sa o hľadanie riešenia "hrubou silou", pretože veľké množstvo potencionálnych riešení môže byť vylúčené bez priameho vyskúšania. Princíp spočíva v tom, že celý proces sa rozloží na niekoľko čiastkových úloh, ktoré sa často vyjadrujú pomocou rekurzie a spočívajú v preskúmaní konečného počtu podúloh. Opakovaním pokusov (vyhľadávaní) sa postupne vytvorí a skúmaním zmenšuje strom podúloh.
Algoritmus funguje tak, že sa zoberú do úvahy všetky možnosti, ktoré môžu viesť k vyriešeniu problému. Potom sa postupne rekurzívne riešia jednotlivé podproblémy. Množina rekurzívnych volaní vytvára stromovú štruktúru, kde je postupne kontrolovaná každá podmnožina možností. Z toho vyplýva, že ak riešenie existuje, algoritmus ho po určitom čase nájde.
Backtracking je však vo všeobecnosti neefektívny prístup k riešeniu problému. Pomocou rôznych optimalizačných techník sa dá zredukovať hĺbka stromu a aj počet podstromov. Technika sa volá prehľadávanie s návratom preto, lebo po každom navštívenom liste stromu sa algoritmus vráti do zásobníka kde má uložené miesta, odkiaľ sa vnoril. Potom vyberie ďalšiu vetvu a znova sa vnorí.

== Algoritmus backtrackingu ==
1. k:=1; a[0] := Ø; {Vektor Ø je prázdny}

2. IF V[k] = Ø THEN pokračuj bodom 8; {Vo V[k] nie sú ďalší kandidáti}

3. Vyber a[k] z V[k]; V[k] := V[k] - {a[k]}; {Z V[k] vybrať ďalšieho kandidáta}

4. a[k] := a[k-1] a[k]; {Vektor a[k-1] je predĺžený o 1 prvok}

5. IF k >= n THEN Vypíš riešenie; Koniec

6. k := k + 1; {Prechod k ďalšiemu predĺženiu}

7. Pokračuj krokom 2;

8. k := k - 1; {Odstránenie posledného predĺženia}

9. IF k=0 THEN Vypíš "Riešenie neexistuje";Koniec

10. Pokračuj krokom 2;

== Formulácia ==
Problém označme ako P. Predpokladajme, že riešením problému má byť vektor a[n] = (a[1], a[2], ..., a[n]), ktorý spĺňa určitú vlastnosť, ktorú označme ako A. Vo všeobecnosti platí, že i-tá položka tohoto vektora bola vybratá z množiny povolených hodnôt V[i], t.j. a[i] z V[i] pre i= 1, 2, ..., n. Vektor a[n] má n, pre n=1, 2, ..., prvkov a je postupne predlžovaný, t.j. pre n=1 má jeden prvok, pre n=2 dva prvky, atď. Jedna možnosť ako vyriešiť problém P by bolo vyskúšať všetky možnosti (použiť "hrubú silu"), ale to by viedlo k prevereniu |V[1]|*|V[2]|*... *|V[n]| vektorov.
Metóda prehľadávania s návratom umožňuje ušetriť skúmanie niektorých vektorov, pretože vektor riešenia je konštruovaný postupne a predlžovaný v súlade s vlastnosťou A. Predĺženie je vždy najprv skontrolované a je možné len vtedy, ak nebude porušená vlastnosť A.

== Použité zdroje ==
[1] Problém osmi dam. Dostupné: <http://cs.wikipedia.org/wiki/Problém_osmi_dam>

[2] Backtracking. Dostupné: <http://cs.wikipedia.org/wiki/Backtracking>

[3] Andrejková, G.: Metóda prehľadávanie s návratom (Backtrack). Dostupné:
<http://ics.upjs.sk/~novotnyr/home/skola/programovanie_a_algoritmy/10tyzden.doc>

[4] Backtracking. Dostupné: <http://www.sprite.edi.fmph.uniba.sk/~szorad/Zaklady/Backtracking.html>

Problém 8-mich dám

2010-05-07T18:27:17Z

Pa3k:

Problém 8-mich dám

2010-05-07T18:26:00Z

Pa3k:

Problém 8-mich dám

2010-05-04T15:31:07Z

Pa3k:

== O čo vlastne ide? ==

Problém ôsmich dám je šachová úloha resp. kombinatorický problém kde treba umiestniť na šachovnicu osem dám tak, aby sa podľa pravidiel šachu navzájom neohrozovali.

== História úlohy ==
Problém ôsmich dám bol prvý krát zverejnený v berlínskom časopise Schachzeitung v roku 1848 Maxom Bezzelom. V dalších rokoch sa problémom zaoberalo veľa slávnych matematikov vrátane Carla Friedricha Gaussa. Zovšeobecnenie problému na n dám navrhol v roku 1850 Franz Nauck, ktorý tiež správne stanovil počet všetkých riešení pôvodného problému. V roku 1874 navrhol Siegmund Günther metódu riešenia úlohy pomocou determinantov, ktorú neskôr vylepšil James Whitbread Lee Glaisher.

== Počet riešení ==
Problém má 92 riešení (uvažujú sa kombinácie). Riešenia sa získavajú aj pomocou symetrie (zrkadlovým otáčaním). Je 12 základných riešení: 11 má osem symetrií, 1 iba štyri lebo je samo stredovo symetrické.
Počet všetkých riešení problému n dám, započítaním symetrie aj bez nej je pre malé n takýto: pre n=1 existuje jediné triviálne riešenie, pre n=2 a n=3 neexistuje riešenie. Je domnienka, že počet riešení sa asymptoticky chová ako n!/c*n, kde c je okolo 2,54.

== Tabuľka počtu riešení ==
{| class=wikitable border=1 cellpadding=5
|-
! n
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
| 9
| 10
| 11
| 12
|-
! unikátne
| 1
| 0
| 0
| 1
| 2
| 1
| 6
| 12
| 46
| 92
| 341
| 1785
|-
|-
! všetky
| 1
| 0
| 0
| 2
| 10
| 4
| 40
| 92
| 352
| 724
| 2680
| 14200
|-
|}

== Niektoré základné riešenia pre n <4,7> dám ==
[[Súbor:4.jpg]] [[Súbor:5.jpg]] [[Súbor:6.jpg]] [[Súbor:7.jpg]]

== Niektoré riešenia pre 8 dám ==
[[Súbor:8_1.jpg]] [[Súbor:8_2.jpg]] [[Súbor:8_3.jpg]] [[Súbor:8_4.jpg]] [[Súbor:8_5.jpg]]

== Metóda riešenia – backtracking ==
Spôsob hľadania riešenia pre rôzne všeobecné problémy je tzv. metóda Backtracking (metóda pokusov a opráv, prehľadávanie s návratom, prehľadávanie do hĺbky). Jedná sa o hľadanie riešenia "hrubou silou", pretože veľké množstvo potencionálnych riešení môže byť vylúčené bez priameho vyskúšania. Princíp spočíva v tom, že celý proces sa rozloží na niekoľko čiastkových úloh, ktoré sa často vyjadrujú pomocou rekurzie a spočívajú v preskúmaní konečného počtu podúloh. Opakovaním pokusov (vyhľadávaní) sa postupne vytvorí a skúmaním zmenšuje strom podúloh.
Algoritmus funguje tak, že sa zoberú do úvahy všetky možnosti, ktoré môžu viesť k vyriešeniu problému. Potom sa postupne rekurzívne riešia jednotlivé podproblémy. Množina rekurzívnych volaní vytvára stromovú štruktúru, kde je postupne kontrolovaná každá podmnožina možností. Z toho vyplýva, že ak riešenie existuje, algoritmus ho po určitom čase nájde.
Backtracking je však vo všeobecnosti neefektívny prístup k riešeniu problému. Pomocou rôznych optimalizačných techník sa dá zredukovať hĺbka stromu a aj počet podstromov. Technika sa volá prehľadávanie s návratom preto, lebo po každom navštívenom liste stromu sa algoritmus vráti do zásobníka kde má uložené miesta, odkiaľ sa vnoril. Potom vyberie ďalšiu vetvu a znova sa vnorí.

Problém 8-mich dám