【读书笔记】算法漫步 第5章

问题4 拼块游戏

问题导入

在平面上矩形框内有m x n个小方块，按照m行n列排放。每个方块面上被两条对角线分为4个三角形区域。每个三角形可以从4中颜色中任选一种着色。如果相邻方块邻接边两侧的三角形区域颜色相同则记1分。给定一种排列，玩家每一步可任选两个方块相互交换位置（称为置换），但不能旋转。玩家需通过置换操作争取尽可能的高分，置换次数并无限制。

 

显然，内部边界线段数是可能的最高分。

 

因为置换次数无限制，那么似乎可以用穷举发，穷举m x n个小方块可能的排列，计算每种排列的分值。但是这个排列数是(m x n)!。显然，想用穷举的方法确认最优解（最高分）显然不容易。

 

人工智能的启发式算法在这里派上了用场。

 

“人工智能”“智能”算法，这个名词听起来非常高大上。

 

其实在目前计算机领域内，应用层面上的“智能”背后的算法支撑，简单说就是“碰运气”。

 

作者在本章中，针对这个问题，给出了两个启发式算法，一个是基于贪婪思想，追求局部优化的方法；另一个是更加“智能”的启发式算法—模拟退火算法。（这类受生命现象或物理过程启发而设计的算法，往往不能严格证明在允许的输入条件下算法结果的正确性，但通过大量实验，经验数据支撑了算法的可用性和有效性。）【通俗说，就是启发式算法不能证明算法能得到最优解，但是通过实际大量的运行，得到解就是最优解或者很接近最优解】

 

作者在本章，就拼块游戏，也给出了两个算法的运行结果。想感受，现在计算机领域的“智能”算法在解这个问题时，能做到什么程度。看书吧。

 

【作者感受】

我自己在学习 启发式算法时，也觉得不可思议（初学时），也觉得不可理喻（学了一会后，因为水平不够）。

后来，自己读博士时，求解一个问题，需要用到启发式算法，实验室的一些同门求解其他问题时，有时也要用启发式算法（模拟退火、遗传算法。。。），确实能求得一些更好的结果出来。其实还是不理解，因为研究方向不同，以后对人工智能也没有什么涉猎了。

“智能”算法“智能”吗？有兴趣的读者自己去探索和体会吧。