我正在开发一个代码来查找复杂图中的最佳子路径。我的图只是物理结构的表示,所以我的边是实际的线段。当我说“最佳”时,我想获得可能的最长子路径,这也可以最大限度地减少生成的“短”子路径(仅一条边)。我现在正在做的是一种迭代的方法。 给定子路径的最大长度:,
我想实现像布谷鸟巢或蝙蝠算法这样的元启发式算法,但我这里的条件略有不同。就我而言,节点必须被访问多次,因为我需要将所有节点包含在最终计数中。这意味着节点在完成后将被排除在搜索之外,而不仅仅是被访问。 我的代码工作正常,问题是我仍然有大量的短子路径(仍然占边总数的 30%,这是很多),所以也许我错过了另一个视角或另一种我没有的方法想过!
我最好的猜测是,您希望在具有一个组件的图中找到一组路径(路径定义:具有 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)来生成生成树并从那里开始优化。 (这是获得旅行推销员问题近似解决方案的标准启发式,与您的问题类似。)