嘉华伊美网站建设,注册网站流程和费用,凯里网络推广,网页代理地址博弈论(b站视频) 文章目录一些概念以Nim游戏为例Nim游戏介绍定义 必败/必胜局面必败/必胜局面的判定引理Nim游戏判定引理的等价命题有向图游戏对判定引理的数学描述-Sg函数有向图游戏的和题目#xff1a;[有向图游戏][有向图游戏的和][构造/转化类]一些概念 以Nim游戏为例
Ni…博弈论(b站视频)
文章目录一些概念以Nim游戏为例Nim游戏介绍定义 必败/必胜局面必败/必胜局面的判定引理Nim游戏判定引理的等价命题有向图游戏对判定引理的数学描述-Sg函数有向图游戏的和题目[有向图游戏][有向图游戏的和][构造/转化类]一些概念 以Nim游戏为例
Nim游戏介绍 定义 必败/必胜局面
P-position:先手必败 N-position:先手必胜
例如三堆式子的Nim游戏
必败/必胜局面的判定引理 Nim游戏判定引理的等价命题 为什么直接异或呢(看图)
有向图游戏
大部分公平组合游戏都可以转换为有向图游戏 单个有向图游戏的胜负可根据判定引理判定
对判定引理的数学描述-Sg函数
mex最小的不属于这个集合的自然数 sg(x)mex{sg(y)|x-y} 必败局面sg(x) 0 必胜局面sg(x) ! 0 sg函数验证三条判断引理 SG函数刻画了三条判定引理的性质
有向图游戏的和
G1G2…Gn是n个有向图游戏 有SG定理 sg(G) sg(G1) ^ sg(G2) ^ … ^ sg(Gn)
题目
[有向图游戏]
DAG图上dfs:sg(x)mex{sg(y)|x-y},也可以直接用判定引理复杂度O(NM)如果N是一两百可以直接爆搜 找规律(类nim游戏 P1247 取火柴游戏 P1290 欧几里得的游戏 P1288 取数游戏II CF917B MADMAX
[有向图游戏的和]
求单个游戏的sg值xor起来不能直接使用判断引理需要求出sg的具体值 sg定理sgGsg(G1) ^ sg(G2) ^ … ^ sg(Gn) P2575 高手过招 Acwing 219 剪纸游戏 Acwing 235魔法珠
[构造/转化类]
P1199 三国游戏 Acwing 236.格鲁吉亚和鲍勃
