Aplikácie teórie grafov a teórie hier v rozhodovacích problémoch
|
Trenčianska Univerzita Alexandra Dubčeka v Trenčíne
Fakulta Mechatroniky |
|
| Autor: | Ľubomír Milko
|
| Pedagogický vedúci: | Ing. Juraj Ďuďák |
| Študijný odbor: | Mechatronika
|
| Akademický rok | 2009/2010
|
| Abstrakt
Táto práca obsahuje charakteristiku teórie hier a teórie grafov a následne popisuje použitie princípov z tejto oblasti v základných druhoch rozhodovacích problémov. Vo štvrtej kapitole sa podrobnejšie opisujú princípy analýzy a riešenia hier, ktoré môžu byť reprezentované hernými stromami. Posledná časť práce je venovaná implementácii rozobraných princípov voľby vhodného ťahu v doskovej hre dáma. |
| Abstract
tu bude anstrakt v AJ |
Úvod
Problémy vyžadujúce správne rozhodovanie s ohľadom na následky zvoleného rozhodnutia nás sprevádzajú v takmer všetkých oblastiach ľudskej činnosti od hrania rôznych spoločenských hier až po pokročilé riadenie cestnej siete, správne ekonomické rozhodnutia alebo stratégiu vojenských konfliktov. Postupné snahy o matematickú interpretáciu a riešenie týchto problémy voľby správneho rozhodnutia vyústili v samostatné odvetvie aplikovanej matematiky s názvom teória hier. V tejto teórii sa rozhodovacie problémy znázorňujú ako množina stratégií, ktoré možno prijať a množina následkov, ktoré vzniknú v dôsledku zvolenej stratégie. Následky sú často číselnou interpretáciou daného stavu. Na praktickú interpretáciu tohto súboru množín sa využíva teória grafov. Tieto dve teórie možno použiť na vyriešenie mnohých praktických rozhodovacích problémov. Zaujímavým praktickým a názorným príkladom aplikácie môže byť aj hľadanie optimálneho ťahu v doskových hrách akou je napríklad dáma. Súčasťou tejto práce je teda aj podrobnejšia ukážka využitia teórie hier a teórie grafov v tomto type hier. Cieľom tejto práce potom je:
- charakteristika teórie hier a teórie grafov,
- popis interpretácie základných rozhodovacích problémov pomocou týchto teórií,
- praktické použitie popísaných teoretických princípov pri voľbe vhodného ťahu v doskovej hre dáma.
Zoznam použitých skratiek a symbolov
- hra
- strategická interakcia medzi jednotlivcami
- hráč
- účastník hry
- minimax
- algoritmus, ktorý prechádzaním herného stromu vyberá optimálny ťah v hre
- pozícia
- aktuálny stav hry
- strom
- typ grafu, využívaný na znázornenie hier v rozšírenej forme
- ťah
- zvolená a uskutočnená stratégia hráča v danom bode hry
