algorithm - 优化的TSP算法

我感兴趣的是如何改进或提出算法，这些算法能够解决大约n = 100 to 200个城市的Travelling salesman problem。
我提供的wikipedia链接列出了各种优化，但它是在相当高的级别上实现的，我不知道如何在代码中实现它们。
有一些行业实力的解决方案，如Concorde，但这些方法太复杂了，无法满足我的要求，而充斥着tsp搜索的经典解决方案都是随机算法或经典回溯或动态规划算法，这些算法只适用于大约20个城市。
那么，是否有人知道如何实现一个简单的（简单的说，我的意思是一个实现不需要超过100-200行代码）tsp解算器，它至少在100个城市的合理时间（几秒钟）内工作？我只对精确解感兴趣。
你可以假设输入是随机生成的，所以我不关心那些专门用来破坏某个算法的输入。

最佳答案

200行，没有库是一个严格的限制。高级解算器使用branch并与hold–karp松弛绑定，我不确定哪怕是最基本的版本也能容纳200条普通线。不过，这里有个提纲。
持卡人
将tsp编写为整数程序的一种方法如下（dantzig、fulkerson、johnson）。对于所有边e，常数我们表示边e的长度，如果边e在巡更中，变量xe为1，否则为0。对于顶点的所有子集，（s）表示连接s中顶点和非s中顶点的边。
最小化sumedges e we xe
从属于
一。对于所有顶点v，sumedges e in（{v}）xe=2
2.对于顶点的所有非空真子集，sumedges e in（s）xe≥2
三。对于e中的所有边e，xe in{0，1}
条件1确保边集是巡更的集合。条件2确保只有一个。（否则，设为其中一个巡更访问的顶点集）通过进行此更改可获得hold–karp松弛。
三。对于e中的所有边e，xe in{0，1}
三。对于E中的所有边缘E，0≤Xe≤1
hold-karp是一个线性程序，但它有指数级的约束。一种方法是引入拉格朗日乘子，然后进行次梯度优化。这可以归结为一个循环，它计算一个最小生成树，然后更新一些向量，但细节有点复杂。除了“hold-karp”和“次梯度（下降优化）”之外，“1-树”是另一个有用的搜索词。
（另一个较慢的方法是编写lp解算器并引入subour约束，因为它们被先前的optima所违反。这意味着编写一个lp求解器和一个min cut过程，这也是更多的代码，但它可能更好地扩展到更奇特的tsp约束。）
分支和绑定
所谓“部分解”，我指的是变量的部分赋值为0或1，其中赋值为1的边肯定在巡更中，赋值为0的边肯定在巡更中。评估持有-KARP与这些方面的限制，给出了一个最低限度的最佳旅游，尊重已作出的决定（一个扩展）。
分枝定界保持一组局部解，其中至少有一个扩展到最优解。一个变量的伪代码，深度优先搜索和最佳第一回溯如下。

let h be an empty minheap of partial solutions, ordered by Held–Karp value
let bestsolsofar = null
let cursol be the partial solution with no variables assigned
loop
    while cursol is not a complete solution and cursol's H–K value is at least as good as the value of bestsolsofar
        choose a branching variable v
        let sol0 be cursol union {v -> 0}
        let sol1 be cursol union {v -> 1}
        evaluate sol0 and sol1
        let cursol be the better of the two; put the other in h
    end while
    if cursol is better than bestsolsofar then
        let bestsolsofar = cursol
        delete all heap nodes worse than cursol
    end if
    if h is empty then stop; we've found the optimal solution
    pop the minimum element of h and store it in cursol
end loop

分枝定界的概念是有一个部分解的搜索树。解决hold-karp问题的关键在于，lp的值至多是最优旅行的长度选择，但也被推测为至少3/4选择（实际上，通常更接近于选择）。
伪代码中我遗漏的一个细节是如何选择分支变量。目标通常是先做出“难”的决定，所以固定一个值已经接近0或1的变量可能不明智。一种选择是选择最接近0.5的，但还有很多其他选择。
编辑
Java实现。198行非空非注释行。我忘记了1-树不能将变量分配给1，所以我通过查找1-树的阶数大于2的顶点进行分支，然后依次删除每个边。该程序接受EUC_2D格式的tsplib实例，例如eil51.tsp和eil76.tsp以及eil101.tsp和lin105.tsp来自http://www2.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/的实例。

// simple exact TSP solver based on branch-and-bound/Held--Karp
import java.io.*;
import java.util.*;
import java.util.regex.*;

public class TSP {
  // number of cities
  private int n;
  // city locations
  private double[] x;
  private double[] y;
  // cost matrix
  private double[][] cost;
  // matrix of adjusted costs
  private double[][] costWithPi;
  Node bestNode = new Node();

  public static void main(String[] args) throws IOException {
    // read the input in TSPLIB format
    // assume TYPE: TSP, EDGE_WEIGHT_TYPE: EUC_2D
    // no error checking
    TSP tsp = new TSP();
    tsp.readInput(new InputStreamReader(System.in));
    tsp.solve();
  }

  public void readInput(Reader r) throws IOException {
    BufferedReader in = new BufferedReader(r);
    Pattern specification = Pattern.compile("\\s*([A-Z_]+)\\s*(:\\s*([0-9]+))?\\s*");
    Pattern data = Pattern.compile("\\s*([0-9]+)\\s+([-+.0-9Ee]+)\\s+([-+.0-9Ee]+)\\s*");
    String line;
    while ((line = in.readLine()) != null) {
      Matcher m = specification.matcher(line);
      if (!m.matches()) continue;
      String keyword = m.group(1);
      if (keyword.equals("DIMENSION")) {
        n = Integer.parseInt(m.group(3));
        cost = new double[n][n];
      } else if (keyword.equals("NODE_COORD_SECTION")) {
        x = new double[n];
        y = new double[n];
        for (int k = 0; k < n; k++) {
          line = in.readLine();
          m = data.matcher(line);
          m.matches();
          int i = Integer.parseInt(m.group(1)) - 1;
          x[i] = Double.parseDouble(m.group(2));
          y[i] = Double.parseDouble(m.group(3));
        }
        // TSPLIB distances are rounded to the nearest integer to avoid the sum of square roots problem
        for (int i = 0; i < n; i++) {
          for (int j = 0; j < n; j++) {
            double dx = x[i] - x[j];
            double dy = y[i] - y[j];
            cost[i][j] = Math.rint(Math.sqrt(dx * dx + dy * dy));
          }
        }
      }
    }
  }

  public void solve() {
    bestNode.lowerBound = Double.MAX_VALUE;
    Node currentNode = new Node();
    currentNode.excluded = new boolean[n][n];
    costWithPi = new double[n][n];
    computeHeldKarp(currentNode);
    PriorityQueue<Node> pq = new PriorityQueue<Node>(11, new NodeComparator());
    do {
      do {
        boolean isTour = true;
        int i = -1;
        for (int j = 0; j < n; j++) {
          if (currentNode.degree[j] > 2 && (i < 0 || currentNode.degree[j] < currentNode.degree[i])) i = j;
        }
        if (i < 0) {
          if (currentNode.lowerBound < bestNode.lowerBound) {
            bestNode = currentNode;
            System.err.printf("%.0f", bestNode.lowerBound);
          }
          break;
        }
        System.err.printf(".");
        PriorityQueue<Node> children = new PriorityQueue<Node>(11, new NodeComparator());
        children.add(exclude(currentNode, i, currentNode.parent[i]));
        for (int j = 0; j < n; j++) {
          if (currentNode.parent[j] == i) children.add(exclude(currentNode, i, j));
        }
        currentNode = children.poll();
        pq.addAll(children);
      } while (currentNode.lowerBound < bestNode.lowerBound);
      System.err.printf("%n");
      currentNode = pq.poll();
    } while (currentNode != null && currentNode.lowerBound < bestNode.lowerBound);
    // output suitable for gnuplot
    // set style data vector
    System.out.printf("# %.0f%n", bestNode.lowerBound);
    int j = 0;
    do {
      int i = bestNode.parent[j];
      System.out.printf("%f\t%f\t%f\t%f%n", x[j], y[j], x[i] - x[j], y[i] - y[j]);
      j = i;
    } while (j != 0);
  }

  private Node exclude(Node node, int i, int j) {
    Node child = new Node();
    child.excluded = node.excluded.clone();
    child.excluded[i] = node.excluded[i].clone();
    child.excluded[j] = node.excluded[j].clone();
    child.excluded[i][j] = true;
    child.excluded[j][i] = true;
    computeHeldKarp(child);
    return child;
  }

  private void computeHeldKarp(Node node) {
    node.pi = new double[n];
    node.lowerBound = Double.MIN_VALUE;
    node.degree = new int[n];
    node.parent = new int[n];
    double lambda = 0.1;
    while (lambda > 1e-06) {
      double previousLowerBound = node.lowerBound;
      computeOneTree(node);
      if (!(node.lowerBound < bestNode.lowerBound)) return;
      if (!(node.lowerBound < previousLowerBound)) lambda *= 0.9;
      int denom = 0;
      for (int i = 1; i < n; i++) {
        int d = node.degree[i] - 2;
        denom += d * d;
      }
      if (denom == 0) return;
      double t = lambda * node.lowerBound / denom;
      for (int i = 1; i < n; i++) node.pi[i] += t * (node.degree[i] - 2);
    }
  }

  private void computeOneTree(Node node) {
    // compute adjusted costs
    node.lowerBound = 0.0;
    Arrays.fill(node.degree, 0);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) costWithPi[i][j] = node.excluded[i][j] ? Double.MAX_VALUE : cost[i][j] + node.pi[i] + node.pi[j];
    }
    int firstNeighbor;
    int secondNeighbor;
    // find the two cheapest edges from 0
    if (costWithPi[0][2] < costWithPi[0][1]) {
      firstNeighbor = 2;
      secondNeighbor = 1;
    } else {
      firstNeighbor = 1;
      secondNeighbor = 2;
    }
    for (int j = 3; j < n; j++) {
      if (costWithPi[0][j] < costWithPi[0][secondNeighbor]) {
        if (costWithPi[0][j] < costWithPi[0][firstNeighbor]) {
          secondNeighbor = firstNeighbor;
          firstNeighbor = j;
        } else {
          secondNeighbor = j;
        }
      }
    }
    addEdge(node, 0, firstNeighbor);
    Arrays.fill(node.parent, firstNeighbor);
    node.parent[firstNeighbor] = 0;
    // compute the minimum spanning tree on nodes 1..n-1
    double[] minCost = costWithPi[firstNeighbor].clone();
    for (int k = 2; k < n; k++) {
      int i;
      for (i = 1; i < n; i++) {
        if (node.degree[i] == 0) break;
      }
      for (int j = i + 1; j < n; j++) {
        if (node.degree[j] == 0 && minCost[j] < minCost[i]) i = j;
      }
      addEdge(node, node.parent[i], i);
      for (int j = 1; j < n; j++) {
        if (node.degree[j] == 0 && costWithPi[i][j] < minCost[j]) {
          minCost[j] = costWithPi[i][j];
          node.parent[j] = i;
        }
      }
    }
    addEdge(node, 0, secondNeighbor);
    node.parent[0] = secondNeighbor;
    node.lowerBound = Math.rint(node.lowerBound);
  }

  private void addEdge(Node node, int i, int j) {
    double q = node.lowerBound;
    node.lowerBound += costWithPi[i][j];
    node.degree[i]++;
    node.degree[j]++;
  }
}

class Node {
  public boolean[][] excluded;
  // Held--Karp solution
  public double[] pi;
  public double lowerBound;
  public int[] degree;
  public int[] parent;
}

class NodeComparator implements Comparator<Node> {
  public int compare(Node a, Node b) {
    return Double.compare(a.lowerBound, b.lowerBound);
  }
}

关于algorithm - 优化的TSP算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7159259/