激勵勢場算法的復雜性研究.pdf

1、當面對求解一個問題的新算法的時候，我們的興趣在于形成這樣一種粗略的認識：新算法預期能有多好，對于同一個問題它比其他的算法如何。計算復雜性研究能夠提供這種認識。對算法的分析能夠幫助我們對算法更深入地理解，并能夠提出有根有據(jù)的改進。尤為重要的是，正確分析所需要的仔細全面的審查常常使得算法更好和更有效地實現(xiàn)。 激勵學習因為具有較強的在線自適應性以及對復雜系統(tǒng)的自學習能力，受到機器人導航研究者的關注。目前，激勵學習對于許多現(xiàn)實的問題，如

2、大尺度和部分可觀測環(huán)境，仍然是沒有解決的問題。這些問題采用傳統(tǒng)的算法很難滿意地解決。通過利用人工勢場將激勵學習問題轉(zhuǎn)換為路勁規(guī)劃問題。然后為解決人工勢場中的局部最小問題，應用虛擬水流法的概念提出的一種新的人工勢場算法。實驗結果表明該方法在激勵學習系統(tǒng)中是有效的。但只有當解析的結果與經(jīng)驗研究一致的時候，我們才會確信算法的合理性以及分析過程的正確性。為了說明該方法的合理性和正確性，本論文將從解析的結果與經(jīng)驗研究兩方面對此算法進行了分析和研究