数学知识——博弈论(巴什博奕、尼姆博奕、威佐夫博奕)思路及例题「建议收藏」

数学知识——博弈论(巴什博奕、尼姆博奕、威佐夫博奕)思路及例题「建议收藏」争先恐后地博弈

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

博弈论基础

    博弈论又被称为对策论(Game Theory),既是现代数学的一个新分支,也是运筹学的一个重要学科。博弈论主要研究公式化了的激励结构间的相互作用,是研究具有斗争或竞争性质现象的数学理论和方法。博弈论考虑游戏中的个体的预测行为和实际行为,并研究它们的优化策略

引入:囚徒困境

    囚徒困境的故事讲的是,两个嫌疑犯小A、小B作案后被警察抓住,分别关在不同的屋子里接受审讯。警察知道两人有罪,但缺乏足够的证据。警察告诉每个人:如果两人都抵赖,各判刑一年;如果两人都坦白,各判五年;如果两人中一个坦白而另一个抵赖,坦白的放出去,抵赖的判十年

于是,每个囚徒都面临两种选择:坦白或抵赖。

数学知识——博弈论(巴什博奕、尼姆博奕、威佐夫博奕)思路及例题「建议收藏」

    在不和小B商量的情况下,作为小A的你是选择招供坐牢5年或0年,还是会选择抵赖坐牢10年或1年呢?

                                        数学知识——博弈论(巴什博奕、尼姆博奕、威佐夫博奕)思路及例题「建议收藏」

一般的人都会选着保险一点的招供吧。

    反观小B,也一定会做出同样的选择,也就是招供。换句话说,只要两名囚徒都是自私且理性的,那么双方都会同时选择招供,结果就是双方各判5年。

    在这个场景中,双方都无法单方面改变自己的博弈策略(单方面改变只会让自己蒙受损失),使得局面进入了一个微妙而又稳定的平衡,这个平衡被称为纳什均衡

    在现实中,也有很多类似的现象,比如家长给孩子报越来越多的课外班,比如高三考生备战高考,起来了啊.从局外人看来,许多竞争都是显而易见双输的局面,但是我们没有办法,因为我们都是参与博弈的“囚徒”。

ICG博弈

所讨论的博弈问题满足以下条件:

    玩家只有两个人轮流做出决策。

    游戏的状态集有限,保证游戏在有限步后结束,这样必然会产生不能操作者,其输。

    对任何一种局面,胜负只决定于局面本身,而与轮到哪位选手无关。

取石子游戏:取石子游戏是一个古老的博弈游戏,发源于中国,它是组合数学领域的一个经典问题。它有许多不同的玩法,基本上是两个玩家,玩的形式是轮流抓石子,胜利的标准是抓走最后的石子玩家设定: 先取石子的是玩家A(先手A),后取石子的是玩家B(后手B)。

经典的三种玩法

一、巴什博奕(Bash Game)

二、尼姆博奕(Nimm Game)

三、威佐夫博奕(Wythoff Game)

(一)巴什博弈

1堆n个石子每次最多取m个、至少取1个

Case 1:如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余的物品,后者取胜

Case 2:n=(m+1)*r+s,(r为任意自然数,s≤m),那么先取者要拿走s个物品,如果后者拿走k(1≤k≤m)个,那么先取者再拿走m+1-k个,结果剩下(m+1)(r-1)个,以后保持这样的取法,那么先取者肯定获胜

Case 3:n=r*(m+1),先手拿走k(1≤k≤m)个,那么后手再拿走m+1-k个,结果剩下(m+1)(r-1)个,以后保持这样的取法,则后手胜,先手必败

总之,要保持给对手留下(m+1)的倍数,就能最后获胜。

术语:正经人称(m+1)的局面为奇异局势

变相的玩法

两个人轮流报数,每次至少报一个,最多报十个,谁能报到100者胜。(等价于从一堆100个石子中取石子,最后取完的胜)

例题:2368 — Buttons (poj.org)

题面:

数学知识——博弈论(巴什博奕、尼姆博奕、威佐夫博奕)思路及例题「建议收藏」

      题面意思:有一堆k个的石头,每人轮流拿1,2,..L个石头,数据范围是3 <= K <= 100 000 000 ,2 <= L < K。输入k的值,要求输出最小的L,使得后者胜。

在理解了巴什博弈之后来看这题还是思路比较清晰的,首先想让后手胜,就必须把(1+L)的局面留给先手。这题没问我们谁会赢,问的是后手要赢的最小L值为多少。那我们就找到能被k整除的最小大于2的因数,之后减1输出就是答案了。

于是有了以下代码注意下(poj用不了万能头文件,编译器要求有点严格。):

//#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=100005;
ll n;//石子数量
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    ll i;
    for(i=2;i<n;i++)//依次找最小的因子
    {
        if(n%(i+1)==0)
        {
            cout<<i<<endl;
            break;
        }
    }
    if(i==n) cout<<0<<endl;//找不到的情况下输出0
    return 0;
}

 就是说数据范围1e8,就超时快乐,TEL了哈哈哈哈哈哈。由于循环2~n,时间复杂度是O(n)。

    再有一个新的思路就是,遍历一遍所有的n的因数,存起来,在输出最小大于等于3的因数减一。一下代码时间复杂度为O(log n)。AC快乐。

//#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll n,a[N];//n为石头总数,a[i]存n的因数
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    int temp=0;
    for(int i=1;i*i<=n;i++)
    {
        if(n%i==0&&i*i!=n) a[temp++]=i,a[temp++]=n/i;
        //注意要区别开类似n=4时,因数为1,2,4.而不是1,2,2,4的情况
        else if(n%i==0&&i*i==n) a[temp++]=i;
    }
    sort(a,a+temp);//从小到大排序一下
    for(int i=0;i<temp;i++)
    {
        if(a[i]>=3)//找到最小大于等于3的因数,减一输出
        {
            cout<<a[i]-1<<endl;
            break;
        }
    }
    return 0;
}

(二)尼姆博弈

有n堆石子,每堆石子的数量是a1,a2,a3……,二个人依次从这些石子堆中的一个拿取任意的石子至少一个,最后一个拿光石子的人胜利

n=1: 先手全拿,先手必胜。

n=2:有两种情况,一种可能相同,一种情况一堆比另一堆少(多)

        (m,m) 按照“有一学一,照猫画猫”法,先手必输。

        (m,M)先手先从多的一堆中拿出(M-m)个,此时后手面对(m,m)的局面先手必胜。

术语:正经人称(m,m)的局面为奇异局势

n=3:(m,m,M)先手必胜局,先手可以先拿M,之后变成了(m,m,0)的局面,是不是很熟悉~

 (a1,a2,a3)的话,举个例子(1,2,3),先手取完之后可能的局面为(0,2,3),(1,1,3),(1,0,3),(1,2,2),(1,2,1),(1,2,0)都是之前讲过的,情况如下:

数学知识——博弈论(巴什博奕、尼姆博奕、威佐夫博奕)思路及例题「建议收藏」

 数学知识——博弈论(巴什博奕、尼姆博奕、威佐夫博奕)思路及例题「建议收藏」

数学知识——博弈论(巴什博奕、尼姆博奕、威佐夫博奕)思路及例题「建议收藏」

前人告诉我们的规律是:异或的结果均为0

获胜情况的讨论

面对异或结果为0的玩家必输。

结果不为0,则玩家有获胜的取法。

例题:891. Nim游戏 – AcWing题库

 题面:

数学知识——博弈论(巴什博奕、尼姆博奕、威佐夫博奕)思路及例题「建议收藏」

看懂了尼姆博奕,这个题目就是分分钟AC咯。

上代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll n,a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int ans=a[0];
    for(int i=1;i<n;i++) ans^=a[i];//^就是做异或运算
    if(ans==0) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    return 0;
}

(三)威佐夫博弈

有两堆各若干个物品,两个人轮流从任一堆取至少一个同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。

举一个例子:局势是(1,2),先手有四种取法,动动你聪明的脑子就会发现无论先手怎么取,后手都能胜利,也就是说(1,2)是奇异局势。

没脑子的人来看看分析咯:

先手从第一堆里面拿1个,后者拿光后面的2个,后者胜。

先手从第一堆和第二堆里面同时拿1个,后者只能拿走第二堆剩下的1个,后者胜。

先手从第二堆里面拿2个,后手拿走第一堆的1个,后者胜.

先手从第二堆里面拿1个,后手从第一堆和第二堆里面同时拿走1个,后者胜。

假设现在的局势是(3,5):

(1)先手在“3”中取1个,后手就可以在“5”中取走4个,这样就变成了(1,2)的局势

(2)先手在“3”中取2个,后手就可以在 “5” 中取走3个,这样也变成了(1,2)的局势

(3)先手在“5”中取1个,后手就在 “3”和“5” 中各取走2个,这样成了(1,2)的局势

(4)先手在”5”中取2个,后手就在 “3”和”5”中各取走3个,这样变成了(0,0)的局势,先手输

(5)先手在“5”中取3个,后手就在 “3”和“5” 中各取走1个,也变成了(1,2)的局势

(6)先手在“5”中取4个,后手在“3”中取走1个,还是(1,2)的局势

我们可以来找找那些先手必输局势的规律(奇异局势)

  • 第一种(0,0)
  • 第二种(1,2)
  • 第三种(3,5)
  • 第四种  (4 ,7)
  • 第五种(6,10)
  • 第六种  (8,13)              
  • 第七种  (9 ,15)
  • 第八种  (11 ,18)
  • 第n种(a,b)

我们会发现他们的差值是递增的,分别是0,1,2,3,4,5,6,7……n

还有一个规律(正常人都发现不了):a=(b-a)*1.618向下取整

 就是:a = int(b – a)*1.618

注:这里的int是强制类型转换,注意这不是简单的四舍五入,假如后面的值是3.9,转换以后得到的不是4而是3,也就是说强制int类型转换得到的是不大于这个数值的最大整数

有些题目要求精度较高,我们可以用下述式子来表示这个值:

1.618 = (sqrt(5.0) + 1) / 2   

头文件:include<math.h>

例题:1067 — 取石子游戏 (poj.org)

题面:

数学知识——博弈论(巴什博奕、尼姆博奕、威佐夫博奕)思路及例题「建议收藏」

 代码:

//#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll a,b;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(cin>>a>>b)//多组输入!!!
    {
        double flag= (sqrt(5.0) + 1) / 2.0;//精度高一些用double来存1.618
        if(a>b) swap(a,b);//保证b要比a大,后面有用到b-a
        if(a==int((b-a)*flag))cout<<0<<endl;//先手面对奇异局势必输
        else cout<<1<<endl;
    }

    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/181728.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 使用IDEA搭建一个简单的SpringBoot项目——详细过程

    使用IDEA搭建一个简单的SpringBoot项目——详细过程一、创建项目1.File->new->project;2.选择“SpringInitializr”,点击next;(jdk1.8默认即可)3.完善项目信息,组名可不做修改,项目名可做修改;最终建的项目名为:test,src->main->java下包名会是:com->example->test;点击next;4.Web下勾选Spri…

  • 三极管导通条件与电位关系

    三极管导通条件与电位关系npn管导通条件:Ub>Ue,通常e极接地,即Ue为0V。饱和导通是Ub>Ue(锗0.2V/硅0.7V)pnp管导通条件:Ub0V。饱和导通是Ub

  • 笔记之kafuka「建议收藏」

    笔记之kafuka「建议收藏」#########################1、启动集群每个节点的进程###################################nohupkafka-server-start.sh/home/hadoop/apps/kafka_2.11-1.1.0/config/server.properties1&amp;amp;amp;gt;~/kafkalogs/kafka_…

  • Java volatile关键字最全总结:原理剖析与实例讲解(简单易懂)

    Java volatile关键字最全总结:原理剖析与实例讲解(简单易懂)一、简介volatile是Java提供的一种轻量级的同步机制。Java语言包含两种内在的同步机制:同步块(或方法)和volatile变量,相比于synchronized(synchronized通常称为重量级锁),volatile更轻量级,因为它不会引起线程上下文的切换和调度。但是volatile变量的同步性较差(有时它更简单并且开销更低),而且其使用也更容易出错。二、并发编程的3…

  • Java入门基础知识点总结(详细篇)

    Java入门基础知识点总结(详细篇)Java入门基础知识点总结(详细篇)~~~~~目录1.1图解1.1.1Java基础知识点1.1.2Java基础语法的相关内容1.2关键字1.3标识符1.3.1标识符概念1.3.2定义标识符的合法规则1.3.3Java中的一些命名规范1.4变量1.4.1变量的分类1.4.2整数类型1.4.3浮点类型1.4.4字符类型char1.4.5布尔类型boolean1.5ASci…

  • Spring之ORM

    Spring之ORMSpring之ORM

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号