algorithm - 最小化数组中相关项之间的距离

Question

我有一组相关项，{ A, B, C, D }。

C 依赖于 A。 D 依赖于 B 和 C。

因此，我将此排列中项目之间的总距离计算为以下各项之间的距离总和: C和A(2)， D 和 B (2), D 和 C (1)。 所以，我们在这个排列中总共有 5 个。

但是，最佳解决方案是 {A, C, D, B}，总距离为 3。

我有一个(复杂得多的)大约 200 个项目的列表，我想尽可能地优化它，而且我不知道任何以这种方式排序的排序算法 - 谁能指出我现有算法的方向？

来自评论: 数据图如下所示-(对格式表示歉意!)

#Dependencies #Items
            0      9
            1     27
            2     57
            3     55
            4     11
            5      3
            6      1

Answer 1

我相信您正在寻找的是拓扑排序。

此算法用于有向图。这里字母构成图的节点，依赖关系构成单向边。 该算法是深度优先搜索的应用，用于排序作业。

This是一个非常简洁的解释。