2

几天来，我一直在尝试解决一个名为 Sling Blade Runner 的存档ITA 软件难题。谜题的要点如下：

“你能找到多长的重叠电影片名，比如 Sling Blade Runner？”

使用以下电影标题列表：MOVIES.TXT。多字重叠，如“杀死一只知更鸟的许可证”，是允许的。同一个标题不能在一个解决方案中多次使用。可能并不总是产生最多标题的启发式解决方案将被接受：寻求效率和最优性的合理权衡。

MOVIES.TXT文件包含按字母顺序排列的 6561 个电影标题。

我对解决方案的尝试有几个部分。

图表构建：

我所做的是将每个电影标题映射到它可以链接到的每个其他电影标题（在右边）。我最终得到的图表是Map[String, List[String]]. 您可以在此处查看使用此过程构建的图表。

图遍历：

我使用每个节点（地图中的每个键）作为搜索的起始节点进行了深度优先搜索。我跟踪了搜索过程中访问每个节点的深度，并在 DFS 返回的节点中进行了标记。我最终得到的是列表中的List[List[Node]]每一个List[Node]都是来自特定搜索的 DFS 树。

寻找最长的链：

我在上一步中获取了所有图遍历的结果，并且对于每一个List[Node]我都按照我之前标记节点的深度值按降序对列表进行排序。然后从列表的头部开始（这给了我在 DFS 中访问的最深节点），我通过节点回溯以构建一个链。这给了我一个列表中的List[List[String]]每一个List[String]都是该特定 DFS 的最长链的位置。List[List[String]]按每个的大小排序List[String]并抓住头部，然后给了我最大的链条。

结果：

用我的算法找到的最长链是 217 个标题。输出可以在这里查看。

我只能通过谷歌搜索找到其他一些尝试，而且似乎所有其他尝试都产生了比我能够完成的更长的链。例如，这篇文章指出，Eric Burke 发现了一个包含 245 个标题的链条，而Reddit 上名为 icefox 的用户发现了一个包含 312 个标题的链条。

鉴于其他人找到了更长的链，我想不出我的算法在哪里找不到最长的链。非常感谢任何帮助/指导。如果你想查看我的代码，可以在这里找到（它是用 Scala 编写的，我刚开始学习 Scala，如果我犯了一些菜鸟错误，请原谅我）。

更新：

我对我的算法进行了一些更改，现在可以找到长度为 240+ 的链。看这里

4

1 回答 1

1

问题是，由于电影图（我假设）有循环，无论您如何为循环的顶点分配深度，都存在一个深度不单调的子路径，因此您的算法不会考虑. Sling Blade Runner 是 NP 难的，因为我们不想要，所以没有已知的多项式时间策略会在每个输入上产生最优解。

（Sling Blade Runner 并不是 NP-hard 最长路径问题，它指定了没有重复顶点而不是没有重复弧的路径，但是从后者到前者有一个简单的多项式时间减少。将每个顶点拆分v为v_in -> v_out,将弧头移动到入顶点，将弧尾移动到出顶点。从源顶点到另一个源顶点到每个入顶点，以及从每个出顶点到汇顶点到另一个汇顶点的附加弧。

为了在图上找到最长的路径a->b, b->c, c->a, c->d，Sling Blade Runner 的输入将是

s1->s2,
s2->a_in, s2->b_in, s2->c_in, s2->d_in,
a_in->a_out, b_in->b_out, c_in->c_out, d_in->d_out,
a_out->b_in, b_out->c_in, c_out->a_in, c_out->d_in,
a_out->t1, b_out->t1, c_out->t1, d_out->t1,
t1->t2.

最长路径问题禁止重复顶点，因此最优解是a->b->c->d而不是c->a->b->c->d。Sling Blade Runner 中对应的链条是s1->s2->a_in->a_out->b_in->b_out->c_in->c_out->d_in->d_out->t1->t2. 具有重复顶点的路径的相应变换将重复弧c_in->c_out，因此对于 Sling Blade Runner 是不可行的。）

假设电影标题是

S A
S B
A B
A E
B C
C D
D A
E F

, 使图形看起来像

    F
    ^
    |
    E
    ^
    |
S-->A-->B<--
|   ^   |   \
|   |   v   |
|   D<--C   |
\___________/

我们从 DFS 开始S并得到以下树（因为我说过；这不是唯一可能的 DFS 树）。

S-->A-->B-->C-->D
     \
      ->E-->F

. 深度是

S 0
A 1
B 2
C 3
D 4
E 2
F 3

，所以最长的深度单调路径是S A B C D。最长的路径是S B C D A E F。如果您在其他地方启动 DFS，那么您甚至不会分配S深度。

一个更简单的例子是

A B
B C
C D
D A

，无论你从哪里开始，一直围绕循环的最佳路径都不是深度单调：A B C D A或B C D A B或C D A B C或D A B C D。

于 2014-10-06T18:40:49.907 回答