algorithm - 找到将一个序列更改为另一个序列的最少步骤数

Question

我们有两个定向序列，

例如 (+A-) (-B+) (+C-) (-D+) (+E-) 和 (+B-) (+C-) (-D+) (+E- ) (+A-).

注意(+A-)表示一个定向子序列，其中'+'表示子序列的头部，'-'表示尾部。如果'1234'是(+A-)，那么'4321'就是(-A+)，这是 (+A-).

的反转

目标是找到仅通过反向操作将一个序列更改为另一个序列的最少步数。

比如我们需要反转一次，将(+A-)(+B-)改为(-B+)(-A+)。

并且我们需要反转两次，将(+A-) (+B-) (+C-)改为(-A+) (+B-) (-C+)。

首先给定的两个序列之间操作的最小步数是3。这是一种方法:

Step 0. (+A-) (-B+) (+C-) (-D+) (+E-)

Step 1. (+B-) (-A+) (+C-) (-D+) (+E-)

Step 2. (+B-) (-A+) (-E+) (+D-) (-C+)

Step 3. (+B-) (+C-) (-D+) (+E-) (+A-)

---

我的想法是问题可能与排序问题有关，但不是交换序列中的两个单独元素，这里我们必须考虑交换两个子序列。

Answer 1

您可以尝试的一种方法是考虑一个函数 g，它计算序列中两个相邻元素未正确连接的所有位置。

因此在您的原始示例中，目标为:

Start (+B-) (+C-) (-D+) (+E-) (+A-) End

我们考虑原始序列中的每对元素:

Start (+A-) (-B+) (+C-) (-D+) (+E-) End ->
Start (+A-) Incorrect because Start should be followed by +B
(+A-) (-B+) Incorrect because A- should be followed by End
(-B+) (+C-) Incorrect because B+ should be followed by Start
(+C-) (-D+) Correct
(-D+) (+E-) Correct
(+E-) End   Incorrect because E- should be followed by +A

所以这有 4 分不正确。

每当你反转一个子串时，你改变了最多 2 个相邻元素的状态，所以最好的分数将减少 2。

在你的例子中我们有:

步骤 0. x (+A-) x (-B+) x (+C-) (-D+) (+E-) x 得分 4

第 1 步。(+B-) x (-A+) x (+C-) (-D+) (+E-) x 得分 3

第 2 步。(+B-) x (-A+) (-E+) (+D-) (-C+) x 分数 2

步骤 3. (+B-) (+C-) (-D+) (+E-) (+A-) 得分 0

由于原始分数为 4，我们确定至少需要 2 次交换(因为分数每步最多减少 2)，而您的解决方案使用 3，因此我们只需要检查替代方案为了排除更好的解决方案，每一步得分减少 2。

有一种著名的算法可以进行此类搜索，称为 A star search .

对于这种类型的搜索，您需要一个可以接受的启发式算法，它永远不会高估到目标的距离。我建议您尝试使用 0.5*g 给出的启发式方法解决您的问题。