时间戳

首页 > 解决方案 > 最大多样性：用 C（或伪代码）翻译启发式算法

algorithm - 最大多样性：用 C（或伪代码）翻译启发式算法

问题描述

我有一组 N 个项目，我知道它们的相互距离。每个元素都有成本，我有预算。我应该完成以下任务：假设我在篮子里放了一个项目，篮子中的以下项目将是与第一个项目的距离最大的项目（在预算约束下）第三个项目将是距离总和的项目从项目 1 和项目 2 是最大值（在预算限制下），第四项目将是项目 1,2 和 3 的距离总和是最大值（总是预算）等。我如何找到总距离的子集（如上计算）是最大值？你知道解决这个问题的算法吗？提前致谢

更新：我做了一些研究，这个问题被称为最大多样性问题。我无法用 C 或伪代码翻译上述启发式算法（可以解决问题）！

标签： algorithmoptimizationcombinatorics

解决方案

这是个有趣的问题。如果我理解正确，您正在尝试在给定预算的情况下找到一条距离最大的路径。

让我们把这里的项目想象成一个连通图，这样我们就可以使用图论中的工具。边是成本，顶点或节点是实际项目。本质上，您似乎想在预算限制下找到一条最大路径，因此需要使用反向 dijkstra 算法。

脚步：

  1. 选择起始顶点

  2. 评估距起点的距离。

  3. 如果这超出您的预算，则选择具有最大距离的顶点转到下一个燃烧超出预算的边缘的顶点

  4. 将新添加的项目与其他项目之间的距离计算为到达该项目的路径之和 + 选择另一个项目的成本（即第一次迭代说我们得到项目 1 然后转到项目 2 然后项目 2 和项目 x 将是项目 1 + 项目 2 + 项目 x)

  5. 如果超出预算，则再次选择最大值，以达到下一个最大值，将边缘燃烧到超出预算的最大值。

  6. 重复直到预算用完

希望这有助于随时要求澄清，如果这是有道理的。我建议阅读一些图论和相关算法的背景知识

推荐阅读