标签: traveling-salesman

我希望通过多次访问来讨论TSP的分支和绑定解决方案.(即每个城市需要至少访问一次,而不是仅访问一次)

编辑:

删除了怀疑,因为它与Jitse指出的不相关.现在问题更清楚了.

我对两个单词列表的功能感兴趣,这两个单词列表将返回它们之间的顺序不可知的编辑距离.

也就是说,参数将是两个(例如空格分隔)单词列表,返回值将是列表中单词的编辑(或Levenshtein)距离的最小总和.

"cat rat bat"和之间的距离"rat bat cat"将为0. "cat rat bat"和之间的"fat had bad"距离与"rat bat cat"和之间的距离相同"had fat bad".4.如果列表中的单词数不相同,则较短的列表将填充0长度的单词.

我的直觉(没有用计算机科学课程培养)没有找到任何其他解决方案而不是使用蛮力:

   |had|fat|bad|   a solution
---+---+---+---+ +---+---+---+
cat| 2 | 1 | 2 | |   | 1 |   |
---+---+---+---+ +---+---+---+
rat| 2 | 1 | 2 | | 3 |   |   |
---+---+---+---+ +---+---+---+
bat| 2 | 1 | 1 | |   |   | 4 |
---+---+---+---+ +---+---+---+

从第一行开始,选择一列并转到下一行,而无需重新访问已访问过的列.一遍又一遍地这样做,直到你尝试了所有的组合.

对我来说这听起来有点像旅行推销员的问题.是吗,你会如何解决我的特定问题？

我试图通过使用Hill Climbing算法来理解禁忌搜索,以解决旅行商问题.

我理解'纯' 爬山算法,但Tabu搜索如何改变这个算法对我来说不是很清楚.

爬山示范:

让我们说,我们给了6个城市A,B,C,D,E,F,我们随机选择一个初始状态:(A,B,C,D,E,F),旅行费用为120.

然后我将选择一组邻近状态(通过将第一个元素与第二,第三,第四等交换),并计算每个状态的旅行成本:

(B,A,C,D,E,F) = 110   /* <120; mark as optimal */
(C,B,A,D,E,F) = 127
(D,B,C,A,E,F) = 145
(E,B,C,D,A,F) = 102   /* <110; mark as optimal */
(F,B,C,D,E,A) = 80    /* <102; mark as optimal */

现在我们找到了局部最优:(F,B,C,D,E,A).

Tabu搜索如何改变上述算法？如果你能展示一两次迭代,我将非常感谢.

注意:这几乎与此问题相同:访问所有节点的最短路径

但我有一个完整的图表.

问题:考虑具有非负边长的完整无向图.问题:计算至少访问每个节点一次的最短路径.

注意:这不是TSP问题.路径没有结束节点,路径可以多次通过节点.

其他说明:

节点数很少(小于20).

我正在努力实现基于模拟退火的程序来解决旅行商问题。我得到的所有解决方案都不令人满意，我也不知道如何改善实施。显然，我不是在关注基准，而只是在寻找视觉上可接受的最短路径。如果有人能启发我，我将不胜感激。

# weight function, simple euclidean norm
def road(X,Y):
    sum = 0
    size = len(X) -1
    for i in range(0,size):
        sum +=math.sqrt((X[i]-X[i+1])**2 + (Y[i]-Y[i+1])**2)

    return sum   

def array_swap(X,Y,index_1,index_2):
    X[index_1],X[index_2] = X[index_2],X[index_1]
    Y[index_1],Y[index_2] = Y[index_2],Y[index_1]


def arbitrarty_swap(X,Y):
    ran = len(X)-1
    pick_1 = random.randint(0,ran)
    pick_2 = random.randint(0,ran)

    X[pick_1],X[pick_2] = X[pick_2],X[pick_1]
    Y[pick_1],Y[pick_2] = Y[pick_2],Y[pick_1]

    return pick_1, pick_2

N = 40

X = np.random.rand(N) * 100
Y = np.random.rand(N) * 100


plt.plot(X, Y, '-o')
plt.show()


best = road(X,Y)
X1 = X.copy()
Y1 = Y.copy() …

是否有一种算法可以在多项式时间内准确地解决(时间独立的)TSP问题(没有启发式,节点不是空间中的点,成本是任意的)？

谢谢!

我正在尝试为C99中的旅行商问题实施我自己的深度优先搜索算法,但是我遇到了意外的分段错误.

我有一小部分节点(大致)对应于英国的地方,它们之间有对称的路径.问题发生在newNode()方法的早期,我创建一个新节点并设置其初始状态.这涉及为节点创建一个路径数组,它将指定连接的节点和它们之间的"距离",其中每个路径的节点元素初始化为NULL.数组比我目前实现的示例图所需的要大得多(参见参考资料MAX_PATHS),因此以后很容易扩展.

paths在这种情况下,数组可以包含16个元素.初始化此数组的FOR循环在何时引发分段错误i = 3.之所以完全逃避我.我gdb在代码下面添加了一些输出.希望它有所帮助,或者您可能更喜欢使用自己的方法.

谢谢; 任何帮助将不胜感激!

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NODES 4
#define MAX_PATHS 16

typedef struct _node_t node_t;
typedef struct _path_t path_t;

struct _node_t
{
    char name[64];
    struct _path_t* paths;
};

struct _path_t
{
    struct _node_t* node;
    int dist;
};

node_t* nodes[NODES];

node_t* newNode(char* name)
{
    node_t* toReturn = (node_t*) malloc(sizeof(node_t*));

    if (toReturn == NULL)
    {
        perror("malloc");
        exit(EXIT_FAILURE);
    }

    printf("toReturn (%p)\n", toReturn);

    strcpy(toReturn->name, name);

    toReturn->paths = …

我很难构建一个小的无向图G,它具有超出给定算法的加权边,这意味着无论起点是什么,算法都不会选择最优解.每个节点都连接到每个其他节点.

给定起点,算法迭代地选择图上最近的未使用点并访问它直到它循环回到起始点.该算法执行强力,以每个点为起点运行并从所有输出循环中选择最短的哈密顿循环.

我因为我的生活已经无法解决这个问题,我已经绘制了无数的图表,经历并解决了它们,但仍然无法提出算法无法找到最佳解决方案的图表.

这完全是理论上的,没有代码.我非常感谢任何有关如何处理/思考这一问题的指导或指示.

我正在使用 Google Or-Tools 通过使用这个例子来解决一个旅行商问题（基本上我只是用我的距离矩阵替换了距离矩阵）。在示例中，我设置了data['depot'] = 0.

对于我的应用程序，返回到路径末尾的第一个节点并不重要。我可以从解决方案中删除最后一条边，但我想知道如果我可以完全删除此约束，它可能会找到更好的整体路径。

我明显错过了穿过树林的森林......

我知道旅行商问题,但有没有其他算法/问题更符合我的需求/描述？我需要借助这样的数学描述来描述我的问题.

我知道起始点和终点点最多有5个点.所以我只需要计算访问这两者之间所有三个点的最短路径.Dijkstra和类似的算法试图找到两点之间的最短路径,所以在这里它们可能不会访问它们之间的所有点.或者是否有一种算法找到最短路并访问两点之间的所有点？