logic - n-puzzle问题的DP方法

Question

n-puzzle问题是否有DP方法

谢谢大家，谢谢...

拉詹

Answer 1

动态规划是一种用于解决问题的技术，它通过递归地将困难的案例减少到更简单的案例，直到你达到一个足够简单的案例以“通过检查”来解决。因此，只有在每个阶段，您都可以考虑采取降低问题复杂性的举措，才能对 n-puzzle 问题采取明智的 DP 方法。

例如，如果 n-puzzle 中的第一个“move”总是进入“(n-1)-puzzle”（对于“move”的一些具体定义，并且假设 (n-1)-puzzle 是有意义的） )，然后你可以应用 DP，最终解决“1-puzzle”，然后向上组合以解决 n-puzzle。

我不知道 n-puzzle 有任何这样的简化过程；我现在想不出一个。但是，这并不意味着不存在。