001    
002    package algo;
003    
004    import java.io.Serializable;
005    
006    /**
007     * A sequential algorithm for an euclidean 2d TSP Problem.
008     * @author Heinz Kredel.
009     */
010    public class SeqByteTSP implements TSPInf, Serializable {
011    
012        protected Graph graph;
013        protected Point[] points;
014        protected double best;   // beware of threads
015        protected Path bestPath; // beware of threads
016        protected long iter;
017        protected long maxiter;
018    
019    
020    /**
021     * @param p the cities.
022     */
023        public SeqByteTSP(Point[] p) {
024            this.points = p;
025            graph = new PlaneGraph(p);
026            bestPath = PathByteArray.standardPath(graph); // standard path
027            best = bestPath.cost();
028            iter = 0; 
029            maxiter = Long.MAX_VALUE;
030        }
031    
032    
033    /**
034     * @param p the cities.
035     * @param g the corresponding graph.
036     */
037        public SeqByteTSP(Point[] p, Graph g) {
038            this.points = p;
039            graph = g;
040            bestPath = PathByteArray.standardPath(graph); // standard path
041            best = bestPath.cost();
042            iter = 0; 
043            maxiter = Long.MAX_VALUE;
044        }
045    
046    
047    /**
048     * @return number of iterations.
049     */
050        public long getIterations() {
051            return iter;
052        }
053    
054    
055    /**
056     * @return maxiter.
057     */
058        public long getMaxIterations() {
059            return maxiter;
060        }
061    
062    
063    /**
064     * @param m new maxIter.
065     * @return old maxIter.
066     */
067        public long setMaxIterations(long m){
068            long x = maxiter;
069            maxiter = m;
070            return x;
071        }
072    
073    
074    /**
075     * @return the actual best Path.
076     */
077        public Path actualBest() {
078            return bestPath;
079        }
080    
081    
082    /**
083     * @param b a possible new best path.
084     */
085        public void setBest(Path b) {
086            if ( b == null ) {
087               return;
088            }
089            if ( b.cost() < best ) {
090               bestPath = b;
091               best = b.cost();
092            }
093        }
094    
095    
096    /**
097     * @return getBest(Long.MAX_VALUE).
098     */
099        public Path getBest() {
100            return getBest(Long.MAX_VALUE);
101        }
102    
103    
104    /**
105     * @param max maximal number of iterations.
106     * @return best Path.
107     */
108        public Path getBest(long max) {
109            iter = 0; 
110            maxiter = max;
111            bestPath = PathByteArray.standardPath(graph); // standard path
112            best = bestPath.cost();
113            if ( bestPath.length() <= 2 ) {
114                return bestPath;
115            }
116            Path path = PathByteArray.onePath(graph); // one/empty path
117            getBest(path);
118            System.out.println("iterations = " + iter);
119            return bestPath;
120        }
121    
122    
123    /**
124     * @param path a starting path.
125     */
126        public void getBest(Path path) {
127            Path[] ps = path.nextPaths(); 
128            iter += ps.length;
129            if ( path.length()+1 == path.maxsize() ) {
130               for ( int i = 0; i < ps.length; i++ ) { // branch
131                   //System.out.println("seq path = " + ps[i]);
132                   if ( ps[i].cost() < best ) {
133                      best = ps[i].cost();
134                      bestPath = ps[i];
135                      System.out.println("seq best = " + bestPath);
136                   }
137               }
138               return;
139            }
140            if ( iter >= maxiter ) {
141                return;
142            }
143            if ( path.length()+5 >= path.maxsize() ) {
144               for ( int i = 0; i < ps.length; i++ ) { // branch
145                   if ( ps[i].cost() < best ) { // cut
146                       //System.out.print("#");
147                       getBestRec( ps[i].copyMax(), path.length()+1 ); // changes best and bestPath
148                      //stack.add( ps[i] );
149                   }
150               }
151               return;
152            }
153            for ( int i = 0; i < ps.length; i++ ) { // branch
154                //System.out.println("seq path part = " + ps[i]);
155                if ( ps[i].cost() < best ) { // cut
156                   getBest( ps[i] ); // changes best and bestPath
157                }
158            }
159            return;
160        }
161    
162    
163    /**
164     * @param path a starting path.
165     * @param depth length of this path.
166     */
167        public void getBestRec(Path path, int depth) {
168            for ( int k = 0; k < path.maxsize()-depth; k++ ) { // branch
169                Path ps = path.nextPath(k); 
170                iter++;
171                if ( depth+1 == path.maxsize() ) {
172                   if ( ps.cost() < best ) {
173                      best = ps.cost();
174                      bestPath = (Path)ps.clone();
175                      System.out.println("seq best = " + ps);
176                   }
177                }
178                if ( iter >= maxiter ) {
179                   return;
180                }
181                if ( ps.cost() < best ) { // cut
182                    getBestRec( ps, depth+1 ); // changes best and bestPath
183                    //stack.add( ps[i] );
184                }
185            }
186            return;
187        }
188    
189    }