Název:
Řešení hry Battleship Solitaire pomocí celočíselného programování
Překlad názvu:
Solving the Battleship Solitaire puzzle as an integer programming problem
Autoři:
Přibylová, Lenka ; Jablonský, Josef (vedoucí práce) ; Fábry, Jan (oponent) Typ dokumentu: Bakalářské práce
Rok:
2011
Jazyk:
cze
Nakladatel: Vysoká škola ekonomická v Praze
Abstrakt: [cze][eng] Bakalářská práce se zabývá logickou hrou Battleship Solitaire. Seznamuje čtenáře s historií této hry a s jejími pravidly, ze kterých následně vychází formulace hry jako úlohy celočíselného programování. Vytvořeny jsou dva matematické modely, založené na odlišných přístupech; "cell-based" model je založený na zkoumání jednotlivých polí, zatímco "ship-based" model je založený na kombinaci mřížek obsahujících právě jednu loď. Pro ověření, zda je řešení hry jedinečné, jsou do modelů přidány účelové funkce. Oba modely jsou převedeny do modelovacího systému LINGO, a řešeny pro různé rozměry herní mřížky. Z výsledků testování vyplývá, že "ship-based" model sice pracuje s menším počtem proměnných i omezení, ale je velmi náročný na práci s daty, což řešení velmi zpomaluje, a pro větší rozměry naprosto znemožňuje. Mnohem rychleji byly úlohy vyřešeny pomocí "cell-based" modelu. Řešení bylo nalezeno i pro úlohy s většími rozměry, i když se doba řešení výrazně prodloužila.The bachelor thesis deals with the Battleship Solitaire puzzle. It introduces the history and the rules of this puzzle, which are thereafter used to formulate the puzzle as an integer programming problem. Two mathematical models based on different approaches are created, a cell-based model and a ship-based model. In order to determine whether a puzzle has a unique solution an objective function is added to each model. Both models are developed in LINGO modeling language and tested with different grid sizes. The test results show that even though the ship-based model uses fewer variables and constraints, it is too demanding in terms of data processing. It results in longer solving times and the model fails to find a solution for larger grids. Solving the problem using the cell-based model is significantly faster. The solution was found even for larger grids, though the solving time was very long.
Klíčová slova:
battleship; celočíselné programování; LINGO; rekreační matematika; battleship; integer programming; LINGO; recreational mathematics
Instituce: Vysoká škola ekonomická v Praze
(web)
Informace o dostupnosti dokumentu:
Dostupné v digitálním repozitáři VŠE. Původní záznam: http://www.vse.cz/vskp/eid/25116