N-数码问题的一些求解思路
search
Share

N-数码问题的一些求解思路

概述

利用启发式算法求解N-数码问题(具体见N-Puzzle)。分两部分：

  • 最短路径解(对应BFSearch)
  • 可行解(对应estimateValue)

测评

代码

两者不同见Commit 历史，主要是修改测试用例，调整得分规则，以及在异常时退出。

得分规则

  • 最短路径解: 2分
  • 一个可行解: 4分
  • 求可行解的效率高: 2分

评测输入

score
runtime
11
22 1 2 3 4 5 6 7 8 9 10 11 13 17 14 15 21 16 12 19 20 22 0 18 23 24
25 23 10 21 14 17 5 4 11 3 20 2 15 6 1 9 24 7 13 22 18 8 16 12 19 0
25 3 20 6 24 19 22 23 18 10 13 5 2 15 14 4 11 8 21 9 12 1 17 16 7 0
25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

思路

主要是补充说明题目中的Hint。

需要说明的一点是代码的自由度极高。Solution中任意添加属性，函数，唯一限制只是需要通过ASearch的搜索。这完全可以在estimateValue中绕过去。因为ASearch是直接调用estimateValue且无法停止estimateValue。有兴趣的可以思考如何实现限时调用。

只要在estimateValue求解完毕，再按求解决路径来进行估价，可以做到搜索点数等于路径长度加一。所以搜索过程完全可以自定义。

求最短路径解

  • 广度搜索过程中，检查节点是否目标节点应该在何处进行。是加入容器时就进行检查，还是等待从容器取出时再检查？时间复杂度虽然是一样，但常数因子相差较大。
  • 就求解本问题的使用场景来看，凡是遍历容器来查找节点所费的花销很大且不值得。虽然这次测试样例弱，在加入容器时就进行检查节点是否目标节点能刚好通过评测，但最短路径长度加到12应该是会超时的。
  • 就求解本问题的使用场景来看，凡是在数组容器进行头部移除所费的花销很大且不值得。但由于 Java 内置的数组复制实现使用了System.arraycopy且数量并不大，所以并不会超时。
  • 虽然函数名叫BFSearch，但最终目的是求最短路径解。实质上应该利用启发式搜索进行求解的，但评估函数一定得符合启发式搜索求最优解的要求。有兴趣的可以了解评估函数的约束以及证明为什么满足约束后启发式搜索得出的解肯定是最优解。这样才是认识了启发式搜索，而不是写个加权求和函数就自以为懂得了启发式搜索。此处的评估函数简单使用曼哈顿距离之和可满足约束条件。

求可行解

  1. 求解算法优化
    • 评估函数
      • 加权多因子：这个因子调整并不难，调整方法有很多，暴力搜索，梯度下降，遗传等。但在采取这些方法的时候，应该思考这些方法是否合理，是否能被证明得到正确的结果，而不是一味套用。实质上更重要是明白为什么使用这些因子进行评估而不是其他因子。选择正确的因子进行评估比调整参数重要得多，但大家重点似乎都在调整参数上面。
      • 评估因子：有兴趣的可以思考更合理的评估因子。合理的评估因子可获得评测满分。
    • 搜索过程
      • 双向：实质上此处使用双向搜索应该效果并不大。
      • 模拟退火：实质上是剪枝的一种策略。可以极大程度上降低失败率。但似乎有不少人的代码实现应该是错的，正确的大概只有一个人。
      • 剪枝：实质上求解路径长度大多在250以上，前期的搜索极多是不会用到的，而后期的搜索中也可以去除一部分恶化的状态，以快速达到目标状态。比如可以这样实现：若深度小于某个阈值并且几代之内并无恶化，则以某概率进行探索节点列表清空。若恶化程度超过某个阈值，则以某概率添加惩罚值。恶化程度可以与自身估值和先代节点估值相关，概率可以与节点深度，恶化程度相关。
      • 随机：一般将评估函数适当地添加随机过程后，成功率应该会上升。比如以某个概率增加惩罚值，幅度以节点状态为准则。
  2. Java代码优化
    • 应用层
      • 分清使用场合: 最常见的String与StringBuilder，还有很多。有兴趣的可以自行了解。
      • HotSpot: 关键函数调优
        • JigsawNode中的hashCode是预留的一个改进地方，自写hashCode实现，在搜索点达到29000次时耗时降低三分之一以上。
          • java 库的类的hashCode实现大多利用了31这个因子，有兴趣的可以思考为什么使用这个因子。
          • 若参照String的hashCode实现方法，有兴趣的可以证明为什么JigsawNode产生的哈希值总是2的倍数。
        • ASearch中的低效代码。如PriorityQueue中的Comparator，多余的复制构造等。但这些在29000个搜索点中影响并不算很大。
      • … …

    • JVM 层

      实质上评测代码并不怎么涉及这一层。

      • GC: 虽然给出了GC的Hint，但评测所给出代码的性能关键并不在这一块，给出仅是凑数。有兴趣的可以了解检测GC情况的方法及如何调优。
      • JIT: 除非自主添加的代码过于复杂，否则也不用考虑这一块。有兴趣的了解JIT机制及使用场景。
      • … …
  3. Hack
    1. 评测时是禁止反射的。反射是敏感操作，在README中有提到禁止敏感操作。有兴趣的可以思考为什么需要反射机制以及实现反射的原理。
    2. 实质上，尝试破解个人代码远比社区代码容易得多。而且，展示代码已经预留了一个显而易见的后门—JigsawNode中的public方法并没有禁止覆盖。再仔细看评判求解是否正确的关键函数isValidPath。 
       public static final boolean isValidPath(List<JigsawNode> path, JigsawNode startNode, JigsawNode destNode) {
 ... ...
     if (!path.get(0).equals(destNode) ||
         !path.get(len - 1).equals(startNode)) {

      看到这里，想必也明白了该怎么绕过isValidPath检查。修正后的代码直接禁止继承JigsawNode。

      实质上，这是很基本的 Java 知识：方法覆盖。有兴趣的可以思考 Java 中的 “一切都是对象” 思想以及 Hibernate 和 Spring 框架如何使用这点实现了 AOP 的“无损注入”。

      按此思路写的代码可获得评测满分。实质上测试用例的空白块都在最右下角，所以很轻易地通过低于1000个搜索节点检测。有兴趣的可以思考空白块在任意位置时该如何将搜索节点降下来。