| Abstract: |  This thesis aims to investigate an effect of a graph representing the polygonal domain to the solution quality of the traveling salesman problem (TSP) that is solved by an algorithm of self-organizing map for a graph. Three types of graphs, which are created by different approaches, were selected: (1) Triangular-mesh graph; (2) Visibility graph, (3) and Growing neural gas graph (GNG).
The last mentioned graph is studied in a more detail as one of the main goal of this bachelor thesis is to find parameters of the GNG algorithm in order to create a graph suitable for the self-organizing map based algorithm for the TSP. Although the GNG approach is well known, its application for describing the polygonal domain is not straightforward because of obstacles. A feasible solution of the TSP in the polygonal domain has to be entirely inside the free space, and therefore, several approaches to consider obstacles in the GNG algorithm have been proposed and experimentally examined in a set of selected problems. A comparison of influence of various graphs to the solution quality of the TSP is presented in the thesis. Besides, benefits of the graph representation to the solution quality and computational requirements are discussed in the conclusion. |
|---|