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

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

【摘要】：智能規(guī)劃是隸屬于人工智能領(lǐng)域的一個(gè)重要研究方向,近年來受到許多學(xué)者的關(guān)注。而不確定規(guī)劃則是其中的一個(gè)重要分支。近幾年來,有較多針對(duì)不確定規(guī)劃的研究,但由于在求規(guī)劃問題的解時(shí),缺少引導(dǎo)信息,會(huì)導(dǎo)致許多無用狀態(tài)和動(dòng)作被搜索,造成冗余計(jì)算。因此在求規(guī)劃解之前,先對(duì)不確定狀態(tài)轉(zhuǎn)移系統(tǒng)中的狀態(tài)之間的關(guān)系進(jìn)行預(yù)處理,找出它們之間的可達(dá)關(guān)系,這樣能加快對(duì)于規(guī)劃問題的求解。有學(xué)者運(yùn)用鄰接矩陣來表示不確定狀態(tài)轉(zhuǎn)移系統(tǒng),運(yùn)用矩陣自乘來模擬系統(tǒng)的中控制器的位置轉(zhuǎn)移,能求出狀態(tài)之間的可達(dá)關(guān)系,但該類算法對(duì)于規(guī)模較大的系統(tǒng)效率比較低。因此,本文仔細(xì)分析了現(xiàn)有算法的優(yōu)勢(shì)之處,找出了其存在的不足之處,設(shè)計(jì)了一種全新的求可達(dá)關(guān)系算法,能高效的求解大規(guī)模不確定狀態(tài)轉(zhuǎn)移系統(tǒng)的可達(dá)關(guān)系。并對(duì)不確定系統(tǒng)中可能存在動(dòng)作變化(確定動(dòng)作因某種因素?zé)o法執(zhí)行),設(shè)計(jì)了一種局部更新其可達(dá)關(guān)系算法,避免了重新求解狀態(tài)之間的可達(dá)關(guān)系,提高了效率。具體研究?jī)?nèi)容如下:1.參考了計(jì)算機(jī)網(wǎng)絡(luò)中的RIP路由協(xié)議,提出了用信息傳遞法來求解可達(dá)關(guān)系,仍舊用鄰接矩陣表示不確定狀態(tài)轉(zhuǎn)移系統(tǒng),并且將每一行中的可達(dá)關(guān)系視為其他狀態(tài)到達(dá)該狀態(tài)的可達(dá)信息;通過狀態(tài)之間的信息的收集、狀態(tài)之間信息傳遞、狀態(tài)自身信息的更新,分三個(gè)階段求得不確定系統(tǒng)的狀態(tài)可達(dá)關(guān)系,避免了大量的矩陣運(yùn)算,并通過分析算法的時(shí)間復(fù)雜度,從理論上證明了該算法的高效性。與此同時(shí),對(duì)每個(gè)狀態(tài)的可達(dá)信息進(jìn)行標(biāo)記,避免了對(duì)不確定規(guī)劃系統(tǒng)是否有回路進(jìn)行分類及設(shè)計(jì)不同的算法,降低了算法實(shí)現(xiàn)的難度。最后通過實(shí)例以及實(shí)驗(yàn),運(yùn)用信息傳遞法求解非循環(huán)和循環(huán)的不確定狀態(tài)轉(zhuǎn)移系統(tǒng)的可達(dá)關(guān)系,進(jìn)行了詳細(xì)的說明。2.提出了針對(duì)非循環(huán)的不確定狀態(tài)轉(zhuǎn)移系統(tǒng)在確定動(dòng)作無法執(zhí)行的情況下,維護(hù)該系統(tǒng)可達(dá)關(guān)系的算法。在信息傳遞法的基礎(chǔ)之上,提出了對(duì)于非循環(huán)不確定狀態(tài)轉(zhuǎn)移系統(tǒng)的最小信息傳遞集(簡(jiǎn)稱MIDS),分析了MIDS的性質(zhì)。通過MIDS,可以快速判斷無法執(zhí)行的確定動(dòng)作是否會(huì)對(duì)系統(tǒng)的可達(dá)關(guān)系產(chǎn)生影響。同時(shí),對(duì)于每個(gè)狀態(tài)的可達(dá)信息建立索引,通過索引,可以實(shí)現(xiàn)對(duì)系統(tǒng)的可達(dá)關(guān)系進(jìn)行局部更新,從而避免了對(duì)該系統(tǒng)狀態(tài)之間可達(dá)關(guān)系的重新計(jì)算,提高了求可達(dá)關(guān)系的效率。
【關(guān)鍵詞】：不確定規(guī)劃 可達(dá)關(guān)系 信息傳遞 可達(dá)關(guān)系維護(hù)
【學(xué)位授予單位】：湘潭大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：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ī)劃的背景知識(shí)12-16
• 2.1 不確定規(guī)劃12-13
• 2.2 基于模型檢測(cè)的不確定規(guī)劃13-15
• 2.2.1 模型檢測(cè)的發(fā)展與運(yùn)用13-14
• 2.2.2 模型檢測(cè)的基本概念14-15
• 2.3 本章小結(jié)15-16
• 第三章 信息傳遞法算法16-37
• 3.1 相關(guān)概念18-20
• 3.2 信息傳遞法求可達(dá)關(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 算法實(shí)例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 算法實(shí)驗(yàn)33-36
• 3.6 本章小節(jié)36-37
• 第四章 可達(dá)關(guān)系維護(hù)的算法37-52
• 4.1 研究維護(hù)可達(dá)關(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 維護(hù)非循環(huán)不確定狀態(tài)轉(zhuǎn)移系統(tǒng)可達(dá)關(guān)系的方法41-44
• 4.3.1 維護(hù)可達(dá)關(guān)系的基本思路41-42
• 4.3.2 判斷可達(dá)關(guān)系是否發(fā)生變化42-43
• 4.3.3 局部更新可達(dá)關(guān)系的方法43-44
• 4.4 維護(hù)非循環(huán)不確定系統(tǒng)可達(dá)關(guān)系的算法及復(fù)雜度分析44-46
• 4.4.1 求最小信息傳遞集合算法44-45
• 4.4.2 局部更新算法45
• 4.4.3 算法復(fù)雜度分析45-46
• 4.5 實(shí)例分析及算法性能分析46-51
• 4.5.1 求最小信息傳遞集合舉例46-48
• 4.5.2 維護(hù)可達(dá)關(guān)系舉例48-50
• 4.5.3 實(shí)驗(yàn)性能比較50-51
• 4.6 本章小節(jié)51-52
• 第五章 總結(jié)與期望52-53
• 參考文獻(xiàn)53-57
• 致謝57-58
• 附錄A （攻讀碩士學(xué)位期間發(fā)表的論文）58-59
• 附錄B （攻讀碩士學(xué)位期間參與的科研項(xiàng)目）59
• 附錄C （攻讀碩士學(xué)位期間獲獎(jiǎng)情況）59

【參考文獻(xiàn)】

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

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

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

，

本文編號(hào)：1094155