查找的步驟的最小數目的順序改變爲另一個

Question

我們給出了兩個導向序列，

例如(+A-) (-B+) (+C-) (-D+) (+E-) and (+B-) (+C-) (-D+) (+E-) (+A-)。

注意(+A-)表示一個定向的子序列，其中'+'表示子序列的頭部，而'-'表示尾部。如果'1234'是(+A-)，然後'4321'是(-A+)，這是(+A-).

背面的目標是找到最少的步驟數變更序列到另一個反向的唯一操作。

例如，我們需要反轉一次更改(+A-)(+B-) to (-B+)(-A+).

我們需要扭轉兩次改變(+A-) (+B-) (+C-) to (-A+) (+B-) (-C+).

的以下步驟中的第一給定兩個序列之間進行操作的最小數量是3。這裏是這樣做的一種方法：

步驟0（+ A - ）（-B +）（+ C-）（-D +）（+ E-）

步驟1。 （+ B-）（-A +）（+ C-）（-D +）（+ E-）

步驟2.（+ B-）（-A +）（-E +）（+ D- ）（-C +）

步驟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。 - ）（+ A-）分數0

由於原始分數爲4，我們確定至少需要2次掉期（因爲每步最多可減少2次），並且您的解決方案使用3次所以我們只需要檢查每個步驟中得分減少2的替代方案，以排除更好的解決方案。

有一種熟知的算法來做這種類型的搜索，它被稱爲A star search。

對於這種類型的搜索，您需要一個可接受的啓發式，永遠不會高估與目標的距離。我建議你嘗試用0.5 * g給出的啓發式方法來解決你的問題。