旅行商问题贪心算法

① 用动态规划求旅行商问题是不是一个有效的算法为什么

实际工程中动态规划往往很难实现，但是求解能得到全局最优。 但是贪心算法虽然较易陷入局部最优，但是求解效率极高。 若是决策量前后之间影响不是很大，且较大规模问题贪心法较好。

② 对于大规模TSP问题，为什么遍历算法不可行而贪心算法可行

TSP属于NPC问题，一般只能靠近似算法求出近似解，问题规模小的时候，可以直接穷举问题空间，得出最优解，不过问题规模一大就不行了，问题空间是指数暴涨的，这时候只能退而求其次，求近似最优解，而对应的近似算法中会大量使用贪心策略，所以其实不是可不可行的问题，贪心牺牲了 解的精度（求得的不一定是最优解），但换来了时间上可观的节约（直接降到多项式）。

③ 对于大规模的TSP问题，为何遍历算法是不可行的，而贪心算法则是一种可

贪心自然也是不行的，这是NPC问题。
你说的应该是剪枝，剪枝并不改变时间复杂度，规模大之后剪枝也不可行，一般只能用近似算法。

④ 1.简述一下：两军问题及其引申的含义。2.生产者与消费者问题，反映了计算机学科的说没问题

5 贪心算法的核心思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质：1.整体的最优解可以通过局部的最优解来求出；2.一个整体能够被分为多个局部，并且这些局部都能够求出最优解
6 程序调用自身的编程技巧称为递归,是函数自己调用自己。
迭代:利用变量的原值推算出变量的一个新值.如果递归是自己调用自己的话,迭代就是A不停的调用B。
7 回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”

哎，太多了。写不完了。。。。
尽量帮你一点吧

⑤ 最短哈密顿回路！！！！！！！！！

你这个问题是NPC问题，不存在多项式时间的算法。

只有两种方法：
1，搜索：O(n!)
2，状态压缩的动态规划：O(n^2*2^n)

⑥ tsp问题的贪心算法，分析时间复杂度，试分析是否存在o的有效算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产

⑦ TSP算法在实际中有什么意义

不要问解决数学问题有什么用，总会有用的，数学是自然科学的基础。

TSP问题的概述
旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中着名问题之一。假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值，这是一个NP难问题。
TSP问题的由来
TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。
TSP由美国RAND公司于1948年引入，该公司的声誉以及线形规划这一新方法的出现使得TSP成为一个知名且流行的问题。
TSP在中国的研究
同样的问题，在中国还有另一个描述方法：一个邮递员从邮局出发，到所辖街道投邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么他应该如何选择投递路线，使所走的路程最短？这个描述之所以称为中国邮递员问题（Chinese Postman Problem CPP）因为是我国学者管梅古教授于1962年提出的这个问题并且给出了一个解法。

⑧ tsp贪心算法旅行商问题怎么判断是否到过某个城市

用vis[]数组标记。。。

⑨ 假设哈密顿问题是NPC,证明:TSP（旅行商问题）属于NP-hard问题（现代优化计算方法 邢文旬主编 P50第11题）

首先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问题