<待整理>关于搜索的笔记

Camber 2月 03, 2019

XDU_ICPC /搜索Ex.ppt / Memo Rawα
/w vjudge_2

待整理，或许就不整理了

概述

特征明显，容易想出算法
代码量大，容易出错

状态空间与搜索树

<Todo>

(这个去看XuzhouICPC Memo Day8)(还没写)

优化

状态空间角度: 去重&压缩
搜索树角度: 剪

*TODO* 去看A*

博弈 + 搜索

双人零和博弈

特点: 双方对抗，策略最优
博弈过程交替
零和: 结果必须为一方胜利另一方失败/平局
完全信息: 双方都知道完整的状态

其中策略最优要满足: 自己获利最大 <-> 对方获利最小
Minimax极大极小搜索(零和博弈)

由零和定义知，在A选择的回合，A想要获利最大，必须选择使B获利最小的走法
轮到B，同理，B在自己的回合想要使自己的获利最大。双方交替进行

~~极大极小树的遍历时自底向上的，就说怎么一直理解不能~~
最终会产出对于B的最大/最小层交替出现的树
从PPT扒出来的图:

在不加以剪枝的情况下，仍然需要遍历树的每一个节点

Reference >>>(待补全)
```
def minimax():
```
Reference >>> XDOJ 1405
α-β剪枝(Minimax)
一句话：对搜索过程中存在着不必要的状态，剪掉

针对 “仍然需要遍历树的每一个节点” 会出现许多不可能的情况，如选择了一个明显劣势的位置(*劣势需要实际定义)
类似于A 将搜索时间放在更有希望的子树上

写法：在上述minimax搜索中传递一个α和β变量
其中α指max层得到的极大值，β指min层的极小值

Negamax负极大值(零和博弈)
待补全

精确覆盖问题

精确覆盖
给定0-1稀疏矩阵，找出一个行集合，使其每列上总共有且只有一个1
数独
暴力暴力暴力 & 精确覆盖的延申
N皇后问题
回溯回溯回溯 & 简化版精确覆盖

精确覆盖的搜索

是一个NPC问题<-解释
暴力：针对有1的那一行的进行枚举

X算法

~~哪里还能找到这么好理解的算法（（（~~

选择了某一行，就拿走(this + conflict(this))

0 0 1 0 1 1 0     0 0 x 0 x x 0  
1 0 0 1 0 0 1     1 0   1     1     1 0 1 1
0 1 1 0 0 1 0  -> x              -> 1 0 1 0 -> ...
1 0 0 1 0 0 0     1 0   1     0     0 1 0 1
0 1 0 0 0 0 1     0 1   0     1
0 0 0 1 1 0 1     x

然后继续搜索，回溯时加回

优点是减少了搜索规模
但是其他东西仍然不尽人意

DancingLinks X 舞蹈链(a.k.a. DLX) -> 对X Algorithm的优化

如上图，利用链表快速查找1的位置 && 快速删除、插入

~~在ppt里提到的一种数据结构, 由于懒就不写推导过程了~~

Reference>>>
Dancing Links的核心是基于双向链的方便操作（移除、恢复加入）(实现略)

将链表的操作应用于 X算法 中，即可得到DancingLinksX数据结构
利用链表添加删除O(1)的特点满足X算法的需求，而且矩阵中若1的个数很大，X算法+DLX可以极快的缩小搜索规模

特点: 每列有一个辅助节点，列节点首有一个head节点
节点保存 上下左右的指针 <- 核心

运行效率很高，理由：
链表的跳转次数取决于矩阵中1的个数
如果矩阵中1的个数很多，会被X算法迅速缩小到很小的规模

请求裸题>>>

End

除非另有说明皆以CC BY-SA 4.0发布
本文链接：https://logistics.camber.moe/2019/memo-Searching/

XDU_ICPC /搜索Ex.ppt / Memo Rawα /w vjudge_2

概述