假设哈密顿问题是NPC,证明：TSP（旅行商问题）属于NP

首先HC是一个npc问题且是一个搜索问题，假设使用贪心策略的算法A（·）可解HC得到一条哈密顿回路.再利用无向图G构造tsp的图G'，图G中存在的边权值设为1，图G中不存在的边权值设为X(X>1的整数).这样得到的一个TSP问题可使用算法A（·）来解.图灵规约条件：（1）问题1，问题2都是搜索问题； （2）求解问题1的算法A（·）可求解问题2; (3)算法A（问题1）时间复杂度是多项式时间，则算法A（问题2）也是多项式时间；所以HC可以图灵规约到这样一个TSP问题实例.又因为HC是NPC类问题，可以图灵规约到TSP，所以TSP是NP-hard问题

...老师还是说语法不行旅行商问题（TravelingSalesmanProblem,简记...

添改了一些词，有几个句子稍微改了一下顺序，有的变为从句连贯些，供参考~Traveling Salesman Problem(TSP)is a typical NP-hard problem in combinatorial optimization field, of which the solution time is exponential with the increase of the problem scale.Since traditional optimization algorithm fails to meet demand, what based on intelligent algorithms for TSP has been a hot topic in recent years. Simulated annealing algorithm is a random iterative optimization algorithm that combines the physical annealing process and Combinatorial Optimization,which converges to the overall optimal solution by Metropolis criteria.Using Simulated annealing algorithm to solve the TSP problem is an ideal method. This design uses simulated annealing algorithm to solve TSP problem, and has made designs of the city's position and its algorithm rules, according to the characteristics of TSP problem and simulated annealing algorithm. A basic window is constructed based on C++, which has defined random city positions in the window. At the same time, neighborhood search methods and the Calculation of Path difference are designed to speed up algorithm speed. Experimental test results show that this design has achieved good effects.

求最短路径问题 送货郎问题

最佳答案检举 模型一：利用“图”的知识，将送货点抽象为“图”中是顶点，由于街道和坐标轴平行，即任意两顶点之间都有路。

在此模型中，将两点之间的路线权值赋为这两点横纵坐标之和。

如A(x1,y1),B(x2,y2)两点，则权值为Q=|x2-x1|+|y2-y1|。

并利用计算机程序对以上结果进行了校核。

经典的Dijkstra算法和 Floyd算法思路清楚、 方法简便，但随着配送点数的增加，计算的复杂性以配送点数的平方增加，并具有一定的主观性. 所以本研究在利用动态规划法的基础上引入扑食搜索法的原理，提高辆车的装载率，从而减少车辆的需求，达到降低成本的目的.模型二：根据题意（B题），建立动态规划的数学模型。

然后用动态规划的知识求得最优化结果。

根据所建立的两个数学模型，对满足设计要求的送货策略和费用最省策略进行了模拟，在有标尺的坐标系中得到了能够反映运送最佳路线的模拟图。

最后，对设计规范的合理性进行了充分和必要的论证。

快递公司送货策略1 问题的提出在快递公司送货策略中，确定业务员人数和各自的行走路线是本题的关键。

这个问题可以描述为：一中心仓库（或配送调度中心） 拥有最大负重为25kg的业务员m人， 负责对30个客户进行货物分送工作， 客户i 的货物需求为以知 ， 求满足需求的路程最短的人员行驶路径，且使用尽量少的人数，并满足以下条件：1） 每条配送路径上各个客户的需求量之和不超过个人最大负重。

2） 每个客户的需求必须满足， 且只能由一个人送货.3）每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h。

4）为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克。

处于实际情况的考虑， 本研究中对人的最大行程不加限制.本论文试图从最优化的角度，建立起满足设计要求的送货的数学模型，借助于计算机的高速运算与逻辑判断能力，求出满足题意（B题）要求的结果。

2 问题的分析2. 1根据题意（B题）的要求，每个人的工作时间不超过6小时，且必须从早上9点钟开始派送，到当天17点之前（即在8小时之内）派送完毕。

表一列出了题中任意两配送点间的距离。

表一：任意两点间的距离矩阵因为距离是对称的，即从送货点i到送货点j的距离等于从j到i的距离。

记作：di,j.表二给出了产品的需求，为了完成配送任务，每个人在工作时间范围内，可以承担两条甚至更多的配送线路。

表中给出了送货点编号，快件量T，以及送货点的直角坐标。

表二对于上述的路线确定和费用优化问题，应用如下启发从公司总部配出一个人，到任意未配送的送货点，然后将这个人配到最近的未服务的送货点范围之内的邻居，并使送货时间小于6小时，各送货点总重量不超过25kg。

继续上述指派，直到各点总重量超过25kg，或者送货时间大于6小时。

最后业务员返回总部，记录得到的可行行程（即路线）。

对另一个业务员重复上述安排，直到没有未服务的送货点。

对得到的可行的行程安排解中的每一条路径，求解一个旅行商问题，决定访问指派给每一条行程的业务员的顺序，最小化运输总距离。

得到可行解的行程安排解后退出。

上面的方法通过以下两种方法实现：（1） 每一个行程的第一个送货点是距离总部最近的未服务的送货点。

用这种方法，即可得到一组运行路线，总的运行公里数，以及总费用。

（2） 每一个行程的第一个送货点是距离总部最远的未服务的送货点。

然后以该点为基准，选择距它最近的点，加上约束条件，也可得到一组数据。

然后比较两组结果，通过函数拟合即可得到最优化结果。

3 模型假设 （1）假设每个人的送货路线一旦确定，再不更改。

（2）送货期间，每个人相互之间互不影响。

（3）如果到某一个点距离最近的点不至一个，就按下面的方法进行确定：考虑该点需求的快件量，将其从大到小依次排列，快件量需求大者优先，但路线中各点总重量加上该点的快件量超过25kg的上限时，该点舍去。

如距离4最近的点有2,5,6,7四个点，其中，0-1-3-4路线易确定，且各点重量之和为 19.5kg，因此对于2,7两点，直接舍去，选5最合适。

4 符号说明 A：所有配送点的集合，A={0,1,2,3，…….，n}，其中0代表配送中心m： 业务员人数 C：任意一点到原点（总部）的距离 C总：表示一条路线所运行的总公里数 i,j： 表示送货点，如i点，j点 K：表示K条路线 qi： 点i的需求量，q0=0，表示总部的需求量 B总K: K条路线的总运行费用 X：校核时的适应度 Xij： 业务员路线安排5 模型的建立及求解5.1 TSP模型的数学描述为：其顶点集合为A顶点间的距离为C={Cij| i,j∈N,1≤i,j≤n} m nmin ∑ ∑ CijXij i=1j=1满足 n∑ Xij=1，ⅰi=1,2，⋯nj=1 m∑ Xij=1,j=1,2，⋯nj=1Xij∈{0,1}, i=1,2⋯n,j=1,2⋯n，而根据题意，任意两点之间都有通路，即不存在Xij=0的情况。

根据上述所列的启发式方法生成一个行程安排解。

每一个行程的第一个送货点是距离总部最近的未服务的送货点。

第一条行程中访问了节点0-1-3-4-5-0，是因为1距离原点最近，因此由1出发，3是距离1点最近的点，而且两处快件量之和为14kg，小于每个人最大负重量，可以继续指配。

接着，4是距离3最近的点，而且三处快件量之和为 19.5...