难道真的可以通过回溯解决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难题吗？

回答

相关问题