realproblemiohandler.java

用于求解TSP(Traveling salesman problem

/**
 * Description: reads the problem data in TSPLIB format
 *
   The following description of the file format is extracted from the TSPLIB
   documentation (by K. Helsgaun, LKH 1.3, July 2002).

   The file consists of a specification part and a data part. The specification part
   contains information on the file format and on its contents. The data part contains
   explicit data.

   (1) The Specification part

   All entries in this section are of the form <keyword> : <value>, where <keyword>
   denotes an alphanumerical keyword and <value> denotes alphanumerical or numerical
   data. The terms <string>, <integer> and <real> denote character string, integer
   or real data, respectively. The order of specification of the keywords in the data
   file is arbitrary (in principle), but must be consistent, i.e., whenever a keyword
   is specified, all necessary information for the correct interpretation of the
   keyword has to be known. Below is given a list of all available keywords.

   NAME : <string>e
   Identifies the data file.

   TYPE : <string>
   Specifies the type of data. Possible types are
   TSP          Data for a symmetric traveling salesman problem

   COMMENT : <string>
   Additional comments (usually the name of the contributor or the creator of the
   problem instance is given here).

   DIMENSION : < integer>
   The number of nodes.

   EDGE_WEIGHT_TYPE : <string>
   Specifies how the edge weights (or distances) are given. The values are:
   EXPLICIT     Weights are listed explicitly in the corresponding section
   EUC_2D       Weights are Euclidean distances in 2-D
   EUC_3D       Weights are Euclidean distances in 3-D
   MAX_2D       Weights are maximum distances in 2-D
   MAX_3D       Weights are maximum distances in 3-D
   MAN_2D       Weights are Manhattan distances in 2-D
   MAN_3D       Weights are Manhattan distances in 3-D
   CEIL_2D      Weights are Euclidean distances in 2-D rounded up
   CEIL_3D      Weights are Euclidean distances in 3-D rounded up
   GEO          Weights are geographical distances (TSPLIB)
   GEOM         Weights are geographical distances (used for the world TSP)
   ATT          Special distance function for problem att48 and att532

   EDGE-WEIGHT_FORMAT : <string>
   Describes the format of the edge weights if they ar given explicitely. The values
   are
   FULL_MATRIX          Weights are given by a full matrix
   UPPER_ROW            Upper triangular matrix (row-wise without diagonal entries)
   LOWER_ROW            Lower triangular matrix (row-wise without diagonal entries)
   UPPER_DIAG_ROW       Upper triangular matrix (row-wise including diagonal entries)
   LOWER_DIAG_ROW       Lower triangular matrix (row-wise including diagonal entries)
   UPPER_COL            Upper triangular matrix (column-wise without diagonal entries)
   LOWER_COL            Lower triangular matrix (column-wise without diagonal entries)
   UPPER_DIAG_COL       Upper triangular matrix (column-wise including diagonal entries)
   LOWER_DIAG_COL       Lower triangular matrix (colum-wise including diagonal entries)

   EDGE_DATA_FORMAT : <string>
   Describes the format in which the edges of a graph are given, if the graph is
   not complete. The values are
   EDGE_LIST    The graph is given by an edge list
   ADJ_LIST     The graph is given by an adjacency list

   NODE_COORD_TYPE : <string>
   Specifies whether the coordinates are associated with each node (which, for
   example may be used for either graphical display or distance computations.
   The values are
   TWOD_COORDS          Nodes are specified by coordinates in 2-D
   THREE_COORDS         Nodes are specified by coordinates in 3-D
   NO_COORDS            The nodes do not have associated coordinates
   The default value is NO_COORDS. In the current implementation, however, the value
   has no significance.

   DISPLAY_DATA_TYPE : <string>
   Specifies how a graphical display of the nodes can be obtained. The values are
   COORD_DISPLAY        Display is generated from the node coordinates
   TWOD_DISPLAY         Explicit coordinates in 2-D are given
   BO_DISPLAY           No graphical display is possible

   The default value is COORD_DISPLAY if node coordinates are specifies and
   NO_DISPLAY otherwise. In the current implementation, however, the value has no
   significance.

   EOF
   Terminates input data. The entry is optional.

   (2) The data part

   Depending on the choice of specifications some additional data may be required.
   These data are given corresponding data sections following the specification part.
   Each data section begins with the corresponding keyword. The length of the section
   is either explicitly known form the format specification, or the section is
   terminated by an appropriate end-of-section identifier.

   NODE_COORD_SECTION :
   Node coordinates are given in this section. Each line is of the form
   <integer> <real> <real>
   if NODE_COORD_TYPE is TWOD_COORDS, or
   <integer> <real> <real> <real>
   if NODE_COORD_TYPE is THREED_COORDS. The integers give the number of the
   respective nodes. The real numbers are the associated coordinates.

   EDGE_DATA_SECTION :
   Edges of the graph are specified in either of the two formats allowed in the
   EDGE_DATA_FORAT entry. If a type is EDGE_LIST, then the edges are given as a
   sequence of lines of the form
   <integer> <integer>
   each entry giving the terminal nodes of some edge. The list is terminated by
   a -1. If the type is ADJ_LIST, the section consists of adjacency list for nodes.
   The adjacency list of a node x is specified as
   <integer> <integer> ... <integer> -1
   where the first integer gives the number of node x and the following integers
   (terminated by -1) the numbers of the nodes adjacent to x. The list of adjacency
   lists are terminated by an additional -1.

   FIXED_EDGES_SECTION :
   In this section, edges are listed that are required to appear in each solution
   to the problem. The edges to be fixed are given in the form (per line)
   <integer> <integer>
   meaning that the edge (arc) from the first node to the second node has to be
   contained in a solution. This section is terminated by a -1.

   DISPLAY_DATA_SECTION :
   If DISPLAY_DATA_TYPE is TWOD_DISPLAY, the 2-dimensional coordinates from which
   a display can be generated are given in the form (per line)
   <integer> <real> <real>
   The integers specify the respective nodes and the real numbers give the
   associated coordinates. The contents of this section, however, has no
   significance in the current implementation.

   TOUR_SECTION :
   A tour is specified in this section. The tour is given by a list of integers
   giving the sequence in which the nodes are visited in the tour. The tour is
   terminated by a -1. Note: In contrast to the TSPLIB format, only one tour can
   be given in this section. The tour is used to limit the search (the last edge
   to be removed in a non-gainful move must not belong to the tour). In addition,
   the Alpha field of its edges is set to zero.

   EDGE_WEIGHT_SECTION :
   The edge weights are given in the format specifies by the EDGE_WEIGHT_FORMAT
   entry. At present, all explicit data are integral and is given in one of the
   (self-explanatory) matrix formats, with explicitly known lengths.
 *
 * @ Author        Create/Modi     Note
 * Xiaofeng Xie    Apr 6, 2005     [e-mail]
 *
 * @ Reference:
 *  [1] Program's name: acotsp
 *  Ant Colony Optimization algorithms (AS, ACS, EAS, RAS, MMAS, BWAS) for the
 *  symmetric TSP, Copyright (C) 2004  Thomas Stuetzle
 *  Email: stuetzle no@spam informatik.tu-darmstadt.de
 *  [2] TSPLIB, Gerhard Reinelt, Gerhard.Reinelt{at}informatik.uni-heidelberg.de
 */

package implement.TSP.infoIO;

import Global.define.*;
import Global.basic.data.matrix.*;
import Global.methods.*;

import maosKernel.represent.*;
import implement.TSP.represent.*;
import implement.common.infoIO.*;

public class RealProblemIOHandler extends AIProblemIOHandler {

  public String writeSolution(EncodedState state) throws Exception {
    String tourStr = "";
    int[] tour = state.getSearchState().getIArray();
    tourStr += "NAME : see file name"+BasicTag.RETURN_TAG;
    tourStr += "COMMENT : Optimum tour with cost "+state.writeEncodeInfo()+BasicTag.RETURN_TAG;
    tourStr += "TYPE : TOUR"+BasicTag.RETURN_TAG;
    tourStr += "DIMENSION : "+tour.length+BasicTag.RETURN_TAG;
    tourStr += "TYPE : TOUR"+BasicTag.RETURN_TAG;
    tourStr += "TOUR_SECTION"+BasicTag.RETURN_TAG;
    for (int i=0; i<tour.length; i++) {
      tourStr += (tour[i]+1)+BasicTag.RETURN_TAG;
    }
    tourStr += "-1"+BasicTag.RETURN_TAG;
    tourStr += "EOF"+BasicTag.RETURN_TAG;
    return tourStr;
  }

  public void naiveReadSolution(EncodedState state, String content) throws Exception {
    String[] lines = GlobalString.getMeaningfulLines(content);