n-puzzle问题是否有DP方法
谢谢大家,谢谢...
拉詹
动态规划是一种用于解决问题的技术,它通过递归地将困难的案例减少到更简单的案例,直到你达到一个足够简单的案例以“通过检查”来解决。因此,只有在每个阶段,您都可以考虑采取降低问题复杂性的举措,才能对 n-puzzle 问题采取明智的 DP 方法。
例如,如果 n-puzzle 中的第一个“move”总是进入“(n-1)-puzzle”(对于“move”的一些具体定义,并且假设 (n-1)-puzzle 是有意义的) ),然后你可以应用 DP,最终解决“1-puzzle”,然后向上组合以解决 n-puzzle。
我不知道 n-puzzle 有任何这样的简化过程;我现在想不出一个。但是,这并不意味着不存在。