课程设计报告(6)

public List newLoop(String cityName) { List list = usOP.showCity(cityName); float sum0=99999990,sum1=0;

int T = list.size(), k = 0, m = 0; // 循环n次来查找最佳路径

for (int i = 0; i

if (k < m) {

list = this.backMiddleS(list, k, m); } else {

list = this.backBottom(list, k, m); }

if(!this.testHaveWay(list, cityName)){ continue; }

// 获得该序列的路径长度

sum1 = this.getWayLength(list, cityName); if (sum1 < sum0) {

sum0 = sum1; OKList.clear();

OKList.addAll(list); } }

wayLength=sum0; return OKList; }

// 获得路径序列的总路程

public float getWayLength(List list, String cityName) { // 获得原始序列

List primitiveList = usOP.showCity(cityName); // 获得该城市的路程数组

int cityWay[][] = usOP.getCityWay(cityName); String str = null, startStr = null; int x = 0, y = 0; float sum = 0;

Iterator li = list.iterator(); if (li.hasNext()) { str = li.next(); startStr = str;

}

for (int i = 0; i < list.size(); i++) { x = primitiveList.indexOf(str); if (i == (list.size() - 1)) {

y = primitiveList.indexOf(startStr); } else {

if (li.hasNext()) { str = li.next();

y = primitiveList.indexOf(str); } }

sum += cityWay[x][y]; }

return sum; }

// 判断新路径序列中是否存在两个城市之间无路的情况

public boolean testHaveWay(List newList,String cityName){ List S = usOP.showCity(cityName); Iterator isWay = newList.iterator(); String str1=null,str2=null,startStr1=null;

int cityZB[][]=usOP.getCityWay(cityName),len=S.size(); if(isWay.hasNext()){ str1=isWay.next(); startStr1=str1; }

for (int j = 0; j

str2=startStr1; }

else if(isWay.hasNext()){ str2=isWay.next(); }

int x=S.indexOf(str1); int y = S.indexOf(str2); if(cityZB[x][y]==0){ haveWay=0; break; }

haveWay=1; str1=str2; }

if(haveWay==0){ return false; }

}

return true; }

// 逆转两端

public List backBottom(List S, int k, int m) { int T = S.size(); // 逆转最左端

S = this.backMiddleS(S, 0, m); // 逆转最右端

S = this.backMiddleS(S, k, T - 1); return S; }

// 逆转某一范围

public List backMiddleS(List S, int k, int m) { String cityName = null;

for (int i = k; i <= ((m + k) / 2); i++) { cityName = S.get(i); S.set(i, S.get(m)); S.set(m, cityName); m--; }

return S; }

// 获得0--T之间的随机数,包括0，不包括T public int getRandom(int T) {

return (int) (Math.random() * T); }

// 判断两个随机数是否相等

public boolean testSame(int k, int m) { if (k == m) { return false; }

return true; }

//获得n的阶乘

public int getN(int n){ int m=1;

for(int i=1;i<=n;i++){ m*=i; }

return m*4; }