Řešení hry Battleship Solitaire pomocí celočíselného programování
| Název práce: | Řešení hry Battleship Solitaire pomocí celočíselného programování |
|---|---|
| Autor(ka) práce: | Přibylová, Lenka |
| Typ práce: | Bakalářská práce |
| Vedoucí práce: | Jablonský, Josef |
| Oponenti práce: | Fábry, Jan |
| Jazyk práce: | Česky |
| Abstrakt: | 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. |
| Klíčová slova: | rekreační matematika; battleship; LINGO; celočíselné programování |
| Název práce: | Solving the Battleship Solitaire puzzle as an integer programming problem |
|---|---|
| Autor(ka) práce: | Přibylová, Lenka |
| Typ práce: | Bachelor thesis |
| Vedoucí práce: | Jablonský, Josef |
| Oponenti práce: | Fábry, Jan |
| Jazyk práce: | Česky |
| Abstrakt: | 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; LINGO; recreational mathematics; integer programming |
Informace o studiu
| Studijní program / obor: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
|---|---|
| Typ studijního programu: | Bakalářský studijní program |
| Přidělovaná hodnost: | Bc. |
| Instituce přidělující hodnost: | Vysoká škola ekonomická v Praze |
| Fakulta: | Fakulta informatiky a statistiky |
| Katedra: | Katedra ekonometrie |
Informace o odevzdání a obhajobě
| Datum zadání práce: | 25. 2. 2011 |
|---|---|
| Datum podání práce: | 10. 5. 2011 |
| Datum obhajoby: | 1. 6. 2011 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/30787/podrobnosti |