对于大规模TSP问题，为什么遍历算法不可行而贪心算法可行
TSP属于NPC问题，一般只能靠近似算法求出近似解，问题规模小的时候，可以直接穷举问题空间，得出最优解，不过问题规模一大就不行了，问题空间是指数暴涨的，这时候只能退而求其次，求近似最优解，而对应的近似算法中会大量使用贪心策略，所以其实不是可不可行的问题，贪心牺牲了 解的精度（求得的不一定是最优解），但换来了时间上可观的节约（直接降到多项式）。
试设计解决tsp问题的贪心算法，分析时间复杂度，试分析是否存在o的有效算法5分
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 比如最小生成树Kruskal算法，每次在不构成环的前提下，总是选择权最小的边。 找零钱问题：以人民币1元，2元，5元，10元，20元，50元，100元为例，要求所找的张数最少 背包问题：假设物体重量W1，W2．．．Wn其对应的价值为P1，P2．．．Pn，物体可分割，求装入重量限制为m的背包中的物体价值最大．
对于大规模的TSP问题，为何遍历算法是不可行的，而贪心算法则是一种可
tsp属于npc问题，一般只能靠近似算法求出近似解，问题规模小的时候，可以直接穷举问题空间，得出最优解，不过问题规模一大就不行了，问题空间是指数暴涨的，这时候只能退而求其次，求近似最优解，而对应的近似算法中会大量使用贪心策略，所以其实不是可不可行的问题，贪心牺牲了 解的精度（求得的不一定是最优解），但换来了时间上可观的节约（直接降到多项式）。
贪心算法TSP问题，有代码但是看不懂，求注释
int[] part = new int[3];//这里定义了3个int数组空间 { 0，1，2} pat[1]=2;//数据的第二位设置为2
C++算法，动态规划法实现TSP问题
c++listmatrixiteratoriostream算法
[cpp] view plaincopyprint?
#include
#include
using namespace std ;
typedef list<int> LISTINT;
LISTINT listAnother;
LISTINT list_result;
int d[4][4]={{-1,3,6,7},{2,-1,8,6},{7,3,-1,5,},{7,3,7,-1}}; //路径权值
int matrix_length=4;
int getPath(int n,LISTINT list_org)
{
LISTINT::iterator i;
int minValue;
if(n==1)
{
i=list_org.begin();
minValue= d[*i-1][0];
if(list_org.size()==matrix_length-1)
{
list_result=list_org;
}
}
else
{
int temp;
i=list_org.begin();
temp=*i;
list_org.erase(i);
i=list_org.begin();
minValue=d[temp-1][*(i)-1]+getPath(n-1,list_org);
if(list_org.size()==matrix_length-1)
{
list_result=list_org;
}
for(int j=2;j
{
i=list_org.begin();
for(int k=1;k
{
i++;
}
int tempvalue=*i;
list_org.erase(i);
list_org.push_front(tempvalue);
i=list_org.begin();
tempvalue=d[temp-1][*(i)-1]+getPath(n-1,list_org);
if(tempvalue
{
if(list_org.size()==matrix_length-1)
{
list_result=list_org;
}
minValue=tempvalue;
}
}
}
return minValue;
}
int main(int argc, char* argv[])
{
LISTINT list_org;
LISTINT::iterator h;
list_org.push_front(4);
list_org.push_front(3);
list_org.push_front(2);
list_org.push_front(1);
cout<<"旅行商问题动态规划算法"<
用java解决tsp问题用什么算法最简单
package noah; import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; public class TxTsp { private int cityNum; // 城市数量 private int[][] distance; // 距离矩阵 private int[] colable;//代表列，也表示是否走过，走过置0 private int[] row;//代表行，选过置0 public TxTsp(int n) { cityNum = n; } private void init(String filename) throws IOException { // 读取数据 int[] x; int[] y; String strbuff; BufferedReader data = new BufferedReader(new InputStreamReader( new FileInputStream(filename))); distance = new int[cityNum][cityNum]; x = new int[cityNum]; y = new int[cityNum]; for (int i = 0; i < cityNum; i++) { // 读取一行数据，数据格式1 6734 1453 strbuff = data.readLine(); // 字符分割 String[] strcol = strbuff.split(" "); x[i] = Integer.valueOf(strcol[1]);// x坐标 y[i] = Integer.valueOf(strcol[2]);// y坐标 } data.close(); // 计算距离矩阵 // ，针对具体问题，距离计算方法也不一样，此处用的是att48作为案例，它有48个城市，距离计算方法为伪欧氏距离，最优值为10628 for (int i = 0; i < cityNum - 1; i++) { distance[i][i] = 0; // 对角线为0 for (int j = i + 1; j < cityNum; j++) { double rij = Math .sqrt(((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) / 10.0); // 四舍五入，取整 int tij = (int) Math.round(rij); if (tij < rij) { distance[i][j] = tij + 1; distance[j][i] = distance[i][j]; } else { distance[i][j] = tij; distance[j][i] = distance[i][j]; } } } distance[cityNum - 1][cityNum - 1] = 0; colable = new int[cityNum]; colable[0] = 0; for (int i = 1; i < cityNum; i++) { colable[i] = 1; } row = new int[cityNum]; for (int i = 0; i < cityNum; i++) { row[i] = 1; } } public void solve(){ int[] temp = new int[cityNum]; String path="0"; int s=0;//计算距离 int i=0;//当前节点 int j=0;//下一个节点 //默认从0开始 while(row[i]==1){ //复制一行 for (int k = 0; k < cityNum; k++) { temp[k] = distance[i][k]; //System.out.print(temp[k]+" "); } //System.out.println(); //选择下一个节点，要求不是已经走过，并且与i不同 j = selectmin(temp); //找出下一节点 row[i] = 0;//行置0，表示已经选过 colable[j] = 0;//列0，表示已经走过 path+="-->" + j; //System.out.println(i + "-->" + j); //System.out.println(distance[i][j]); s = s + distance[i][j]; i = j;//当前节点指向下一节点 } System.out.println("路径:" + path); System.out.println("总距离为:" + s); } public int selectmin(int[] p){ int j = 0, m = p[0], k = 0; //寻找第一个可用节点，注意最后一次寻找，没有可用节点 while (colable[j] == 0) { j++; //System.out.print(j+" "); if(j>=cityNum){ //没有可用节点，说明已结束，最后一次为 *-->0 m = p[0]; break; //或者直接return 0; } else{ m = p[j]; } } //从可用节点J开始往后扫描，找出距离最小节点 for (; j < cityNum; j++) { if (colable[j] == 1) { if (m >= p[j]) { m = p[j]; k = j; } } } return k; } public void printinit() { System.out.println("print begin...."); for (int i = 0; i < cityNum; i++) { for (int j = 0; j < cityNum; j++) { System.out.print(distance[i][j] + " "); } System.out.println(); } System.out.println("print end...."); } public static void main(String[] args) throws IOException { System.out.println("Start...."); TxTsp ts = new TxTsp(48); ts.init("c://data.txt"); //ts.printinit(); ts.solve(); } }
对于大规模的TSP问题，为何遍历算法是不可行的，而贪心算法则是一种可
贪心自然也是不行的，这是NPC问题。 你说的应该是剪枝，剪枝并不改变时间复杂度，规模大之后剪枝也不可行，一般只能用近似算法。
急求tsp问题算法的源代码（c++）
根据限界函数计算下界lb,估计上界up
将k=0,lb,x[1:n]=0存入PT
while(PT不为空)
{ 从PT中取出lb值最小元素
k=k+1;
for(i=1; i<=n; i++)
{ x[k]=i;
if(c[i][x[k-1]<+∞)
{ die=0;计算 lb ;
for(j=1; j
蚁群算法做tsp问题与vrp的代码有什么不同
、旅行商问题（Traveling Salesman Problem, TSP） 这个问题字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。 TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象...
谁能帮我编个贪心算法求解TSP问题的C++源代码
AC代码，132kb，0ms 记得给分哦~~ #include #include using namespace std; int a[12],n,k,visit[12]; __int64 sum=0; void dfs(int num,int x,int j) { if(num==k) { sum+=x; return; } for(int i=1;ij) { visit[i]=1; if(!x) dfs(num+1,a[i],i...