标签: traveling-salesman

我有一个强连接的有向图(即,对于图G中的每对节点(i,j),存在从i到j和j到i的路径).我希望从该图中找到一个强连通图,使得所有边的总和最小.

换句话说,我需要摆脱边缘,以便在移除它们之后,图形仍将是强连接的,并且边缘总和的成本最低.

我认为这是NP难题.我正在为一小组数据(如20个节点)寻找最佳解决方案,而不是近似.

编辑

更一般的描述:给定grap G(V,E)找到图G'(V,E'),使得如果在G中存在从v1到v2的路径,则在G中存在v1和v2之间的路径'和E'中每个ei的总和是最不可能的.所以它类似于找到最小等效图,只是在这里我们想要最小化边权重的总和而不是边的总和.

编辑:

到目前为止我的方法:我想过使用多次访问的TSP来解决它,但这是不正确的.我的目标是覆盖每个城市,但使用最低成本路径.所以,它更像是封面设置问题,我猜,但我不完全确定.我需要使用总成本最低的路径来覆盖每个城市,因此多次访问已访问过的路径不会增加成本.

我正在尝试使用分支和绑定算法来解决TSP.

我必须建立一个有成本的矩阵,但我有这个问题:我有一个坐标为x和y的城市.

旅行费用是ceil(ceil(sqrt((x1-x2)^2+(y1-y2)^2))/v)在城市花费+天.V是速度.

在这个城市度过的日子取决于来到这个城市的日子.例如,如果我们星期一(t1)到达城市1,我们会停留9天,但如果我们星期二抵达,那么我们将在这个城市逗留4天.

         x   y   t1 .        t7
city 1. 79 -36   9 4 8 5 5 7 8
city 2. 8  67    6 9 2 1 9 9 1
city 3. 29 57    7 5 10 8 10 9 4

如何使用分支定界算法解决此问题？

我是整个旅行商问题以及stackoverflow的新手,所以如果我说一些不太正确的话,请告诉我.

介绍:

我正在尝试为涉及多个国家(地区)内的多个城市(节点)的游戏编写利润/时间优化的多重交易算法,其中:

• 在两个相连的城市之间旅行所需的物理时间总是相同的;
• 城市没有线性联系(你可以同时在一些城市之间传送);
• 一些国家(地区)拥有传送路线,通过其他国家提供最短路径.
• 旅行者(或交易者)对他的钱包,货物的重量以及在某个贸易路线中可交易的数量有限制.贸易路线可以跨越多个城市.

问题参数:

内存中已存在一个数据库(python:sqlite),它根据源城市和目的地城市进行交易,中间的最短路径城市作为数组和金额,以及限制因素及其总资本回报率(或在没有任何因素限制的情况下,那么只是给出总资本回报最高的方法).

• 我试图找到某个预设大块时间(即30分钟)的最佳利润
• 穿越新城市的行为实际上是同步的
• 在城市地图上旅行通常需要相同的时间(即2分钟)
• 启动第一个或任何新交易的行为与穿越一个城市地图(即2分钟)的时间相同
• 我的起点可能实际上没有有效的交易(我必须前往第一个/最近/最好的一个)

迄今为止的伪解决方案

优化

首先,我意识到因为我对时间有限制,并且我知道每一跳需要多长时间(包括-1用于启动交易),我可以将图形限制为跳数低于或等于的所有交易max_hops=int(max_time/route_time) -1.我删除了不属于这个时间限制的交易数据库的元素,修剪最短路径长度大于的城市max_hops.

我再次进入交易数据库,其中包括我当前城市与所有现有交易的起始城市之间的最短路径,而不是我当前的城市,并给予他们0%的回报.我会将这些限制在城市啤酒花的数量小于的地方max_hops,我还会计算当前城市到起始城市加上交易最短路径的啤酒花是否会超出max_hops并删除那些超出此限制的城市.

然后我采取其余的交易,(current_city->starting_city)并在所有目的地和起始城市之间添加0%的交易路线,因为啤酒花不会超过max_hops

然后,我为所有不在交易数据库中的城市做最后一次修剪,作为起始城市,目的地城市或最短路径城市阵列的一部分.

图搜索 我留下了一个(多)较小的交易图表,在时限内(即30分钟)可行.

因为所有连接的节点都是相邻的,所以连接默认都是加权1.我将%return除以交易中的跳数然后取倒数并加上+ 1(这意味着一个权重为1.01) 100%回程路线).在收益率为0%的情况下,我加上...... 2？

它应该返回最有利可图的路线......

问题:

大多,

1. 当我遗留金钱或空间并通过路径离散到单一贸易路线时,如何添加获取多条路线的能力？由于在城市内以多种价格和数量出售货物的性质,将会有很多重叠的路线.

2. 我如何惩罚启动新的贸易路线？

3. 图搜索在这种情况下是否有用？

在旁注,

3. 我应该(或者我不应该)对图表进行哪些修剪/优化？
4. 我的加权方法是否正确？我觉得它会给我不成​​比例的重量.我应该使用实际回报而不是百分比回报吗？
5. 如果我在python中编码的是python-graph这样的库适合我的需求？或者它会为我节省很多开销(据我所知,图搜索算法可能是计算密集型的)来编写一个专门的函数？
6. 我最好使用A*搜索吗？
7. 我应该预先计算交易数据库中的最短路径点并进行最大化优化,还是应该将其全部留给图搜索？
8. 你能注意到我可以提高的一切吗？

可能重复:
使用A*解决旅行商问题

我最近了解到A*算法可以应用于旅行商问题.我们如何确定这里的起点和目标,以及如何将权重应用于节点(什么是启发式)？

有人会向我解释如何在这里应用A*吗？

基于这个伪代码,我试图为旅行商问题实现一个java fittness函数,但我不确定我是否做得对,有人可以帮助我.

N   The number of cities to visit
T   A tour (list of integers of size N)
D   An N by N matrix containing each d(i,j)

Let s = 0
For i = 1 to (N-1)
Let a = ti
Let b = ti+1
Let s = s + d(a,b)
 End For
     Let end_city = tn
     Let start_city = t1
     Let s = s + d(end_city,start_city)
The tour length s

我尝试用java编写这个

public static ArrayList<Integer> Fitness(){
    int n = 10; …

我实施了一种遗传算法来解决增强的旅行商问题(边缘的权重随着时间的推移而变化).目前我正在评估我的模拟的不同参数,我偶然发现了一个我无法向自己解释的相关性:

突变率越高,运行时间越短.就个人而言,我会假设相反,因为更高的突变率会产生更多的操作.(25%的突变率比5%快12%)

突变率为8%(5%优于10%,25%表现最差(0%除外)),效果最佳.适应值越低越好.

迭代计数由生成参数设置,在所有测试用例中设置为10.000.

每个测试用例执行10次.

我在变异中的实现(在python中)看起来像这样:

def mutate(self,p):
    for i in self.inhabitants:
        r = random()
        if r <= p:
            i.mutate()

p 是突变率

突变看起来像这样

def mutate(self):
    r1 = randint(0,self.locations.size()-1)
    r2 = randint(0,self.locations.size()-1)
    self.locations.swap(r1,r2)

为什么更高的突变率会导致更快的执行时间？

编辑:我实际上在我的Raspberry Pi上运行了相同的测试(速度慢了9倍),结果相同:

问题:我需要删除(N)从办公室员工家园(坐标可用).我有(x) 7座和(y) 4座驾驶室.

1. 我必须设计一种算法,让所有员工在最短距离内离开家.

2. 此外,该算法必须告诉我必须选择多少7座或/和4座车辆以便行驶最小距离.

例如.如果我有15名员工,那么算法可能会告诉我使用1(7座)驾驶室和2(4座)驾驶室并让每个驾驶室的员工如下:

[(E2,E4,E6,E8),(E1,E3,E5,E7,E9,E10,E12),(E11,E13,E14,E15)]

方法:我认为这是一个旅行推销员问题,有多个推销员,每个人都可以旅行的城市数量上限.销售人员也不需要回到原点.我想到了Ant的殖民地问题,但我无法明智地选择哪种算法可供选择

要求:我真的需要ALGORITHM.无论是TSP还是Ant的殖民地,都无关紧要.我会欢迎意见,但我真的需要算法.

问题

我正在寻找一种方法来有效地对固定对象周围发生的随机选择的采样横断面进行排序。这些横断面一旦生成，就需要以一种在空间上有意义的方式进行排序，以使行进的距离最小化。这将通过确保当前横断面的终点尽可能靠近下一个横断面的起点来实现。此外，没有一个横断面可以重复。

因为有数千条断面需要订购，这是手动完成的一项非常繁琐的任务，我正在尝试使用 R 来自动化此过程。我已经生成了横断面，每个横断面都有一个起点和终点，其位置使用 360 度系统表示（例如，0 是北，90 是东，180 是南，270 是西）。我还生成了一些似乎指示下一个横断面的起点和 ID 的代码，但此代码存在一些问题：(1) 根据所考虑的起点和终点，它可能会产生错误，(2 ) 它没有实现我最终需要它实现的目标，并且 (3) 照原样，代码本身似乎过于复杂，我不禁想知道是否有更直接的方法来做到这一点。

理想情况下，代码将导致横断面被重新排序，以便它们匹配它们应该飞行的顺序，而不是它们最初输入的顺序。

数据

为简单起见，我们假设只有 10 个横断面需要排序。

# Transect ID for the start point
StID <- c(seq(1, 10, 1))

# Location of transect start point, based on a 360-degree circle
StPt <- c(342.1, 189.3, 116.5, 67.9, 72, 208.4, 173.2, 97.8, 168.7, 138.2)

# Transect ID for the end point
EndID <- c(seq(1, 10, 1))

# Location of transect start point, based on a 360-degree …

我用Python制作了一个用于旅行商问题的模因算法.但是,我遇到的所有测试数据(城市之间的距离列表)缺乏最佳解决方案的信息,所以我不知道我的算法得到的全局最优值有多接近.

有没有人知道在哪里可以找到一些已知的最佳解决方案的tsp测试数据(最好是矩阵形式,但一切都很好)？

我们正在开发一个应用程序,我们将在谷歌地图中显示一些可供出售的房屋.用户可以从地图中选择任何房屋,并可以找到他/她选择的所有房屋之间的最短驾车路线.

任何人都可以告诉我如何找到最短路线并在地图上显示？有没有基于PHP的TSP库,可以帮助我们实现我们正在尝试的目标？