use*_*695 5 arrays sorting algorithm set
我正在寻找一种算法来执行某种扩展数组排序,当元素之间的关系可以相互矛盾时.
所以我们有一组I(项目)由n个项目组成i1 ... in
有一组R(关系)由在I中的项之间定义的m个关系组成
这种关系可以相互矛盾,例如,一种关系可以说是A>B另一种关系A<B.
例如
r1:i1<i35
r2:i100<i4
...
rm:i45>i3
通常,r和m (集合的大小)可以是任何正整数.
任务是对I进行排序,以便项目以这样的方式进行:优选地,较低的(基于关系)在较高的之前...
我正在寻找一种算法,它会对集合进行排序,使其尽可能接近"最佳"顺序.我想必须有一个众所周知的算法来解决这样的问题.
谢谢!
我认为衡量特定排序质量的最明智的方法是它违反的给定关系的数量.如果您决定使用此度量,则问题等同于(最小)反馈弧集.不幸的是,这个问题是NP难的,因此不存在有效的(多项式时间)算法.
在反馈弧集问题中,您将获得一个有向图,并要求查找最小尺寸的边集,如果删除这些边将破坏图中的所有周期.
要了解这与您的问题如何对应,请注意我们可以将每个项目表示为图形中的顶点,并将每个关系表示为两个顶点之间的有向边(指向较小的顶点).当且仅当此图中存在循环时才会发生冲突- 即,如果存在2个或更多不同顶点v_1,v_2,...,v_k的有序列表,则v_i <v_(i + 1) )对于所有i <k,以及v_k <v_1.在不违反至少一个约束的情况下,不可能对这些k个顶点进行排序.相反,如果不存在循环 - 也就是说,如果图形是有向非循环图形 - 那么拓扑排序可以快速(在线性时间内)找到不违反任何约束的有效顺序.因此,一个反馈弧集的大小,你需要,以消除获得在不违反任何约束,责令图形边缘的最小数量的-或者相当于边缘的最小数必须在违反任何排序.