A Grid-Based TSP Solver
| Autor: | Chia-Shiang Chang, 張家祥 |
|---|---|
| Rok vydání: | 2004 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 92 The traveling salesperson problem (TSP for short) is an optimization problem, which addresses the problem of a salesperson visiting n cities. In the visiting tour, the salesperson wishes to visit each city exactly once and ‾nish at the city he starts from such that the total traveling cost is the minimum. Given a complete graph G = (V;E) with n vertices and a traveling cost function between each pair of vertices, find a shortest tour, which may start from any vertex, for visiting each vertex exactly once and returning the starting vertex. TSP has many applications in computational biology, such as multiple sequence alignment. In this thesis, we propose an algorithm for TSP solver kernel and design the TSP solver program that can accept one asymmetric n x n matrix that does not have to satisfy the triangle inequality as its input. Finally, we implement the TSP solver on computational Grid to solve the significant computational biology problems, like multiple sequence alignment. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|