草庐IT

python - 有方向约束的旅行推销员

coder 2023-05-24 原文

我正在尝试按路径上的顺序排列一组 3D 坐标。一个样本:

points = np.array([[ 0.81127451,  0.22794118,  0.52009804],
                   [ 0.62986425,  0.4546003 ,  0.12971342],
                   [ 0.50666667,  0.41137255,  0.65215686],
                   [ 0.79526144,  0.58186275,  0.04738562],
                   [ 0.55163399,  0.49803922,  0.24117647],
                   [ 0.47385621,  0.64084967,  0.10653595]])

这些点的顺序是随机的，但始终只有一条路径通过它们。我正在使用 LKH solver 找到适合旅行商问题 (TSP) 解决方案的路径(赫尔斯冈 2009)。它涉及两个修改:

  • 在原点或原点附近添加一个点。这在我迄今为止处理的每个实例中都找到了最佳起点。这是我的想法，我没有其他依据。
  • 在距每个点零距离处添加一个点。这使求解器找到通往路径另一端的路径。这个想法来自 this SO question .

注意，TSP 不涉及位置，只涉及节点之间的距离。所以求解器确实“知道”(或关心)我正在使用 3D。我只是像这样制作一个距离矩阵:

import numpy as np
from scipy.spatial.distance import pdist, squareform

# Add a point near the origin.
points = np.vstack([[[0.25, 0, 0.5]], points])
dists = squareform(pdist(points, 'euclidean'))

# Normalize to int16s because the solver likes it.
d = 32767 * dists / np.sqrt(3)
d = d.astype(np.int16)

# Add a point that is zero units from every other point.
row, col = d.shape
d = np.insert(d, row, 0, axis=0)
d = np.insert(d, col, 0, axis=1)

我把这个传给 my fork of pytsp ，将其传递给 LKH 求解器。一切都很好......除了路径交叉时。 TSP 解决方案不能有闭环，所以我总是得到右侧显示的开环:

请注意，这是我的情况的类似 2D 版本。另请注意，这些点未完全对齐，即使沿着“直”位也是如此。

所以我的问题是:我怎样才能帮助求解器尽可能保持路径的方向？我有两个不正确的想法，但到目前为止无法实现任何东西:

  • 使用其他指标而不是 L2。但我认为这行不通，因为在给定的路口，“错误”点没有本质上的不同。它的错误取决于前一点。而且我们还不知道哪一点是前一点(这就是我们想要弄清楚的)。所以我认为这不好。
  • 评估每组三个点的局部共线性(例如，使用每个三元组的行列式)。通过这个共线性系数调制局部“3D 斜率”(不确定我的意思)。给每个点另一个维度来表达这种局部对齐。现在，规范将反射(reflect)局部对齐，并且(希望)大致共线的事物将连接起来。

我已将这些文件放在 Dropbox 上:

感谢您的阅读；任何想法表示赞赏。

引用

K。 Helsgaun，Lin-Kernighan TSP 启发式的通用 k-opt 子 Action 。数学规划计算，2009，doi: 10.1007/s12532-009-0004-6 .

最佳答案

从 pytsp 上的文档来看，距离矩阵不一定是对称的。这意味着您可以修改 L2 范数以将有关首选方向的信息合并到该矩阵中。假设您有一些点对 (i,j) 的首选方向，那么对于这些​​点中的每一个，您可以将 dists[i,j] 除以 (1+a) 并将 dists[j,i] 乘以 (1+a) 以使该方向更有利。这意味着，如果您的算法确定找到全局最优值，您可以通过使 a 足够大来强制它满足您的首选方向。

另外，我不确定在距离矩阵取自 3D 数据的解决方案中不可能有闭环。在我看来，“无闭环”是 2D 特有的(三角不等式)结果。

关于python - 有方向约束的旅行推销员，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39195429/

有方pythoncodenoreferrernoopenernumpylinear-algebragraph-algorithmtraveling-salesman

有关python - 有方向约束的旅行推销员的更多相关文章

  1. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  2. ruby - 如何在 Ruby 中向现有方法定义添加语句 - 2

    我注意到类定义，如果我打开classMyClass，并在不覆盖的情况下添加一些东西我仍然得到了之前定义的原始方法。添加的新语句扩充了现有语句。但是对于方法定义，我仍然想要与类定义相同的行为，但是当我打开defmy_method时似乎,def中的现有语句和end被覆盖了，我需要重写一遍。那么有什么方法可以使方法定义的行为与定义相同，类似于super，但不一定是子类？ 最佳答案 我想您正在寻找alias_method:classAalias_method:old_func,:funcdeffuncold_func#similartoca

  3. Python 相当于 Perl/Ruby ||= - 2

    这个问题在这里已经有了答案:关闭10年前。PossibleDuplicate:Pythonconditionalassignmentoperator对于这样一个简单的问题表示歉意，但是谷歌搜索||=并不是很有帮助；)Python中是否有与Ruby和Perl中的||=语句等效的语句？例如:foo="hey"foo||="what"#assignfooifit'sundefined#fooisstill"hey"bar||="yeah"#baris"yeah"另外，类似这样的东西的通用术语是什么？条件分配是我的第一个猜测，但Wikipediapage跟我想的不太一样。

  4. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

  5. 华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2

    华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o

  6. python - 如何读取 MIDI 文件、更改其乐器并将其写回？ - 2

    我想解析一个已经存在的.mid文件，改变它的乐器，例如从“acousticgrandpiano”到“violin”，然后将它保存回去或作为另一个.mid文件。根据我在文档中看到的内容，该乐器通过program_change或patch_change指令进行了更改，但我找不到任何在已经存在的MIDI文件中执行此操作的库.他们似乎都只支持从头开始创建的MIDI文件。 最佳答案 MIDIpackage会为您完成此操作，但具体方法取决于midi文件的原始内容。一个MIDI文件由一个或多个音轨组成，每个音轨是十六个channel中任何一个上的

  7. 「Python｜Selenium｜场景案例」如何定位iframe中的元素？ - 2

    本文主要介绍在使用Selenium进行自动化测试或者任务时，对于使用了iframe的页面，如何定位iframe中的元素文章目录场景描述解决方案具体代码场景描述当我们在使用Selenium进行自动化测试的时候，可能会遇到一些界面或者窗体是使用HTML的iframe标签进行承载的。对于iframe中的标签，如果直接查找是无法找到的，会抛出没有找到元素的异常。比如近在咫尺的例子就是，CSDN的登录窗体就是使用的iframe，大家可以尝试通过F12开发者模式查看到的tag_name,class_name,id或者xpath来定位中的页面元素，会抛出NoSuchElementException异常。解决

  8. python ffmpeg 使用 pyav 转换 一组图像 到 视频 - 2

    2022/8/4更新支持加入水印水印必须包含透明图像，并且水印图像大小要等于原图像的大小pythonconvert_image_to_video.py-f30-mwatermark.pngim_dirout.mkv2022/6/21更新让命令行参数更加易用新的命令行使用方法pythonconvert_image_to_video.py-f30im_dirout.mkvFFMPEG命令行转换一组JPG图像到视频时，是将这组图像视为MJPG流。我需要转换一组PNG图像到视频，FFMPEG就不认了。pyav内置了ffmpeg库，不需要系统带有ffmpeg工具因此我使用ffmpeg的python包装p

  9. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  10. python - 是否可以使用 Ruby 或 Python 禁用 anchor /引用来发出有效的 YAML？ - 2

    是否可以在PyYAML或Ruby的Psych引擎中禁用创建anchor和引用(并有效地显式列出冗余数据)？也许我在网上搜索时遗漏了一些东西，但在Psych中似乎没有太多可用的选项，而且我也无法确定PyYAML是否允许这样做.基本原理是我必须序列化一些数据并将其以可读的形式传递给一个不是真正的技术同事进行手动验证。有些数据是多余的，但我需要以最明确的方式列出它们以提高可读性(anchor和引用是提高效率的好概念，但不是人类可读性)。Ruby和Python是我选择的工具，但如果有其他一些相当简单的方法来“展开”YAML文档，它可能就可以了。 最佳答案

随机推荐