以下是我在VC上用C语言运行的回溯法解旅行商问题的程序，运行结果不对啊，哪位大神能帮我修改一下。
我没看你后面的部分，就说第一段程序问题 swap()函数必须使用传地址方式，传值方式不能达到交换的作用，因为作用域只是函数内的局部变量x和y 改为 void swap(int *x,int *y) { int temp=*x; *x=*y; *y=temp; } 调用时传地址，即swap(&a,&b)形式。 修改后你再试试你的程序对不对。
用回溯法和分支限界法求对称的旅行商问题
望采纳，谢谢
旅行商问题的问题分析
旅行商问题要从图G的所有周游路线中求取最小成本的周游路线，而从初始点出发的周游路线一共有(n-1)!条，即等于除初始结点外的n-1个结点的排列数，因此旅行商问题是一个排列问题。排列问题比子集合的选择问题通常要难于求解得多，这是因为n个物体有n!种排列，只有 个子集合(n!>O( ))。通过枚举(n-1)!条周游路线，从中找出一条具有最小成本的周游路线的算法，其计算时间显然为O(n!)。
枚举法思想：程序中采用深度优先策略。（采用隐式和显式两种形式）
枚举算法的特点是算法简单，但运算量大，当问题的规模变大，循环的阶数越大，执行的速度越慢。如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。在解决旅行商问题时，以顶点1为起点和终点，然后求{2…N}的一个全排列，使路程1→{2…N}的一个全排列→1上所有边的权（代价）之和最小。所有可能解由（2，3，4，…，N）的不同排列决定。
为便于讨论，介绍一些关于解空间树结构的术语。在下面分析回溯法和分支限界法时都直接或间接用到解空间树。在解空间树中的每一个结点确定所求问题的一个问题状态（problem state）。由根结点到其它结点的所有路径则确定了这个问题的状态空间（state space）。解状态（solution states）表示一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组。答案状态（answer states）表示一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这问题的一个解（即，它满足隐式约束条件）。解空间的树结构称为状态空间树（state space tree）。
对于旅行商问题，一旦设想出一种状态空间树，那么就可以先系统地生成问题状态，接着确定这些问题状态中的哪些状态是解状态，最后确定哪些解状态是答案状态，从而将问题解出。为了生成问题状态，采用两种根本不同的方法。如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。当前正在生成其儿子结点的活结点叫E-结点。不再进一步扩展或者其儿子结点已全部生成的生成结点就是死结点。在生成问题状态的两种方法中，都要用一张活结点表。在第一种方法中，当前的E-结点R一旦生成一个新的儿子C，这个儿子结点就变成一个新的E-结点，当完全检测了子树C之后，R结点就再次成为E-结点。这相当与问题状态的深度优先生成。在第二种状态生成方法中，一个E-结点一直保持到死结点为止。这两种方法中，将用限界函数去杀死还没有全部生成其儿子结点的那些活结点。如果旅行商问题要求找出全部解，则要生成所有的答案结点。使用限界函数的深度优先结点生成方法称为回溯法。E-结点一直保持到死为止的状态生成方法称为分支限界法。
回溯法思想
为了应用回溯法，所要求的解必须能表示成一个n- 元组(x1,…,Xn)，其中x1是取自某个有穷集Si。通常，所求解的问题需要求取一个使某一规范函数P(x1,…,Xn)取极大值（或取极小值或满足该规范函数条件）的向量。
假定集合Si的大小是mi，于是就有m=m1m2…Mn个n-元组可能满足函数P。所谓硬性处理是构造这m个n-元组并逐一测试它们是否满足P，从而找出该问题的所有最优解。而回溯法的基本思想是，不断地用修改过的函数Pi(x1,…Xi)（即限界函数）去测试正在构造中的n-元组的部分向量(x1,…,Xi)，看其是否可能导致最优解。如果判定(x1,…,Xi)不可能导致最优解，那么就可能要测试的后n-i个元素组成的向量一概略去。因此回溯法作的次数比硬性处理作的测试次数（m次）要少得多。用回溯法求解的旅行商问题，即在枚举法的基础上多了一个约束条件，约束条件可以分为两种类型：显示约束和隐式约束。
分支限界法思想
采用FIFO分支限界法。
如前所述，分支限界法是在生成当前E-结点全部儿子之后再生成其它活结点的儿子，且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。在总的原则下，根据对状态空间树中结点检索的次序的不同又将分支限界设计策路分为数种不同的检索方法。在求解旅行商问题时，程序中采用FIFO检索（First In First Out），它的活结点表采用一张先进先出表（即队列）。可以看出，分支限界法在两个方面加速了算法的搜索速度，一是选择要扩展的节点时，总是选择选择一个最小成本的结点，尽可能早的进入最有可能成为最优解的分支；二是扩展节点的过程中，舍弃导致不可行解或导致非最优解的子结点。
贪心法思想
贪心法是一种改进了的分级处理方法。它首先旅行商问题描述，选取一种度量标准。然后按这种度量标准对n个输入城市排序，并按序一次输入一个城市。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把这个城市加入到这部分解中。这种能够得到某种量度意义下的最优解的分级处理方法成为贪心方法。
获得最优路径的贪心法应一条边一条边地构造这棵树。根据某种量度来选择将要计入的下一条边。最简单的量度标准是选择使得迄今为止计入的那些边的成本的和有最小增量的那条边。
1.简述一下：两军问题及其引申的含义。2.生产者与消费者问题，反映了计算机学科的说没问题？
5 贪心算法的核心思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质：1.整体的最优解可以通过局部的最优解来求出；2.一个整体能够被分为多个局部，并且这些局部都能够求出最优解 6 程序调用自身的编程技巧称为递归,是函数自己调用自己。 迭代:利用变量的原值推算出变量的一个新值.如果递归是自己调用自己的话,迭代就是A不停的调用B。 7 回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点” 哎，太多了。写不完了。。。。 尽量帮你一点吧
对于非完全图的旅行商问题，用什么算法？就是有些节点之间是没有路的
汉密尔顿回路问题是NP的 但是如果图满足一定条件（可以不是完全图），也可以构造出解（不同的条件有不同的构造法，具体百度吧） 但没有一般解法 所以，如果一定说，一般方法的话，只能是搜索。
想用动态规划算法解决旅行商（TSP）问题，麻烦指点下方法和思路，详细点，谢谢1
[hi.baidu.com] [liouwei20051000285.blog.163.com] 以上都是动态规划解决TSP问题的，但是个人觉得不是太好，建议你去了解一下遗传算法，很容易懂，网上有很详细的讲解。希望你学到知识
TSP问题数学模型的问题分析
旅行商问题要从图G的所有周游路线中求取最小成本的周游路线，而从初始点出发的周游路线一共有(n-1)!条，即等于除初始结点外的n-1个结点的排列数，因此旅行商问题是一个排列问题。排列问题比子集合的选择问题通常要难于求解得多，这是因为n个物体有n!种排列，只有 个子集合(n!>O( ))。通过枚举(n-1)!条周游路线，从中找出一条具有最小成本的周游路线的算法，其计算时间显然为O(n!)。
枚举法思想：程序中采用深度优先策略。（采用隐式和显式两种形式）
枚举算法的特点是算法简单，但运算量大，当问题的规模变大，循环的阶数越大，执行的速度越慢。如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。在解决旅行商问题时，以顶点1为起点和终点，然后求{2…N}的一个全排列，使路程1→{2…N}的一个全排列→1上所有边的权（代价）之和最小。所有可能解由（2，3，4，…，N）的不同排列决定。
为便于讨论，介绍一些关于解空间树结构的术语。在下面分析回溯法和分支限界法时都直接或间接用到解空间树。在解空间树中的每一个结点确定所求问题的一个问题状态（problem state）。由根结点到其它结点的所有路径则确定了这个问题的状态空间（state space）。解状态（solution states）表示一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组。答案状态（answer states）表示一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这问题的一个解（即，它满足隐式约束条件）。解空间的树结构称为状态空间树（state space tree）。
对于旅行商问题，一旦设想出一种状态空间树，那么就可以先系统地生成问题状态，接着确定这些问题状态中的哪些状态是解状态，最后确定哪些解状态是答案状态，从而将问题解出。为了生成问题状态，采用两种根本不同的方法。如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。当前正在生成其儿子结点的活结点叫E-结点。不再进一步扩展或者其儿子结点已全部生成的生成结点就是死结点。在生成问题状态的两种方法中，都要用一张活结点表。在第一种方法中，当前的E-结点R一旦生成一个新的儿子C，这个儿子结点就变成一个新的E-结点，当完全检测了子树C之后，R结点就再次成为E-结点。这相当与问题状态的深度优先生成。在第二种状态生成方法中，一个E-结点一直保持到死结点为止。这两种方法中，将用限界函数去杀死还没有全部生成其儿子结点的那些活结点。如果旅行商问题要求找出全部解，则要生成所有的答案结点。使用限界函数的深度优先结点生成方法称为回溯法。E-结点一直保持到死为止的状态生成方法称为分支限界法。 为了应用回溯法，所要求的解必须能表示成一个n- 元组(x1,…,Xn)，其中x1是取自某个有穷集Si。通常，所求解的问题需要求取一个使某一规范函数P(x1,…,Xn)取极大值（或取极小值或满足该规范函数条件）的向量。
假定集合Si的大小是mi，于是就有m=m1m2…Mn个n-元组可能满足函数P。所谓硬性处理是构造这m个n-元组并逐一测试它们是否满足P，从而找出该问题的所有最优解。而回溯法的基本思想是，不断地用修改过的函数Pi(x1,…Xi)（即限界函数）去测试正在构造中的n-元组的部分向量(x1,…,Xi)，看其是否可能导致最优解。如果判定(x1,…,Xi)不可能导致最优解，那么就可能要测试的后n-i个元素组成的向量一概略去。因此回溯法作的次数比硬性处理作的测试次数（m次）要少得多。用回溯法求解的旅行商问题，即在枚举法的基础上多了一个约束条件，约束条件可以分为两种类型：显示约束和隐式约束。
分支限界法思想：本题采用FIFO分支限界法。
如前所述，分支限界法是在生成当前E-结点全部儿子之后再生成其它活结点的儿子，且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。在总的原则下，根据对状态控件树中结点检索的次序的不同又将分支限界设计策路分为数种不同的检索方法。在求解旅行商问题时，程序中采用FIFO检索（First In First Out），它的活结点表采用一张先进先出表（即队列）。可以看出，分支限界法在两个方面加速了算法的搜索速度，一是选择要扩展的节点时，总是选择选择一个最小成本的结点，尽可能早的进入最有可能成为最优解的分支；二是扩展节点的过程中，舍弃导致不可行解或导致非最优解的子结点。 贪心法是一种改进了的分级处理方法。它首先对旅行商问题进行描述，选取一种度量标准。然后按这种度量标准对n个输入城市排序，并按序一次输入一个城市。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把这个城市加入到这部分解中。这种能够得到某种量度意义下的最优解的分级处理方法成为贪心方法。
获得最优路径的贪心法应一条边一条边地构造这棵树。根据某种量度来选择将要计入的下一条边。最简单的量度标准是选择使得迄今为止计入的那些边的成本的和有最小增量的那条边。
微信扫一扫