本文關(guān)鍵詞：信息傳遞法求解與維護不確定狀態(tài)系統(tǒng)的可達關(guān)系

  更多相關(guān)文章： 不確定規(guī)劃 可達關(guān)系 信息傳遞 可達關(guān)系維護

【摘要】：智能規(guī)劃是隸屬于人工智能領(lǐng)域的一個重要研究方向,近年來受到許多學(xué)者的關(guān)注。而不確定規(guī)劃則是其中的一個重要分支。近幾年來,有較多針對不確定規(guī)劃的研究,但由于在求規(guī)劃問題的解時,缺少引導(dǎo)信息,會導(dǎo)致許多無用狀態(tài)和動作被搜索,造成冗余計算。因此在求規(guī)劃解之前,先對不確定狀態(tài)轉(zhuǎn)移系統(tǒng)中的狀態(tài)之間的關(guān)系進行預(yù)處理,找出它們之間的可達關(guān)系,這樣能加快對于規(guī)劃問題的求解。有學(xué)者運用鄰接矩陣來表示不確定狀態(tài)轉(zhuǎn)移系統(tǒng),運用矩陣自乘來模擬系統(tǒng)的中控制器的位置轉(zhuǎn)移,能求出狀態(tài)之間的可達關(guān)系,但該類算法對于規(guī)模較大的系統(tǒng)效率比較低。因此,本文仔細分析了現(xiàn)有算法的優(yōu)勢之處,找出了其存在的不足之處,設(shè)計了一種全新的求可達關(guān)系算法,能高效的求解大規(guī)模不確定狀態(tài)轉(zhuǎn)移系統(tǒng)的可達關(guān)系。并對不確定系統(tǒng)中可能存在動作變化(確定動作因某種因素?zé)o法執(zhí)行),設(shè)計了一種局部更新其可達關(guān)系算法,避免了重新求解狀態(tài)之間的可達關(guān)系,提高了效率。具體研究內(nèi)容如下:1.參考了計算機網(wǎng)絡(luò)中的RIP路由協(xié)議,提出了用信息傳遞法來求解可達關(guān)系,仍舊用鄰接矩陣表示不確定狀態(tài)轉(zhuǎn)移系統(tǒng),并且將每一行中的可達關(guān)系視為其他狀態(tài)到達該狀態(tài)的可達信息;通過狀態(tài)之間的信息的收集、狀態(tài)之間信息傳遞、狀態(tài)自身信息的更新,分三個階段求得不確定系統(tǒng)的狀態(tài)可達關(guān)系,避免了大量的矩陣運算,并通過分析算法的時間復(fù)雜度,從理論上證明了該算法的高效性。與此同時,對每個狀態(tài)的可達信息進行標(biāo)記,避免了對不確定規(guī)劃系統(tǒng)是否有回路進行分類及設(shè)計不同的算法,降低了算法實現(xiàn)的難度。最后通過實例以及實驗,運用信息傳遞法求解非循環(huán)和循環(huán)的不確定狀態(tài)轉(zhuǎn)移系統(tǒng)的可達關(guān)系,進行了詳細的說明。2.提出了針對非循環(huán)的不確定狀態(tài)轉(zhuǎn)移系統(tǒng)在確定動作無法執(zhí)行的情況下,維護該系統(tǒng)可達關(guān)系的算法。在信息傳遞法的基礎(chǔ)之上,提出了對于非循環(huán)不確定狀態(tài)轉(zhuǎn)移系統(tǒng)的最小信息傳遞集(簡稱MIDS),分析了MIDS的性質(zhì)。通過MIDS,可以快速判斷無法執(zhí)行的確定動作是否會對系統(tǒng)的可達關(guān)系產(chǎn)生影響。同時,對于每個狀態(tài)的可達信息建立索引,通過索引,可以實現(xiàn)對系統(tǒng)的可達關(guān)系進行局部更新,從而避免了對該系統(tǒng)狀態(tài)之間可達關(guān)系的重新計算,提高了求可達關(guān)系的效率。
【關(guān)鍵詞】：不確定規(guī)劃 可達關(guān)系 信息傳遞 可達關(guān)系維護
【學(xué)位授予單位】：湘潭大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TP18
【目錄】：

• 摘要4-5
• ABSTRACT5-9
• 第一章 引言9-12
• 1.1 智能規(guī)劃的研究現(xiàn)狀以及意義9-11
• 1.1.1 經(jīng)典智能規(guī)劃10-11
• 1.1.2 非經(jīng)典智能規(guī)劃11
• 1.2 本文主要內(nèi)容以及章節(jié)安排11-12
• 1.2.1 主要內(nèi)容11
• 1.2.2 章節(jié)安排11-12
• 第二章 不確定規(guī)劃的背景知識12-16
• 2.1 不確定規(guī)劃12-13
• 2.2 基于模型檢測的不確定規(guī)劃13-15
• 2.2.1 模型檢測的發(fā)展與運用13-14
• 2.2.2 模型檢測的基本概念14-15
• 2.3 本章小結(jié)15-16
• 第三章 信息傳遞法算法16-37
• 3.1 相關(guān)概念18-20
• 3.2 信息傳遞法求可達關(guān)系20-24
• 3.2.1 信息傳遞法步驟說明20-23
• 3.2.2 信息傳遞方法的正確性23-24
• 3.3 信息傳遞算法及復(fù)雜度分析24-27
• 3.3.1 信息傳遞算法24-26
• 3.3.2 信息傳遞算法復(fù)雜度分析26-27
• 3.3.3 性能比較27
• 3.4 算法實例27-33
• 3.4.1 非循環(huán)的不確定狀態(tài)轉(zhuǎn)移系統(tǒng)27-30
• 3.4.2 循環(huán)的不確定狀態(tài)轉(zhuǎn)移系統(tǒng)30-33
• 3.5 算法實驗33-36
• 3.6 本章小節(jié)36-37
• 第四章 可達關(guān)系維護的算法37-52
• 4.1 研究維護可達關(guān)系算法的意義37-38
• 4.2 相關(guān)概念38-41
• 4.2.1 相關(guān)定義38-40
• 4.2.2 最小信息傳遞集合的性質(zhì)40-41
• 4.3 維護非循環(huán)不確定狀態(tài)轉(zhuǎn)移系統(tǒng)可達關(guān)系的方法41-44
• 4.3.1 維護可達關(guān)系的基本思路41-42
• 4.3.2 判斷可達關(guān)系是否發(fā)生變化42-43
• 4.3.3 局部更新可達關(guān)系的方法43-44
• 4.4 維護非循環(huán)不確定系統(tǒng)可達關(guān)系的算法及復(fù)雜度分析44-46
• 4.4.1 求最小信息傳遞集合算法44-45
• 4.4.2 局部更新算法45
• 4.4.3 算法復(fù)雜度分析45-46
• 4.5 實例分析及算法性能分析46-51
• 4.5.1 求最小信息傳遞集合舉例46-48
• 4.5.2 維護可達關(guān)系舉例48-50
• 4.5.3 實驗性能比較50-51
• 4.6 本章小節(jié)51-52
• 第五章 總結(jié)與期望52-53
• 參考文獻53-57
• 致謝57-58
• 附錄A （攻讀碩士學(xué)位期間發(fā)表的論文）58-59
• 附錄B （攻讀碩士學(xué)位期間參與的科研項目）59
• 附錄C （攻讀碩士學(xué)位期間獲獎情況）59

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前2條

1 黃麗芳;文中華;胡雨隆;吳正成;;不確定規(guī)劃中狀態(tài)循環(huán)可達關(guān)系的求解方法[J];計算機應(yīng)用研究;2013年09期

2 文中華;黃巍;劉任任;姜云飛;;模型檢測規(guī)劃中的狀態(tài)之間的可達關(guān)系研究[J];計算機學(xué)報;2012年08期

，

本文編號：1094155