4

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

我有一个有序的阶段列表。每个阶段都有一组角色，无序。人物可以出现在多个阶段。

当两个连续的阶段不能将它们的演员串连起来时，就会发生交叉，允许重叠，因为它会在两个演员表上统一相同的字符，从而在串连中留下重复的字符。或者，非正式地，交叉是当一个角色需要在组合演员阵容中同时出现在两个不同的位置时。在代码中：

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 一起，但这不是问题，因为排序允许（有重叠）无交叉连接。但是，在第三个示例中，排序强制交叉。

就我的目的而言，交叉可能发生在非连续的舞台上，就好像角色不在“舞台上”时实际上并没有偏离他们先前在演员阵容中的顺序一样。

我想对每个阶段的演员进行排序，以使交叉点尽可能少，并理解绝对有可能出现交叉点不可避免的情况。需要交叉的示例系列：

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

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

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

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

4

1 回答 1

0

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

有一个字符C集，称为它，并且有一个有限有序的场景序列，其中一个场景是由一些字符组成的集合。角色可能（并且通常确实）出现在多个场景中。S_1, ... S_n

我想以与您的表述方式略有不同的方式表述您想要的结果，因为我认为它可以更清楚地说明人们如何寻找解决方案（或者至少，它可以完全清楚如何暴力破解解决方案）：

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

安排A_n对应的是故事板中角色的从上到下的顺序，在场景期间n，在以下意义上：在故事板上画一条穿过场景的垂直线n。此线应按 指定的顺序命中角色的生命线A_n。

我们需要我们的安排的以下属性：给定场景S_n，安排A_n需要将包含的字符S_n放入一个连续的块中，在以下意义上：假设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]。这是因为您不希望有错误的角色“切入”故事板中的场景。

我们希望尽量减少“过境点”的数量。在这里，交叉很容易定义： 和 之间的交叉数A_i正好A_(i+1)等于从 permutation到 permutation所需的相邻字符的转置数。A_iA_(i+1)

我没有给你答案，但我认为鉴于上述设置，蛮力方法并不难编码，并且如果情节提要不是的话，它会在一夜之间毫无问题地给你答案大的。

我认为，如果您在 MathOverflow 上发布此问题，您可能会引起有人对此感兴趣。或者也许它已经解决了，谁知道呢？

于 2013-12-30T20:02:19.617 回答