标签: traveling-salesman

在过去的几天里,我已经注意到了几个网站 的网站是展示了使用遗传算法TS解决方案.

哪种方法在TSP问题中产生较短的旅程:最近邻居或遗传算法？

我正在使用遗传算法(GA)来优化旅行商问题(TSP).我的问题是我如何计算个人的健康状况.显然,具有较短路线的解决方案更适合但是我如何在不知道最短路径和最长可能路线确定我的解决方案在该范围内的位置的情况下分配适合度值？

假设我们给了7个城市A,B,C,D,E,F,G,我们有一个开始状态ABCDEFGA,有一些成本'x',我不明白这个节点的孩子会是什么.意思是怎么样爬山算法的第二次迭代会继续进行吗？

作为开始状态的节点ABCDEFGA是否有6个孩子？就像在

第二次迭代是ACBDEFGA,ADCBEFGA,AECDBFGA,AFCDEBGA,AGCDEFBA？

第三次迭代:假设在第二次迭代中选择了ADCBEFGA,那么第三次迭代是否会与所有其他城市交换城市"C"等等？

我想知道我对算法的理解是否正确.

在连通图中,有饥饿人群站立的n个点.每个饥饿的人都想去图中的一家餐厅.每个人的行程距离应在1公里范围内.餐厅不能超过CEILING [n/k]客人.

提供这些饥饿的人和该地区的餐馆的点,是否有一个有效的算法,运行在多项式时间,告诉每个客人是否可以容纳(如真或假)？

这让我想起了旅行商问题,所以它只是一个修改过的版本吗？

我要解决像谷歌地图旅行商问题确实在其DirectionsRequest与request.setOptimizeWaypoints(true);.它在一条路线中命令一些航路点,以便减少旅行费用.

我的问题:有人知道它背后的算法是什么吗？任何启发式？到目前为止,无法通过谷歌找到任何信息.

我告诉自己,发现了很多插入 - 启发式,最近邻居等等......或者它是一个精确的解决方案程序？

我正在学习TSP,我遇到了掩盖代表所有城市组合的比特.我不明白它背后的逻辑.请帮帮我.

#define size 10 //maximum 10 cities
#define min(a,b) a>b?b:a
#define sizePOW 1024 // 2^10

int n,npow,g[size][sizePOW],p[size][sizePOW],adj[size][size];

int compute(int start,int set)
{   
    int masked,mask,result=INT_MAX,temp,i;

    if(g[start][set]!=-1)
        return g[start][set];
    for(i=0;i<n;i++)
    {   
        mask=(npow-1)-(1<<i);
        masked=set&mask;
        if(masked!=set)
        {   
            temp=adj[start][i]+compute(i,masked);
            if(temp<result)
                result=temp,p[start][set]=i;
        }
    }
    return g[start][set]=result;
}

void getpath(int start,int set)
{
    if(p[start][set]==-1) return;
    int x=p[start][set];
    int mask=(npow-1)-(1<<x);  // What is the use of this line
    int masked=set&mask;
    printf("%d ",x);
    getpath(x,masked);
}
void TSP()
{   
    int i,j;
    //g(i,S) is length of shortest path starting at i …

我在SO的答案中读到以下内容:

通常提出的旅行推销员问题是找到连接所有城市的最便宜的路线.这不是决策问题,我们无法直接验证任何建议的解决方案.我们可以将其重申为一个决策问题:给定成本C,是否有比C便宜的路线？这个问题是NP完全的,通过一些工作,我们可以像修改的NP完全形式一样轻松地解决原始TSP.因此,TSP是NP难的,因为它至少与NP完全问题一样难.

我知道TSP是NP-Complete但问题是NP-Hard？我读到NP中但不是P中的问题是NP-Hard.我无法将此事与TSP联系起来.请解释一下.

以下算法的时间复杂度是多少？

输入:点P的集合及其欧几里德坐标

1. 计算点的浏览(使用最近邻算法,如TSP问题)

2. 对于每个点,获取最近的邻居信息(相对于原始数据集中的所有点)

复杂度是O(n)还是O(n²)？我们如何轻松地将复杂性和效率可视化？

我目前正在研究旅行商问题,并且想知道是否有人能够简单地解释持有的karp下限.我一直在看很多论文,我很难理解它.如果有人可以简单地解释它会很棒.

我也知道有一种计算不包括起始顶点的顶点的最小生成树然后从起始顶点添加两个最小边的方法.

通过尝试所有可能性，计算给定字符串的所有字符串排列可以在 O(n!) 中解决。

现在，看看旅行商问题，我们可以通过尝试城市的所有排列来解决它。假设我们有城市 A、B 和 C。假设我们从城市 A 开始。通过计算 BC 字符串的所有排列，我们得到 ABC ACB，然后我们只需求和（在多项式时间内，AB、CB 和 CA 之间的距离为第一个案件...）

那么这不是旅行商问题的所有字符串排列的减少吗？它不是一个NP完全问题吗？