algorithm - Matlab:删除矩阵的冗余 "shifted"条目

Question

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

首先我有一个矩阵 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 到 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 每一行的索引给出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 行重复。即使与第 1 行具有相同的路线，第 3 行也不会重复，因为存在导致部分路线的不同断点 [1], [2 4], [3] and [5] .

我怎样才能干净、快速地做到这一点？矩阵可以包含很多元素，比如 X = 5e4行和 N = 10 , M = 6 .

Answer 1

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

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

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

对复合记录进行排序后，遍历它们以查找相邻条目的相等性，直至源索引。例如，(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 因素。