算法设计与分析论文

package Search;

publicclass EnumerationSearch { }

publicint search(double[] a,double goal) { }

publicint search(int[] a,int goal) { }

int add=-1;

for (int i=0;i

return add;

if (a[i]==goal) { }

add=i; break;

int add=-1;

for (int i=0;i

return add;

if (a[i]==goal) { }

add=i; break;

package TSP.console;

import java.util.Arrays; import TSP.find.*;

publicclass console {

/**

* @param args */

publicstaticvoid main(String[] args) {

// TODO Auto-generated method stub

int[][] distance = { //各个节点之间路径长度的二维数组 {0, 2, 1, 3, 4, 5, 5, 6}, {1, 0, 4, 4, 2, 5, 5, 6}, {5, 4, 0, 2, 2, 6, 5, 6}, {5, 2, 2, 0, 3, 2, 5, 6}, {4, 2, 4, 2, 0, 3, 5, 6}, {4, 2, 4, 2, 3, 0, 5, 6}, {4, 2, 4, 2, 4, 3, 0, 6}, {4, 2, 4, 2, 8, 3, 5, 0}}; }

int[] ans = newint[distance.length]; Arrays.fill(ans, 0);

TSPadjline fin = new TSPadjline();

long preTime = System.currentTimeMillis(); fin.find(distance, ans);

long aftTime = System.currentTimeMillis(); long currentTime = aftTime - preTime;

System.out.println(\：\ + currentTime+\); System.out.println(Arrays.toString(ans)); int s=0; //路程

for(int i=0;i

s=s+distance[ans[i]-1][ans[i+1]-1]; s=s+distance[ans[ans.length-1]-1][ans[0]-1];

System.out.println(\路程：\+s); }

package TSP.find;

import Search.EnumerationSearch;

publicclass TSPadjline { }

//adjacent line

publicvoid find(int[][] distance,int[] ans) { }

privateint min(int[] a,int[] b) { }

int minN=0; int temp=100;

EnumerationSearch sea = new EnumerationSearch(); for(int i=0;i

if(sea.search(b, (i+1))==-1)

if(a[i]

temp=a[i]; minN=i;

int j=1; //starting city

for(int i=0;i

ans[i]=j;

j=min(distance[j-1],ans);

程序运行截图：

背包问题截图

动态规划法求解TSP问题

贪心算法求解TSP问题