基于贪心算法求解TSP问题(JAVA)
前段时间在搞贪心算法,为了举例,故拿TSP来开刀,写了段求解算法代码以便有需之人,注意代码考虑可读性从最容易理解角度写,没有优化,有需要可以自行优化!
一、TSP问题
TSP问题(Travelling Salesman Problem)即旅行商问题,又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。TSP问题可以分为两类,一类是对称TSP问题(Symmetric TSP),另一类是非对称问题(Asymmetric TSP)。所有的TSP问题都可以用一个图(Graph)来描述:
V={c1, c2, …, ci, …, cn},i = 1,2, …, n,是所有城市的集合.ci表示第i个城市,n为城市的数目;
E={(r, s): r,s∈ V}是所有城市之间连接的集合;
C = {crs: r,s∈ V}是所有城市之间连接的成本度量(一般为城市之间的距离);
如果crs = csr, 那么该TSP问题为对称的,否则为非对称的。
一个TSP问题可以表达为:
求解遍历图G = (V, E, C),所有的节点一次并且回到起始节点,使得连接这些节点的路径成本最低。
二、贪心算法
贪心算法,又名贪婪算法(学校里老教授都喜欢叫贪婪算法),是一种常用的求解最优化问题的简单、迅速的算法。贪心算法总是做出在当前看来最好的选择,它所做的每一个在当前状态下某种意义上是最好的选择即贪心选择,并希望通过每次所作的贪心选择导致最终得到问题最优解。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。
1、贪心算法的基本思路
1)建立数学模型来描述问题;
2)把求解的问题分成若干个子问题
3)对每一个子问题求解,得到子问题的局部最优解
4)把子问题的局部最优解合成原问题的一个解
2、贪心算法的实现框架
贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择,而贪心策略适用的前提是:局部最优策略能导致产生全局最优解。
从问题的某一初始解出发;
while (能朝给定总目标前进一步)
{
利用可行的决策,求出可行解的一个解元素;
}
由所有解元素组合成问题的一个可行解;
3、贪心算法存在的问题
1)不能保证求得的最后解是最佳的;
2)不能用来求最大最小解问题;
3)只能在某些特定条件约束的情况下使用,例如贪心策略必须具备无后效性等。
4、典型的贪心算法使用领域
马踏棋盘、背包、装箱等
三、贪心算法求解TSP问题
贪心策略:在当前节点下遍历所有能到达的下一节点,选择距离最近的节点作为下一节点。基本思路是,从一节点出发遍历所有能到达的下一节点,选择距离最近的节点作为下一节点,然后把当前节点标记已走过,下一节点作为当前节点,重复贪心策略,以此类推直至所有节点都标记为已走节点结束。我们使用TSP问题依然来自于tsplib上的att48,这是一个对称TSP问题,城市规模为48,其最优值为10628.其距离计算方法下图所示:
好,下面是具体代码:
package noah; import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; public class TxTsp { private int cityNum; // 城市数量 private int[][] distance; // 距离矩阵 private int[] colable;//代表列,也表示是否走过,走过置0 private int[] row;//代表行,选过置0 public TxTsp(int n) { cityNum = n; } private void init(String filename) throws IOException { // 读取数据 int[] x; int[] y; String strbuff; BufferedReader data = new BufferedReader(new InputStreamReader( new FileInputStream(filename))); distance = new int[cityNum][cityNum]; x = new int[cityNum]; y = new int[cityNum]; for (int i = 0; i < cityNum; i++) { // 读取一行数据,数据格式1 6734 1453 strbuff = data.readLine(); // 字符分割 String[] strcol = strbuff.split(" "); x[i] = Integer.valueOf(strcol[1]);// x坐标 y[i] = Integer.valueOf(strcol[2]);// y坐标 } data.close(); // 计算距离矩阵 // ,针对具体问题,距离计算方法也不一样,此处用的是att48作为案例,它有48个城市,距离计算方法为伪欧氏距离,最优值为10628 for (int i = 0; i < cityNum - 1; i++) { distance[i][i] = 0; // 对角线为0 for (int j = i + 1; j < cityNum; j++) { double rij = Math .sqrt(((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) / 10.0); // 四舍五入,取整 int tij = (int) Math.round(rij); if (tij < rij) { distance[i][j] = tij + 1; distance[j][i] = distance[i][j]; } else { distance[i][j] = tij; distance[j][i] = distance[i][j]; } } } distance[cityNum - 1][cityNum - 1] = 0; colable = new int[cityNum]; colable[0] = 0; for (int i = 1; i < cityNum; i++) { colable[i] = 1; } row = new int[cityNum]; for (int i = 0; i < cityNum; i++) { row[i] = 1; } } public void solve(){ int[] temp = new int[cityNum]; String path="0"; int s=0;//计算距离 int i=0;//当前节点 int j=0;//下一个节点 //默认从0开始 while(row[i]==1){ //复制一行 for (int k = 0; k < cityNum; k++) { temp[k] = distance[i][k]; //System.out.print(temp[k]+" "); } //System.out.println(); //选择下一个节点,要求不是已经走过,并且与i不同 j = selectmin(temp); //找出下一节点 row[i] = 0;//行置0,表示已经选过 colable[j] = 0;//列0,表示已经走过 path+="-->" + j; //System.out.println(i + "-->" + j); //System.out.println(distance[i][j]); s = s + distance[i][j]; i = j;//当前节点指向下一节点 } System.out.println("路径:" + path); System.out.println("总距离为:" + s); } public int selectmin(int[] p){ int j = 0, m = p[0], k = 0; //寻找第一个可用节点,注意最后一次寻找,没有可用节点 while (colable[j] == 0) { j++; //System.out.print(j+" "); if(j>=cityNum){ //没有可用节点,说明已结束,最后一次为 *-->0 m = p[0]; break; //或者直接return 0; } else{ m = p[j]; } } //从可用节点J开始往后扫描,找出距离最小节点 for (; j < cityNum; j++) { if (colable[j] == 1) { if (m >= p[j]) { m = p[j]; k = j; } } } return k; } public void printinit() { System.out.println("print begin...."); for (int i = 0; i < cityNum; i++) { for (int j = 0; j < cityNum; j++) { System.out.print(distance[i][j] + " "); } System.out.println(); } System.out.println("print end...."); } public static void main(String[] args) throws IOException { System.out.println("Start...."); TxTsp ts = new TxTsp(48); ts.init("c://data.txt"); //ts.printinit(); ts.solve(); } }
求解结果截图:
四、总结
单从求解结果来看,我个人其实还是能接受这个解,但仔细想想,实际上这个求解结果有太多运气成分在里面,贪心算法毕竟是贪心算法,只能缓一时,而不是长久之计,问题的模型、参数对贪心算法求解结果具有决定性作用,这在某种程度上是不能接受的,于是聪明的人类就发明了各种智能算法(也叫启发式算法),但在我看来所谓的智能算法本质上就是贪心算法和随机化算法结合,例如传统遗传算法用的选择策略就是典型的贪心选择,正是这些贪心算法和随机算法的结合,我们才看到今天各种各样的智能算法。转载请注明:http://blog.csdn.net/wangqiuyun/article/details/38680151
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。