第一篇：四皇后問(wèn)題實(shí)驗(yàn)報(bào)告

人工智能——四皇后問(wèn)題

一、問(wèn)題描述

四皇后問(wèn)題

一個(gè)4×4國(guó)際象棋盤，依次放入四個(gè)皇后，條件：每行、每列及對(duì)角線上只允許出現(xiàn)一枚棋子。

設(shè)：DATA=L（表）x∈L x ∈﹛i j﹜ 1≤ i, j ≤4 其中：i j 表示棋子所在行列 如：24 表示第二行第四列有一枚棋子 ∵棋盤上可放入的棋子數(shù)為0 ～ 4 個(gè)

∴L表中的元素?cái)?shù)為0 ～ 4 個(gè)，即 Length L = 0 ～ 4，如圖A ﹛12，24，31，43 ﹜

定義規(guī)則： if 1≤ i ≤4 and Length DATA = i －1 then APPEND(DATA(ij))1≤ j ≤4 ① 對(duì)于任一行i，1≤ j ≤4 表明每行有四條規(guī)則。

比如第一行：R11，R12，R13，R14 ② 棋盤中共有四行，所以共有16條規(guī)則。

即： R11，R12，R13，R14 R21，R22，R23，R24 R31，R32，R33，R34 R41，R42，R43，R44 ③ 16條規(guī)則中，哪些是當(dāng)前可用規(guī)則，取決于DATA的長(zhǎng)度，即：DATA中的元素個(gè)數(shù)。換言之，每次只能將一個(gè)棋子放在當(dāng)前行的下一行。

二、回溯法搜索策略圖

討論：

上述算法產(chǎn)生22次回溯，原因在于規(guī)則自然順序排列，沒(méi)考慮任何智能因素。改進(jìn)算法

定義對(duì)角線函數(shù)：diag(i,j)：過(guò)ij點(diǎn)最長(zhǎng)的對(duì)角線長(zhǎng)度值。

規(guī)定：① 如果： diag(i,k)≤ diag(i,j)則規(guī)則排列次序?yàn)椋?Rik，Rij 同一行四條規(guī)則中，對(duì)角線函數(shù)值小的排在前面

② 如果：diag(i,k)＝ diag(i,j)則規(guī)則排列次序?yàn)椋?Rij，Rik j ＜ k 對(duì)角線長(zhǎng)度相等的規(guī)則按照字母排列順序排序

討論：

① 利用局部知識(shí)排列規(guī)則是有效的。

② BACKTRACK算法對(duì)重復(fù)出現(xiàn)的狀態(tài)沒(méi)有判斷，所以可能造成出現(xiàn)死循環(huán)。③ 沒(méi)有對(duì)搜索深度加以限制，可能造成搜索代價(jià)太大。

三、算法描述

回溯法——在約束條件下先序遍歷，并在遍歷過(guò)程中剪去那些不滿足條件的分支。

使用回溯算法求解的問(wèn)題特征，求解問(wèn)題要分為若干步，且每一步都有幾種可能的選擇，而且往往在某個(gè)選擇不成功時(shí)需要回頭再試另外一種選擇，如果到達(dá)求解目標(biāo)則每一步的選擇構(gòu)成了問(wèn)題的解，如果回頭到第一步且沒(méi)有新的選擇則問(wèn)題求解失敗。

在回溯策略中，也可以通過(guò)引入一些與問(wèn)題相關(guān)的信息來(lái)加快搜索解的速度。對(duì)于皇后問(wèn)題來(lái)說(shuō)，由于每一行、每一列和每一個(gè)對(duì)角線，都只能放一個(gè)皇后，當(dāng)一個(gè)皇后放到棋盤上后，不管它放在棋盤的什么位置，它所影響的行和列方向上的棋盤位置是固定的，因此在行、列方面沒(méi)有什么信息可以利用。但在不同的位置，在對(duì)角線方向所影響的棋盤位置數(shù)則是不同的?？梢韵胂?，如果把一個(gè)皇后放在棋盤的某個(gè)位置后，它所影響的棋盤位置數(shù)少，那么給以后放皇后留下的余地就太大，找到解的可能性也大；反之留有余地就小，找到解的可能性也小。

四、算法流程圖

五、源程序

#include #define N 4 char board[N][N];int t;int col[N];

//存儲(chǔ)第i行對(duì)應(yīng)的列的值，這樣的(i,j)值滿足當(dāng)前棋盤上的皇后不能互相攻擊。

int safetyPlace(int x,int y)//(x,y)位置是否安全 {

int i,j;

for(i=0;i

{

j=col[i];

if(x==i||y==j)

return 0;

if(x-y==i-j||x+y==i+j)

//判斷左右對(duì)角線

return 0;

}

return 1;} void get_position(int i)

//處在第i行時(shí)狀態(tài) {

int w,j;

char a[1]={3};

if(i==N)

//輸出棋盤

{

for(w=0;w

{

for(j=0;j

{

if(board[w][j]==001)

printf(“%c ”,board[w][j]);

else

{

printf(“%c”,a[0]);

printf(“%c ”,board[w][j]);

}

}

printf(“n”);

}

printf(“n”);

printf(“--------------n”);

t++;

}

else

{

int u;

for(u=0;u

{

if(safetyPlace(i,u)==1)

{

col[i]=u;

//記錄下第i行可行的列的位置

board[i][u]=001;

//放置皇后

get_position(i+1);

//轉(zhuǎn)換到下一個(gè)狀態(tài)，即下一行

col[i]=0;

//回溯到當(dāng)前狀態(tài)，重置列和棋盤的值

board[i][u]=0;

} }

} } main(){

printf(“%c是皇后!nn”,001);get_position(0);printf(“一共有%d種方法！n”,t);}

六、結(jié)果截圖

七、總結(jié)——心得體會(huì)

通過(guò)對(duì)四皇后問(wèn)題的編程學(xué)習(xí)，讓我對(duì)搜索策略更深層次的理解，尤其能比較熟練掌握回溯策略——首先將規(guī)則給出一個(gè)固定的排序，在搜索時(shí)，對(duì)當(dāng)前狀態(tài)（搜索開(kāi)始時(shí)，當(dāng)前狀態(tài)是初始狀態(tài)）依次檢測(cè)每一條規(guī)則，在當(dāng)前狀態(tài)未使用過(guò)的規(guī)則中找到第一條可應(yīng)用規(guī)則，應(yīng)用于當(dāng)前狀態(tài)，得到的新?tīng)顟B(tài)重新設(shè)置為當(dāng)前狀態(tài)，并重復(fù)以上搜索。如果當(dāng)前狀態(tài)無(wú)規(guī)則可用，或者所有規(guī)則已經(jīng)被試探過(guò)仍未找到問(wèn)題的解，則將當(dāng)前狀態(tài)的前一個(gè)狀態(tài)（即直接生成該狀態(tài)的狀態(tài)）設(shè)置為當(dāng)前狀態(tài)。重復(fù)以上搜索，直到找到問(wèn)題的解，或者試探了所有可能后仍找不到問(wèn)題的解為止。

同時(shí)，在整個(gè)編程學(xué)習(xí)過(guò)程中，使得我對(duì)人工智能感到越來(lái)越多的趣味性（例如四皇后問(wèn)題上升到n皇后如何求解），更引起我對(duì)學(xué)習(xí)人工智能這門課程的積極性。

第二篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告--八皇后（寫寫幫整理）

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

1．實(shí)驗(yàn)要求

實(shí)驗(yàn)?zāi)康模豪脳＝Y(jié)構(gòu)實(shí)現(xiàn)八皇后問(wèn)題

八皇后問(wèn)題如下：八皇后問(wèn)題是19世紀(jì)著名的數(shù)學(xué)家高斯于1850年提出的。他的問(wèn)題是，在8*8的棋盤上放置8個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行，同一列，同一斜線上。

實(shí)驗(yàn)內(nèi)容：利用所學(xué)的棧結(jié)構(gòu)用遞歸或非遞歸解決八皇后問(wèn)題。

2.程序分析

程序使用程序最主要只是在主函數(shù)用了一個(gè)遞歸函數(shù)Queen。

Queen函數(shù)使用了三個(gè)參數(shù)m,flag[][],chess[][]。其中m是行數(shù)，flag[][]是判斷二維數(shù)組何處可以放置皇后，chess[][]是存儲(chǔ)字符串的二維數(shù)組。

主函數(shù)中對(duì)Queen函數(shù)中的形參數(shù)組flag[][],chess[][]進(jìn)行初始化，在Queen函數(shù)中再進(jìn)行各種操作。

Queen函數(shù)執(zhí)行代碼，首先行數(shù)m為0，當(dāng)m小于7時(shí)，通過(guò)if…else…語(yǔ)句，利用Queen(m+1,f,c)重新執(zhí)行遞歸函數(shù)到下一行。

2.1 存儲(chǔ)結(jié)構(gòu)

存儲(chǔ)結(jié)構(gòu)：數(shù)組存儲(chǔ)。

flag[][]數(shù)組存儲(chǔ)數(shù)字判斷輸出和儲(chǔ)能放置皇后,chess[][]數(shù)組存儲(chǔ)字符串即皇后和非皇后的形狀。

2.2 關(guān)鍵算法分析

1、關(guān)鍵算法： a．

for(i=0;i<8;i++)

for(j=0;j<8;j++)

{

f[i][j]=0;

c[i][j]='*';

說(shuō)明：對(duì)棋盤進(jìn)行初始化 未放置皇后的為“*” b．

for(i=0;i<8;i++)

for(j=0;j<8;j++)

{

c[i][j]=chess[i][j];

f[i][j]=flag[i][j];

} 說(shuō)明：對(duì)c[][]，f[][]進(jìn)行初始化。c．

for(i=0;i<8;i++)

for(j=0;j<8;j++)

{

if(f[i][j]==0 &&(i+j==m+k || m==i || k==j || m-k==i-j))

f[i][j]=-1;

}

c[m][k]='#';

說(shuō)明：已放置皇后的行、列以及對(duì)角線都不能再放置皇后。

已放置皇后的顯示為“#”。d.if(m==7)

{

cout<<“算法的第”<<++count<<“個(gè)解為：”<

for(int i=0;i<8;i++)

{

for(int j=0;j<8;j++)

{

cout<

}

cout<

}

cout<

cout<

return;

}

else Queen(m+1,f,c);

說(shuō)明：首先判斷是否已執(zhí)行到最后一行

每輸出一個(gè)算法，count計(jì)數(shù)器加1 若沒(méi)有執(zhí)行到最后一行，m+1繼續(xù)執(zhí)行Queen函數(shù)

2.3 其他

要求程序在一開(kāi)始創(chuàng)建一個(gè)統(tǒng)計(jì)算法解個(gè)數(shù)的加法器。

3.程序運(yùn)行結(jié)果

1、測(cè)試主函數(shù)流程：流程圖如圖所示

2、測(cè)試結(jié)論：輸出解決算法的個(gè)數(shù)及八皇后問(wèn)題的圖解。

4.總結(jié)

一．問(wèn)題及解決辦法

1.一開(kāi)始編的時(shí)候?qū)ν恍?，同一列以及同一斜行不能排皇后的算法不能?zhǔn)確編寫，后來(lái)通過(guò)畫(huà)圖發(fā)現(xiàn)了這三個(gè)情況數(shù)組行標(biāo)和列標(biāo)的特點(diǎn)，從而解決了這個(gè)問(wèn)題。

2.程序只能輸出從65至99的解，其他解不顯示，后來(lái)發(fā)現(xiàn)是因?yàn)榻缑嫣〉脑颉６牡皿w會(huì)

對(duì)于剛學(xué)的棧表以及遞歸函數(shù)一定要多用才能熟悉，才能知道實(shí)現(xiàn)的具體細(xì)節(jié)問(wèn)題。對(duì)一些出現(xiàn)的錯(cuò)誤一點(diǎn)要仔細(xì)分析，明白以后就會(huì)掌握的很牢固。對(duì)于遞歸函數(shù)一定要充分理解它的意義才能用好它。

在編寫代碼中如果對(duì)于一些抽象的算法構(gòu)思感到困難，可以通過(guò)畫(huà)圖，在紙上先進(jìn)行演算推導(dǎo)出各變量之間的關(guān)系，再進(jìn)行編寫可能會(huì)使問(wèn)題變得簡(jiǎn)單明了一些。三．改進(jìn)

遞歸算法解決八皇后問(wèn)題比較簡(jiǎn)單明了，下次可以嘗試不使用遞歸而用非遞歸編寫算法，這樣可能會(huì)更牢固更好的掌握棧的思想，鞏固已學(xué)的知識(shí)。

第三篇：分析化學(xué)實(shí)驗(yàn)報(bào)告四

實(shí)驗(yàn)四標(biāo)定氫氧化鈉、測(cè)定銨態(tài)氮

摘要：固體NaOH容易吸收空氣中的水分和CO2，因此不能直接配制準(zhǔn)確濃度的NaOH標(biāo)準(zhǔn)溶液，只能先配置近似濃度的溶液，然后用基準(zhǔn)物質(zhì)標(biāo)定其準(zhǔn)確 濃度，標(biāo)定結(jié)果顯示NaOH溶液濃度為0.09675mol/L。銨態(tài)氮中除碳酸氫銨 可用標(biāo)準(zhǔn)酸直接滴定外，其他銨鹽由于NH4+是一種極弱酸（Ka=5.6x10-10), 不能用標(biāo)準(zhǔn)堿直接滴定。一般用“蒸餾法”或“甲醛法”來(lái)測(cè)定其含量，測(cè) 定結(jié)果顯示銨態(tài)氮的含量為26.12％。

關(guān)鍵詞：滴定；NaOH標(biāo)準(zhǔn)溶液；銨態(tài)氮

前言

由于NaOH固體在空氣中易變質(zhì)，很難配制標(biāo)準(zhǔn)濃度的NaOH溶液，所以先配制近似濃度的溶液，再用基準(zhǔn)物質(zhì)來(lái)標(biāo)定其準(zhǔn)確濃度；測(cè)定除NaHCO3外的銨態(tài)氮，因NH4+是一種極弱酸，不能用標(biāo)準(zhǔn)堿直接滴定，應(yīng)采用“蒸餾法”或“甲醛法”間接測(cè)定，本次試驗(yàn)采用“甲醛法”，即銨鹽先與甲醛生成六亞甲基四胺酸和強(qiáng)酸，再用標(biāo)定后的NaOH溶液滴定，w?

計(jì)算可得銨態(tài)氮的含量。

一、儀器與試劑

50mL堿式滴定管1支、20mL移液管1支、25mL移液管1支、250mL容量瓶1個(gè)、250mL錐形瓶3只、200mL燒杯1只、電子天平；KHR固體、酚酞指示劑、3mol/L NaOH溶液。

二、試驗(yàn)方法

1、制備NaOH溶液：17mL 3mol/L NaOH→0.1mol/L 500mL NaOH；

2、標(biāo)定NaOH：稱取KHR 0.405~0.415g，加20mL水溶解，再加兩滴酚酞指示劑，最后用NaOH溶液滴定至淺紅色且30s不褪色，平行五次；

3、測(cè)定銨態(tài)氮：

?稱取1.6g氯化銨，加水溶解，250mL容量瓶定容，移取25.00mL至錐形瓶，加入5mL甲醛，再滴加兩滴酚酞指示劑，最后用標(biāo)定過(guò)后的NaOH溶液滴定至淺紅色，平行五次：

?空白試驗(yàn)：取25.00mL蒸餾水代替氨溶液進(jìn)行測(cè)定，平行三次。cNaOH?VNaOH?MmN?100%

注意：標(biāo)定NaOH要求

ds或

d≤0.2％；測(cè)定銨態(tài)氮要求

s或

d≤0.4％；空白滴

定要求≤0.4%，且空白>0.2mL要扣除。

三、結(jié)果與討論

1、標(biāo)定NaOH 初讀數(shù)(mL)末讀數(shù)(mL)V滴定(mL)

0.03 20.72 20.69

0.12 20.79 20.67

?xn?i

0.03

20.72 20.69 0.11 20.78 20.67 0.22 20.86 20.64

V

=20.672mL，s?

cKHRVKHRVNaOH

??x

n?i

n

n?1

=0.02049，s=0.1%<0.2%，則：

cNaOH?

=

0.1?2020.672

=0.09675mol/L2、銨態(tài)氮的測(cè)定 ?測(cè)定銨態(tài)氮 0.01 30.87 30.86

0.13 31.07 30.94

0.04 30.89 30.85

30.77 30.77

0.01 30.86 30.85

??x

V

n

i

?xn?

=30.854mL，s?

cNaOH?VNaOH?M

m

n?i

n?1

=0.06025，s=0.2%<0.4%，則：

?3

w?

N

?100%

=

0.09675?30.854?10

0.1600

?14

?100%=26.12%

?空白滴定 初讀數(shù)(mL)末讀數(shù)(mL)V滴定(mL)

0.09 0.28 0.19

n

0.05 0.23 0.18 0.02 0.21 0.19

dV

=0.187，d?

?

n?i

dn

i

=

0.003?0.007?0.003

=0.0043，=2.3%>0.4%

討論：經(jīng)標(biāo)定確定NaOH濃度為0.09675mol/L，后經(jīng)滴定確定銨態(tài)氮含量為26.12%。配置的NaOH標(biāo)準(zhǔn)溶液濃度偏低，原因可能是因?yàn)?mol/L NaOH放

置久了，與空氣中的CO2反應(yīng)，造成溶液濃度降低，從從而影響NaOH標(biāo)準(zhǔn)溶液的濃度；而銨態(tài)氮的測(cè)定則有可能因?yàn)榈味ú粶?zhǔn)確或者是由于NaOH溶液的標(biāo)定有誤差，造成結(jié)果的不準(zhǔn)確。

感謝吳明君老師，感謝四川農(nóng)業(yè)大學(xué)生命科學(xué)與理學(xué)院分析化學(xué)實(shí)驗(yàn)室！

第四篇：實(shí)驗(yàn)報(bào)告8-Excel_2010(四)

實(shí)驗(yàn)報(bào)告8 Excel 電子表格2010(四)

班級(jí) 091 學(xué)號(hào) 201509104 姓名 王曉博

【實(shí)驗(yàn)?zāi)康摹?/p>

1.了解Excel的圖表類型和圖表功能； 2．掌握?qǐng)D表的創(chuàng)建與格式化；

3．理解圖表的基本組成及一些選項(xiàng)的作用。

【實(shí)驗(yàn)內(nèi)容和步驟】

完成實(shí)踐教程第92頁(yè)4.4.3中的實(shí)驗(yàn)并回答下列問(wèn)題。如何選擇不連續(xù)的兩列數(shù)據(jù)？

按住ctrl鍵同時(shí)在表格中選中要?jiǎng)?chuàng)建的表格的不連續(xù)區(qū)域

2如何選擇圖例的位置以及添加數(shù)據(jù)標(biāo)簽。

1.右擊圖標(biāo)中的圖例，從快捷菜單中選擇“設(shè)置圖例格式”命令

2.探出‘設(shè)置圖例格式對(duì)’話框，選擇右側(cè)的‘圖例位置’區(qū)中的其他模式按鈕。

3.選中圖表，單擊‘插入’選項(xiàng)卡/文本/文本框 按鈕下方的下拉按鈕，在彈出的下拉菜單中選擇‘橫排文本框’選項(xiàng)，在圖表中拖入鼠標(biāo)，插入文本框。在文本框中輸入解釋文本‘XX’然后在圖表任意位置單擊即可

3如何設(shè)置圖表背景墻和地板格式？如何設(shè)置圖表區(qū)域的漸變填充。

單擊圖表，點(diǎn)擊“布局”中的“背景墻設(shè)置”進(jìn)行設(shè)置即可。雙擊圖表區(qū)域，出現(xiàn)“設(shè)置圖表區(qū)格式”對(duì)話框，點(diǎn)擊“填充”-“漸變填充”即可 如何修改圖表邊框的顏色和樣式

右擊鼠標(biāo)，單擊繪圖模式，選擇相應(yīng)的顏色和樣式即可 怎樣改變圖表的位置和大小。

右擊圖標(biāo)中的圖例，從彈出的快捷菜單中選擇“設(shè)置圖例樣式”在探出的對(duì)話框右側(cè)“圖列位置”選項(xiàng)區(qū)中選擇相應(yīng)的位置和大小。

6、寫出柱形圖、餅圖兩種圖表類型適用場(chǎng)合。

柱形圖：顯示一段時(shí)期內(nèi)數(shù)據(jù)的變化或者描繪各項(xiàng)之間的比較時(shí)。餅圖：只顯示一個(gè)數(shù)據(jù)系列，需要突出某個(gè)重要數(shù)據(jù)項(xiàng)時(shí)。

【實(shí)驗(yàn)心得與體會(huì)】 學(xué)會(huì)了如何做圖表，收獲頗豐，感覺(jué)自己棒棒嗒。

第五篇：賭徒問(wèn)題實(shí)驗(yàn)報(bào)告

賭徒問(wèn)題實(shí)驗(yàn)報(bào)告

一、引言

賭徒問(wèn)題是針對(duì)第四章動(dòng)態(tài)規(guī)劃的練習(xí)，同時(shí)也是對(duì)第三章介紹的貝爾曼方程和強(qiáng)化學(xué)習(xí)的基本知識(shí)的實(shí)際應(yīng)用。兩者緊密結(jié)合只有充分了解相關(guān)內(nèi)容才能了解實(shí)驗(yàn)經(jīng)過(guò)，才能對(duì)強(qiáng)化學(xué)習(xí)的基本問(wèn)題有所了解。

二、相關(guān)知識(shí)介紹

1、馬爾科夫性：能夠保存此狀態(tài)的來(lái)歷的方式，稱此方式是馬爾科夫的。

也就是s',r，和歷史的st,at,rt,st?1,at?1,...,r1,s0,a0來(lái)說(shuō)，st?1?s',rt?1?r|st,at,rt,st?1,at?1,...r1，s0,a0}=Pr{st?1?s',rt?1?r|st,at}

Pr{在這種情況下，環(huán)境和任務(wù)是一體的，也都稱為具有馬爾可夫性質(zhì)。

PS：每個(gè)狀態(tài)都是有前一個(gè)可能的狀態(tài)動(dòng)作對(duì)和發(fā)生的各個(gè)概率計(jì)算得來(lái)的。

2、值函數(shù)：一個(gè)策略?是每個(gè)狀態(tài)s?S以及動(dòng)作a?A(s)到狀態(tài)s下采取動(dòng)作a的概率?(s,a)的一個(gè)映射。通俗地說(shuō)，在策略?下?tīng)顟B(tài)s的值記為V?(s)，它是從狀態(tài)s開(kāi)始并遵循策略?的期望回報(bào)。對(duì)MDP而言，我們可以形式化地定義V?(s)為：

??k?V(s)?E?{Rt|st?s}?E????rt?k?1|st?s?，（3.8）

?k?0??其中E?{}表示了agent在遵循策略?之后的期望值。而終止?fàn)顟B(tài)的值總是0。我們把函數(shù)V?稱為策略?的狀態(tài)值函數(shù)（state－value function for policy π）。

類似地，我們定義在策略?下?tīng)顟B(tài)s中采取動(dòng)作a的值，記為Q(s,a)，作為在策略?從狀態(tài)s開(kāi)始，采取動(dòng)作a的期望回報(bào):

??k?Q(s,a)?E?{Rt|st?s,at?a}?E????rt?k?1|st?s,at?a?

（3.9）

?k?0???我們將Q稱為策略?的動(dòng)作值函數(shù)（action－value function for policy π）。

在強(qiáng)化學(xué)習(xí)和動(dòng)態(tài)規(guī)劃中，值函數(shù)的基本性質(zhì)是它們滿足一定的遞歸關(guān)系。對(duì)任意策略??和狀態(tài)s，在s的值和它可能的后繼狀態(tài)值之間，（3.10）的一致條件成立：

V(s)?E?{Rt|st?s} ???k?

?E????rt?k?1|st?s?

?k?0??

?E??rt?1?????k?0?rt?k?2|st?s?

?k?

?

???(s,a)?as'as'?a??k?? P?Rss'??E????rt?k?2|st?1?s'??，（3.10）

?k?0???ass'ass'ass'??(s,a)?P?R???V(s')

?其中，動(dòng)作a是從集合A(s)中得到的，下一狀態(tài)s'從集合S中得到的，或者是從情節(jié)式任務(wù)中的S?中得到的。等式（3.10）是V?的Bellman方程。它表達(dá)了一個(gè)狀態(tài)的值和它的后繼狀態(tài)值之間的關(guān)系。

公式（3.10）就是貝爾曼方程，而V值就是貝爾曼方程的唯一解。

3、計(jì)算值函數(shù)：利用動(dòng)態(tài)規(guī)劃去計(jì)算值函數(shù)。找到符合Bellman最優(yōu)方程

?的最優(yōu)值函數(shù)V*或Q*，從而得到最優(yōu)策略。對(duì)于所有s?S，a?A(s)，且s'?S，Bellman最優(yōu)方程如下：

V(s)?maxE{rt?1??V(st?1)|st?s,at?a}

a**

?maxa?s'Pss'[Rss'??V(s')]

（4.1）

aa*或

Q(s,a)?E{rt?1??maxQ(st?1,a')|st?s,at?a}

a'**

??Ps'ass'[Rss'??maxQ(s',a')]

a'a*（4.2）

PS：此方法就是修改貝爾曼方程從而得到V值的近似解。

三、實(shí)驗(yàn)過(guò)程簡(jiǎn)介

賭徒問(wèn)題是一個(gè)典型的值迭代問(wèn)題，值迭代是策略迭代的方法之一。

將貝爾曼最優(yōu)方程轉(zhuǎn)換成更新規(guī)則就可以得到值迭代。除了策略迭備份需要從所有的動(dòng)作中選出最大動(dòng)作以外，值迭代更新等同于策略評(píng)估更新。當(dāng)每次掃描過(guò)后V的改動(dòng)很小的時(shí)候就可以停止算法。認(rèn)為V值已經(jīng)解出。

以下是題目：

一個(gè)賭徒利用硬幣投擲的反正面結(jié)果來(lái)賭博。假如投擲結(jié)果是硬幣的正面朝上，那么他就贏得他所壓的賭注，如果是反面朝上，那么他輸?shù)羲馁€注。當(dāng)這個(gè)賭徒贏滿100美元或者他輸?shù)羲械腻X時(shí)，賭博結(jié)束。每一輪投擲，賭徒必須取出他資金的一部分作為賭注，賭注金額必須是整數(shù)。這個(gè)問(wèn)題可以表述為一個(gè)無(wú)折扣的、情節(jié)式的有窮馬爾可夫決策過(guò)程。狀態(tài)就是賭徒所擁有的資金，s?{1,2,?,99}，動(dòng)作就是下賭注，a?{1,2,?,min(s,100?s)}。除了賭徒達(dá)到100美元的目標(biāo)而獎(jiǎng)賞為＋1以外，其他獎(jiǎng)賞均為0。狀態(tài)－值函數(shù)給出每個(gè)狀態(tài)能夠獲勝的概率。策略就是如何決定每輪取出多少錢去下注。最優(yōu)策略就是使取得最后勝利的概率最大化。令p代表硬幣正面朝上的概率。假如p已知，那么整個(gè)問(wèn)題也就知道了，并且可以得解，比如通過(guò)值迭代求解。圖4.6就是當(dāng)p?0.4時(shí)，值迭代每一輪后值函數(shù)的變化情況和得到的最終策略。

以下是算法：

任意初始化V，比如：V(s)?0，對(duì)于所有s?S

Repeat ??0

?

For each s?S

v?V(s)V(s)?maxa?s'Pss'[Rss'??V(s')]aa

??max(?,|v?V(s)|)Until ???（一個(gè)極小的正數(shù)）

輸出一個(gè)確定的策略? ?(s)?argmaxa?s'Pss'[Rss'??V(s')]

aa根據(jù)算法和題目的具體要求得到的C++代碼如下：

#include //#include

using namespace std;//vector V(99,0);double V[100];

//將V值放在數(shù)組中存放，為了方便起見(jiàn)這里V[0]是不使用的！double AF(double S);

//a值的計(jì)算函數(shù)題目中a是a?{1,2,?,min(s,100?s)} double Q(int S,int a);

//Q(S,a)動(dòng)作值函數(shù)的計(jì)算

double RP(double S,double a);//這里P是加法的縮寫M是減法的縮寫賭徒賭錢可能的情況 double RM(double S,double a);// 為贏錢和輸錢兩種，+為贏概率0.4，同樣輸錢為-概率0.6； //=============================== void main(){

for(int i=0;i<100;i++)

//初始化V值為0； { V[i]=0;} double Delta=0.0;

//初始化△=0 double Cta=0.0000000001;

//初始化?=0 double i;double K=0;do { for(int S=1;S<=99;S++)

//對(duì)于1~99個(gè)狀態(tài)

{

} double v=V[S];

//將V值暫時(shí)保存下來(lái)

i=AF(S);

//i用來(lái)接收計(jì)算出來(lái)的a值 for(int a=0;a<=i;a++){ K+=Q(S,a);

//貝爾曼最優(yōu)方程 } V[S]=K;Delta=max(Delta,fabs(v-V[S]));

//計(jì)算△

} while(Delta

//當(dāng)V的變化一定小的時(shí)候結(jié)束

for(int i=1;i<=99;i++)

//輸出最終的V值也就是貝爾曼方程的cout<<“V[”<

//最優(yōu)解，賭徒問(wèn)題的最優(yōu)解。double AF(double S){

} double T;T=min(S,100-S);return T;

double Q(int S,int a){ double RESULT;RESULT=0.4*(RP(S,a)+V[S+a])+0.6*(RM(S,a)+V[S-a]);return RESULT;} //RP,RM判斷匯報(bào)的值是1還是0.double RP(double S,double a){

} double C=S+a;if(C>=100)return 1.0;else return 0;

double RM(double S,double a){

} double C=S-a;if(C>=100)return 1.0;else return 0;結(jié)果顯示:

就一個(gè)50是對(duì)的，我就無(wú)語(yǔ)了。。。

V(s)?maxa?s'Pss'[Rss'??V(s')]aa 其實(shí)這個(gè)程序就是實(shí)現(xiàn)這個(gè)公式，我暈啊檢查了幾遍

maxa?s'還沒(méi)發(fā)現(xiàn)問(wèn)題，還麻煩老師幫忙看看。我知道這樣不好，但是真的沒(méi)招了，感覺(jué)這里可能有問(wèn)題。。。

總結(jié)：

通過(guò)實(shí)驗(yàn)讓我更加理解貝爾曼方程，對(duì)值函數(shù)的計(jì)算有了進(jìn)一步的認(rèn)識(shí)。同時(shí)學(xué)會(huì)了用值迭代的方法求出貝爾曼方程的最優(yōu)解，對(duì)V與Q的關(guān)系理解更加深刻。V[S]=S狀態(tài)下對(duì)應(yīng)不同動(dòng)作a的所有Q的和。