algorithm - 如何从数字子序列中恢复数字？

Question

给定四位数字 1234，有六个可能的两位数子序列(12、13、14、23、24、34)。给定一些子序列，是否有可能恢复原始数字？

这是一些示例数据。每行列出了一个不同的 6 位数字(待查找)的一些 3 位子序列

528, 508, 028, 502, 058, 528, 028, 528, 552, 050
163, 635, 635, 130, 163, 633, 130, 330, 635, 135
445, 444, 444, 444, 454, 444, 445, 
011, 350, 601, 651, 601, 511, 511, 360, 601, 351
102, 021, 102, 221, 102, 100, 002, 021, 021, 121
332, 111, 313, 311, 132, 113, 132, 111, 112
362, 650, 230, 172, 120, 165, 372, 202, 702
103, 038, 138, 150, 110, 518, 510, 538, 108
343, 231, 431, 341, 203, 203, 401, 303, 031, 233

编辑:有时解决方案可能不是唯一的(多个数字可能给出子序列)。在这种情况下，最好返回其中一个，甚至可能是一个列表。

Answer 1

你要做的是找到Shortest common supersequence你所有的子序列。显然，如果您拥有所有子序列，包括原始编号，那么 SCS 将是您要查找的内容。否则不能保证，但很有可能。

不幸的是，这个问题没有一个很好的多项式算法，但如果你谷歌一下，你会发现有很多近似算法可用。例如。 An ACO Algorithm for the Shortest Common Supersequene Problem其中提到了三种总体方法:

1. 动态编程或 Branch'n'Bound。除了很少的字符串或小字母外，这些通常很慢。

2. 使用动态规划成对查找字符串的 SCS，使用启发式方法选择要“合并”的字符串。

3. Majority Merge 启发式算法可能是最适合您的案例。

4. 论文中描述的方法。

这是关于该问题的另一篇不错的文章:http://www.update.uu.se/~shikaree/Westling/