-1

我正在尝试通过一系列所需的总成本或总边长来计算哈密顿路径，即访问图中每个节点一次的路径。旅行推销员问题有多种算法可以计算最短路径，但我还没有找到一个按所需总成本计算的解决方案。

结果，我采用了适用于少数节点的蛮力解决方案，但无法计算出我拥有的 50 个节点。

import itertools
import numpy as np
from numpy import std

dist_matrix = np.array([[0.0,484.5434935135364,632.0078925008858,735.0398352819755,493.16148400859885],[484.5434935135364,0.0,425.69916384832044,525.3371082385308,322.51794796977657],[632.0078925008858,425.69916384832044,0.0,109.91947970385735,143.67555771554203],[735.0398352819755,525.3371082385308,109.91947970385735,0.0,252.8369873480788],[493.16148400859885,322.51794796977657,143.67555771554203,252.8369873480788,0.0]])

size=len(dist_matrix)
tours = []

for tour in itertools.permutations(list(range(0,size))):
    distances = [dist_matrix[i][j] for i, j in list(zip(tour, tour[1:]))]
    length = sum(distances)
    tours.append([tour, distances, length, std(distances)])

请注意，我还返回了标准偏差，因此我可以按所需的游览长度和最低标准偏差进行过滤（以在节点之间获得大致相等的距离），例如：

best_tours = [i for i in tours if int(i[2]) in range(1800, 2100) and i[3] < 120]

用例是一个城市游戏，我想为参与者提供一些等距的个性化路线，以避免他们混合（Covid-restrictions）。路线的总长度取决于游戏的持续时间，因此需要按总成本进行过滤。

是否有任何算法或解决方案允许这种类型的计算，或者是否有可能提高我的代码的效率，使其在合理的时间内为 50 个节点工作？

4

2 回答 2

0

I don't know such an algorithm as you described. Thus you didn't append your brute force solution - many times you can use several methods to significantly reduce the computation time. using methods from the branch "Dynamic Programing" and in particular "memoization" for recursive algorithms.

Added a link for a great video that demonstrates the concept

于 2021-05-05T12:15:03.557 回答
0

您可能想看看： https ://github.com/potassco/guide/releases/tag/v2.2.0 章节：6.2。它是 TSP 问题的逻辑描述，可以直接由 ASP 求解器（如clingo.

使用这些工具 ( https://potassco.org/ )，您可以轻松地将目标函数修改为您需要的任何内容，并且它们非常擅长解决 NP 完全问题。

于 2021-05-26T06:45:21.130 回答