第一篇：傳教士和野人問題實驗報告
1.上機內容 傳教士與野人問題求解（寬度搜索算法）
二 二 問題背景：
從前有一條河，河的左岸有 m 個傳教士(Missionary)和 m 個野人(Cannibal)，和一艘最多可乘 n 人的小船。約定左岸，右岸和船上或者沒有傳教士，或者野人數量少于傳教士，否則野人會把傳教士吃掉。
三 三 實驗內容：
編程，接收 m 和 n，搜索一條可讓所有的野人和傳教士安全渡到右岸的方案，例如下圖:（M 表示傳教士(Missionary)，C 表示野人(Cannibal)）
初
態
目
標 Left Bank River Right bank
Left Bank River Right bank M….M….C….C….注：本實驗的舉例均以 3 個傳教士和 3 個野人同在左岸作為初始狀態。
四 四 實驗方案和算法：．數據結構：
本實驗需要用到的數據結構主要是隊列和堆棧，其實現均包含于 dso.h 頭文件中，分別命名為 class stack 和 class queue。2 ． 寬 度搜索算法：
(1)結點結構 ：
class Move {
public:
int missionary;
//要移動的傳教士數量
int cannibal;
//野人
};class ElemType : Move {
//繼承 Move 類，獲得傳教士，野人數據成員。
private:
bool boat;
//船是否在左岸？
public:
ElemType* flag;
// 標示前一狀態即擴展出本結點的父結點信息
ElemType(int MAX_PEOPLE){
//創建初始狀態
missionary = cannibal = MAX_PEOPLE;
boat = true;
flag = NULL;
} ……
在這里，Elemtype 集成了 Move，從而獲得 Move 類的傳教士和野人數據成員。以上兩個類的數據成員用于保存所有擴展生成的結點。其中 missionary 表示表示左岸上傳教士的樹目，cannibal 表示左岸上野人的樹目，boat 表示船在哪個岸上（其中 true 表示在左岸，這是船的初始狀態，表示 false 在右岸），flag用于標示前一狀態即擴展出本結點的父結點信息，以便最后回搜找出解的 路徑。
舉例說明：假設左岸有 3 個傳教士和 3 個野人，小船最多可乘 2 人。把當前左岸的狀態抽象為：(3,3,1)，前兩個“3”代表左岸有 3 個傳教士和 3 個野人，1 代表船在左岸。很明顯，目標狀態為(0,0,0),表示左岸的傳教士和也人數目都是 0，而船在右岸。
(2)船的行動規則（successor function）: :
把每一次可行的渡船方案作為行動規則，用 Move 類的（m,c）表示。行動規則的兩位數分別代表要移動的傳教士，野人的數量。對于固定大小的船，其裝載能力是一定的，所以它的行動規則空間也是一定的。在這里，用 MoveGroup 類的構造函數構造出所有的行動規則。
注意，這里 MoveGroup 類中的 Move 對象只有 500 的可用空間，所以，輸入的傳教士和野人數目構成的行動規則不能超過 500 種。
(3)寬度優先算法：
實驗的主要搜索算法由 ANSWER 類的構造函數實現，這里主要用到了 OPEN 和 CLOSED 隊列，以及一個臨時的 TEMP 堆棧。其中，OPEN 表用于存放擴展結點，CLOSED 表用于存放被擴展結點，TEMP 則用于用于記錄成功搜索的路徑。
搜索過程大致如下描述：先構造初始結點以及船的行動規則，初始結點入 OPEN 隊列，以寬度優先依次搜索 OPEN 隊列頭結點的子結點，同時保存受訪問結點的父結點信息，知道搜索到目標結點或者無解為止。
算法框圖如下所示：
開始 初始接結點并入 OPEN 隊列 OPEN 為空？ OPEN 隊列頭結點 n 出列，并入 CLOSED 隊列 返回 Y N
程序界面 和功能 說明：
程序運行環境為 DOS 控制臺，運行開始以后，程序提示輸入需要坐船的傳教士和野人數目，例如輸入 3 表示有 3 個傳教士和 3 個野人。
用戶按回車鍵以后，程序繼續提示輸入船的裝載能力，例如輸入 2 表示這個船依次最多可以坐 2 人。注：一般情況下，船的裝載能力應該少于傳教士或野人的數量，而且一般為偶數。
程序 開始運行時的 界面截圖：
程序 運行結束時的 界面截圖：
把結點的子結點并入 OPEN隊列，保存父結點 被擴展結點還有子結點嗎？ 返回
Y N
輸出文件示例：
Left(3, 3)|(0, 0)Right [Step 1]
Move 0 missionaries and 2 cannibals to the right side.Left(3, 1)|(0, 2)Right [Step 2]
Move 0 missionaries and 1 cannibals to the left side.Left(3, 2)|(0, 1)Right [Step 3]
Move 0 missionaries and 2 cannibals to the right side.Left(3, 0)|(0, 3)Right [Step 4]
Move 0 missionaries and 1 cannibals to the left side.Left(3, 1)|(0, 2)Right [Step 5]
Move 2 missionaries and 0 cannibals to the right side.Left(1, 1)|(2, 2)Right [Step 6]
Move 1 missionaries and 1 cannibals to the left side.Left(2, 2)|(1, 1)Right [Step 7]
Move 2 missionaries and 0 cannibals to the right side.Left(0, 2)|(3, 1)Right [Step 8]
Move 0 missionaries and 1 cannibals to the left side.Left(0, 3)|(3, 0)Right [Step 9]
Move 0 missionaries and 2 cannibals to the right side.Left(0, 1)|(3, 2)Right [Step 10]
Move 0 missionaries and 1 cannibals to the left side.Left(0, 2)|(3, 1)Right [Step 11]
Move 0 missionaries and 2 cannibals to the right side.Left(0, 0)|(3, 3)Right OK!錯誤說明：
（1）
關于有沒有解的問題：由于傳教士和野人問題是一個真實的問題，來到岸邊的傳教士和野人數目與船的裝載能力都是隨機的，所以某些特定情況下，要以一定規則把人都運到船的對岸是沒有解的，例如假設有 10 個傳教士和 10 個野人，船一次最多能夠裝 2 人，這時候是不能把人都運到對岸的，這時候程序會提示：There may not be any way to transport these guys.（2）
關于運行時間的問題：本實驗使用寬度優先搜索算法，但并沒有進行優化，所以有時候程序雖然確實有解，但是由于算法的效率確實很低，造成的時間上的開銷有時候可能會比起喝一杯咖啡的時間還要長，這時候程序會提示：
Please wait patiently。Working...六 六 心得體會：
這個是我們小組的第一個實驗，由于經驗以及能力有限，所以算法上比較簡單，只用了一個寬度優先搜索算法，但畢竟能夠成功找出解，雖然效率較低。經過一些測試數據的測試以后，發現了寬度優先搜索算法雖然必能找到最優解（有時候無解），但效率真的很低，如我們提供的那個測試數據（50 個傳教士，50 個野人，船最多能坐 4 人），雖然能解，但也花費了 75 秒多的時間才能找出解，可見優化算法的必要。
第二篇：實驗報告五 生產者和消費者問題
實驗報告五
——生產者和消費者問題
姓名：叢菲 學號：20100830205 班級：信息安全二班
一、實習內容
? ?
1、模擬操作系統中進程同步和互斥
2、實現生產者和消費者問題的算法實現
二、實習目的
? ? ? ? ?
1、熟悉臨界資源、信號量及PV操作的定義與物理意義
2、了解進程通信的方法
3、掌握進程互斥與進程同步的相關知識
4、掌握用信號量機制解決進程之間的同步與互斥問題
5、實現生產者－消費者問題，深刻理解進程同步問題
三、實習題目
? 在Linux操作系統下用C實現經典同步問題：生產者—消費者，具體要求如下：
(1)一個大小為10的緩沖區，初始狀態為空。
(2)2個生產者，隨機等待一段時間，往緩沖區中添加數據，若緩沖區已滿，等待消費者取走數據之后再添加，重復10次。
(3)2個消費者，隨機等待一段時間，從緩沖區中讀取數據，若緩沖區為空，等待生產者添加數據之后再讀取，重復10次。? 提示
本實驗的主要目的是模擬操作系統中進程同步和互斥。在系統進程并發執行異步推進的過程中，由于資源共享和進程間合作而造成進程間相互制約。進程間的相互制約有兩種不同的方式。
（1）間接制約。這是由于多個進程共享同一資源（如CPU、共享輸入/輸出設備）而引起的，即共享資源的多個進程因系統協調使用資源而相互制約。
（2）直接制約。只是由于進程合作中各個進程為完成同一任務而造成的，即并發進程各自的執行結果互為對方的執行條件，從而限制各個進程的執行速度。
生產者和消費者是經典的進程同步問題，在這個問題中，生產者不斷的向緩沖區中寫入數據，而消費者則從緩沖區中讀取數據。生產者進程和消費者對緩沖區的操作是互斥，即當前只能有一個進程對這個緩沖區進行操作，生產者進入操作緩沖區之前，先要看緩沖區是否已滿，如果緩沖區已滿，則它必須等待消費者進程將數據取出才能寫入數據，同樣的，消費者進程從緩沖區讀取數據之前，也要判斷緩沖區是否為空，如果為空，則必須等待生產者進程寫入數據才能讀取數據。
在本實驗中，進程之間要進行通信來操作同一緩沖區。一般來說，進程間的通信根據通信內容可以劃分為兩種：即控制信息的傳送與大批量數據傳送。有時，也把進程間控制在本實驗中，進程之間要進行通信來操作同一緩沖區。一般來說，進程間的通信根據通信內容可以劃分為兩種：即控制信息的傳送與大批量數據傳送。有時，也把進程間控制信息的交換稱為低級通信，而把進程間大批量數據的交換稱為高級通信。
目前，計算機系統中用得比較普遍的高級通信機制可分為3大類：共享存儲器系統、消息傳遞系統及管道通信系統。
? 共享存儲器系統
共享存儲器系統為了傳送大量數據，在存儲器中劃出一塊共享存儲區，諸進程可通過對共享存儲區進行讀數據或寫數據以實現通信。進程在通信之前，向系統申請共享存儲區中的一個分區，并為它指定一個分區關鍵字。信息的交換稱為低級通信，而把進程間大批量數據的交換稱為高級通信。
目前，計算機系統中用得比較普遍的高級通信機制可分為3大類：共享存儲器系統、消息傳遞系統及管道通信系統。
? 消息傳遞系統
在消息傳遞系統中，進程間的數據交換以消息為單位，在計算機網絡中被稱為報文。消息傳遞系統的實現方式又可以分為以下兩種：(1)直接通信方式
發送進程可將消息直接發送給接收進程，即將消息掛在接收進程的消息緩沖隊列上，而接收進程可從自己的消息緩沖隊列中取得消息。(2)間接通信方式
發送進程將消息發送到指定的信箱中，而接收進程從信箱中取得消息。這種通信方式又稱信箱通信方式，被廣泛地應用于計算機網絡中。相應地，該消息傳遞系統被稱為電子郵件系統。
? 管道通信系統
向管道提供輸入的發送進程，以字符流方式將大量的數據送入管道，而接收進程從管道中接收數據。由于發送進程和接收進程是利用管道進行通信的，故稱為管道通信。為了協調發送和接收雙方的通信，管道通信機制必須提供以下3方面的協調功能。（1）互斥
當一個進程正在對pipe文件進行讀或寫操作時，另一個進程必須等待。（2）同步
當寫進程把一定數量的數據寫入pipe文件后，便阻塞等待，直到讀進程取走數據后，再把寫進程喚醒。
（3）確認對方是否存在 只有確定對方已存在時，才能進行管道通信，否則會造成因對方不存在而無限制地等待。在這個問題當中，我們采用信號量機制進行進程之間的通信，設置兩個信號量，空的信號量和滿的信號量。在Linux系統中，一個或多個信號量構成一個信號量集合。使用信號量機制可以實現進程之間的同步和互斥，允許并發進程一次對一組信號量進行相同或不同的操作。每個P、V操作不限于減1或加1，而是可以加減任何整數。在進程終止時，系統可根據需要自動消除所有被進程操作過的信號量的影響
1．緩沖區采用循環隊列表示，利用頭、尾指針來存放、讀取數據，以及判斷隊列是否為空。緩沖區中數組大小為10；
2．利用隨機函數rand()得到A～Z的一個隨機字符，作為生產者每次生產的數據，存放到緩沖區中；
3.使用shmget()系統調用實現共享主存段的創建，shmget()返回共享內存區的ID。對于已經申請到的共享段，進程需把它附加到自己的虛擬空間中才能對其進行讀寫。
4.信號量的建立采用semget()函數，同時建立信號量的數量。在信號量建立后，調用semctl()對信號量進行初始化，例如本實習中，可以建立兩個信號量SEM_EMPTY、SEM_FULL，初始化時設置SEM_EMPTY為10，SEM_FULL為0。使用操 作信號的函數semop()做排除式操作，使用這個函數防止對共享內存的同時操作。對共享內存操作完畢后采用shmctl()函數撤銷共享內存段。
5.使用循環，創建2個生產者以及2個消費者，采用函數fork()創建一個新的進程。6．一個進程的一次操作完成后，采用函數fflush()刷新緩沖區。7．程序最后使用semctl()函數釋放內存。模擬程序的程序流程圖如下所示： 1.主程序流程圖：
2.生產者進程流程圖
3.消費者進程流程圖
4.P操作流程圖
5.V操作流程圖
四、實現代碼為：
// exet5.cpp //#include “stdafx.h” #include
= {7,10,1,2,10,3,10,4,2,3,10,3,2,1,2,10,1,7,10,1};void build();void LRU();
int main(intargc, char *argv[]){ printf(“Random sequence is as follows:n”);build();printf(“nInvoking LRU Algorithn: n”);LRU();return 0;}
void build(){ inti = 0;for(i=0;i
{ process[i] =(int)(10.0*rand()/(RAND_MAX));printf(“%d ”,process[i]);
} printf(“n”);}
void LRU(){ int flag[mSIZE] = {0};inti = 0, j = 0;int m =-1, n =-1;int max =-1,maxflag = 0;int count = 0;for(i = 0;i
//Find the first free Physical Block
for(j=0;j { if(memery[j] == 0) { m = j;break; } } //Find if there are same processes for(j = 0;j { if(memery[j] == process[i]) { n = j; } } //Find free PB for(j = 0;j { if(flag[j]>maxflag) { maxflag = flag[j];max = j; } } if(n ==-1)// Find no same process { if(m!=-1)// find free PB { memery[m] = process[i];flag[m] = 0;for(j = 0;j <= m;j++) { flag[j]++; } m =-1; } else //NO find free PB { memery[max] = process[i];flag[max] = 0; for(j = 0;j { flag[j]++; } max =-1;maxflag = 0;count++; } } else // Find same process { memery[n] = process[i];flag[n] = 0;if(m!=-1)//find free PB { flag[m] = 0; } for(j = 0;j { flag[j]++; } max =-1;maxflag = 0; n =-1; } for(j = 0;j { printf(“%d ”,memery[j]); } printf(“n”);} printf(“nThe is: %dn”,count);} times of page conversion 五、在虛擬機上的具體操作及結果 執行exe5.c文件 選擇Applications?Acecessories?Terminal,執行文件： 依次預處理?編譯?匯編?連接?執行用文件，編譯通過之后-o執行。報錯！！錯誤顯示為很多頭文件沒有預定義。連續查找之后得知原因是鏈接不上pthread庫 在執行命令后面加上-pthread，即新命令格式為：gcc-oexe5exe5.c–lpthread，重新執行后的結果顯示如下截圖： 其中1表示緩沖區被生產者producer1或者二producer2寫入了Item，0表示沒有寫入數據或者被消費者consumer1或者consumer2消耗掉 六、實驗總結及思考 1、本次實驗是關于生產者與消費者之間互斥和同步的問題。問題的是指是P、V操作，實驗設一個共享緩沖區，生產者和消費者互斥的使用，當一個線程使用緩沖區的時候，另一個讓其等待直到前一個線程釋放緩沖區為止。 2、實驗中包含的知識點很多，包括臨界區資源共享問題、信號量定義、PV操作流程、進程間的通信方式（消息傳遞和共享內存）、進程同步和互斥、信號量機制解決進程之間的同步與互斥問題等等。加深了對于本部分內容的理解 通過本實驗設計，我們對操作系統的P、V進一步的認識，深入的了解P、V操作的實質和其重要性。課本的理論知識進一步闡述了現實中的實際問題。 新教傳教士和近代術語的傳播 作者：余冬林 《光明日報》（2015年09月05日 04版） 近代術語是中國各學科賴以構建的基石。它既是鴉片戰爭以來西學東漸的產物，又為中國學術從傳統四部之學向近代七科之學演進奠定了基礎。1807年9月，英國傳教士馬禮遜抵達廣州，由此揭開以新教傳教士為主角的新一輪西學東漸的序幕。此后，西方諸國新教傳教士相繼來華，在近代術語的生成和傳播中發揮了重要作用。從近代術語的變遷中，我們也不難窺見近代以來中西文化沖突與融合的歷史狀貌。 馬禮遜初抵廣州時，由于清政府厲行禁教政策，使其不敢公開露面，更不用說進行宗教布道和文化傳播。“廣州高度警惕的清朝官員在禁止中國人信仰這一外來宗教方面做得要比禁止鴉片流入成功得多。顯然，他們認為宣揚外國教義遠比單純售賣藥物危險。”（費正清：《新教傳教士著作在中國文化史上的地位》）第二次鴉片戰爭后，禁教令雖然被解除，但新教傳教士很快發現傳教依然步履維艱，不僅因為儒釋道文化與基督教文化的不相容，而且人們往往把傳教士與殖民侵略聯系起來。要改變這種狀況和中國人心目中的“蠻夷”形象，新教傳教士開始了近一個世紀的文化傳播活動。需要指出的是，不僅當時的中國人不理解這些新教傳教士，甚至一些西方人對他們也頗有微詞，如揚州教案發生后，時任英國駐上海領事麥華佗認為傳教士是“一群不切實際、惹事生非的神經質”。 當時，曾有西方人云：“中國語言文字最難為西人所通，即通之亦難將西書之精奧譯至中國。蓋中國文字最古最生而最硬，若以之譯泰西格致（物理、化學等自然科學的總稱）與制造等事，幾成笑談。”（傅蘭雅：《江南制造總局翻譯西書事略》）。英國傳教士傅蘭雅雖然對此不以為然，但是依然要面對中西語言文化的巨大鴻溝。此外，近代西方自然科學門類和名目繁多，而在中國其學其名幾乎都沒有，因此，此類術語的翻譯更為困難。對于術語的翻譯，傅蘭雅等提出了著名的譯名三原則：“沿用中文已有之名、設立新名、編輯中西名詞字匯”。其中創設新名采用三種方法：一是以平常字加偏旁作為新字，仍讀本音，如鎂、矽等，或以不常用字釋以新義為新名，如鉑、鉀、鋅等；二是數個字解釋某物作為新名，并以字數少為妙，如“養氣”“輕氣”“火輪船”等；三是音譯，以官音為主，凡以前譯書已慣用者則襲之（參見傅蘭雅：《江南制造總局翻譯西書事略》）。 受到中國上層敵視的新教傳教士轉而致力于在普通民眾和下層知識分子中開展活動。“那些在1842年前被禁止布道并因此而總要躲避一段時間的新教先驅們不得不借助于書面文字。這與相信鉛印經典只要能到達普通民眾的手里就具有巨大效力這一最早的傳道信念相契合。中國的現實條件則強化了這種寫作偏好。”（費正清：《新教傳教士著作在中國文化史上的地位》）因此，新教傳教士主要通過編纂英漢字典、編寫教科書、創辦報刊、譯述漢文西書等渠道來傳播西學和近代術語亦在情理之中。 編纂英漢字典。為解決語言障礙問題，19世紀20年代以來，入華新教傳教士相繼編纂、出版了多種英漢字典，如馬禮遜的《英華字典》、衛三畏的《英華韻府歷階》等。這些字典大都問世于西學大規模涌入之前，一批政治類新術語如自由、國會、內閣等，自然知識類如陽極、蛋白質、分子等應運而生。馬禮遜及后繼者在英華字典中厘定的術語，“不僅在中國傳播開來，構成中國近代新詞的重要組成部分，而且麥都思、羅存德等的辭典東傳幕末、明治間的日本，被日本各種英和、和英辭典所借鑒。”（馮天瑜：《新語探源——中西日文化互動與近代漢字術語生成》） 編寫教科書。新教傳教士為拓展傳教事業，紛紛以興辦學校作為主要手段。因中西知識體系的差異，新式學校往往會面臨教科書匱乏的困境。為解決這一問題，1895年之前，新教傳教士充當了教科書編寫者的角色。早期來華的傳教士幾乎都有過單獨編寫教科書的經歷，如英國傳教士理雅各為英華書院編寫了《智環啟蒙塾課初步》等教科書。為克服編輯教科書中的困難而加強合作，他們于1877年組建了“益智書會”，專門負責編輯、出版教科書。益智書會總計出版數學、天文、地理、化學、心理、歷史、哲學等各科教科書共98種，20余萬冊，銷往全國各地。此外，還有墨海書館、美華書館、上海土山灣印書館等傳教士出版機構與團體參與了清末教科書的編輯。教科書因其權威性和受眾的廣泛性，在近代術語的厘定和傳播中發揮了重要作用，很多術語因出現在教科書中更容易獲得人們的認可。 創辦報刊。由于清政府的限制，傳教士入華之初只能在廣州、澳門以及東南亞一帶進行傳教活動。近代第一份中文報刊《察世俗每月統記傳》，就是由英國倫敦布道會傳教士米憐于1815年8月在馬六甲創辦刊行的。該刊以傳播基督教教義為主，兼及介紹西方地理、歷史、天文等知識。其中宗教術語的厘定，多沿用早期漢文西書中的譯詞，如圣經、靈魂、耶穌等，但一些天文學術語的翻譯如行星等已有不同。中國境內出現的第一份中文刊物，是普魯士傳教士郭實臘在廣州創辦的《東西洋考每月統記傳》（1833—1835年在廣州，1837—1838年遷往新加坡）。該刊沿用和創譯了一批近代以來具有重要影響的學科術語，如赤道、經緯線、國會、文藝復興等。此外，新教傳教士創辦的報刊還有《遐邇貫珍》《中外新報》《六合叢談》《萬國公報》等。傳教士創辦的中文報刊為吸引中國讀者也兼載部分非宗教性的內容，有的在后來的發展中演變為傳播西學的綜合性報刊如《六合叢談》等，或成為知識性專刊如《格致匯編》等，其中厘定的學科術語甚多，涉及地理、政法、經濟、教育諸領域。 譯述漢文西書。新教傳教士還與中國士人合作，進行了規模空前的西學譯介工作。明清之際由耶穌會士與中國士人合作著譯介紹西學的漢文書籍稱為“早期漢文西書”；清末入華新教傳教士著譯或傳教士與中國士人合作著譯的介紹西學的漢文書籍稱“晚期漢文西書”。概而言之，晚期漢文西書涉及“神理之學”（哲學）、“人生當然之理”（社會科學）、“物理之學”（自然科學）諸部類。（馮天瑜：《新語探源：中西日文化互動與近代漢字術語生成》）據1886年艾約瑟的《西學略述》，可大致得知當時西學所涵蓋的具體學科和門類，主要包括嬰幼兒教育、方言（包括印度、歐洲各國方言等）、教會、文學、理學等。據初步統計，自1811年英國傳教士馬禮遜出版第一本漢文西書，至1911年辛亥革命結束清政府統治，譯出的西學書籍至少在2000種以上（熊月之：《西學東漸與晚清社會》）。在這些漢文西書中，新教傳教士和中國士人共同努力借用或創制了涵蓋各學科領域的大批術語。這些漢文西書術語對近代中國的維新運動等產生了深遠影響。 在清政府學部編訂名詞館出現以前，推動清末術語統一的主要機構是益智書會與博醫會等民間機構。1890年益智書會在術語統一上已有較大進展，最突出的成果就是由傅蘭雅負責的《譯者手冊》全部完成。1904年，狄考文、赫士等負責編纂的《術語辭匯》正式出版，這是對益智書會自成立以來在統一術語方面所做工作的一個全面總結。《術語辭匯》共收錄1.2萬個英文術語和大約1.8萬個相對應的中文術語，涉及微積分、地質學、地理學、天文學、心理學、國際法、神學等50余種門類。博醫會則編纂出版了《英漢醫學詞典》和《醫學字典》等多種醫學術語詞典。這些機構編輯的術語譯名表、術語辭典以及術語命名的原則等，對后來中國術語統一工作的開展有重要的借鑒與參考價值，其中的一些術語譯名也一直沿用至今。不過，雖然傅蘭雅等制定了術語翻譯的三原則，但遺憾的是當時新教傳教士在從事譯介活動時大都并未遵循這些原則，如合信、瑪高溫、偉烈亞力等都按照各自原則譯制新術語，使術語混亂問題并未真正解決。同時文化傳播自有其規律，不以傳播者的主觀意志為轉移，新教傳教士所譯介的政治、經濟、科技等術語及相關知識觀念，不但沒有成為近代中國人膜拜上帝的心理依據和根基，反而成了他們抨擊西方侵略的武器，開眼看世界的中國人在接受西學新知的基礎上開始以更為宏闊的眼光勾勒中國的未來藍圖。 （作者單位：武漢輕工大學藝術與傳媒學院） 賭徒問題實驗報告 一、引言 賭徒問題是針對第四章動態規劃的練習，同時也是對第三章介紹的貝爾曼方程和強化學習的基本知識的實際應用。兩者緊密結合只有充分了解相關內容才能了解實驗經過，才能對強化學習的基本問題有所了解。 二、相關知識介紹 1、馬爾科夫性：能夠保存此狀態的來歷的方式，稱此方式是馬爾科夫的。 也就是s',r，和歷史的st,at,rt,st?1,at?1,...,r1,s0,a0來說，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{在這種情況下，環境和任務是一體的，也都稱為具有馬爾可夫性質。 PS：每個狀態都是有前一個可能的狀態動作對和發生的各個概率計算得來的。 2、值函數：一個策略?是每個狀態s?S以及動作a?A(s)到狀態s下采取動作a的概率?(s,a)的一個映射。通俗地說，在策略?下狀態s的值記為V?(s)，它是從狀態s開始并遵循策略?的期望回報。對MDP而言，我們可以形式化地定義V?(s)為： ??k?V(s)?E?{Rt|st?s}?E????rt?k?1|st?s?，（3.8） ?k?0??其中E?{}表示了agent在遵循策略?之后的期望值。而終止狀態的值總是0。我們把函數V?稱為策略?的狀態值函數（state－value function for policy π）。 類似地，我們定義在策略?下狀態s中采取動作a的值，記為Q(s,a)，作為在策略?從狀態s開始，采取動作a的期望回報: ??k?Q(s,a)?E?{Rt|st?s,at?a}?E????rt?k?1|st?s,at?a? （3.9） ?k?0???我們將Q稱為策略?的動作值函數（action－value function for policy π）。 在強化學習和動態規劃中，值函數的基本性質是它們滿足一定的遞歸關系。對任意策略??和狀態s，在s的值和它可能的后繼狀態值之間，（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') ?其中，動作a是從集合A(s)中得到的，下一狀態s'從集合S中得到的，或者是從情節式任務中的S?中得到的。等式（3.10）是V?的Bellman方程。它表達了一個狀態的值和它的后繼狀態值之間的關系。 公式（3.10）就是貝爾曼方程，而V值就是貝爾曼方程的唯一解。 3、計算值函數：利用動態規劃去計算值函數。找到符合Bellman最優方程 ?的最優值函數V*或Q*，從而得到最優策略。對于所有s?S，a?A(s)，且s'?S，Bellman最優方程如下： 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值的近似解。 三、實驗過程簡介 賭徒問題是一個典型的值迭代問題，值迭代是策略迭代的方法之一。 將貝爾曼最優方程轉換成更新規則就可以得到值迭代。除了策略迭備份需要從所有的動作中選出最大動作以外，值迭代更新等同于策略評估更新。當每次掃描過后V的改動很小的時候就可以停止算法。認為V值已經解出。 以下是題目： 一個賭徒利用硬幣投擲的反正面結果來賭博。假如投擲結果是硬幣的正面朝上，那么他就贏得他所壓的賭注，如果是反面朝上，那么他輸掉他的賭注。當這個賭徒贏滿100美元或者他輸掉他所有的錢時，賭博結束。每一輪投擲，賭徒必須取出他資金的一部分作為賭注，賭注金額必須是整數。這個問題可以表述為一個無折扣的、情節式的有窮馬爾可夫決策過程。狀態就是賭徒所擁有的資金，s?{1,2,?,99}，動作就是下賭注，a?{1,2,?,min(s,100?s)}。除了賭徒達到100美元的目標而獎賞為＋1以外，其他獎賞均為0。狀態－值函數給出每個狀態能夠獲勝的概率。策略就是如何決定每輪取出多少錢去下注。最優策略就是使取得最后勝利的概率最大化。令p代表硬幣正面朝上的概率。假如p已知，那么整個問題也就知道了，并且可以得解，比如通過值迭代求解。圖4.6就是當p?0.4時，值迭代每一輪后值函數的變化情況和得到的最終策略。 以下是算法： 任意初始化V，比如：V(s)?0，對于所有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 ???（一個極小的正數） 輸出一個確定的策略? ?(s)?argmaxa?s'Pss'[Rss'??V(s')] aa根據算法和題目的具體要求得到的C++代碼如下： #include using namespace std;//vector //將V值放在數組中存放，為了方便起見這里V[0]是不使用的！double AF(double S); //a值的計算函數題目中a是a?{1,2,?,min(s,100?s)} double Q(int S,int a); //Q(S,a)動作值函數的計算 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++) //對于1~99個狀態 { } double v=V[S]; //將V值暫時保存下來 i=AF(S); //i用來接收計算出來的a值 for(int a=0;a<=i;a++){ K+=Q(S,a); //貝爾曼最優方程 } V[S]=K;Delta=max(Delta,fabs(v-V[S])); //計算△ } while(Delta //當V的變化一定小的時候結束 for(int i=1;i<=99;i++) //輸出最終的V值也就是貝爾曼方程的cout<<“V[”< //最優解，賭徒問題的最優解。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判斷匯報的值是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;結果顯示: 就一個50是對的，我就無語了。。。 V(s)?maxa?s'Pss'[Rss'??V(s')]aa 其實這個程序就是實現這個公式，我暈啊檢查了幾遍 maxa?s'還沒發現問題，還麻煩老師幫忙看看。我知道這樣不好，但是真的沒招了，感覺這里可能有問題。。。 總結： 通過實驗讓我更加理解貝爾曼方程，對值函數的計算有了進一步的認識。同時學會了用值迭代的方法求出貝爾曼方程的最優解，對V與Q的關系理解更加深刻。V[S]=S狀態下對應不同動作a的所有Q的和。 人工智能——四皇后問題 一、問題描述 四皇后問題 一個4×4國際象棋盤，依次放入四個皇后，條件：每行、每列及對角線上只允許出現一枚棋子。 設：DATA=L（表）x∈L x ∈﹛i j﹜ 1≤ i, j ≤4 其中：i j 表示棋子所在行列 如：24 表示第二行第四列有一枚棋子 ∵棋盤上可放入的棋子數為0 ～ 4 個 ∴L表中的元素數為0 ～ 4 個，即 Length L = 0 ～ 4，如圖A ﹛12，24，31，43 ﹜ 定義規則： if 1≤ i ≤4 and Length DATA = i －1 then APPEND(DATA(ij))1≤ j ≤4 ① 對于任一行i，1≤ j ≤4 表明每行有四條規則。 比如第一行：R11，R12，R13，R14 ② 棋盤中共有四行，所以共有16條規則。 即： R11，R12，R13，R14 R21，R22，R23，R24 R31，R32，R33，R34 R41，R42，R43，R44 ③ 16條規則中，哪些是當前可用規則，取決于DATA的長度，即：DATA中的元素個數。換言之，每次只能將一個棋子放在當前行的下一行。 二、回溯法搜索策略圖 討論： 上述算法產生22次回溯，原因在于規則自然順序排列，沒考慮任何智能因素。改進算法 定義對角線函數：diag(i,j)：過ij點最長的對角線長度值。 規定：① 如果： diag(i,k)≤ diag(i,j)則規則排列次序為： Rik，Rij 同一行四條規則中，對角線函數值小的排在前面 ② 如果：diag(i,k)＝ diag(i,j)則規則排列次序為： Rij，Rik j ＜ k 對角線長度相等的規則按照字母排列順序排序 討論： ① 利用局部知識排列規則是有效的。 ② BACKTRACK算法對重復出現的狀態沒有判斷，所以可能造成出現死循環。③ 沒有對搜索深度加以限制，可能造成搜索代價太大。 三、算法描述 回溯法——在約束條件下先序遍歷，并在遍歷過程中剪去那些不滿足條件的分支。 使用回溯算法求解的問題特征，求解問題要分為若干步，且每一步都有幾種可能的選擇，而且往往在某個選擇不成功時需要回頭再試另外一種選擇，如果到達求解目標則每一步的選擇構成了問題的解，如果回頭到第一步且沒有新的選擇則問題求解失敗。 在回溯策略中，也可以通過引入一些與問題相關的信息來加快搜索解的速度。對于皇后問題來說，由于每一行、每一列和每一個對角線，都只能放一個皇后，當一個皇后放到棋盤上后，不管它放在棋盤的什么位置，它所影響的行和列方向上的棋盤位置是固定的，因此在行、列方面沒有什么信息可以利用。但在不同的位置，在對角線方向所影響的棋盤位置數則是不同的。可以想象，如果把一個皇后放在棋盤的某個位置后，它所影響的棋盤位置數少，那么給以后放皇后留下的余地就太大，找到解的可能性也大；反之留有余地就小，找到解的可能性也小。 四、算法流程圖 五、源程序 #include //存儲第i行對應的列的值，這樣的(i,j)值滿足當前棋盤上的皇后不能互相攻擊。 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) //判斷左右對角線 return 0; } return 1;} void get_position(int i) //處在第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); //轉換到下一個狀態，即下一行 col[i]=0; //回溯到當前狀態，重置列和棋盤的值 board[i][u]=0; } } } } main(){ printf(“%c是皇后!nn”,001);get_position(0);printf(“一共有%d種方法！n”,t);} 六、結果截圖 七、總結——心得體會 通過對四皇后問題的編程學習，讓我對搜索策略更深層次的理解，尤其能比較熟練掌握回溯策略——首先將規則給出一個固定的排序，在搜索時，對當前狀態（搜索開始時，當前狀態是初始狀態）依次檢測每一條規則，在當前狀態未使用過的規則中找到第一條可應用規則，應用于當前狀態，得到的新狀態重新設置為當前狀態，并重復以上搜索。如果當前狀態無規則可用，或者所有規則已經被試探過仍未找到問題的解，則將當前狀態的前一個狀態（即直接生成該狀態的狀態）設置為當前狀態。重復以上搜索，直到找到問題的解，或者試探了所有可能后仍找不到問題的解為止。 同時，在整個編程學習過程中，使得我對人工智能感到越來越多的趣味性（例如四皇后問題上升到n皇后如何求解），更引起我對學習人工智能這門課程的積極性。第三篇：新教傳教士和近代術語的傳播
第四篇：賭徒問題實驗報告
第五篇：四皇后問題實驗報告
點擊咨詢 