查找給定的輸入和目標串需要轉換的最小數目

Question

假設我有一個輸入字符串，例如：aab
而且我給予目標字符串，例如：bababa
然後我我給了一套轉換規則。例如：

ab -> bba 
b -> ba 

我怎麼能這樣做，在C，一個算法，會發現最低數量將需要在輸入字符串被應用到獲得目標字符串轉換。

在這個例子中，例如，數目將是3。因爲我們會做：

1 - Apply rule 1 (abba) 
2 - Apply rule 1 again (bbaba) 
3 - Apply rule 2 (bababa) 

是可能發生的給定的輸入和目標，有沒有解決辦法，也應該被注意到。

我在做這件事的策略上非常失落。它涉及到我的想法創建自動機，但我不知道我將如何適用於這種情況。我認爲這是一個有趣的問題，我一直在網上進行研究，但我所能找到的只是給定規則的轉換，而不是如何確保它是最小的。

編輯：作爲建議的答案之一，我們可以從初始字符串開始創建一個圖並創建將轉換應用到前一個節點的結果。但是，從我的角度來看，這帶來了一些問題：

1. 想象一下，我有一個看起來像這樣的轉換 - > ab。我的初始字符串是'a'。而我的輸出字符串是'c'。所以，我一直在做轉換（成長圖）所示：

   一個 - > AB AB - > ABB ABB - > AB | BB ...

我怎麼會知道，當我需要停止建立圖表？

1. 說我有以下字符串aaaa，我有一個像aa-> b的轉換規則。我將如何創建新節點？我的意思是，如何在輸入字符串中找到子字符串並記住它們？

Answer 1

我不認爲有一個有效的解決方案。我認爲你必須做廣度優先搜索。通過這樣做，你會知道，只要你有一個解決方案，它是最短的解決方案。

EDIT：

圖片：修改字符串廣度第一

每一層從先前提出通過應用所有可能的規則，以所有可能的子串。例如，對於每個b，b->ba規則可以應用於abba。僅應用單個規則，然後在列表中記住該字符串（例如，ababa和abbaa），這一點很重要。在開始下一層（首先是寬度）之前，必須完全在程序的List中包含每個圖層。

編輯2：

你寫你現在有一個輸出c。爲此，你顯然需要一個規則XX->c。所以說你有規則aaa->c。現在在第2層中，您將有一個字符串aaa，它來自一些a->aa規則。然後，您將再次應用a->aa並得到aaaa，沒關係，因爲您應該首先考慮廣度，然後將aaa->c規則應用於aaa，並且現在具有由aaaa,c等組成的第3層。您不會繼續修改aaaa，因爲它會轉到第4層，您已經在第3層中找到目標c，因此您可以停止。

編輯3：

現在你問，如果你可以決定未指定的一套規則，你如何決定什麼時候停止層次感。一般來說這是不可能的，它被稱爲停機問題https://en.wikipedia.org/wiki/Halting_problem。

但是對於具體的規則，你可以告訴你是否能夠達到輸出。

• 示例1：如果目標包含無法提供規則的原子（您的'c' - 示例）。
• 例2：如果您的規則是所有或者增加字符串的長度或保持長度，因爲它是（無規則減少字符串的長度）
• 示例3：您可以刪除特定的規則，如果你發現了通過算法，他們是循環
• 其他的例子存在