0

假设我有 URL 列表，并且已经进行了一些排序；现在让我们添加一些约束 - 假设连续有两个以上具有相同域的链接是不好的。

实际上我可以有一些限制——两个、三个、五个，不太可能更多。

现在我想重新使用我的原始列表，同时在初始排序和我的约束之间保持一些平衡。这条平衡线应该以某种方式配置。

现在我所想的只是非常简单（而且我相信容易出错）的蛮力方法 - 只需遍历列表，计算我关心的每个统计数据，决定通过一些启发式向上或向下移动链接，重新计算统计数据并进一步移动...

4

2 回答 2

1

我延迟解决这个问题；但我想出了一种可能的解决方案，我会尝试描述它。

它适用于“连续不超过 N 个具有相同属性的元素”的问题 - 在我的原始案例中具有相同域的链接。

所以：

  1. 识别列表中的“坏”位置 - 并将它们作为索引间隔记住。
  2. 对于每个间隔：
    • 在两侧扩展该间隔 - 注意不要超过数组的范围（可能还有另一个间隔的范围）
    • 扩展大小应取决于间隔大小
    • 洗牌该间隔，除非它看起来相对于我们的条件没问题

通过这种方式，我们只在有限的时间间隔内扰乱排序，一般排序不应该有太大变化。

当我们列表的一半以上是单个“坏”间隔时，我们可能应该有特殊情况——例如，只需均匀分布它。

于 2012-12-27T12:48:29.123 回答
0

有一篇 IEEE 论文，介绍了一种使用约束进行排序的通用算法……

如果你喜欢阅读它，那么这里是链接：http://ieeexplore.ieee.org/xpl/articleDetails.jsp;jsessionid=nBBXQnGZGd9bRJhQfjzWQGhLm97BQ7xLG9LChppLPBvfJ0Sb2hRh!1364212599?arnumber=5358031&contentType=Conference+ Publications

于 2012-12-24T11:08:06.393 回答