冪等半環(huán)上矩陣正閉包的一個(gè)計(jì)算方法.pdf

1、求矩陣的逆、最短路徑問題和求二元關(guān)系的傳遞閉包是科學(xué)計(jì)算領(lǐng)域中的三個(gè)基本問題，它們?cè)谟?jì)算機(jī)科學(xué)與工程中有著重要的實(shí)踐意義。Gaussian消元法、Floyd算法和Warshall算法分別是這三個(gè)問題的經(jīng)典算法。1971年，Carré發(fā)現(xiàn)這三個(gè)算法在結(jié)構(gòu)上非常相似，并基于半環(huán)代數(shù)理論提出了它們的統(tǒng)一形式——Gauβ-Jordan消元法。1977年，Carré和Lehmann等抽象出求矩陣的逆、最短路徑問題、求二元關(guān)系的傳遞閉包和正則語言的

2、有理表示問題的本質(zhì)特征，正式提出了代數(shù)距離問題。
　　代數(shù)距離問題可以轉(zhuǎn)化為計(jì)算半環(huán)上的矩陣的正閉包（即其所有正數(shù)次冪的和）的問題。本文的主要內(nèi)容是考慮一類矩陣的正閉包的計(jì)算方法。本文首先引入了矩陣圈非負(fù)的概念，接著給出了冪等半環(huán)上的矩陣圈非負(fù)的充分與必要條件以及計(jì)算圈非負(fù)矩陣的正閉包的方法，再依據(jù)該方法設(shè)計(jì)了時(shí)間復(fù)雜度為O(n3)的Plus_Closure_ of_ Matrix算法（其中n為矩陣的階數(shù)）。最后，本文還考察了Pl