我在“Hitchhiker's guide to algorithm”中读到了这个声明。但是，我无法将其可视化，因为在 LIS 问题中我们所拥有的只是一个数字序列。如何将其调制为图形问题？
问问题
1949 次
2 回答
7
想象一下二维网格的问题。你在左下角，你需要到达右上角。你能想象这个方案中的无环 DAG 吗？
现在想象一些正方形是被禁止的。禁止方格可能会导致“锁定”（您可能会发现自己被困），现在选择要遵循的路径实际上很重要。在图方面，您可以将禁止正方形视为删除顶点，您的目标是从根到一个特定的节点（汇）。
现在让我们回到LIS。在求解 LIS 时，您真正需要做的是决定您将选择哪些数字，以及您不会选择哪些数字。限制是，每当您选择一个数字时，您不能选择任何小于该数字的数字（您按顺序选择数字）。
现在我们可以混合这两种东西。想象一下，您将根据您的数字序列构建一个图形：
- 每个数字都是一个节点。
- 编号节点 A 与编号节点 B 有一条边当且仅当
- B 在序列中位于 A 之后
- B 的值大于 A
- 有一个特殊的节点端
- 每个节点都有一条边到结束
该图上的每条路径都是有效的递增子序列。查找 LIS 的问题现在是查找此图上最长路径的问题。
于 2012-10-16T03:46:59.637 回答
3
如果我们有一个数字数组，例如 1、5、4、8。我们可以像下面这样构造一个 DAG。
- 将每个数字添加为顶点。
- 对于每个数字顶点，将权重为 1 的出边添加到其后面的所有较大数字中。
- 将具有权重为 0 的出边的节点 S 添加到所有数字顶点。
- 添加一个节点 E，该节点 E 具有来自所有数字顶点的权重为 0 的传入边。
因此，最长递增子序列问题变成了从 S 到 E 的最长路径问题。
于 2013-07-16T15:43:08.917 回答