长子路径搜索和小子路径最小化的Matlab路径优化算法

Question

我正在开发一个代码来查找复杂图中的最佳子路径。我的图只是物理结构的表示，所以我的边是实际的线段。当我说“最佳”时，我想获得可能的最长子路径，这也可以最大限度地减少生成的“短”子路径（仅一条边）。我现在正在做的是一种迭代的方法。 给定子路径的最大长度:,

• 每次迭代都从 n 个可用节点之一开始
• 生成 n 条子路径并选择最佳的一条。每个子路径都是根据可用邻居生成的（未完成的节点和未访问的边）
• 我有一个功能可以从下一个子路径生成搜索中删除选定的子路径（以及没有可用邻居的节点）

我想实现像布谷鸟巢或蝙蝠算法这样的元启发式算法，但我这里的条件略有不同。就我而言，节点必须被访问多次，因为我需要将所有节点包含在最终计数中。这意味着节点在完成后将被排除在搜索之外，而不仅仅是被访问。 我的代码工作正常，问题是我仍然有大量的短子路径（仍然占边总数的 30%，这是很多），所以也许我错过了另一个视角或另一种我没有的方法想过！

Answer 1

我最好的猜测是，您希望在具有一个组件的图中找到一组路径（路径定义：具有 2 个或更多成员的顶点列表，其中列表中的每个连续顶点对由一条边连接），其中覆盖每个边恰好一次。在所有这些可能的集合中，您想要选择具有最长路径和最少只有一条边的路径的集合。

为了选择“最佳”集合，您需要指定具有一些很长路径和许多长度为 2 的路径的集合与具有较短路径和较少长度为 2 的路径的集合之间的权衡。也就是说，一组中必须优化的路径长度。像这样的东西：

优化：

score = (sum over paths in set ) f( path length )

您需要指定f。

为了澄清，这里是 f 的可能规范：

ret = 0;
if( pathlength > 10 ) ret = ret + 1;
else if( pathlength = 2 ) ret = ret - 1;
return ret;

由于您的问题省略了指定集合之间的权衡的任何细节，所以不可能有详细的答案，除了说我会使用 Pim 的算法（https://en.wikipedia.org/wiki/Prim%27s_algorithm）来生成生成树并从那里开始优化。 （这是获得旅行推销员问题近似解决方案的标准启发式，与您的问题类似。）