basicneighbormanager.java

来自「用于求解TSP(Traveling salesman problem」· Java 代码 · 共 111 行

/**
 * Description: provide the information for the graph problem
 *
 * @ Author        Create/Modi     Note
 * Xiaofeng Xie    Apr 7, 2005     Inside PheromoneHolder
 * Xiaofeng Xie    Apr 15, 2005    neighborhood manager for nearest
 * Xiaofeng Xie    May 22, 2005    general neighborhood manager
 * Xiaofeng Xie    Apr 28, 2006    MAOS-TSP Beta 1.1.002
 *
 */

package maosKernel.knowledge;

import java.util.*;

import Global.basic.*;
import Global.basic.data.matrix.*;
import Global.methods.*;
import maosKernel.represent.space.*;

public class BasicNeighborManager extends AbsNeighborManager {
  protected int norm_nn_nodes = 0;            /* number of predefined nearest neighbours in tour construction */
  protected int[][] norm_DistSortedIDMatrix;  // the primate IDs of N_neighbor nodes sorted by distance

  public String getSummary() {
    String str = this.getClass().getName()+" norm_nn_nodes="+norm_nn_nodes;
    return str;
  }

  public BasicNeighborManager(ISquareIMatrixEngine costMatrix, int norm_nn_nodes) {
    setNeighborManager(costMatrix, norm_nn_nodes);
  }

  public void setNeighborManager(ISquareIMatrixEngine costMatrix, int norm_nn_nodes) {
    int nodeNumber = costMatrix.getNodeNumber();
    norm_DistSortedIDMatrix = new int[nodeNumber][];
    setNN_NodeNumber(norm_nn_nodes);
    init_Norm_DistMatrix(costMatrix);
  }


  public BasicNeighborManager(ISquareIMatrixEngine costMatrix) {
    this(costMatrix, 5);
  }

  public void setNN_NodeNumber(int nn_Nodes) {
    norm_nn_nodes = Math.min(nn_Nodes, getNodeNumber()-1);
  }

  private void init_Norm_DistMatrix(ISquareIMatrixEngine dataMatrix) {
    int nodeNumber = dataMatrix.getNodeNumber();
    norm_DistSortedIDMatrix = new int[nodeNumber][];
    IndexedIValue[] idValueSet = new IndexedIValue[nodeNumber];
    for (int j=0; j<nodeNumber; j++) {
      idValueSet[j] = new IndexedIValue();
    }
    int elemNumber = dataMatrix.getNodeNumber();
    for (int i=0; i<nodeNumber; i++) {
      idValueSet[i].value = -Integer.MAX_VALUE;
      for (int j=0; j<nodeNumber; j++) {
        idValueSet[j].index = j;
        idValueSet[j].value = dataMatrix.getValueAt(i, j);
      }
      idValueSet[i].value = -Integer.MAX_VALUE;
      Arrays.sort(idValueSet);
      norm_DistSortedIDMatrix[i] = new int[elemNumber-1];
      for (int j=0; j<norm_DistSortedIDMatrix[i].length; j++) {
        norm_DistSortedIDMatrix[i][j] = idValueSet[j+1].index;
      }
    }
  }

  public int getNodeNumber() {
    return norm_DistSortedIDMatrix.length;
  }

  public int getNNNumberUpLimit() {
    return norm_nn_nodes;
  }

  public int[] getNNArrayAt(int index) {
    return norm_DistSortedIDMatrix[index];
  }

  public int getElementNumberAt(int index) {
    return norm_nn_nodes;
  }

  //For debug
  public int[] getOrder(AISearchState point, boolean isForward) {
    int[] nodes = point.getIArray();
    int[] orderIDs = new int[nodes.length];
    if (isForward) {
      for (int i=0; i<nodes.length; i++) {
        orderIDs[i] = getOrder(nodes[i], nodes[(i+1)%nodes.length]);
      }
    } else {
      for (int i=0; i<nodes.length; i++) {
        orderIDs[i] = getOrder(nodes[(i+1)%nodes.length], nodes[i]);
      }
    }
    return orderIDs;
  }

  private int getOrder(int startNode, int endNode) {
    return BasicArray.getExactIndex(norm_DistSortedIDMatrix[startNode], endNode);
  }

}