The diploma thesis Sorting tuples based on their distances deals with the problem of sorting. We want to find a sequence of n k-tuples that gives us the minimization or maximization of the criterion function. If we describe the problem in a more detailed way, the result of the sorting is a sequence that minimizes or maximizes the sum or the maximum of the distances between the tuples which are next to each other in a sequence. We defined the problem and determined the complexity of finding the solutions. By transforming the already known NP-hard problem into the problem of sorting tuples, we have proved that sorting tuples is also NP-hard. The thesis presents the exact and approximate algorithms. Exact algorithms were implemented in Java and used in an experiment. We experimentally compared their efficiency and presented it in a graph. Finally, we can check the representation of the key findings.
|
