0

n-puzzle问题是否有DP方法

谢谢大家,谢谢...

拉詹

4

1 回答 1

1

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

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

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

于 2010-11-30T14:55:45.593 回答