難道真的可以通過回溯解決15難題嗎？

最近我正在讀一本名爲「編程挑戰」的書。它基本上是一本關於算法的書。本書的其中一章專門介紹回溯技術，本章結尾處有來自UVA Online Judge的示例問題。其中一個問題是着名的15 puzzle。難道真的可以通過回溯解決15難題嗎？

儘管在專門討論回溯的章節中介紹了這個問題，但我仍然懷疑這個問題可以在給定時限內通過回溯來解決。

我的問題是：有沒有人在這裏設法接受一個解決方案，只納入回溯的UVA在線法官接受？通過這個，我的意思是你收到了一個沒有花哨的A *算法的接受，或者使用動態編程的記憶或者需要一些聰明的遞歸的一些奇特的解決方案。我的意思是回溯。可能嗎？

來源

2013-06-11 Rustam Issabekov

我會想象memoization是解決方案的一個相當重要的部分... –

是你的回溯問題作爲一個可行的解決方案，以解決這個問題或一般的任何問題？ – jemmanuel

我想我今天很幸運，並且在YouTube上發現了一系列寫這本書的人的講座。其中一個講座是關於回溯部分的問題。 Here is the video。他實際上表明它的回溯問題，只需要一些聰明的修剪。

來源

2013-06-11 16:02:09

如果有人想跳過，相關位從10:30開始。 – IVlad

15拼圖就像國際象棋或魔方，是一個NP難題，需要搜索一棵可能性樹。這種問題只能通過強力加修剪來解決，這就是回溯。我同意你的觀點，很難在短時間內解決這個問題，因爲你可能必須使用某種啓發式方法才能在合理的時間內解決問題。另外，你說得對，必須使用一些額外的邏輯，因爲你必須記住以前訪問過的位置，否則你可能會永遠搜索，一遍又一遍地重複相同的位置。

來源

2013-06-11 19:56:01

「這種問題只能通過蠻力解決」維基百科關於A *的文章說A *也可以用來解決15難題。 – Appleshell

A *是一種圖形搜索算法，可以在樹上使用，因爲樹是一種圖形。 A *不適用於15，因爲沒有明顯的工作成本函數。當A *在沒有有用的成本函數的情況下使用15時，它與回溯沒有區別。 –

難道真的可以通過回溯解決15難題嗎？

回答

相關問題