對於數據結構項目，我必須找到兩個單詞（如"cat"和"dog"）之間的最短路徑，一次只能更改一個字母。我們獲得一個拼字遊戲單詞列表，用於尋找我們的路徑。例如：將一個單詞轉換爲另一個單詞的最短路徑
cat -> bat -> bet -> bot -> bog -> dog
我已經解決了使用廣度優先搜索的問題，但正在尋求更好的東西（我表示有線索的字典）。
請給我一些更有效的方法（速度和內存方面）的想法。有些荒謬和/或具有挑戰性是首選。
我問我的一個朋友（他是一個大三），他說有沒有有效的解決這個問題。他說我會學習爲什麼當我學習算法課程。對此有何評論？
我們必須走出一個字。我們不能去cat -> dat -> dag -> dog。我們還必須打印遍歷。
新的答案
鑑於最近的更新，你可以嘗試用漢明距離作爲啓發式A *。這是一個啓發的，因爲它不會高估的距離
OLD ANSWER
您可以修改用於計算Levenshtein distance獲得的操作順序的動態程序。
編輯：如果有恆定數量的字符串，該問題可以在多項式時間內解決。否則，這是NP-hard（在維基百科中它都在那裏）..假設你的朋友正在談論NP-hard的問題。
編輯：如果您的字符串長度相等，則可以使用Hamming distance。
你可以找到最長的公共子序列，因此找到必須改變的字母。
這是一個典型的dynamic programming問題。檢查編輯距離問題。
不是。仔細閱讀問題。有一個固定的給定詞典，所以編輯距離幾乎沒有關係。 – ShreevatsaR 2009-10-07 12:49:55
爲什麼這是upvoted？它不回答whats問。 – 2014-06-14 11:45:30
我的直覺是，你的朋友是正確的，因爲沒有更有效的解決方案，但這是假設你每次都重新加載字典。如果您要保留一個正在運行的常用轉換數據庫，那麼肯定會找到更有效的方法來找到解決方案，但您需要事先生成轉換，並發現哪些轉換會有用（因爲您無法生成他們都！）可能是它自己的藝術。
有用於尋找鏈接不同的效率的方法 - 你可以構建一個完全圖的每個單詞的長度，或者你可以構造一個BK-Tree，例如，但你的朋友是正確的 - BFS是最有效的算法。
但是，有一種方法可以顯着改善運行時：不是從源節點執行單個BFS，而是從圖的任一端開始執行兩次寬度優先搜索，並在找到公共節點時終止在他們的邊界集合。如果僅從一端進行搜索，則您所要做的工作量大約只需要一半。
請注意，這種方法只適用於未加權圖，我相信。在加權圖上（其中一些邊比其他邊更「成本」或更長），以相同方式使用雙向搜索並不能保證找到最短路徑。查看[此鏈接]（http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf）和[本主題]（http：// stackoverflow .COM /問題/ 4253413 /終止準則，爲雙向搜索）。但在這種情況下，單字母不同單詞之間的步驟完全相同 – 2014-09-15 00:59:07
對於字典，BFS是最優的，但所需的運行時間與其大小（V + E）成正比。用n個字母，字典可能有〜個字母，其中a是字母大小。如果字典中包含的所有單詞都應該放在鏈的末尾，那麼您將遍歷所有可能的單詞，但不會找到任何內容。這是圖遍歷，但大小可能是指數級大。
您可能想知道是否有可能更快地做到 - 以「智能」的方式瀏覽結構並在多項式時間內完成。答案是，我認爲，不。
問題：
你給出一個快速的（線性）的方式，來檢查單詞在字典兩個字U，V，並檢查是否有一個序列u - >一個 - > a - > ... - > a n - > v。
是NP-hard。
證明：花一些3SAT例如，像
（P或Q或者不r）和（p或非q或r）
您將與0 000 00開始，並檢查有可能去2 222 22.
第一個字符將是「我們完成」，三個下一個位將控制p，q，r，然後兩個控制子句。
允許的話是：
從0 000 00產生2 222 22你必須這樣做，以這樣的方式。
（1）翻轉相應的位 - 例如，在四個步驟0 100 111這需要找到一個解決方案3SAT
（2）將第一位更改爲2：2 100 111.在這裏您將驗證這確實是3SAT解決方案。
（3）改變2 100 111 - > 200 2 111 - > 220 2 111 - > 222 2 111 - > 222 2 211 - > 222 2 221 - > 222 2 222
這些規則強制執行你不能作弊（檢查）。只有當公式是可以滿足的，並且檢查是NP-hard時，纔可能去2 222 22。我覺得它可能更難（可能是#P或FNP），但我認爲NP硬度就足夠了。您可能有興趣disjoint set data structure。這將會把你的字典和分組單詞彼此聯繫起來。您還可以存儲從每個頂點到根或其他某個頂點的路徑。這會給你一條道路，而不是最短的道路。
偉大的總結。如果原作者正在尋找真正有創意的東西，編輯距離可以與單詞到達圖一起用作遺傳算法的適應函數。輸出是從一個開始字到結束字的圖形路徑，所以最好的答案是最短的。 （雖然很酷，但會找到答案最快，但不會產生明確的答案。非常TS。） 我會堅持現實世界。消除週期，枚舉路徑並使用上述建議找到'最好'的路徑。這被標記爲'Java'，所以試試JGraphT。 – 2009-10-06 15:03:53
很酷，在Stackoverflow的答案中不常見到NP硬度證明。 :-)如果詞典只是簡單地作爲成員資格預先給定的話，我也懷疑這個問題比NP（PSPACE-complete？）更困難......但是如果字典實際上是在輸入中給出的，那麼問題可以簡單地在多項式時間，因爲字典大小是輸入的一部分（這是NP硬度證明中的缺陷）。 – ShreevatsaR 2009-10-07 02:56:27
你在找什麼叫做編輯距離。有很多不同的類型。
From（http://en.wikipedia.org/wiki/Edit_distance）：「在信息理論和計算機科學中，兩個字符串之間的編輯距離是將其中一個字符轉換爲另一個字符所需的操作次數。」
這篇文章爵士（java的拼寫檢查API）有這些類型比較的一個很好的概述 - 通過消除的話http://www.ibm.com/developerworks/java/library/j-jazzy/
你可以把它再快一點（這是一個類似的問題提供建議的更正）首先，這不是正確的長度。更多的有限字典將適合CPU的緩存。可能全是它。另外，所有的strncmp比較（假設你做的都是小寫的）可以是memcmp比較，甚至展開比較，這可以是一個加速比。
您可以使用一些預處理器魔法，並針對該字長對任務進行硬編譯，或針對常用字長度對任務進行幾次優化變化。所有這些額外的比較可以'消失'純粹展開的樂趣。
在你的例子中，爲什麼在那裏下注？你連續兩次更改了同一封信，它應該是： cat - > bat - > bot - > bog - > – CaffGeek 2009-10-07 15:01:51
duplicate http://stackoverflow.com/questions/11811918/how-to-compute-shortest-距離之間的雙字/ 11813399＃11813399 – 2012-08-24 04:47:01
達克曼，你介意分享多少你的表現改善使用啓發式與BFS？ – 2014-09-15 00:38:46