博弈论算法的实现2

简介: 博弈论算法的实现2

1.Mex运算:

设S表示一个非负整数集合.定义mex(S)为求出不属于集合S的最小非负整数运算,即:

mes(S)=min{x};

例如:S={0,1,2,4},那么mes(S)=3;

2.SG函数

有向图游戏中,对于每个节点x,设从x出发共有k条有向边,分别到达节点y1,y2,····yk,定义SG(x)的后记节点y1,y2,····

yk的SG函数值构成的集合在执行mex运算的结果,即:

SG(x)=mex({SG(y1),SG(y2)····SG(yk)})

特别地,整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值,即 SG(G)=SG(s).

3.有向图游戏的和

设G1,G2,····,Gm是m个有向图游戏.定义有向图游戏G,他的行动规则是任选某个有向图游戏Gi,并在Gi上行动一步.G被称为有向图游戏G1,G2,·····,Gm的和.

有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数的异或和,即:

SG(G)=SG(G1)xorSG(G2)xor···xor SG(Gm)

代码:

#include
#include
#include
#include
using namespace std;
const int N=110,M=10010;
int n,m;
int f[M],s[N];//s存储的是可供选择的集合,f存储的是所有可能出现过的情况的sg值
int sg(int x)
{
if(f[x]!=-1) return f[x];
//因为取石子数目的集合是已经确定了的,所以每个数的sg值也都是确定的,如果存储过了,直接返回即可
set S;
//set代表的是有序集合(注:因为在函数内部定义,所以下一次递归中的S不与本次相同)
for(int i=0;i<m;i++)
{
int sum=s[i];
if(x>=sum) S.insert(sg(x-sum));
//先延伸到终点的sg值后,再从后往前排查出所有数的sg值
}
for(int i=0;;i++)
//循环完之后可以进行选出最小的没有出现的自然数的操作
 if(!S.count(i))
  return f[x]=i;
}
int main()
{
cin>>m;
for(int i=0;i<m;i++)
cin>>s[i];
cin>>n;
memset(f,-1,sizeof(f));//初始化f均为-1,方便在sg函数中查看x是否被记录过
int res=0;
for(int i=0;i<n;i++)
{
    int x;
    cin>>x;
    res^=sg(x);
    //观察异或值的变化,基本原理与Nim游戏相同
}
if(res) printf("Yes");
else printf("No");
return 0;

}

往年题解(非常lj,可直接跳过)

将每一个h[i]h[i]的所有方案看做是一张有向图,例

若S=[2,5],h=10S=[2,5],h=10,则有如下展开形式:

mex():mex():设集合S是一个非负整数集合,定义mex(S)mex(S)为求出不属于S的最小非负整数的运算,即:mes(S)=min[x],其中xmes(S)=min[x],其中x属于自然数,且xx不属于SS(用人话说就是不存在SS集合中的数中,最小的那个数)

SG():SG():在有向图中,对于每个节点xx,设从xx出发共有kk条有向边,分别达到节点y1,y2……yky1,y2……yk,定义SG(x)SG(x)为xx的后继节点的SGSG值构成的集合执行mex()mex()运算后的值

即:SG(x)=mex(SG(y1),SG(y2)…SG(yk))SG(x)=mex(SG(y1),SG(y2)…SG(yk));(用人话说就是比后继节点的SGSG都小的值)

特别的整个图GG的SGSG值被定义为起点ss的SGSG值,即SG(G)=SG(s)SG(G)=SG(s)

上图标红的值就是每一个节点的SGSG值

性质:1.SG(i)=k,则i最大能到达的点的SG值为k−1。1.SG(i)=k,则i最大能到达的点的SG值为k−1。

2.非0可以走向0 2.非0可以走向0

3.0只能走向非0 3.0只能走向非0

定理:

对于一个图GG,如果SG(G)!=0SG(G)!=0,则先手必胜,反之必败

证明:

若SG(G)=!0SG(G)=!0,

1.根据性质2,先手必可以走向0,

2.因此留给后手的是0,根据性质3,后手只能走向非0

3.以此类推,后手始终无法走向0,后手永远处于非0,当先手到达终点的0时,先手获胜

(由此我们可以知道,有些事是命中注定的~~~)

反之同理,必败

定理:

对于n个图,如果SG(G1)SG(G1) ^ SG(G2)SG(G2) ^ … SG(Gn)!=0SG(Gn)!=0 ,则先手必胜,反之必败

证明(类似与Nim游戏):

①当SG(Gi)=0SG(Gi)=0 时 , xor=0xor=0 , 显然先手必败

(PS:结束状态必是状态①,但状态①不一定是结束状态)

②当xor=x!=0xor=x!=0 时,因为肯定存在一个SG(xi)SG(xi)^x <SG(xi)<SG(xi),而根据SG()SG()的性质1可知,SG(k)SG(k)可以走到0−k−10−k−1的任何一个状态,

因此,必定可以从SG(xi)−>SG(xi)SG(xi)−>SG(xi)^xx , 于是使得xor=0xor=0

③当xor=0xor=0时,当移动任何一个节点时,对应的SGSG值必然减小,可以证明:xor!=0xor!=0

下证:xor!=0xor!=0

假设:xor=0xor=0,则说明移动的那个节点的值并没有变化,即从SG(k)SG(k)变成了kk,但是这与SGSG函数的性质1相矛盾,因此不成立

证得:若先手面对的状态是xor!=0xor!=0,则先手方总能使xor=0xor=0,即使后手面对的永远是必败态直到结束状态①,因此先手必胜!

反之,必败!

C++ 代码

#include
#include <unordered_set>
#include
using namespace std;
const int N = 110 , M = 10010;
int n , m;
int s[N] , f[M];
int sg(int x)
{
if(f[x] != -1) return f[x];//记忆化搜索,如果f[x]已经被计算过,则直接返回
// 因为这题中较大堆的拆分情况独立于较小堆,因此有别于894.拆分-Nim,这里的S必须开成局部变量
unordered_set<int> S;//用一个哈希表来存每一个局面能到的所有情况,便于求mex
for(int i = 0 ; i < m ; i++)
    if(x >= s[i]) S.insert(sg(x - s[i]));//如果可以减去s[i],则添加到S中
for(int i = 0 ; ; i++)//求mex(),即找到最小并不在原集合中的数
    if(!S.count(i)) return f[x] = i;
}
int main()
{
cin >> m;
for(int i = 0 ; i < m ; i++) cin >> s[i];
memset(f , -1 , sizeof f);
cin >> n;
int res = 0;
while(n--)
{
    int x;
    cin >> x;
    res ^= sg(x);
}
if(res) puts("Yes");
else puts("No");
return 0;

}


相关文章
|
机器学习/深度学习 人工智能 算法
博弈论算法的实现
博弈论算法的实现
博弈论算法的实现
|
人工智能 算法 决策智能
数学:博弈论算法概述
数学:博弈论算法概述
213 0
|
算法 Shell 决策智能
只用一行代码就能搞定,博弈论究竟是什么神仙算法?
云栖号资讯:【点击查看更多行业资讯】在这里您可以找到不同行业的第一手的上云资讯,还在等什么,快来! 博弈论是一门很庞大的学科,它算是数学的一个分支,也和运筹学甚至是经济学有关。虽然它严格说起来并不是算法领域的内容,但是有不少关于博弈论有趣的算法和问题。
|
12天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。
|
18天前
|
机器学习/深度学习 算法 Serverless
基于WOA-SVM的乳腺癌数据分类识别算法matlab仿真,对比BP神经网络和SVM
本项目利用鲸鱼优化算法(WOA)优化支持向量机(SVM)参数,针对乳腺癌早期诊断问题,通过MATLAB 2022a实现。核心代码包括参数初始化、目标函数计算、位置更新等步骤,并附有详细中文注释及操作视频。实验结果显示,WOA-SVM在提高分类精度和泛化能力方面表现出色,为乳腺癌的早期诊断提供了有效的技术支持。
|
6天前
|
存储 算法
基于HMM隐马尔可夫模型的金融数据预测算法matlab仿真
本项目基于HMM模型实现金融数据预测,包括模型训练与预测两部分。在MATLAB2022A上运行,通过计算状态转移和观测概率预测未来值,并绘制了预测值、真实值及预测误差的对比图。HMM模型适用于金融市场的时间序列分析,能够有效捕捉隐藏状态及其转换规律,为金融预测提供有力工具。
|
6天前
|
机器学习/深度学习 算法 信息无障碍
基于GoogleNet深度学习网络的手语识别算法matlab仿真
本项目展示了基于GoogleNet的深度学习手语识别算法,使用Matlab2022a实现。通过卷积神经网络(CNN)识别手语手势,如&quot;How are you&quot;、&quot;I am fine&quot;、&quot;I love you&quot;等。核心在于Inception模块,通过多尺度处理和1x1卷积减少计算量,提高效率。项目附带完整代码及操作视频。
|
14天前
|
算法
基于GA遗传算法的PID控制器参数优化matlab建模与仿真
本项目基于遗传算法(GA)优化PID控制器参数,通过空间状态方程构建控制对象,自定义GA的选择、交叉、变异过程,以提高PID控制性能。与使用通用GA工具箱相比,此方法更灵活、针对性强。MATLAB2022A环境下测试,展示了GA优化前后PID控制效果的显著差异。核心代码实现了遗传算法的迭代优化过程,最终通过适应度函数评估并选择了最优PID参数,显著提升了系统响应速度和稳定性。
|
11天前
|
算法
基于WOA鲸鱼优化的购售电收益与风险评估算法matlab仿真
本研究提出了一种基于鲸鱼优化算法(WOA)的购售电收益与风险评估算法。通过将售电公司购售电收益风险计算公式作为WOA的目标函数,经过迭代优化计算出最优购电策略。实验结果表明,在迭代次数超过10次后,风险价值收益优化值达到1715.1万元的最大值。WOA还确定了中长期市场、现货市场及可再生能源等不同市场的最优购电量,验证了算法的有效性。核心程序使用MATLAB2022a实现,通过多次迭代优化,实现了售电公司收益最大化和风险最小化的目标。