基于探针机的旅行商问题研究

The traveling salesman problem (TSP) is the basis for solving many practical problems in life. Since TSP belongs to NP-complete problems, it is difficult to obtain the global optimal solution for the TSP based on the existing algorithms when the size of TSP is large enough. The reason for this problem is that the existing algorithms are designed based on Truing machine, and the architecture of Turing machine is not suitable for solving NP-complete problems. As a result, this project intends to solve the TSP based on Probe machine. The Probe machine can solve NP-complete problems efficiently due to the characteristics of parallel data storage and parallel data problems. This project first models the TSP based on Probe machine, then designs a scheme for implementing Probe machine based on file programmable logic gate array. Finally, a hardware experimental platform of Probe machine for solving the TSP is established. The platform can be used to verify the effectiveness of Probe machine and compare the performance with Turing machine for solving the TSP.

旅行商问题是解决生活中众多实际问题的基础。由于旅行商问题属于NP-完全问题，因此当问题规模较大时，基于现有算法难以得到旅行商问题的全局最优解。造成这种问题的原因是现有算法是基于图灵机设计的，而图灵机的架构并不适合求解NP-完全问题。因此，本项目拟基于探针机求解旅行商问题。探针机由于并行存储数据以及并行处理数据的特性，可以高效求解NP-完全问题。本项目首先建立基于探针机的旅行商问题的模型，然后设计基于现场可编程逻辑门阵列实现探针机的方案，最后搭建能够求解旅行商问题的探针机硬件实验平台，验证探针机的有效性，并与图灵机求解旅行商问题进行性能对比。

本项目针对在实际生活中有众多应用的TSP难以求解的问题，通过将TPS问题规约为图着色问题，研究基于探针机求解图着色问题的模型与算法，并搭建了基于FPGA的仿真实验验证平台。减少了求解图着色问题所需的时间，并且通过增加LE可以使得求解图着色问题的所需时间不会随顶点个数显著增加，验证了所设计方案的有效性。