贪心算法【TSP问题】
贪心简介:
只看下一次选择,比如:我需要做完一张数学试卷,我哪到试卷后做题,就先选择我最熟悉的,做完后选择我会的,最后尝试难题!每一个阶段都选择当前最优的解;
注意:我们选择的只是当前阶段的最优解,所有整体上不一定是最优解;
TSP+贪心
题目简介:
TSP问题(旅行家问题):旅行家旅行n个城市,要求每个城市仅经过一次,最后返回出发城市
选择算法:贪心算法
选择原因:每次选取到达城市代价最小的城市,当城市数量教下时,算法将近似最优解。
方便实现、复杂度较低
解决问题:
第一步:(建图)
TSP问题需要用到图,因此第一步为建图
建图(建立代价矩阵)
例:
∞ 3 3 2 6
3 ∞ 7 3 2
3 7 ∞ 2 5
2 3 2 ∞ 3
6 2 5 3 ∞
第二步:
确定起点和终点,并且将终点标记,下次选择不再选择
例:
标记 : 1
1 -> 4 代价:2 标记 :4
4 -> 3 代价:2 3
3 -> 5 代价:5 5
5 -> 2 代价:2 2
回到起点 :
(因为第一步就将1标记,无法返回需要单独添加)
2 -> 1 代价:3 2
总代价 : 2+2+5+2+3
贪心所得结果仅是每一次选择的最优选择,从整体看并不一定是最优解!
核心代码分析:(三问)
1、我需要什么?
代价矩阵:从当前起点中寻找下一次目的地的最小代价
起点:旅行起始位置
城市数量:判断所有城市是否走完,添加回家代价
2、我要做什么?
从每一次起点中找寻下一次代价最小的路线
输出每一次选择的路线结果
记录代价的总和
3、我需要返回什么?
返回代价和:判断该代价是否在接受范围内!
代码分享:
import java.util.Scanner;
public class 贪心TSP {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] arr = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arr[i][j] = sc.nextInt();
}
}
System.out.println(tsp(arr, n, 0));
}
//核心代码 :
static int tsp(int[][] arr , int n , int start){
boolean[] f = new boolean[n];
int ans = 0 , u = start , end = 0;
f[start] = true;
while (--n>0){
int min = Integer.MAX_VALUE;
for(int i = 0 ; i < arr[0].length;i++){
if(f[i] == false && arr[u][i] != 0 && arr[u][i] < min){
end = i ;
min = arr[u][i];
}
}
ans += min;
f[end] = true;
System.out.println(u + "-->" + end);
u = end;
}
System.out.println(u + "-->" + start);
return ans+arr[u][start];
}
//
}
测试结果: