logic - DP approach for the n-puzzle problem

Question

is there a DP approach for the n-puzzle problem

thanks all, appreciate that...

rajan

Answer 1

動的計画法は、「検査によって」解決するのに十分単純なケースに到達するまで、困難なケースをより単純なケースに再帰的に減らすことによって問題を解決するために使用される手法です。したがって、各段階で問題の複雑さを軽減する動きを検討できる場合にのみ、nパズル問題に対する賢明なDPアプローチが存在する可能性があります。

たとえば、nパズルの最初の「移動」が常に「（n-1）パズル」になった場合（「移動」の具体的な定義では、（n-1）パズルが理にかなっていると仮定します） ）、次にDPを適用して、最終的に「1パズル」を解き、上向きに構成してnパズルを解くことができます。

私はnパズルのそのような単純化プロセスを知りません。現時点では考えられません。しかし、それは存在しないという意味ではありません。