Skip to content

Instantly share code, notes, and snippets.

@kishida
Created Feb 5, 2016
Embed
What would you like to do?
TSP with random
import java.awt.Graphics;
import java.awt.GridLayout;
import java.awt.image.BufferedImage;
import java.util.ArrayList;
import java.util.DoubleSummaryStatistics;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import javax.swing.ImageIcon;
import javax.swing.JFrame;
import javax.swing.JLabel;
/**
*
* @author naoki
*/
public class TSP {
public static void main(String[] args) {
JFrame f = new JFrame();
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.setSize(500, 400);
f.setLayout(new GridLayout(2, 1));
Random r = new Random(1235);
int[] xs = r.ints(30, 0, 300).toArray();
int[] ys = r.ints(30, 0, 300).toArray();
//double solved = solve(xs, ys, 1, new int[xs.length]);
//System.out.println(solved);
BufferedImage route = new BufferedImage(320, 320, BufferedImage.TYPE_INT_RGB);
Graphics g = route.getGraphics();
for(int i = 0; i < xs.length; ++i) {
g.drawRect(xs[i] + 9, ys[i] + 9, 3, 3);
}
f.add(new JLabel(new ImageIcon(route)));
int[] minRoute = null;
double min = Double.MAX_VALUE;
List<Double> hist = new ArrayList<>();
for(int ii = 0; ii < 800000; ++ii){
int[] gene = IntStream.range(0, xs.length).map(i -> r.nextInt(xs.length - i)).toArray();
List<Integer> list = IntStream.range(0, xs.length).boxed().collect(Collectors.toList());
int[] rt = IntStream.of(gene).map(list::remove).toArray();
double d = 0;
for(int i = 0; i < rt.length; ++i){
int j = (i + 1) % rt.length;
d += Math.sqrt((xs[rt[i]] - xs[rt[j]]) * (xs[rt[i]] - xs[rt[j]]) +
(ys[rt[i]] - ys[rt[j]]) * (ys[rt[i]] - ys[rt[j]]));
}
if(d < min) {
min = d;
minRoute = rt;
}
hist.add(min);
}
System.out.println(min);
for(int i = 0; i < minRoute.length; ++i){
int j = (i + 1) % minRoute.length;
g.drawLine(xs[minRoute[i]] + 10, ys[minRoute[i]] + 10, xs[minRoute[j]] + 10, ys[minRoute[j]] + 10);
}
DoubleSummaryStatistics st = hist.stream().mapToDouble(d -> d).summaryStatistics();
BufferedImage img = new BufferedImage(500, 300, BufferedImage.TYPE_INT_RGB);
Graphics gg = img.getGraphics();
double solved = st.getMin();
double range = st.getMax() - solved;
gg.drawLine(20, 275, 470, 275);
for(int i = 1; i < hist.size(); ++i){
int y1 = (int)((hist.get(i - 1) - solved) / range * 250);
int y2 = (int)((hist.get(i) - solved) / range * 250);
gg.drawLine(i * 450 / hist.size() + 20, 275 - y1, (i + 1) * 450 / hist.size() + 20, 275 - y2);
}
f.add(new JLabel(new ImageIcon(img)));
f.setVisible(true);
}
/*
static double solve(int[] xs, int[] ys, int idx, int[] root){
if(idx >= root.length) {
List<Integer> list = IntStream.range(0, root.length).boxed().collect(Collectors.toList());
int[] rt = IntStream.of(root).map(list::remove).toArray();
double d = 0;
for(int i = 0; i < rt.length; ++i){
int j = (i + 1) % rt.length;
d += Math.sqrt((xs[rt[i]] - xs[rt[j]]) * (xs[rt[i]] - xs[rt[j]]) +
(ys[rt[i]] - ys[rt[j]]) * (ys[rt[i]] - ys[rt[j]]));
}
return d;
}
double min = Double.MAX_VALUE;
for(int i = 0; i < root.length - idx; ++i){
root[idx] = i;
double d = solve(xs, ys, idx + 1, root);
if (d < min){
min = d;
}
}
return min;
}*/
}
@kishida
Copy link
Author

kishida commented Feb 5, 2016

tsp_en

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment