时间戳

首页 > 解决方案 > 给定一个比较列表，用尽可能少的额外比较对项目进行排序

algorithm - 给定一个比较列表，用尽可能少的额外比较对项目进行排序

问题描述

你有n物品x[0], ..., x[n-1]。事先，您会得到一个c[0], ..., c[k]包含这些项目的几个比较的列表（例如c[0] = (x[0] < x[4])、c[1] = (x[3] > x[7])等）。

目标是通过请求尽可能少的额外比较来对项目进行排序。

例如，如果c包含所有成对比较，则您无需请求任何其他比较即可对列表进行排序。如果c不包含任何内容，那么您O(n*log(n))可能会要求进行额外的比较以对项目进行快速排序。但如果c介于两者之间，我们如何巧妙地利用这些现有的比较来指导我们要求的额外比较？

计算时间无关紧要（只要它是次指数的）。最重要的是算法要求的额外比较最少。

含糊地说，我有一个想法，即从 中的比较构造一个 DAG c，然后对 DAG 进行拓扑排序以获得部分排序，但我不确定从那里去哪里。

标签： algorithmsortingtime-complexitygraph-theorydirected-acyclic-graphs

解决方案

答案是Karzanov 和 Khachiyan (1991)（随机），以及Kahn 和 Kim (1995)（改进和确定性）。

两者都是最优顺序O(log(E(P)))，其中E(P)是满足您的比较列表的项目的排列总数c。

我将在这里快速介绍随机算法。以下是您选择下一个要进行比较的方法：

  1. 通过 RandWalk 算法生成n满足比较的项目的样本排列
  2. r_i根据样本的平均指数为每个项目分配一个平均排名
  3. 选择比较平均排名差小于 1 的两个项目。

RandWalk算法如下

  1. 进行拓扑排序以获得x_1, ..., x_n满足比较的项目的排序c。
  2. 要获得下一个样本，请重复n几次：
  3. i从 1 到 统一选择一个索引n-1。如果x_i < x_(i+1)您的比较没有暗示c（它们之间没有直接路径），则交换x_i和x_(i+1).
  4. 您剩下的排序将是 1 个样本排序，它从满足 的所有可能排序中大致均匀地选择c。

推荐阅读