其实旅行商问题的应用的问题并不复杂，但是又很多的朋友都不太了解回溯法解决旅行商问题，因此呢，今天小编就来为大家分享旅行商问题的应用的一些知识，希望可以帮助到大家，下面我们一起来看看这个问题的分析吧！
旅行商问题的问题分析
1、旅行商问题要从图G的所有周游路线中求取最小成本的周游路线，而从初始点出发的周游路线一共有(n-1)!条，即等于除初始结点外的n-1个结点的排列数，因此旅行商问题是一个排列问题。排列问题比子集合的选择问题通常要难于求解得多，这是因为n个物体有n!种排列，只有个子集合(n!>O())。通过枚举(n-1)!条周游路线，从中找出一条具有最小成本的周游路线的算法，其计算时间显然为O(n!)。
2、枚举法思想：程序中采用深度优先策略。（采用隐式和显式两种形式）
3、枚举算法的特点是算法简单，但运算量大，当问题的规模变大，循环的阶数越大，执行的速度越慢。如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。在解决旅行商问题时，以顶点1为起点和终点，然后求{2…N}的一个全排列，使路程1→{2…N}的一个全排列→1上所有边的权（代价）之和最小。所有可能解由（2，3，4，…，N）的不同排列决定。
4、为便于讨论，介绍一些关于解空间树结构的术语。在下面分析回溯法和分支限界法时都直接或间接用到解空间树。在解空间树中的每一个结点确定所求问题的一个问题状态（problem state）。由根结点到其它结点的所有路径则确定了这个问题的状态空间（state space）。解状态（solution states）表示一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组。答案状态（answer states）表示一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这问题的一个解（即，它满足隐式约束条件）。解空间的树结构称为状态空间树（state space tree）。
5、对于旅行商问题，一旦设想出一种状态空间树，那么就可以先系统地生成问题状态，接着确定这些问题状态中的哪些状态是解状态，最后确定哪些解状态是答案状态，从而将问题解出。为了生成问题状态，采用两种根本不同的方法。如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。当前正在生成其儿子结点的活结点叫E-结点。不再进一步扩展或者其儿子结点已全部生成的生成结点就是死结点。在生成问题状态的两种方法中，都要用一张活结点表。在第一种方法中，当前的E-结点R一旦生成一个新的儿子C，这个儿子结点就变成一个新的E-结点，当完全检测了子树C之后，R结点就再次成为E-结点。这相当与问题状态的深度优先生成。在第二种状态生成方法中，一个E-结点一直保持到死结点为止。这两种方法中，将用限界函数去杀死还没有全部生成其儿子结点的那些活结点。如果旅行商问题要求找出全部解，则要生成所有的答案结点。使用限界函数的深度优先结点生成方法称为回溯法。E-结点一直保持到死为止的状态生成方法称为分支限界法。
6、为了应用回溯法，所要求的解必须能表示成一个n-元组(x1,…,Xn)，其中x1是取自某个有穷集Si。通常，所求解的问题需要求取一个使某一规范函数P(x1,…,Xn)取极大值（或取极小值或满足该规范函数条件）的向量。
7、假定集合Si的大小是mi，于是就有m=m1m2…Mn个n-元组可能满足函数P。所谓硬性处理是构造这m个n-元组并逐一测试它们是否满足P，从而找出该问题的所有最优解。而回溯法的基本思想是，不断地用修改过的函数Pi(x1,…Xi)（即限界函数）去测试正在构造中的n-元组的部分向量(x1,…,Xi)，看其是否可能导致最优解。如果判定(x1,…,Xi)不可能导致最优解，那么就可能要测试的后n-i个元素组成的向量一概略去。因此回溯法作的次数比硬性处理作的测试次数（m次）要少得多。用回溯法求解的旅行商问题，即在枚举法的基础上多了一个约束条件，约束条件可以分为两种类型：显示约束和隐式约束。
8、如前所述，分支限界法是在生成当前E-结点全部儿子之后再生成其它活结点的儿子，且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。在总的原则下，根据对状态空间树中结点检索的次序的不同又将分支限界设计策路分为数种不同的检索方法。在求解旅行商问题时，程序中采用FIFO检索（First In First Out），它的活结点表采用一张先进先出表（即队列）。可以看出，分支限界法在两个方面加速了算法的搜索速度，一是选择要扩展的节点时，总是选择选择一个最小成本的结点，尽可能早的进入最有可能成为最优解的分支；二是扩展节点的过程中，舍弃导致不可行解或导致非最优解的子结点。
9、贪心法是一种改进了的分级处理方法。它首先旅行商问题描述，选取一种度量标准。然后按这种度量标准对n个输入城市排序，并按序一次输入一个城市。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把这个城市加入到这部分解中。这种能够得到某种量度意义下的最优解的分级处理方法成为贪心方法。
10、获得最优路径的贪心法应一条边一条边地构造这棵树。根据某种量度来选择将要计入的下一条边。最简单的量度标准是选择使得迄今为止计入的那些边的成本的和有最小增量的那条边。
旅行商问题的变种问题
1、您好，您提的问题很实际。的确，在旅途过程中，乘坐怎样的交通工具即省钱又省时这是个相当重要的问题，这个问题解决的好与坏直接影响到旅行的心情。
2、根据您提供的条件，可以知道您与同学以射线形出游，即玩完每个景点都要回到小区。实际上，您如果采取这种出游方式无论乘什么交通工具，交通费用肯定会很高，原因之一就是您每次都要回到小区，之二就是不知道您要具体到哪些景点，因为即使是同一个景点，到达那里多数也会有很多不同路线，交通费用当然也不一样。
3、如果你计划去的N个景点可以有几个相连，即从小区先到A，从A再到B,玩完B又可以到C，这样路费相对会节省些，同时也可以节省时间，但是对个人体力要求不叫高，当然也要看您的时间是否来得及。
4、您此次出行的目的是促进新生之间的交流，而不是真正的去旅行，所以我建议您，把N个景点拆分开，1-2个景点做为一周的活动内容，每周都有不同的景点，每到一个景点大家可以借景发挥，设计一些小游戏，聊聊谈谈，玩玩闹闹，也不至于为了赶景点那么疲惫，同学之间也有充分的交流，等到下一周换其他景点，也能激起同学们的热情。这样比一下子都逛完好些。
5、在活动当中，主要组织者要特别熟悉交通线路，多找些相同景点的不同线路，以备应急只用；做好每次出行的费用记录，回来后及时向大家公布；同时把途中能涉及到的问题罗列清楚，拆分任务，让出行的每个同学都参与到旅行的计划与实施中来，这也是一种很好的交流过程，一旦大家都积极的参与，每个人了解了旅行的意义，就会珍惜大家在一起的时光，而不是只有组织者忙前忙后，没做周到的地方其他同学还埋怨。
6、旅行不仅仅只有快乐，很多时候烦恼也尽在其中，希望您和同学们能借旅行的机会好好交流，增进彼此的信任与理解，在欢乐与烦恼中慢慢成长。
旅行商问题的解法思路
旅行推销员的问题，我们称之为巡行（Tour），此种问题属于NP完全问题（NP-Complete），所以旅行商问题大多集中在启发式解法。Bodin（1983）等人将旅行推销员问题的启发式解法分成三种：从距离矩阵中产生一个近似最佳解的途径，有以下几种解法：如近邻点法（Nearest Neighbor Procedure）：一开始以寻找离场站最近的需求点为起始路线的第一个顾客，此后寻找离最后加入路线的顾客最近的需求点1、，直到最后。
2、节省法（Clark and Wright Saving）：以服务每一个节点为起始解，根据三角不等式两边之和大于第三边之性质，其起始状况为每服务一个顾客后便回场站，而后计算路线间合并节省量，将节省量以降序排序而依次合并路线，直到最后。
3、插入法（Insertion procedures）：如今插入法、最省插入法、随意插入法、最远插入法、最大角度插入法等。先给定一个可行途程，然后进行改善，一直到不能改善为止。有以下几种解法：
1、K-Opt(2/3 Opt)：把尚未加入路径的K条节线暂时取代如今路径中K条节线，并计算其成本（或距离），如果成本降低（距离减少），则取代之，直到无法改善为止，K通常为2或3。
2、Or-Opt：在相同路径上相邻的需求点，将之和本身或其它路径交换且仍保持路径方向性，合成启发法
先由途程建构法产生起始途程，然后再使用途程改善法去寻求最佳解，又称为两段解法（two phase method）。有以下几种解法：
1、起始解求解+2-Opt：以途程建构法建立一个起始的解，再用2-Opt的方式改善途程，直到不能改善为止。
2、起始解求解+3-Opt：以途程建构法建立一个起始的解，再用3-Opt的方式改善途程，直到不能改善为止。
关于本次旅行商问题的应用和回溯法解决旅行商问题的问题分享到这里就结束了，如果解决了您的问题，我们非常高兴。