博弈論的算法總結

  開頭先啰嗦一句:想學好博弈,必然要花費很多的時間,深入學習,不要存在一知半解,應該是一看到題目,就想到博弈的類型。

以及,想不斷重復不斷重復,做大量各大oj網站的題目,最后吃透它。

博弈:

  博弈論又被稱為對策論(Game Theory),既是現代數學的一個新分支,也是運籌學的一個重要學科。

博弈,具體的例子就是下棋,雙方都考慮最有利于自已的步驟,但是最終必有一方輸,一方贏。

  博弈的策略:參與者在行動之前所準備好的一套完整的行動方案,就是想好下完這步棋,對方會如何下,

以及接下來該如何下,最終得出結果。

常見的博弈有以下:

1.博弈:合作博弈和非合作博弈
?? 合作博弈:指參與者能夠達成一種具有約束力的協議,在協議范圍內選擇有利于雙方的策略
?? 非合作博弈:指參與者無法達成這樣一種協議
2.博弈:靜態博弈和動態博弈
?? 靜態博弈:指在博弈中,參與者同時選擇,或雖非同時選擇,但是在邏輯時間
?????????????????? 上是同時的。(期末老師評分與同學給老師評分)
?? 動態博弈:指在博弈中,參與者的行動有先后順序,且后行動者能夠觀察
?????????????????? 到先行動者的行動。(下棋)
3.博弈:完全信息博弈與不完全信息博弈
?? 完全信息博弈:指在博弈中,每個參與者對其他參與者的類型,策略空間及損益函數都有準確的信息。(賣家與買家)
?? 不完全信息博弈:總有一些信息不是所有參與者都知道的
4.博弈:零和博弈與非零和博弈
?? 零和博弈:指博弈前的損益總和與博弈后的損益總和相等
?? 非零和博弈:指博弈后的損益大于(小于)博弈前的損益總和(正和或負和 )

下面我主要講一些關于算法比賽中用到的博弈類型:

首先你要理解必勝狀態和必敗狀態:

  對下先手來說,

  一個狀態是必敗狀態當且僅當它的所有后繼都是必敗狀態。

  一個狀態是必勝狀態當且僅當它至少有一個后繼是必敗狀態。

  就是說,博弈者,一旦捉住了勝利的把柄,必然最后勝利。

博弈中常常用到的:

  兩個數,不用中間變量實現交換。
  a b;
  a = a^b;
  b = a^b;
  a = a^b;

巴什博弈:

百度百科:

  巴什博弈:只有一堆n個物品,兩個人輪流從這堆物品中取物, 規定每次至少取一個,最多取m個。最后取光者得勝。

  顯然,如果n=m+1,那么由于一次最多只能取m個,所以,無論先取者拿走多少個,后取者都能夠一次拿走剩余的物品,后者取勝。因此我們發現了如何取勝的法則:如果n=(m+1)r+s,(r為任意自然數,s≤m),那么先取者要拿走s個物品,如果后取者拿走k(≤m)個,那么先取者再拿走m+1-k個,結果剩下(m+1)(r-1)個,以后保持這樣的取法,那么先取者肯定獲勝。總之,要保持給對手留下(m+1)的倍數,就能最后獲勝。這個游戲還可以有一種變相的玩法:兩個人輪流報數,每次至少報一個,最多報十個,誰能報到100者勝。對于巴什博弈,那么我們規定,如果最后取光者輸,那么又會如何呢?(n-1)%(m+1)==0則后手勝利

先手會重新決定策略,所以不是簡單的相反行的
例如n=15,m=3
后手 先手 剩余
0 2 13
1 3 9
2 2 5
3 1 1
1 0 0
先手勝利 輸的人最后必定只抓走一個,如果>1個,則必定會留一個給對手

請去刷下面的題目,均是巴什博弈

???? 算博弈題目時,一定要算到一個周期結束,防止出錯,很有可能像HDU2897那樣。中途錯的猝不及防 ? ?

HDU1847?
代碼實現如下:
package Combat.com;import java.util.Arrays;
import java.util.Scanner;public class Main
{public static void main(String []args){Scanner cin = new Scanner(System.in);while(cin.hasNext()){int n = cin.nextInt();PLG(n);}}static void PLG(int n){if(n%3 == 0){System.out.println("Cici");}else{System.out.println("Kiki");}}
}

?

HDU2147
代碼實現如下:
import java.util.Arrays;
import java.util.Scanner;public class Main
{public static void main(String []args){Scanner cin = new Scanner(System.in);while(cin.hasNext()){int n = cin.nextInt();int m = cin.nextInt();if(n == 0 && m == 0){return;}PLG(n,m);}}static void PLG(int n,int m){if(n%2 == 0 || m % 2 == 0){System.out.println("Wonderful!");}else{System.out.println("What a pity!");}}
}

?

HDU2149?
代碼實現如下:
package Combat.com;import java.util.Arrays;
import java.util.Scanner;public class Main
{public static void main(String []args){Scanner cin = new Scanner(System.in);while(cin.hasNext()){int m = cin.nextInt();int n = cin.nextInt();PLG(m,n);}}static void PLG(int m,int n){if(m % (n+1) == 0){System.out.println("none");}else{if(m <= n){for(int i = m; i <= n; i++){if(i!= m){System.out.print(" ");}System.out.print(i);}System.out.println();}else{int flag = 0;for(int i = 1; i <= n; i++){if((m-i)%(n+1) == 0){if(flag == 0){System.out.print(i);}else{System.out.print(" " + i);}flag++;}}System.out.println();}}}
}

?

HDU2188
代碼實現如下:
package Combat.com;import java.util.Arrays;
import java.util.Scanner;public class Main
{public static void main(String []args){Scanner cin = new Scanner(System.in);int C = cin.nextInt();while(C != 0){int n = cin.nextInt();int m = cin.nextInt();PLG(n,m);C--;}}static void PLG(int n,int m){if(n <= m){System.out.println("Grass");}else{if(n % (m+1) == 0){System.out.println("Rabbit");}else{System.out.println("Grass");}}}
}
HDU2897
代碼實現如下:
package Combat.com;import java.util.Arrays;
import java.util.Scanner;public class Main
{public static void main(String []args){Scanner cin = new Scanner(System.in);while(cin.hasNext()){int n = cin.nextInt();int p = cin.nextInt();int q = cin.nextInt();PLG(n,p,q);}}static void PLG(int n,int p,int q){if(n < p+q){if(n <= p){System.out.println("LOST");}else{System.out.println("WIN");}}else if(n%(p+q) == 0){System.out.println("WIN");}else//有坑
        {if(n % (p+q) > p)System.out.println("WIN");elseSystem.out.println("LOST");}}
}

?

威佐夫博弈:

  一定要去百度百科上面,先理解透意思。

  下面是一些威佐夫博弈的總結:

威佐夫博弈(Wythoff's game):有兩堆各若干個物品,兩個人輪流從某一堆取至少一個或同時從兩堆中取同樣多的物品,規定每次至少取一個,多者不限,最后取光者得勝。
這種情況下是頗為復雜的。我們用(a[k],b[k])(a[k] ≤ b[k] ,k=0,1,2,...,n)(表示兩堆物品的數量并稱其為局勢,如果甲面對(0,0),那么甲已經輸了,這種局勢我們稱為奇異局勢。
前幾個奇異局勢是:(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20)。注:k表示奇異局勢的序號, 第一個奇異局勢k=0。
可以看出,a[0]=b[0]=0,a[k]是未在前面出現過的最小自然數,而 b[k]= a[k] + k。
重要結論:(a,b)b>= a的,如果(int)(b-a)*(Math.sqrt(5)+1)/2 == a,那么先手必輸。
如果不等,后者必輸。

設當前局勢為(a,b); a <= b
①a==b:同時從兩堆取走a個石子,轉化為(0,0)
②a==a[k]&&b>b[k]:從第二堆取走b?b[k]個石子,轉化為(a,b[k])
③a==a[k]&&b<b[k]:同時從兩堆取走a?a[b?a]個石子,轉化為(a[b?a],b?a+a[b?a])
④a>a[k]&&b==b[k]:從第一堆取走a?a[k]個石子,轉化為(a[k],b)
⑤a<a[k]&&b==b[k]:若a==a[j] (j<k),則從第二堆取走b?b[j]個石子,轉化為(a,b[j]);

  否則必有a==b[j](j<k)a==b[j](j<k),則從第二堆取走b?a[j]b?a[j]個石子,轉化為(a[j],a)

  例如5 ?8 ,5>a(8-5)=a3=4 ?8>b(8-5)=b3=7 從兩堆中取走a-a(b-a)=5-4=1個,變成奇異局勢(4,7)。

  例如4 6 ,4>a(6-4)=a2=3 ?6>b(6-4)=b2=5 從兩堆中取走a-a(b-a)=4-3=1個,變成奇異局勢(3,5)。

  可以理解成變成差為b-a的奇異局勢。

如果a=bk并且b-a!=k,則從b堆中取走b-ak個,變成奇異局勢(ak,bk).

  例如,5 10 ,5=b2 10-5=5!=2 則從10中取走10-a2=10-3=7個,變成奇異局勢(3,5)。

為什么要b-a!=k呢?例如7 10 , 7=a3,10-7=3=k 也可以變成奇異局勢(4,7)。但這已經在4)判斷過了。

奇異局勢就是當你面臨這種情況的時候,你必然是輸的,反之,你必贏。
(a,b),a,b兩堆物品的重量,此處是b>a;
解題的技巧:
if a > b , 交換兩個值。
c = b-a;
c = (int)(c*((根號5)+1)/2)
if(c == b)? 先手必輸
else 先手必贏
題目:HDU1527?HDU2177特別要注意HDU2177這道題目。
HDU1527的代碼實現如下:
package Combat.com;import java.util.Arrays;
import java.util.Scanner;public class Main
{static final double mid = (Math.sqrt(5)+1)/2;public static void main(String []args){Scanner cin = new Scanner(System.in);while(cin.hasNext()){int a = cin.nextInt();int b = cin.nextInt();int MAX = Math.max(a, b);int MIN = Math.min(a, b);int temp = (int) ((MAX-MIN)*mid);if(temp == MIN){System.out.println("0");}else{System.out.println("1");}}}
}

HDU2177的代碼實現如下:巧妙暴力,分情況太麻煩了。

package Combat.com;

import java.util.Arrays;
import java.util.Scanner;

public class Main
{
?? ?static final double MID = (Math.sqrt(5)+1)/2;
?? ?public static void main(String []args)
?? ?{
?? ??? ?Scanner cin = new Scanner(System.in);
?? ??? ?while(cin.hasNext())
?? ??? ?{
?? ??? ??? ?int a = cin.nextInt();
?? ??? ??? ?int b = cin.nextInt();
?? ??? ??? ?if(a == 0 && b == 0)
?? ??? ??? ?{
?? ??? ??? ??? ?return;
?? ??? ??? ?}
?? ??? ??? ?WTFGame(a,b);
?? ??? ?}
?? ?}
?? ?static void WTFGame(int a,int b)
?? ?{
?? ??? ?int temp = (int) ((b-a)*MID);
?? ??? ?if(temp == a)
?? ??? ?{
?? ??? ??? ?System.out.println("0");
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?System.out.println("1");
?? ??? ??? ?for(int i = 1; i <= a; i++)//先取同樣石子
?? ??? ??? ?{
?? ??? ??? ??? ?int n = a-i;
?? ??? ??? ??? ?int m = b-i;
?? ??? ??? ??? ?temp = (int) ((m-n)*MID);
?? ??? ??? ??? ?if(temp == n)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?System.out.println(n + " " + m);
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?for(int i = a-1; i >=0; i--)//從最小堆單取;
?? ??? ??? ?{
?? ??? ??? ??? ?temp = (int) ((b-i)*MID);
?? ??? ??? ??? ?if(temp > i)//因為a越小,temp就越大,永遠不可能等。
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?for(int i = b-1; i >= 0; i--)//從最大堆單取
?? ??? ??? ?{
?? ??? ??? ??? ?int n = a;
?? ??? ??? ??? ?int m = i;
?? ??? ??? ??? ?if(n > m)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?int t = a;
?? ??? ??? ??? ??? ?n = m;
?? ??? ??? ??? ??? ?m = t;
?? ??? ??? ??? ??? ?temp = (int)((m-n)*MID);
?? ??? ??? ??? ??? ?if(temp > n)//這里充當優先,當條件滿足,無需進行下去了。
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ??? ??? ?temp = (int) ((m-n)*MID);
?? ??? ??? ??? ?if(temp == n)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?System.out.println(n + " " + m);
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ?}
?? ?}
}

?

尼姆博弈(Nimm Game):

尼姆博弈指的是這樣一個博弈游戲: ?有任意堆物品,每堆物品的個數是任意的,雙方輪流從中取物品,每一次只能從一堆物品中取部分或全部物品,最少取一件, ?取到最后一件物品的人獲勝。

百度百科:

有三堆各若干個物品,兩個人輪流從某一堆取任意多的物品,規定每次至少取一個,多者不限,最后取光者得勝。
這種情況最有意思,它與二進制有密切關系,我們用(a,b,c)表示某種局勢,首先(0,0,0)顯然是奇異局勢,無論誰面對奇異局勢,都必然失敗。第二種奇異局勢是  (0,n,n),只要與對手拿走一樣多的物品,最后都將導致(0,0,0)。仔細分析一下,(1,2,3)也是奇異局勢,無論自己如何拿,接下來對手都可以將其變為(0,n,n)  的情形。
計算機算法里面有一種叫做按位模2加,也叫做異或的運算,我們用符號⊕表示這種運算,先看(1,2,3)的按位模2加的結果:
1 =二進制01
2 =二進制10
3 =二進制11 ⊕
———————
0 =二進制00 (注意不進位)
對于奇異局勢(0,n,n)也一樣,結果也是0。
任何奇異局勢(a,b,c)都有a⊕b⊕c =0。
注意到異或運算的交換律和結合律,及a⊕a=0,:
a⊕b⊕(a⊕b)=(a⊕a)⊕(b⊕b)=0⊕0=0。
所以從一個非奇異局勢向一個奇異局勢轉換的方式可以是:
1)使 a = c⊕b
2)使 b = a⊕c
3)使 c = a⊕b

結論就是:把每堆物品數全部異或起來,如果得到的值為0,那么先手必敗,否則先手必勝。

HDU2176

代碼實現如下;

package Combat.com;import java.util.Arrays;
import java.util.Scanner;public class Main
{static final int MAX = 200005;static int array[] = new int[MAX];public static void main(String []args){Scanner cin = new Scanner(System.in);while(cin.hasNext()){int m = cin.nextInt();if(m == 0){return;}int sum = 0;//異或的結果for(int i = 0; i < m; i++){array[i] = cin.nextInt();sum = sum^array[i];}NIMGame(sum,m);}}static void NIMGame(int sum,int k){if(sum == 0)//代表面臨奇異情況,必輸
        {System.out.println("No");return;}else{System.out.println("Yes");for(int i = 0; i < k; i++)//勝的第一次取法,
            {int s = sum^array[i];//結果s相當于,sum沒與array[i]異或。if(s < array[i]){System.out.println(array[i] + " " + s);}}}}
}

HDU1850? 也是一道尼姆博弈題目,解法和上面相同。

HDU1907也是同樣的做法

?

?階梯博弈:

具體意思,參照下面網址:https://www.cnblogs.com/jiangjing/p/3849284.html

  

?

轉載于:https://www.cnblogs.com/674001396long/p/9901811.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/450821.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/450821.shtml
英文地址,請注明出處:http://en.pswp.cn/news/450821.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Slog55_lua面向對象之lua類

Slog55_lua面向對象之lua類 ArthurSlog SLog-55 Year1 GuangzhouChina Aug 30th 2018 微信掃描二維碼&#xff0c;關注我的公眾號GitHub 掘金主頁 簡書主頁 segmentfault 現實中的事情不是根據人的喜好而定的 比如長在你嘴里的智齒 大部分情況下 你會因為自己&#xff0…

Spring中的@scope注解

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 Scope 簡單點說就是用來指定bean的作用域作用域 &#xff08;官方解釋&#xff1a;scope用來聲明IOC容器中的對象應該處的限定場景或者…

編程語言大比拼——誰的效率高

摘要&#xff1a;C、C、Java這幾個屹立不倒的開發語言&#xff0c;如果以功能點作為單位的話&#xff0c;誰的效率最高呢&#xff1f;如果在項目初期就能確定功能點數量&#xff0c;那么就可以很好的預測項目完成時間。這一點是不是對你很有幫助呢&#xff1f; 一份6000個項目的…

Hadoop之Flume詳解

1、日志采集框架Flume   1.1 Flume介紹     Flume是一個分布式、可靠、和高可用的海量日志采集、聚合和傳輸的系統。     Flume可以采集文件&#xff0c;socket數據包等各種形式源數據&#xff0c;又可以將采集到的數據輸出到HDFS、hbase、hive、     kafka等眾多…

搞懂Java的反射機制

搞懂Java的反射機制 1.什么是反射&#xff1f; java的反射機制是指可以在運行狀態下獲取類和對象的所有屬性和方法。 2.反射的作用&#xff1f; 1、在運行時獲取一個類/對象的成員變量和方法 2、在運行時創建一個類的對象 3、在運行時判斷一個對象是否屬于一個類 3.反射有哪些…

表單oninput和onchange事件區別

oninput事件是元素value發生變化是立刻觸發&#xff0c;而onchange是元素發生變化并且失去焦點時才會觸發。 轉載于:https://www.cnblogs.com/ykli/p/9565601.html

Struts2中<s:iterator>基本用法及示例

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 Struts2中<s:iterator>基本用法及示例 Iterator用于遍歷集合&#xff08;java.util.Collection&#xff09;或枚舉值&#xff08;j…

如何使用postman做接口測試

1、get請求傳參 只要是get請求都可以在瀏覽器中直接發&#xff1a; 在訪問地址后面拼 ?keyvalue&keyvalue 例如&#xff1a;在瀏覽器中直接輸入訪問地址&#xff0c;后面直接拼需要傳給服務器的參數http://api.nnzhp.cn/api/user/stu_info?stu_name小黑2、post請求&…

【狂神說】分析前后端分離開源項目?

文章目錄1.如何分析開源項目項目簡介項目源碼2.觀察開源項目3.開源項目下載4.跑起來是第一步5.前后端分離項目固定套路6.如何找到一個開源項目1.如何分析開源項目 學習的方式&#xff1a; 不知道這個代碼怎么來的這個代碼跑不起來這個項目對我們有什么幫助&#xff0c;不會模…

設計公共API的六個注意事項

摘要&#xff1a;俗話說&#xff1a;“好東西就要貢獻出來和大家一起分享”&#xff0c;尤其是在互聯網業務高度發達的今天&#xff0c;如果你的創業公司提供了一項很酷的技術或者服務&#xff0c;并且其他用戶也非常喜歡該產品&#xff0c;在這種情況下&#xff0c;最好的解決…

go 交叉編譯

golang中windows交叉編譯 env GOOSlinux GOARCHamd64 go build .打包鏡像 FROM alpineMAINTAINER "congge"ADD ./casino_niuniu /usr/local/casino_niuniu/bin/casino_niuniu ADD ./templates /usr/loca/lcasino_niuniu/bin/templates ADD ./public /usr/local/casin…

IntelliJ Idea 2017 免費激活方法

見&#xff1a;https://www.cnblogs.com/suiyueqiannian/p/6754091.html 1. 到網站 http://idea.lanyus.com/ 獲取注冊碼。 2.填入下面的license server: http://intellij.mandroid.cn/   http://idea.imsxm.com/   http://idea.iteblog.com/key.php 以上方法驗證均可以

P3193 [HNOI2008]GT考試

傳送門 容易看出是道DP 考慮一位一位填數字 設 f [ i ] [ j ] 表示填到第 i 位&#xff0c;在不吉利串上匹配到第 j 位時不出現不吉利數字的方案數 設 g [ i ] [ j ] 表示不吉利串匹配到第 i 位&#xff0c;再添加一個數字&#xff0c;使串匹配到第 j 位的方案數 那么方程顯然為…

LeetCode刷題攻略

目錄 一、LeetCode簡介 二、刷leetcode的主要目的 三、常用的數據結構 四、常用的算法思想 五、選擇算法題 1、刷題選擇 2、刷題方法 方法一&#xff1a;順序法 方法二&#xff1a;標簽法 方法三&#xff1a;隨機法 方法四&#xff1a;必殺法 六、刷題攻略 TIP 1&…

SQLserver數據庫反編譯生成Hibernate實體類和映射文件

一、建立項目和sqlserver數據庫 eclipse&#xff0c;我使用的版本是neon3 二、Data Source Explorer 選擇OK 在data source Explorer的Database Connections 選擇New 填寫好General的連接信息 新建New Driver Definition 填寫完選擇OK 選擇剛才的Drivers Test Connetion測試 N…

最受歡迎的5大Linux發行版

摘要&#xff1a;要統計有多少人在使用那款Linux發行版幾乎是不可能的事情&#xff0c;但我們可以使用一些在線分析工具來大概地看看哪些Linux發行版更受歡迎。 Google Trends的數據顯示&#xff0c;Ubuntu用戶正在流向Mint&#xff0c;但依然在各方面都比其它Linux發行版更有優…

C#動態操作DataTable(新增行、列、查詢行、列等)

public void CreateTable(){//創建表DataTable dt new DataTable();//1、添加列dt.Columns.Add("Name", typeof(string)); //數據類型為 文本//2、通過列架構添加列DataColumn age new DataColumn("Age", typeof(Int32)); //數據類型為 整形DataColumn…

使用IntelliJ IDEA 配置Maven(入門)

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 1. 下載Maven 官方地址&#xff1a;http://maven.apache.org/download.cgi 解壓并新建一個本地倉庫文件夾 2.配置本地倉庫路徑 3.配…

[算法]不使用*、/、+、-、%操作符求一個數的1/3

摘要&#xff1a;算法一直是程序員進階的一道龍門&#xff0c;通常算法都是為了更高效地解決問題而創造的&#xff0c;但也有的只是出于學術性&#xff0c;并不在意其實際意義。這是近日在國外技術問答網站stackoverflow的一個熱門問題&#xff0c;不知道你能給出幾種解決方法&…

2022屆互聯網秋招備戰

文章目錄1、何為秋招&#xff1f;1.1應屆生身份1.2秋招、春招、校招1.3、社招、海投2.秋招信息如何獲取&#xff1f;3、如何備戰秋招&#xff1f;3.1、簡歷&#xff08;ps做簡歷&#xff09;3.2、筆試準備3.3、面試準備4、日常實習和暑假實習&#xff1f;1、春招≠暑期實習2、什…