贪心算法-旅行商问题

发表于 分类于 阅读次数：

问题

有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只在一个城市逗留一次，最后回到出发的城市，问如何事先确定一条最短的线路已保证其旅行的费用最少？

还有 背包、装箱 问题

注： 递归，时间复杂度为n!

贪心算法

在对问题求解时，总是做出当前情况下的最好选择，否则将来可能会后悔，故名“贪心”。这是一种算法策略，每次选择得到的都是局部最优解。选择的策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

求解的问题分成若干个子问题，每一个子问题求解，得到子问题的局部最优解，子问题的局部最优解合成原问题的一个解

步骤

  1. 从某一个城市开始，每次选择一个城市，直到所有的城市被走完。

  2. 每次在选择下一个城市的时候，只考虑当前情况，保证迄今为止经过的路径总距离最小。

     从问题的某一初始解出发；
     while （能朝给定总目标前进一步）
     { 
           利用可行的决策，求出可行解的一个解元素；
     }
 由所有解元素组合成问题的一个可行解

缺点

  • 不能保证最终为最优解
  • 不能用来求最大最小解问题
  • 无后效性

代码实现

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();
}


}