标签: traveling-salesman

这是针对一个项目,我被要求为旅行商优化问题以及汉密尔顿路径或周期决策问题实施启发式算法.我不需要实现本身的帮助,但对我正在进行的方向有疑问.

我已经有一个基于遗传算法的TSP启发式算法:它假设一个完整的图表,从一组随机解决方案开始作为一个群体,并努力改善人口数代.我还可以用它来解决汉密尔顿路径或循环问题吗？我只是想检查是否有路径,而不是优化以获得最短路径.

现在任何完整的图形都会有哈密顿路径,因此TSP启发式必须扩展到任何图形.如果两个城市之间没有路径,并返回作为有效哈密顿路径的第一条路径,则可以通过将边设置为某个无穷大值来完成此操作.

这是接近它的正确方法吗？或者我应该为汉密尔顿路径使用不同的启发式算法？我主要担心的是它是否是一种可行的方法,因为我可以肯定TSP优化是有效的(因为你从解决方案开始并改进它们),但是如果哈密尔顿路径决策器在固定数量的代中找到任何路径则不行.

我认为最好的方法是自己测试它,但是我受到时间的限制,并且在走下这条路线之前我会问...(我可以找到一个不同的启发式方法来代替汉密尔顿路径)

我阅读了有关这方面的各种内容并理解了所涉及的原理和概念,然而,没有一篇论文提到如何计算染色体(代表一条路线)的适应性的细节,该染色体涉及相邻的城市(在染色体中)没有直接连接通过边缘(在图中).

例如,给定染色体1 | 3 | 2 | 8 | 4 | 5 | 6 | 7,其中每个基因代表图/地图上的城市指数,我们如何计算其适应度(即(例如,在城市2和8之间没有直接边缘/链接).我们是否遵循某种贪婪算法来计算出2到8之间的路线,并将此路线的距离加到总数上？

将GA应用于TSP时,这个问题似乎很常见.任何以前做过的人请分享您的经验.谢谢.

这是一个学术而非实际的问题.在旅行推销员问题中,或任何其他涉及寻找最小优化的问题......如果使用地图/减少方法,似乎有一些价值可以将当前最小结果广播给所有人计算节点以某种方式允许它们放弃超过该计算的计算.

换句话说,如果我们将问题映射出来,我们希望每个节点知道何时在完成之前放弃给定的部分结果,但是当它已经超过其他解决方案时.

如果减速器具有向映射器提供反馈的方法,那么立即想到的一种方法是.考虑一下我们是否有100个节点,映射器为它们提供了数百万条路径.如果reducer将最佳结果提供给mapper,那么该值可以作为参数与每个新路径(问题子集)一起包含.在这种方法中,粒度相当粗糙...... 100个节点将在问题的分区上逐渐磨损完成,并且只有来自映射器的下一个请求才能获得新的最小值.(对于少量节点和大量问题分区/子集来说,这种粒度是无关紧要的;也可能是人们可以将启发式方法应用于可能的路由或问题子集被馈送到节点的序列中获得朝向最优的快速收敛,从而最小化节点执行的"浪费"计算量.

想到的另一种方法是节点主动订阅某种频道,或多播甚至广播,从中可以从计算循环中收集新的最小值.在这种情况下,当被通知更好的解决方案时(他们的同行之一),他们可以立即放弃糟糕的计算.

所以,我的问题是:

• 这个概念是否涵盖了与现有地图/减少讨论相关的任何艺术术语
• 当前的map/reduce框架是否提供支持此类动态反馈的功能？
• 这个想法有一些缺陷......为什么它是愚蠢的一些原因？

什么是一个很好的启发式用于解决以下挑战？

Quality Blimps Inc.希望将销售额扩大到其他城市(N),因此他们聘请您作为推销员飞往其他城市销售飞艇.随身携带的Blimp价格昂贵,因此您需要确定每次旅行时携带多少飞艇以及何时返回总部以获得更多飞艇.Quality Blimps拥有无限量的飞艇.

您可以在您访问的每个城市只销售一个飞艇,但您不需要访问每个城市,因为有些城市的旅行费用很高.每个城市的初始价格都是飞利浦销售的,但随着更多的飞艇出售(并且新颖性消失),这个价格下降了一定比例.找到一条能够实现利润最大化的好路线.

https://www.hackerrank.com/codesprint4/challenges/tbsp

这个挑战类似于标准的旅行商问题,但有一些额外的曲折:推销员需要跟踪他自己的旅行费用和飞艇.每个城市都有不同的价格,而且这些价格在他的旅程中下降.什么是快速算法(即n log n)用于最大化利润？

以某种方式运输物品的价格使TSP更简单.如果推销员在A市并且想要去B,他可以比较直接到B的成本与首先返回总部以获得更多飞艇的成本.也就是说,通过A将额外的飞艇带到B或者回到中间是更便宜的.这项检查将创建一系列循环旅行,销售人员可以按照最高收入顺序进行.但是,首先确定这些循环的好方法是什么？

我很清楚DP解决旅行商问题; 也被称为TSP的Held和Karp算法.

我用bitmask实现了它,它是这样的:

int TSP(int pos, int bitmask) {
  if (bitmask == (1<<(K+1))-1)
      return dist[pos][0];              // Completing the round trip

  if (memo[pos][bitmask] != -1)
      return memo[pos][bitmask];

  int answer = INF;
  for (int i = 0; i <= K; i++) {
      if (i != pos && (bitmask & (1 << i)) == 0)
          answer = Math.min(answer, dist[pos][i] + TSP(i, bitmask | (1 << i)));
  }

  return memo[pos][bitmask] = answer;     // Storing the best dist for the set of traveled cities and …

让我们有一个包含k个节点的完整无向度量图; 度量图是满足三角不等式的图,因此对于所有节点a,b,c,权重函数w(a,c)小于或等于w(a,b)+ w(公元前).

Wlog让我们说循环:<1,2,3,...,k,1>是该图的最佳TSP解决方案.

我的问题是:如果我从图中删除一个节点(例如第n个)并且我快速跳过循环,那么结果循环仍然是最佳的TSP解决方案吗？

nb,循环将变为<1,2,...,n-1,n + 1,...,k,1>

我有一个优化问题，我正在寻找一种算法，该算法的性能要比单纯的方法好。

问题

考虑一个图，，G(N, E)其中N是节点E集，是边集。每个节点n_i在N具有相关联的状态s_i。我使用了字典D来存储它，其中节点作为键，相应的状态作为值。相邻节点可以使用交换策略交换状态。具体来说，交换策略定义为

def swap(G, D, n_i, n_j):
    if n_i not in neighbors(G, n_j):
         print('Cannot swap between disconnected nodes')
    else:
         s_i = D[n_i]
         s_j = D[n_j]
         D[n_i] = s_j
         D[n_j] = s_i
    return D

每个状态现在必须以给定的顺序“访问”其他状态的列表，其中访问意味着这两个状态必须在上的任意一对相邻节点上G(N, E)。例如s_1必须访问[s_3, s_5, s_2]，s_2必须访问[s_1, s_3]，s_3必须访问[s_1, s_2, s_4]等。访问顺序必须保留。但是，允许状态位于相邻节点上，而无需将其标记为访问。例如，如果s_1开始于s_5，则它必须首先成为，然后s_3将该访问标记为已完成，然后s_5 …

尊敬的 OptaPlanner 专家！

我想使用 OptaPlanner（或类似的开源 Java 框架）来优化自行车信使服务的路线。让我们假设 5 个信使必须从某个来源拿起 30 个信封并将它们送到某个目的地：

            X(FROM) Y(FROM) X(TO)   Y(TO)
envelope 1  13745   55419   13883   55756
envelope 2  8406    53246   13937   55854
envelope 3  15738   57396   35996   79499
envelope 4  12045   60418   19349   57118
envelope 5  13750   56416   35733   78403
envelope 6  13190   57068   11860   59749
envelope 7  15021   55768   14098   57379
envelope 8  11513   58543   11501   59683
envelope 9  12013   64155   14120   59301
envelope 10 15006   57578   35511   78426
envelope 11 11450   58819   11916 …

我愿意实现一种算法，以最有效的方式（即最准确的结果 + 最少的时间）解决旅行商问题的二维欧几里得版本。在做我的研究时，我发现了很多算法，但Arora 1998 年的论文和它的介绍让我觉得可能是最好的算法。还有其他版本的解决方案使用相同的想法，例如Schultes在 2004 年的那个。问题是实现它似乎非常困难（如果不是不可能的话），我发现没有任何人以可访问的方式这样做的记录尽管这篇论文发表已经快 20 年了。

是否有任何现有的实施或至少有一个指导方针？如果不是，那么什么是现有且可实现的算法来尽可能最好地替代它？

我正在创建一个遗传算法来使用 python 和 networkx 解决旅行商问题。我添加了一个条件来收敛到满意的解决方案：路径不得有交叉边缘。我想知道 networkx 中是否有一个快速函数来验证图形是否具有交叉边，或者至少想知道是否可以创建一个。

该图是使用一系列点 ( path) 创建的，每个点都有一个 x 坐标和 y 坐标。点的序列索引了游览路径。我创建了一个nx.Graph()如下所示的对象：

        G = nx.Graph()
        for i in range(len(path)):
            G.add_node(i, pos=(path[i].x, path[i].y))
            
        for i in range(len(path)-1):
            G.add_edge(i, i+1)
        G.add_edge(len(path)-1, 0)

收敛非最优解的一个例子：

打印出点nx.get_node_attributes(G,'pos')：

{0: (494, 680), 1: (431, 679), 2: (217, 565), 3: (197, 581), 4: (162, 586), 5: (90, 522), 6:(138, 508), 7: (217, 454), 8: (256, 275), 9: (118, 57), 10: (362, 139), 11: (673, 89), 12: (738, 153), 13: (884, …