====== 2020/08/01--2020/08/07======
----
===== 团队训练 =====
暂无
----
===== 王瑞琦 =====
===比赛===
无
===专题===
无
===== 冯宇扬 =====
无
===== 常程 =====
===比赛===
无
===专题===
搜索：[[2020-2021:teams:no_morning_training:shaco:知识点:搜索:a|A*]]、[[2020-2021:teams:no_morning_training:shaco:知识点:搜索:ida|IDA*]]、[[2020-2021:teams:no_morning_training:shaco:知识点:搜索:dlx|DLX]]
===== 本周推荐 =====
==== 王瑞琦 ====
一道A*入门题
===来源===
洛谷P2324：[[https://www.luogu.com.cn/problem/P2324|[SCOI2005]骑士精神]]
===标签===
搜索，A*算法
===题意===
给出一个棋盘，经移动后变成目标状态。若能在15步及以内完成，则输出步数，否则输出-1。
===题解===
首先对搜索进行一个优化：如果对马的走法进行搜索的话，分支太多了，不妨转为对空格的“走法”进行搜索。\\
然后是估价函数的建立\\
也比较一般，就是离目标状态还有多少个棋子没有‘归位’\\
===comment===
感觉搜索题的一般思路就是从暴搜开始思考，一步一步优化=。=
==== 冯宇扬 ====
本周摸鱼
==== 常程 ====
==== 铁盘整理 ====
**来源**：洛谷p2534

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

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

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

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