Slovenské vysoké školy | 42 770 autorov Zaregistruj
Hľadaj Zobraz: Univerzity Kategórie Rozšírené vyhľadávanie

45 114
projektov

 Home » Bakalárska práca » Aplikácie teórie hier a teórie grafov v rozhodovacích problémoch

Trenčianska univerzita Alexandra Dubčeka v Trenčíne - TNUNI

Fakulta mechatroniky

Aplikácie teórie hier a teórie grafov v rozhodovacích problémoch

«»
Prípona
.pdf		 Typ
bakalárska práca		 Stiahnuté
2 x
Veľkosť
1,3 MB		 Jazyk
slovenský		 ID projektu
35711
Posledná úprava
09.11.2010		 Zobrazené
1 297 x		 Autor:
defluo
Facebook icon Zdieľaj na Facebooku
Detaily projektu
Popis:
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 praktické využitie poznatkov z 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 v programe – hra dáma

Kľúčové slová:

teória grafov

teória hier

graf

hra

herný strom

minimax algoritmus

alfa-beta orezávanie

hra dáma



Obsah:

  •  


    Zoznam obrázkov. 9


    Zoznam tabuliek. 10


    Zoznam skratiek a značiek. 11


    Slovník termínov. 12


    Úvod. 13


    1       Teória hier. 14


    1.1        Základné pojmy a charakteristika teórie hier 14


    1.2        Stručný vývoj teórie hier 15


    1.3        Oblasti využitia teórie hier 16


    1.4        Spôsoby reprezentácie rozhodovacích problémov. 17


    1.4.1         Rozšírená forma (Extensive form) 17


    1.4.2         Normálna forma (Normal form) 18


    1.4.3         Forma charakteristickej funkcie. 19


    1.4.4         Forma rozdeľujúcej funkcie  (Partition function form) 19


    1.5        Typy hier 19


    1.5.1         Kooperatívne a nekooperatívne hry. 19


    1.5.2         Symetrické a asymetrické hry. 19


    1.5.3         Hry s nulovým a nenulovým súčtom.. 20


    1.5.4         Simultánne a ťahové (sekvenčné) hry. 21


    1.5.5         Hry s úplnými a neúplnými informáciami 21


    1.5.6         Nekonečne dlhé hry. 22


    1.5.7         Metahry. 22


    2       Teória grafov. 23


    2.1        Základné pojmy a charakteristika grafov. 23


    2.2        Základné druhy grafových štruktúr 24


    2.3        Typy problémov riešených pomocou teórie grafov. 25


    2.3.1         Hľadanie subgrafov (podgrafov) 26


    2.3.2         Farbenie grafov. 26


    2.3.3         Hľadanie cesty. 27


    2.3.4         Sieť toku. 28


    2.3.5         Rozhodovacie stromy. 29


    3       Aplikácia stromov a princípov z teórie hier v niektorých ťahových hrách. 30


    3.1        Herné stromy. 30


    3.2        Riešenie herných stromov. 31


    3.3        Ohodnocovanie pozícií v hernom strome. 32


    3.4        Algoritmus minimax. 33


    3.4.1         Všeobecný popis. 33


    3.4.2         Princíp algoritmu minimax. 33


    3.4.3         Alfa-Beta orezávanie. 35


    4       Programová implementácia teoretických princípov do hry dáma. 37


    4.1        Popis hry a jej reprezentácia v teórii hier 37


    4.2        Použitý jazyk a vývojové prostredie. 37


    4.3        Základná štruktúra programovej implementácie. 38


    4.3.1         Diagram tried programu v UML.. 39


    4.4        Reprezentácia šachovnice. 40


    4.5        Kontrola ťahov. 41


    4.6        Umelá inteligencia. 42


    4.7        Generátor ťahov. 43


    4.8        Ohodnocovanie pozícií 45


    4.8.1         Materiálne ohodnotenie. 45


    4.8.2         Pozičné ohodnotenie. 46


    4.9 ...


Zdroje:
Facebook icon Zdieľaj na Facebooku

Stiahni


Zadania-seminarky.sk
2006 - 2025 © všetky práva vyhradené
O súboroch cookie na tejto stránke

Súbory cookie používame na funkčné účely, na zhromažďovanie a analýzu informácií o výkone a používaní stránky.

Nastavenia Povoliť všetko