algorithm - 寻找一种对节点中的集合进行排序以满足布局约束的算法

Question

首先，我为糟糕的标题道歉；我想不出这个算法的好名字。

我有一个有序的阶段列表。每个阶段都有一个 类型转换 角色，无序。字符可以出现在多个阶段。

交叉发生在两个连续的阶段不能将它们的类型转换连接起来时，允许重叠，它会在两个类型转换上统一相同的角色，从而在串联中留下重复的角色。或者，非正式地，交叉是指角色需要在组合 Actor 阵容中同时出现在两个不同的位置。在代码中:

uncrossed = [D, F], [N, V, S]
overlap = [D, F, V], [V, N, S]
crossed = [D, V, F], [N, V, S]

在第一个示例中，V 不与 D 和 F，因此没有任何交叉。在第二个示例中，V 与 D 和 F 一起使用，然后与 N 和 S 一起使用，但这不是问题，因为排序允许(重叠)无交叉连接。但是，在第三个示例中，排序强制交叉。

就我而言，交叉可以发生在非连续的舞台上，就好像当角色不在“舞台上”时，他们实际上并没有偏离他们之前在类型转换中的顺序。

我想对每个阶段的 Actor 进行排序，以便交叉点尽可能少，我明白绝对有可能出现交叉点不可避免的情况。需要交叉的示例系列:

required = [A, B], [B, C], [A, C], [A, B]

这一切听起来都非常抽象和愚蠢，所以我将提供一个人类为了与我类似的目的解决这个算法的具体例子:http://xkcd.com/657/在这种情况下，出于审美目的故意忽略约束，但仍然可以直观地了解我在说什么。

对于如何解决这个问题，我已经有了一些粗略的想法，但没有什么可以负担得起的，我想知道这是否与文献中已经涵盖的某些问题同构。这听起来也含糊不清。

自从有人问起，这个算法似乎是自动为故事中人物的 Storyboard生成漂亮的时间线的关键，这就是我打算用它的目的。

Answer 1

这不是一个答案，但我认为可能是您正在寻找的更精确或更正确的表述:

有一个集合，称之为 C，由 characters 组成，并且有一个有限有序序列 S_1, ... S_n 的场景，其中场景是由一些角色组成的集合。角色可能(并且通常会)出现在多个场景中。

我想用一种与您的措辞方式略有不同的方式来表述您想要的结果，因为我认为它可以更清楚地说明人们如何寻找解决方案(或者至少，它完全清楚了如何暴力破解-强制解决方案):

我们算法的输出是一系列字符排列。字符的排列只是有序元组[c_1, ... c_m]的排列，其中c_i是字符，总共有 m 个，所以 C = {c_1, ..., c_m}。我们总共需要 n 个排列，称它们为 A_1, ..., A_n，每个场景一个。

A_n 对应的排列是 Storyboard中角色从上到下的顺序，在场景 n 期间，在以下意义上:画一条垂直线通过你的 Storyboard通过场景 n。此行应按 A_n 指定的顺序命中角色的生命线。

我们需要安排的以下属性:给定场景 S_n，安排 A_n 需要将包含在 S_n 中的字符放入一个连续 block ，在以下意义上:假设 S_n = {c_2, c_3, c_5}。然后 A_n 可能产生 [c_1, c_4, c_2, c_3, c_5]，但可能不会产生 [c_2, c_1, c_3, c_4, c_5]。这是因为您不希望错误的角色“切断” Storyboard中的场景。

我们希望尽量减少“交叉点”的数量。在这里，交叉很容易定义:A_i 和 A_(i+1) 之间的交叉数恰好等于相邻字符的换位数 需要从排列 A_i 到排列 A_(i+1)。

---

我还没有给你答案，但我认为考虑到上述设置，蛮力方法不会太难编写代码，如果 Storyboard是太大了。

我认为如果您将这个问题发布到 MathOverflow 上，您可能会引起其他人的兴趣。或者也许它已经解决了，谁知道呢？