Qualitative Mapping Models In Tsp

TSP(Traveling Salesman Problem) is a classic combination optimizing problem, which has been proved as NP-hard problem that can't be solved in Turing maching. Some kinds of algorithms have been devised to solve it for more than two centries. Solving TSP is significant both in theory and practice. This paper proves that with Generate operator, Qualitative Mapping can be used to solve TSP, this is also supported by our experiments.Qualitative Mapping is a successful mathmatical model whch represent the relationship between the quantity and quality based on philosophy rule of inter-change between quantity and quality. It has been proved to be able to deduce neural network, and is used to solve xor-classfication problem bi- spire problem which are classic difficulty problems in artificial intelligence field. It has been put into practical use in the DSS of nuclear accident and college enrollment system.The nearer the quantity x (ai,pi) of quality character reaches the edge of (a;,p;), the more possible for it to suffer from qualitative change, i.e., if x1, x2 (a1,p1) belong to the same qulity base, the degree it changes into pi(o) varies because x1 x2. This difference caused by quantity exist commonly in the change of quality and quantity, but qualitative mapping i(x) can't express such difference. Change degree function is a tool to define such difference.Criterion transfor change the criterion of qualitative mapping in an certain rule, enabling the model dynamic. This paper gives a special kind of criterion transform-generate operator, hence an dynamic change function which is used to solve TSP. Out model needs no training or learning in advance, in fact, it searches while learing, furthermore, our model is stable. Therefor we provide a new approach the solve this classic problem and finding a new application field for qualitative mapping.Chapter 1 introduce the background of TSP, it's history, significance, modern algorithms to solve it, application and the latest approach..Chapter 2 compares different algorithms such as greedy algorithm and anneal algorithm, and points out some shortcomes of them.Chapter 3 introduce qualitative mapping model, it's principle and application.Chapter 4 introduce heuristic qualitative mapping model , analyse in detail how to apply heuristic qualitative mapping model into solving TSP. Discuss the algorithm and give out the prove of its constringency quality.Finally, Chapter 5 introduce Traveller software, sum up the paper and give some suggestion for the next step of work.