Název:
Procházky v grafech a genetické algoritmy
Překlad názvu:
Procházky v grafech a genetické algoritmy
Autoři:
Szépe, Peter ; Bajer, Lukáš (oponent) ; Pangrác, Ondřej (vedoucí práce) Typ dokumentu: Bakalářské práce
Rok:
2010
Jazyk:
eng
Abstrakt: [eng][cze] Title: Walks in graphs and genetic algorithms Author: Peter Szépe Department: Department of Applied Mathematics Supervisor: RNDr. Ondřej Pangrác, Ph.D. Supervisor's e-mail address: pangrac@kam.mff.cuni.cz Abstract: We solve the problem of finding a maximal walk from the starting vertex to the target vertex with an upper bound of the length of the walk. It is an NP-hard problem where not even the approximation algorithms do guarantee a quick and nice solution. Hence it is important to develop heuristics for practical applications. Keywords: optimization, evolutionary algorithms, genetic algorithms, graphs, walks in graphsNázev práce: Procházky v grafech a genetické algoritmy Autor:Peter Sépe Katedra (ústav): Katedra aplikované matematiky Vedoucí bakalárské práce: RNDr. Ondřej Pangrác, Ph.D. e-mail vedoucího: pangrac@kam.mff.cuni.cz Abstrakt: Řešíme optimalizační úlohy nalezení maximálního tahu mezi dvěma vrcholy v orintovaném grafu s omezením na délku tohoto tahu. Je dán orientovaný graf, startovní a cílový vrchol, délková funkce na hranách a váhová funkce na vrcholech grafu a parametr omezení délky cesty L. Úkolem je najít tah ze startovního do cílového vrcholu celkové délky nejvýše L maximalizující součet vah navštívených vrcholů (každý se započítává pouze jednou).Tato úloha je NP-těžká a ani aproximační algoritmy nedávají příliš dobré výsledky. Proto je třeba pro praktické aplikace použít heuristické přístupy. Klícová slova: optimalizace, evolučné algoritmy, genetické algoritmy, grafy, procházky v grafech