TSPstate.java

//Stanje za problem trgovskega potnika
 
public class TSPstate implements SearchState, Comparable {
  TSPproblem p ;
  int walk[] ;
  int walkLen ;
  double qVal, mVal ;
 
  public TSPstate(TSPproblem pr) {
    p = pr;
    walk = null;
    walkLen = 0;
    qVal = mVal = Double.MAX_VALUE ;
  }
 
  public List next() {
    List successors = new ListLinked() ;
    TSPstate newState ;
    for (int i=0 ; i < p.size ; i++)
      if (! inWalk(i) && p.cost[walk[walkLen-1]][i] != Integer.MAX_VALUE) {
        newState = new TSPstate(p) ;
        newState.walk = (int[])walk.clone() ;
        newState.walk[walkLen] = i ;
        newState.walkLen = walkLen +1 ;
        successors.insert(newState);
      }
    return successors ;
  }
 
  public double q() {
    if (qVal == Double.MAX_VALUE) // pri prvi izvrsitvi
      qVal = -1*qV() ;
    return qVal ;
  }
 
  public double qV() {
    int qVal = 0 ;
    for (int i=1 ; i < walkLen ; i++)
      qVal += p.cost[walk[i-1]][walk[i]] ;
    if (walkLen > 1)
      qVal += p.cost[walk[walkLen-1]][walk[0]] ;
    return (double)(qVal+p.MAX_COST*(p.size - walkLen)) ;
  }
 
  public double max() {
    if (mVal == Double.MAX_VALUE) // izracunamo samo prvic
      mVal = -1*minV() ;
    return mVal ;
  }
 
  public double minV() {
    // hevristika: polovica vsote dveh najkrajsih povezav iz preostalih mest
    int i, j, minCost1, minCost2 ;
    double minVal = 0.0 ;
    int unused[] = new int[p.size] ; // polje preostalih mest
    int noUnused = 0 ;
    // zberemo preostala mesta v polje
    for (i=0 ; i < p.size ; i++)
      if (! inWalk(i))
        unused[noUnused++] = i ;
    int allowed = noUnused ;
    // v polje preostalih dodamo tudi prvo mesto na poti (saj se je treba vrniti)
    unused[allowed++] = walk[0] ;
    if (walkLen >  1) // ce je trenutno uporabljenih mest >1
      unused[allowed++] = walk[walkLen-1] ; // dodamo tudi zadnje mesto na poti
    if (noUnused > 1) { // ce sta preostali vsaj dve mesti
      // za mesta v polju unused poiscemo dve najkrajsi povezavi
      for (i = 0; i < noUnused; i++) {
        minCost1 = minCost2 = Integer.MAX_VALUE;
        for (j = 0; j < allowed; j++) {
          if (i == j)
            continue;
          if (p.cost[unused[i]][unused[j]] < minCost1) {
            minCost2 = minCost1;
            minCost1 = p.cost[unused[i]][unused[j]];
          }
          else if (p.cost[unused[i]][unused[j]] < minCost2)
            minCost2 = p.cost[unused[i]][unused[j]];
        }
        // hevristiki pristejemo polovico vsote dveh najkrajsih povezav
        minVal += (minCost1 + minCost2) / 2.0 ;
      }
    }
    else if (noUnused ==1) // preostalo je samo eno mesto, zato izracun poenostavimo
      minVal = p.cost[walk[0]][unused[0]] + p.cost[walk[walkLen-1]][unused[0]] ;
    else minVal = 0 ; // resitev vsebuje ze vsa mesta
    return minVal ;
  }
 
  boolean inWalk(int el) {
    for (int i=0 ; i < walkLen ; i++)
      if (el == walk[i])
        return true ;
    return false ;
  }
  public void init(int city) {
    walk = new int[p.size] ;
    walk[0] = city ;
    walkLen = 1 ;
    for (int i=1 ; i <p.size ; i++)
      walk[i] = -1 ;
  }
 
  public void printOut() {
    for (int i=0 ; i < walkLen ; i++)
       System.out.print(walk[i]+", ") ;
  }
 
   public int compareTo(Object s) {
      return Double.compare(max(), ((TSPstate)s).max()) ;
   }
}