旅行商问题

题目描述

G = (V,E) 是一个带权重的完全图，顶点个数|v| = n(顶点代表城市 c)，每条边 eij∈E 赋予权重 dij 代表从顶点 ci 到顶点 cj 的距离或者费用。令 π 对对所有顶点的任一排列（排列代表访问城市序列），f（π）为排列的总长度（或）费用，则旅行商问题求

从第一个城市到第 n 个城市，再从第 n 个城市回来

旅行商问题的最优解结构特征

• 最优解子结构性质

• 子问题重叠
  如以下路径 c1c2c3c4….cn 和 c1c3c2c4….cn 都有子问题 c4….cn

旅行商问题最优解对应的最优值，并递归定义最优值

min TSP(c1，C/ci,cj)+dji

得出递归方程

TSP(c1，C/ci,cj)= {
  d(c1,cj)                   |c|=1,i≠1

  min TSP(c1，C/ci,cj)+dji   其他
}

TSP* = TSP(c1，C/ci,cj) +dj1

自底向上求最优解