Formal Derivation of Traveling Salesman Problem

摘要

Traveling salesman problem is a classical combinatorial optimization and NP-complete problem. Formal methods is an important way to improve the software credibility and PAR methods is one of the representatives. Based on brief description of Partition and Recur (PAR) method and traveling salesman problem, an abstract Apla program was obtained by using the PAR method's specification, partition, transformation, recursion and other operations to derive traveling salesman problem's solution. Finally, an experiment was carried out and the experimental results show that the method is correct. When using PAR method to derive the algorithm of traveling salesman problem, the algorithm's correctness proof was simplified. And automation of algorithm design and standardization degree was improved also.