Problém 8-mich dám - História úprav

Juraj na 15:34, 24. máj 2010

2010-05-24T15:34:35Z

Pa3k na 18:41, 7. máj 2010

2010-05-07T18:41:11Z

Pa3k na 18:27, 7. máj 2010

2010-05-07T18:27:17Z

Pa3k na 18:26, 7. máj 2010

2010-05-07T18:26:00Z

Pa3k na 15:31, 4. máj 2010

2010-05-04T15:31:07Z

Pa3k na 15:17, 4. máj 2010

2010-05-04T15:17:13Z

Pa3k na 14:48, 4. máj 2010

2010-05-04T14:48:15Z

Pa3k: /* Niektoré základné riešenia pre n dám */

2010-05-04T14:42:19Z

Niektoré základné riešenia pre n dám

Pa3k na 07:29, 3. máj 2010

2010-05-03T07:29:15Z

Pa3k: Vytvorená stránka „== 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 pravidie…“

2010-05-03T07:14:38Z

Vytvorená stránka „== 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 pravidie…“

Nová stránka

== 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 dám ==

← Staršia verzia		Verzia zo dňa a času 15:34, 24. máj 2010
Riadok 1:		Riadok 1:
−	~~== O čo vlastne ide? ==~~	+	[[Kategória:Algoritmy a programovanie]]

	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.		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.

← Staršia verzia		Verzia zo dňa a času 18:41, 7. máj 2010
Riadok 93:		Riadok 93:
	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.		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.		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>

@@ Riadok 68: / Riadok 68: @@
 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 ==
@@ Riadok 90: / Riadok 89: @@
 . 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.

@@ Riadok 1: / Riadok 1: @@
 == 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.
+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.
+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í ==
@@ Riadok 68: / Riadok 68: @@
 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í.

@@ Riadok 65: / Riadok 65: @@
 == 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 do hĺbky). Jedná sa o hľadanie riešenia "hrubou silou". 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.
+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.
-Algoritmické problémy tohto typu sa dajú vyriešiť pomocou prehľadávania s návratom. 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.
+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že po každom navštívenom liste stromu sa algoritmus vráti do zásobníka. Tam má uložené miesta, odkiaľ sa vnoril. Vyberie ďalšiu vetvu a znova sa vnorí. Napríklad máme umiestnené 4 dámy a všetky políčka na 5-tom riadku pre 5. dámu sú ohrozované, vrátime sa a pre 4. dámu a zvolíme ďaľšie možné umiestnenie.
+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í.

← Staršia verzia		Verzia zo dňa a času 15:17, 4. máj 2010
Riadok 63:		Riadok 63:
	== Niektoré riešenia pre 8 dám ==		== 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]]		[[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 do hĺbky). Jedná sa o hľadanie riešenia "hrubou silou". 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.
		+	Algoritmické problémy tohto typu sa dajú vyriešiť pomocou prehľadávania s návratom. 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že po každom navštívenom liste stromu sa algoritmus vráti do zásobníka. Tam má uložené miesta, odkiaľ sa vnoril. Vyberie ďalšiu vetvu a znova sa vnorí. Napríklad máme umiestnené 4 dámy a všetky políčka na 5-tom riadku pre 5. dámu sú ohrozované, vrátime sa a pre 4. dámu a zvolíme ďaľšie možné umiestnenie.

@@ Riadok 58: / Riadok 58: @@
 |}
-== Niektoré základné riešenia pre n dám ==
+== 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]]

← Staršia verzia		Verzia zo dňa a času 14:42, 4. máj 2010
Riadok 59:		Riadok 59:

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

← Staršia verzia		Verzia zo dňa a času 07:29, 3. máj 2010
Riadok 59:		Riadok 59:

	== Niektoré základné riešenia pre n dám ==		== Niektoré základné riešenia pre n dám ==
		+	[[Súbor:4.jpg]]