我正在研究近场扫描仪，需要找到一种方法来获得扫描仪头的最短路径。
假设我想一次使用 13 个点。
当然，这并不是最短的路径。
扫描仪必须能够同时处理 25 个或更多点，因此不能选择排列。行进1cm需要0.45s，表面多为10x15cm。
主要目标是赢得时间并使扫描速度更快。
这必须在 C# 或 Matlab 中完成。
这可能吗？
除了暴力破解所有可能的组合之外，没有数学“解决方案”。
http://en.wikipedia.org/wiki/Travelling_salesman_problem
您可以尝试不同的算法来找到“好的”解决方案（遗传算法等），但您永远无法判断是否找到了最佳解决方案。
在 SO 上，请参阅什么是计算机科学中的 NP 完全？例如
有时编辑 您可以确定您是否拥有最佳解决方案（尝试全部后除外）。但这些都是一些罕见的特殊情况。如果路径的“长度”等于每个点的最短距离之和，那么您已经找到了最优路径。就像你所有的点都在一条线上，你走 1-2-3-n。但通常你只能找到不是最好的解决方案，而不知道是否会有更好的解决方案。
EDIT2
作为一个想法：如果主要目标不是“浪费”任何时间，我会这样做：选择第一点，您希望扫描仪移动到。开始移动扫描仪。在扫描仪移动（不同线程）时，使用 NN 算法计算路径。现在在路径上运行蒙特卡洛算法以找到更好的东西。当扫描仪到达第一个点时，停止 MC 算法（扫描仪需要发出 MoveCompletetion 信号！）并将路径中的第一个点作为新的扫描仪目标。重复前面的步骤，直到到达最后一点。
这样，您只需要计算扫描仪移动所需的时间。而且由于您始终使用 NN 路径作为基础，因此您永远不会变得更糟，但有时（通常？）会更好。该算法可以很容易地并行完成，因此在多核机器上得到更好的结果。