暂无

无

无

无

无

搜索：A*、IDA*、DLX

一道A*入门题

洛谷P2324：[SCOI2005]骑士精神

搜索，A*算法

给出一个棋盘，经移动后变成目标状态。若能在15步及以内完成，则输出步数，否则输出-1。

首先对搜索进行一个优化：如果对马的走法进行搜索的话，分支太多了，不妨转为对空格的“走法”进行搜索。
然后是估价函数的建立
也比较一般，就是离目标状态还有多少个棋子没有‘归位’

感觉搜索题的一般思路就是从暴搜开始思考，一步一步优化=。=

本周摸鱼

来源：洛谷p2534

标签：排序、搜索、剪枝、A*

概述：有若干铁盘摞在一起，每次操作可以令底部若干铁盘不动，反转上面所有铁盘。铁盘具有不同的半径，求使所有铁盘半径从上到下递增的最少操作次数。

答案：IDA*:迭代加深+估价函数（将铁盘大小离散，故目标状态相邻的铁盘大小相差为1；每次翻转只改变翻转与不动的边界处两个铁盘的大小关系，因此估价函数即统计相邻铁盘大小相差不为1的铁盘对数）

comment: 最终态从上到下递增意味着离散后相差为1，翻转又只能改变交界处相差，因此用这样的方式来得到一个很合适的估价函数。