java实现旅⾏商问题_旅⾏商问题import java.io.IOException;
import java.nio.file.Files;
java valueof
import java.nio.file.Paths;
import java.util.List;
import java.util.Random;
public class Test {
public static void main(String[] args) throws IOException {
List data = (
"test.file"));
Node[] nodes = new Node[102];
for (int i = 0; i < 102; i++) {
nodes[i] = new Node();
}
nodes[0].x = nodes[0].y = nodes[101].x = nodes[101].y = 0;
for (int i = 0; i < 100; i++) {
String point = (i);
String[] xy = point.split(",");
nodes[i + 1].x = Integer.valueOf(xy[0]);
nodes[i + 1].y = Integer.valueOf(xy[1]);
}
//for (int i = 0; i < 101; i++) {
// int index = i + 1;
/
/ int dist = 10000;
// for (int j = i + 1; j < 101; j++) {
// int d = countDist(nodes[i], nodes[j]);
// if (d < dist) {
// dist = d;
// index = j;
// }
// }
// Node k = nodes[index];
// nodes[index] = nodes[i + 1];
// nodes[i + 1] = k;
/
/}
System.out.println(getAnserString(nodes));
System.out.println("最优解:" + countCost(nodes, 1, 102)); int bestAnser = countCost(nodes, 1, 102);
long startTime = System.currentTimeMillis();
Random random = new Random();
while (true) {
if (System.currentTimeMillis() - startTime > 3 * 1000) { break;
}
int p1 = Int(100);
int p2 = Int(100);
if (p1 == p2) {
continue;
}
Node k = nodes[p1 + 1];
Node h = nodes[p2 + 1];
nodes[p1 + 1] = h;
nodes[p2 + 1] = k;
int newAnser = countCost(nodes, 1, 102);
if (newAnser < bestAnser) {
System.out.println(getAnserString(nodes));
System.out.println("最优解:" + countCost(nodes, 1, 102)); bestAnser = newAnser;
} else {
nodes[p1 + 1] = k;
nodes[p2 + 1] = h;
}
}
System.out.println("--------------------------------------");
int minDist = countCost(nodes, 1, 102);
while (true) {
boolean flag = true;
for (int f = 10; f > 0; f--) {
System.out.println("--------------------继续----------------"+f);
for (int i = 1; i + maxDept <= 101; i += f) {
maxDist = 10000;
for (int j = 0; j < maxDept + 2; j++) {
indexNode[j] = position[j] = nodes[i + j - 1];
used[j] = false;
}
dfs(0, 0);
if(maxDist != 10000) {
for (int j = 0; j < maxDept; j++) {
nodes[j + i] = bestPosition[j];
}
}
if (minDist > countCost(nodes, 1, 102)) {
if (minDist > countCost(nodes, 1, 102)) {
System.out.println(getAnserString(nodes));
System.out.println("最优解:" + countCost(nodes, 1, 102)); minDist = countCost(nodes, 1, 102);
}
flag = false;
}
}
}
if (flag) {
break;
} else {
System.out.println("--------------------继续----------------");
}
}
}
final static int maxDept = 30;
public static Node[] bestPosition = new Node[maxDept + 2]; public static Node[] position = new Node[maxDept + 2]; public static Node[] indexNode = new Node[maxDept + 2];
public static boolean[] used = new boolean[maxDept + 2];
public static int maxDist = 100000;
public static void dfs(int depth, int countCost) {
if (depth == maxDept) {
int dist = countCost(position, 1, maxDept + 1);
if (dist < maxDist) {
maxDist = dist;
for (int i = 0; i < maxDept; i++) {
bestPosition[i] = position[i + 1];
}
}
return;
}
for (int i = 0; i < maxDept; i++) {
if (used[i]) {
continue;
}
int newCost = countCost + countDist(position[depth], indexNode[i + 1]);
if (newCost >= maxDist) {
continue;
}
used[i] = true;
position[depth + 1] = indexNode[i + 1];
dfs(depth + 1, newCost);
used[i] = false;
}
}
public static int countDist(Node a, Node b) {
return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}
public static int countCost(Node[] nodes, int begin, int end) {
int anser = 0;
for (int i = begin; i < end; i++) {
anser += Math.abs(nodes[i].x - nodes[i - 1].x) + Math.abs(nodes[i].y - nodes[i - 1].y);
}
return anser;
}
public static String getAnserString(Node[] nodes) {
StringBuilder sb = new StringBuilder("0,0\n");
for (int i = 1; i <= 100; i++) {
sb.append(nodes[i].x).append(",").append(nodes[i].y).append("\n"); }
sb.append("0,0");
String();
}
public static class Node {
public int x;
public int y;
}
}
0,8
1,9
14,8
24,6
35,2
36,7
37,8
38,6
47,4
60,4
67,0
67,10
66,13
82,14
82,17
83,18
90,19
94,13

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。