0

我想在给定的无向加权图中找到 K 最远的邻居（该图以稀疏权重矩阵的形式给出，但我可以使用建议的表示形式）。只是为了确保问题得到明确定义：我想找到彼此之间距离最大的 k 个节点。接近最优集合的解决方案也可以 - 我只需要它来找到网格中的一些最远点:)

4

1 回答 1

1

假设您只是在寻找一个体面的解决方案，我会推荐一个简单的解决方案，类似于旅行商问题的“最远插入”起始位置：

  • 给空集加 1 点，最好在角落或边缘加 1 点（当然你可以全部尝试）
  • 将最远的点添加到集合中（增加与集合中当前点的最大距离）
  • 不断重复上一步，直到集合中有k个点

它不会是最佳的，但可能不是很糟糕。

如果您想对此进行改进，您可以使用启发式方法来改进结果，例如：

  • 考虑点 1 到 j 的集合，j
  • 尝试所有可能的点来代替这 j 个点
  • 记录最好的解决方案
  • 考虑省略了点 2 到 j+1 的集合

等等

此外，如果 k 不是太大，比如小于 5，并且总点数不是太大，比如小于 100，那么计算所有可能的组合可能会更容易。这是假设可以有效地完成范数计算。

编辑：

一旦您知道要实现此功能，常规的继续方法就是找到类似的内容并对其进行一些编辑以满足您的需要。如果您在此页面上向下滚动，您应该会找到最远插入的示例。编辑它以遵循您对“远”的测量应该是可以管理的。

http://snipplr.com/view/4064/shortest-path-heuristics-nearest-neighborhood-2-opt-farthest-and-arbitrary-insertion-for-travelling-salesman-problem/

于 2012-11-11T10:32:29.003 回答