2020-2021:teams:no_morning_training:weekly:week12
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:weekly:week12 [2020/08/20 15:38] nomansland [王瑞琦] |
2020-2021:teams:no_morning_training:weekly:week12 [2020/08/21 22:07] (当前版本) 发源于 |
||
|---|---|---|---|
| 行 10: | 行 10: | ||
| 无 | 无 | ||
| ===== 冯宇扬 ===== | ===== 冯宇扬 ===== | ||
| - | ===比赛=== | + | 无 |
| - | ===专题=== | + | |
| ===== 常程 ===== | ===== 常程 ===== | ||
| ===比赛=== | ===比赛=== | ||
| + | 无 | ||
| ===专题=== | ===专题=== | ||
| + | 搜索：[[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，翻转又只能改变交界处相差，因此用这样的方式来得到一个很合适的估价函数。 | ||
2020-2021/teams/no_morning_training/weekly/week12.1597909092.txt.gz · 最后更改: 2020/08/20 15:38 由 nomansland
