Diplomová práce

Minimální Hamiltonovské cykly v grafech s časovými omezeními

Shortest Hamiltonian Cycles in Graphs with Time Constraints

Bc. Peter Navrátil
Anotace

Diplomová práca je zameraná na popis algoritmov, ktoré hľadajú Hamiltonovské cykle v úplnych grafoch s časovými obmedzeniami. Časové obmedzenia udávajú, ktoré prechody sa dajú použiť pre prechod medzi jednotlivými vrcholmi grafu. Popisujeme deterministický algoritmus hrubej sily, ktorý dokáže spracovať inštancie s obmedzenou veľkosťou. Takto definovaný algoritmus dokáže spoľahlivo vyhľadať minimálny …více

Abstract

The thesis is focusing on the description of algorithms for searching Hamiltonian cycles in total graphs with time restrictions. Those time restrictions are defining which edges of the given graph we can use to traverse through the graph. We are describing deterministic brute force algorithm that can solve instances with limited size. This algorithm can always discover a minimal cycle in the given …více

Klíčová slova
Graf Hamiltonovský cyklus Algoritmus Hrubá sila Heuristika Mravčia kolónia NP-Úplný problém Optimalizačný problém Zložitosť Pseudokód
Zadání práce
Diplomová práca formuluje zobecnenie problému najkratšieho Hamiltonovského cyklu pre grafy s časovými obmedzaniami na hranách a vrcholoch. Pre daný problém navrhne vhodné riešenia založené na princípoch dynamického programovania a na princípoch mravenčej kolónie. Navrhnuté algoritmy budú implementované a experimentálne vyhodnotené na rozsiahlom súbore veľkých grafov.
Administrativní informace
Práce zkontrolována:
12. 12. 2019 09:26, prof. RNDr. Ivana Černá, CSc., učo 1419
Plný text práce
808,2 KB / soubor PDF
Přílohy (1)
Jazyk práce
slovenština slovenština
Termín obhajoby
3. 2. 2020
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Ivana Černá, CSc., učo 1419
KTP FI MU

Oponent

prof. RNDr. Jan Strejček, Ph.D., učo 3366
KTP FI MU

Literatura

  • CORMEN, Thomas H. Introduction to algorithms. 3rd ed. Cambridge, Mass.: MIT Press, 2009, xix, 1292. ISBN 9780262533058.
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Informatika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.