8数码问题是一个非常经典的问题,常用的解决方法有宽搜和A*搜索。

把问题拓展化,拓展成的15数码问题也是一类问题,但是不能用宽搜和A*搜索解决了,取而代之的是用一个叫IDA*的算法。

而如果把问题再扩大化,那么搜索方法就无法满足要求了。

解决这种扩大化问题的一种方法就是构造法。

构造的想法很简单,例如现在需要解决\( n \times m \)\(n\)\(m\)列)规模的数码问题,那么可以先把一行给拼好,变成\(\left(n - 1 \right) \times m \)的问题,是不是就把问题缩小化了呢?

根据这种想法,因此得出了一个近似\( \mathrm{O} \left( n^3 \right) \)的算法。

number.js没有导入成功,请重新刷新页面。

点击“自动运转”将进行自动转换。

  

八数码

发表评论

电子邮件地址不会被公开。 必填项已用*标注

You must enable javascript to see captcha here!