001
002 package algo;
003
004 import thread.Deque;
005
006 import java.util.ArrayList;
007
008 /**
009 * A parallel algorithm for an euclidean 2d TSP Problem.
010 * @author Heinz Kredel.
011 */
012 public class ParByteLocalTSP implements TSPInf {
013
014 protected Graph graph;
015 protected Point[] points;
016 // protected Path bestPath; // beware of threads
017 protected BestByteLocStore best;
018 protected RunByteLocTSP[] threads;
019
020 protected int number = 0;
021
022 /**
023 * @param p the cities.
024 * @param th number of threads.
025 */
026 public ParByteLocalTSP(Point[] p, int th) {
027 this.points = p;
028 graph = new PlaneGraph(p);
029 number = th;
030 threads = null;
031 }
032
033 /**
034 * @return number of iterations or 0.
035 */
036 public long getIterations() {
037 if ( threads == null ) {
038 return 0l;
039 }
040 long iter = 0l;
041 for ( int i = 0; i < threads.length; i++ ) {
042 if ( threads[i] != null ) {
043 iter += threads[i].getIterations();
044 }
045 }
046 return iter;
047 }
048
049 /**
050 * @return maxiter.
051 */
052 public long getMaxIterations() {
053 if ( threads == null ) {
054 return Long.MAX_VALUE;
055 }
056 long maxiter = Long.MAX_VALUE;
057 for ( int i = 0; i < threads.length; i++ ) {
058 long mi = threads[i].getMaxIterations();
059 if ( maxiter > mi ) {
060 maxiter = mi;
061 }
062 }
063 return maxiter;
064 }
065
066 /**
067 * @param m new maxIter.
068 * @return old maxIter.
069 */
070 public long setMaxIterations(long m){
071 if ( threads == null ) {
072 return m;
073 }
074 long maxiter = Long.MAX_VALUE;
075 for ( int i = 0; i < threads.length; i++ ) {
076 long mi = threads[i].setMaxIterations(m);
077 if ( maxiter > mi ) {
078 maxiter = mi;
079 }
080 }
081 return maxiter;
082 }
083
084
085 /**
086 * @return best.getPath().
087 */
088 public Path actualBest() {
089 if ( best == null ) {
090 return null;
091 }
092 return best.getPath();
093 }
094
095 /**
096 * @param b new best path.
097 */
098 public void setBest(Path b) {
099 if ( b == null ) {
100 return;
101 }
102 if ( best == null ) {
103 // best.setPath( b );
104 return;
105 }
106 if ( b.cost() < best.getPath().cost() ) {
107 best.setPath( b );
108 }
109 }
110
111 /**
112 * @return getBest(Long.MAX_VALUE).
113 */
114 public Path getBest() {
115 return getBest(Long.MAX_VALUE);
116 }
117
118 /**
119 * @param max maximal number of iterations.
120 * @return best Path.
121 */
122 public Path getBest(long max) {
123 Path bestPath = PathByteArray.standardPath(graph); // standard path
124 if ( bestPath.length() <= 2 ) {
125 return bestPath;
126 }
127 best = new BestByteLocStore( bestPath, 0, number );
128 Path path = PathByteArray.onePath(graph); // one/empty path
129 Deque globalStack = new Deque(10000);
130 try {
131 globalStack.push( path );
132 } catch (InterruptedException e) {
133 e.printStackTrace();
134 }
135 threads = new RunByteLocTSP[number];
136 for ( int i = 0; i < number; i++ ) {
137 threads[i] = new RunByteLocTSP(globalStack,best,max);
138 threads[i].start();
139 }
140 try {
141 for ( int i = 0; i < number; i++ ) {
142 threads[i].join();
143 }
144 } catch (InterruptedException e) {
145 e.printStackTrace();
146 }
147 return best.getPath();
148 }
149
150 public void getBest(Path path) {
151 System.out.println("method getBest() in ParByteLocalTSP not implemented");
152 }
153
154 }
155
156 /**
157 * Storage for best path found so far.
158 */
159 class BestByteLocStore {
160
161 private Path path;
162 private int idlers;
163 public final int threads;
164
165 /**
166 * @param b best known path.
167 * @param i idle threads.
168 * @param t number of threads.
169 */
170 public BestByteLocStore(Path b, int i, int t) {
171 path = b;
172 idlers = i;
173 threads = t;
174 }
175
176 /**
177 * @return path.
178 */
179 public Path getPath() {
180 return path;
181 }
182
183 /**
184 * @param p new best path.
185 */
186 public void setPath(Path p) {
187 path = p;
188 }
189
190 public synchronized void incIdle() {
191 idlers++;
192 }
193
194 public synchronized void decIdle() {
195 idlers--;
196 }
197
198 /**
199 * @return (idlers == threads).
200 */
201 public synchronized boolean allIdle() {
202 return (idlers == threads);
203 }
204 }
205
206
207 /**
208 * Thread for parallel computation.
209 */
210 class RunByteLocTSP extends Thread {
211
212 private BestByteLocStore best;
213 private Deque globalStack;
214 private long maxiter;
215 private long iter;
216 private long pushes;
217 private ArrayList stack;
218 public final int COUNT;
219
220 /**
221 * @param s work queue.
222 * @param b storage for best path.
223 * @param max maximal number of iterations.
224 */
225 public RunByteLocTSP(Deque s, BestByteLocStore b, long max) {
226 globalStack = s;
227 best = b;
228 COUNT = b.getPath().maxsize()+5; //*2 / +5 ?
229 maxiter = max;
230 stack = new ArrayList(500);
231 }
232
233
234 public void run() {
235 iter = 0;
236 pushes = 0;
237 boolean running = true;
238 while (running) {
239 Object o = null;
240 if ( stack.isEmpty() ) {
241 try {
242 best.incIdle();
243 if ( globalStack.empty() && best.allIdle() ) {
244 for ( int i = 0; i < best.threads-1; i++) {
245 globalStack.push(null);
246 }
247 best.decIdle();
248 break; //return;
249 }
250 o = globalStack.pop();
251 best.decIdle();
252 } catch (InterruptedException e) {
253 e.printStackTrace();
254 running = false;
255 }
256 } else {
257 o = stack.remove( stack.size()-1 );
258 }
259 if ( o == null ) {
260 break; //return;
261 }
262 Path path = (Path)o;
263 getBest( path );
264 }
265 System.out.println("iterations = " + iter + " pushes " + pushes);
266 }
267
268
269 /**
270 * @param path a starting path.
271 */
272 public void getBest(Path path) {
273 Path[] ps = path.nextPaths();
274 iter += ps.length;
275 double bestCost = best.getPath().cost();
276 if ( path.length()+1 == path.maxsize() ) {
277 for ( int i = 0; i < ps.length; i++ ) { // branch
278 if ( ps[i].cost() < bestCost ) {
279 synchronized ( best ) {
280 if ( ps[i].cost() < best.getPath().cost() ) {
281 bestCost = ps[i].cost();
282 best.setPath( ps[i] );
283 System.out.println("par best = " + ps[i]);
284 }
285 }
286 }
287 }
288 return;
289 }
290 if ( iter >= maxiter ) {
291 return;
292 }
293 if ( path.length()+5 >= path.maxsize() ) {
294 for ( int i = 0; i < ps.length; i++ ) { // branch
295 if ( ps[i].cost() < bestCost ) { // cut
296 //System.out.print("#");
297 getBestRec( ps[i].copyMax(), path.length()+1 ); // changes best and bestPath
298 //stack.add( ps[i] );
299 }
300 }
301 return;
302 }
303 for ( int i = 0; i < ps.length; i++ ) { // branch
304 if ( ps[i].cost() < bestCost ) { // cut
305 // getBest( ps[i] ); // changes best and bestPath
306 //System.out.print("-");
307 stack.add( ps[i] );
308 }
309 }
310 if ( stack.size() > COUNT && path.length() <= 3 ) {
311 if ( globalStack.empty() ) {
312 Object o = stack.remove( 0 ); //stack.size()-1, depth first
313 pushes++;
314 try {
315 globalStack.push( o ); // beware of deadlock
316 } catch (InterruptedException e) {
317 e.printStackTrace();
318 }
319 }
320 }
321 return;
322 }
323
324 /**
325 * @param path a starting path.
326 * @param depth length of this path.
327 */
328 public void getBestRec(Path path, int depth) {
329 double bestCost = best.getPath().cost();
330 for ( int k = 0; k < path.maxsize()-depth; k++ ) { // branch
331 Path ps = path.nextPath(k);
332 iter++;
333 if ( depth+1 == path.maxsize() ) {
334 if ( ps.cost() < bestCost ) {
335 synchronized ( best ) {
336 if ( ps.cost() < best.getPath().cost() ) {
337 bestCost = ps.cost();
338 best.setPath( (Path)ps.clone() ); // had error
339 System.out.println("par best rec = " + ps);
340 }
341 }
342 }
343 }
344 if ( iter >= maxiter ) {
345 return;
346 }
347 if ( ps.cost() < bestCost ) { // cut
348 getBestRec( ps, depth+1 ); // changes best and bestPath
349 //stack.add( ps[i] );
350 }
351 }
352 return;
353 }
354
355 /**
356 * @return iter.
357 */
358 public long getIterations() {
359 return iter;
360 }
361
362 /**
363 * @return maxiter.
364 */
365 public long getMaxIterations() {
366 return maxiter;
367 }
368
369 /**
370 * @param m new maxIter.
371 * @return old maxIter.
372 */
373 public long setMaxIterations(long m){
374 long x = maxiter;
375 maxiter = m;
376 return x;
377 }
378
379 }