0

我有一个问题需要解决，但我想不出任何简单且更重要的方法：快速解决方案。这有点像多次旅行推销员问题的一部分。

首先，我有一个包含X行和N列的矩阵，N它是我算法的静态变量，并且X可以变化。让我们假设它看起来像（这里N = 5）：

matrix = [1 2 4 3 5; 4 3 1 2 5; 1 2 4 3 5; ]
matrix =
 1     2     4     3     5
 4     3     1     2     5
 1     2     4     3     5

每一行都被视为一条“路线”，包含 1 到 1 之间的所有唯一数字。N每条路线（= 行）将被分成部分路线。这意味着，我有一个包含X行和M( M < N) 列的断点矩阵。例如：

breakpoints = [2 3 4; 1 2 4; 1 3 4]
breakpoints =
 2     3     4
 1     2     4
 1     3     4

每行的索引breakpoints给出 AFTER 对应行的元素，matrix路线将被分成部分路线。为了清楚起见，让我们以第一行为例：breakpoints(1, :) = 2 3 4这意味着该路线matrix(1, :) = 1 2 4 3 5将被拆分为部分路线[1 2], [4], [3] and [5]。第二行有断点breakpoints(2, :) = 1 2 4，将第二条路线matrix(2, :) = 4 3 1 2 5分成部分路线[4], [3], [1 2] and [5]。

现在我的目标是从 中删除所有行matrix，而部分路由是冗余重复，只是顺序不同。在此示例中，第 2 行是第 1 行的副本。第 3 行即使与第 1 行具有相同的路由也不重复，因为存在不同的断点导致部分路由[1], [2 4], [3] and [5]。

我怎么能干净又快速地做到这一点？矩阵可以包含许多元素，例如X = 5e4行和N = 10, M = 6。

4

1 回答 1

1

对于常数 M，N，这可以通过将复合记录按顺序排序，然后测试相邻条目的相等性，在 O(X log X) 时间内解决。

“复合记录”是指将行的功能及其断点组合成单个记录的记录。对于给定的行，该函数通过以下方式获得：

  1. 对行应用断点，获取部分路由列表。
  2. 按每条路线的第一个元素将部分路线按升序排序。 例如，将 {[4], [3], [1 2], [5]} 排序为 {[1 2], [3], [4], [5]}。
  3. 通过连接 sorted-partial-routes 形成新的复合记录；有效断点；和一个索引到源行。 例如，如果上一步中的示例行是第 2 行 = (4 3 1 2 5)，则保存 (1 2 3 4 5; 2 3 4; 2) 这是（已排序的部分路线；有效断点；索引）。

对复合记录进行排序后，通过它们寻找相邻条目的相等性，直到源索引。例如，(1 2 3 4 5; 2 3 4; 2) 和 (1 2 3 4 5; 2 3 4; 7) 表示第 7 行的部分路线与第 2 行的部分路线重复。每次找到重复项时，将其对应的原始第一行条目设置为无效点编号，例如 N+1。

因此，在花费 O(X log X) 的排序之后，使用 O(X) 时间来检测重复项。然后使用 O(X) 时间通过删除具有无效第一个元素的原始行来挤出重复项。

稍微更准确的总成本是 O((M+N)*X*log X)，它超过了理论最小值 O((M+N)*X) 一个 log X 因子。如果将复合记录存储在哈希表中而不是对它们进行排序，则可以摆脱 log X 因素，并在出现重复的哈希条目时将记录标记为删除。

于 2011-12-11T13:28:37.900 回答