Travelling salesman algorithm in Java Fork/Join Framework
|
1 2 3 4 5 6 7 8 9 10 11 12 |
distance = new long[points.size()][points.size()]; for (int i = -1; ++i < points.size();) { int x1 = points.get(i).getX(); int y1 = points.get(i).getY(); distance[i][i] = 0; for (int j = -1; ++j < i;) { int x2 = points.get(j).getX(); int y2 = points.get(j).getY(); distance[i][j] = Math.max(Math.abs(x1 - x2) * costX, Math.abs(y1 - y2) * costY); distance[j][i] = distance[i][j]; } } |
E.g .: maximum axis velocity of the robot.
An edge is calculated by the TSPAction class. The recursive function returns no results , so TSPAction inherits the RecursiveAction class. You just have to implement the function TSPAction.compute ( ) , which is responsible for the whole logic and heuristics.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
protected void compute() { int nextIndex; TSPAction nextLevel = null; if (bestPathLength < length || abort) { // is current length > best length => go back return; } ArrayList<Integer> newPath = (ArrayList) currentPath.clone(); newPath.add(curPos); ArrayList<Integer> newFreePoints = (ArrayList) freePoints.clone(); removePoint(newFreePoints, curPos); if (newFreePoints.isEmpty()) { // no more unchecked points (max recursion level reached) savePath(newPath, length); } else { ArrayList<Integer> localFreePoints = (ArrayList) newFreePoints.clone(); // at first compute the shortest path nextIndex = getNextNearestPoint(curPos, localFreePoints); if (nextIndex >= 0) { new TSPAction(newPath, newFreePoints, nextIndex, length + distance[curPos][nextIndex], nextLevel).compute(); } // then add all other points to ForkJoin pool while (localFreePoints.size() > 0 && !abort) { nextIndex = getNextNearestPoint(curPos, localFreePoints); if (nextIndex >= 0) { nextLevel = new TSPAction(newPath, newFreePoints, nextIndex, length + distance[curPos][nextIndex], nextLevel); nextLevel.fork(); } } // now try to unfork a task and help with computation or wait for task end while (nextLevel != null) { if (nextLevel.tryUnfork()) { nextLevel.compute(); } else { nextLevel.join(); } nextLevel = nextLevel.getNext(); } } } |
Heuristics:
- the getNextNearestPoint function selects the minimal weighted, adjacent edge to the next available node (local free points list ) .
- in lines 19-23 the path with the minimal weight is searched first . All longer pathes are thrown away ( lines 4-7 )
This is how it looks like in real life:
I have been exploring for a little bit for any high-quality articles or weblog posts on this kind of area . Exploring in Yahoo I finally stumbled upon this website. Studying this info So i am happy to express that I have a very good uncanny feeling I found out just what I needed. I most indubitably will make sure to do not put out of your mind this web site and provides it a glance on a constant basis.