minimumspanningtreesolver.java

用于求解TSP(Traveling salesman problem

/**
 * The MinimumSpanningTree function determines a minimum spanning tree.
 *
 * @ Author        Create/Modi     Note
 * Keld Helsgaun   Jun XX, 2002
 * Xiaofeng Xie    May 21, 2005
 * Xiaofeng Xie    Apr 28, 2006    MAOS-TSP Beta 1.1.002
 *
 * @ Reference:
 * [1] K. Helsgaun,"An Effective Implementation of the Lin-Kernighan Traveling
 *  Salesman Heuristic", European J Operational Research 126 (1), 106-130 (2000).
 */

package implement.TSP.knowledge;

import Global.methods.*;
import Global.basic.data.matrix.*;
import maosKernel.knowledge.*;

public class MinimumSpanningTreeSolver {

  /**
  * @very slow, should be improved by binary heap or Fibonacci heaps
  *
  * Step 0: Pick any vertex as a starting vertex. (Call it S). Mark it with any
  *  given colour, say red.
  * Step 1:  Find the nearest neighbour of S (call it P1). Mark both P1 and the
  *  edge SP1 red. cheapest unmarked (uncoloured) edge in the graph that doesn't
  *  close a coloured circuit. Mark this edge with same colour of Step 1.
  * Step 2  Find the nearest uncoloured neighbour to the red subgraph (i.e., the
  *  closest vertex to any red vertex). Mark it and the edge connecting the vertex
  *  to the red subgraph in red.
  * Step 3 Repeat Step 2 until all vertices are marked red. The red subgraph is a
  *  minimum spanning tree.
  */
  public static double prim_mst(SpanningTree spanningTree, ISquareIMatrixEngine absDMatrix) {
    int n = absDMatrix.getNodeNumber();
    boolean[] usedFlagSet = new boolean[n];

    double small;
    double length, minLength = 0;
    int parentID = 0, currID = 0;
    int parentRefID = 0, currRefID = 0;

    /* select arbitrary point as starting point */
    int usedID = RandomGenerator.intRangeRandom(n);
    usedFlagSet[usedID] = true;
    spanningTree.setRootNode(usedID);

    int count = 1;
    while (count < n) {
      small = Double.MAX_VALUE;

      for (int i = 0; i < n; i++) {
        if (usedFlagSet[i]) {
          parentRefID = i;
          for (int j = 0; j < n; j++) {
            currRefID = j;
            if (!usedFlagSet[j]) {
              length = absDMatrix.getValueAt(parentRefID, currRefID);

              if (length < small) {
                small = length;
                parentID = parentRefID;
                currID = currRefID;
                usedID = j;
              }
            }
          }
        }
      }

      spanningTree.addLink(currID, parentID);

      minLength += small;
      usedFlagSet[usedID] = true;
      count++;
    }
    return minLength;
  }

  //very slow, should be improved by binary heap or Fibonacci heaps
 public static double prim_mst(SpanningTree spanningTree, ISquareIMatrixEngine absDMatrix, AbsNeighborManager neighborManager) {
   int n = absDMatrix.getNodeNumber();
   boolean[] usedFlagSet = new boolean[n];

   double small;
   double length, minLength = 0;
   int parentID = 0, currID = 0;
   int parentRefID = 0, currRefID = 0;

   /* select arbitrary point as starting point */
   int usedID = RandomGenerator.intRangeRandom(n);
   usedFlagSet[usedID] = true;
   spanningTree.setRootNode(usedID);

   int count = 1;
   while (count < n) {
     small = Double.MAX_VALUE;

     for (int i = 0; i < n; i++) {
       if (usedFlagSet[i]) {
         parentRefID = BasicArray.getPeriodID(n, i);
         int nNumber = neighborManager.getElementNumberAt(parentRefID);
         int[] nnArray = neighborManager.getArrayAt(parentRefID);
         for (int j = 0; j < nNumber; j++) {
           currRefID = nnArray[j];
           if (!usedFlagSet[currRefID]) {
             length = absDMatrix.getValueAt(parentRefID, currRefID);

             if (length < small) {
               small = length;
               parentID = parentRefID;
               currID = currRefID;
               usedID = currRefID;
             }
           }
         }
       }
     }

     spanningTree.addLink(currID, parentID);

     minLength += small;
     usedFlagSet[usedID] = true;
     count++;
   }
   return minLength;
 }

 /*
     Prim with heaps:
     make a heap of values (vertex,edge,weight(edge))
         initially (v,-,infinity) for each vertex
         let tree T be empty
     while (T has fewer than n vertices)
     {
         let (v,e,weight(e)) have the smallest weight in the heap
         remove (v,e,weight(e)) from the heap
         add v and e to T
         for each edge f=(u,v)
         if u is not already in T
             find value (u,g,weight(g)) in heap
             if weight(f) < weight(g)
             replace (u,g,weight(g)) with (u,f,weight(f))
     }
   */
  public static double prim_mst_sparse(SpanningTree spanningTree, ISquareIMatrixEngine absDMatrix, AbsNeighborManager neighborManager) {
    return 0;
  }
}