TSP问题的概述.docVIP

TSP问题的概述 　　旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 　　TSP问题的由来 　　TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。 　　TSP由美国RAND公司于1948年引入，该公司的声誉以及线形规划这一新方法的出现使得TSP成为一个知名且流行的问题。 　　TSP在中国的研究 　　同样的问题，在中国还有另一个描述方法：一个邮递员从邮局出发，到所辖街道投邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么他应该如何选择投递路线，使所走的路程最短？这个描述之所以称为中国邮递员问题（Chinese Postman Problem CPP）因为是我国学者管梅古教授于1962年提出的这个问题并且给出了一个解法。人工智能上的旅行商问题，以下给出的是算法，只是理解算法之用。 　　for detail contact me QQ: 座机电话号码2 　　/****************算法总框架*****************************/ 　　int i; gs.search_init adaptee.list_place.getSelectedIndex ,adaptee.list_fun.getSelectedIndex ; 　　do i gs.search_step ; while i 0 ; 　　/***************searchinit**************************/ 　　public void search_init int startindex,int strategy this.strategy strategy; 　　AStar.graph G; 　　G.setSize AStar.len ; start.index startindex; 　　Vertex s new Vertex ; s.index start.index; 　　s.parent -1; 　　n null; 　　s.value f s.index ; //s的估价函数值 　　G.add s ; 　　start.parentpos -1; 　　start.value s.value; 　　open.add start ; 　　step 0; /***************searchstep**************************/ 　　public int search_step Open m ; 　　Vertex old_m; 　　int i,j; int f; int parentpos; 　　if open.next null return -1;//查找失败 　　//扩展的步骤数增加 　　step++; 　　//Open 表非空 //Open 表中移出第一个 　　n open.removeFirst ; 　　//n放入 CLOSE 中 ,返回放入的位置 　　parentpos close.Add n.index, n.parentpos ; 　　if n.index start.indexstep! 1 //结束状态 　　return 1; 　　//扩展n结点 　　i n.index; 　　for j 0;j len;j++ if i! jvalue[j]! -1 //对于所有n的后继结点 m j if j start.indexisAll n //所有城市已访问过，且回到出发城市 f f j ; //计算此时的f值 　　old_m G.getVertex j ; 　　if old_m! null if old_m.value f||old_m.value 0 G.add j,i,f ; //j m i n ,G中添加j m ,父节点为i n ,估价函数值为f 　　G.addSub i,j ; //i n 的后继中添加j m m new Open j,parentpos,f ; //Open表中添加m j open.add m ; 　　continue; if !isExist n,j //m j 不在n i 的祖先中 不扩张n的祖先结点 f f j ; //计算f值 　　//取得旧的m j 中value最小的,G中的节电保存了从出发城市到此地最