Grobner基理論在最短路徑問(wèn)題中的應(yīng)用

在最短路徑問(wèn)題中,若連通圖中相鄰節(jié)點(diǎn)對(duì)xi和xj間的路徑長(zhǎng)為aij,則節(jié)點(diǎn)之間的關(guān)系可用多項(xiàng)式xi-xj-aij描述,把所有的這種多項(xiàng)式以終點(diǎn)所表示的項(xiàng)為首項(xiàng)歸納和排序得到集合F,若存在最短路徑供選擇,則F生成理想的Gr?bner基為{1}. 因此,求節(jié)點(diǎn)xm到xk的最短路徑,可用多項(xiàng)式xk-xm對(duì)F中的元素約化,所得到的一個(gè)常數(shù)就是這條可達(dá)路徑的長(zhǎng)度;若有多條路徑可供選擇,則每條路徑對(duì)應(yīng)一個(gè)常數(shù),所有這些常數(shù)中的最小數(shù)就是最短路徑的長(zhǎng)度.

作 者： 陳小松 彭豐富   作者單位： 中南大學(xué),數(shù)學(xué)科學(xué)與計(jì)算技術(shù)學(xué)院,湖南,長(zhǎng)沙,410083  刊 名： 中南工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版)  ISTIC EI PKU 英文刊名： JOURNAL OF CENTRAL SOUTH UNIVERSITY OF TECHNOLOGY(NATURAL SCIENCE)  年，卷(期)： 2002 33(6)  分類(lèi)號(hào)： O157.6 O51.26  關(guān)鍵詞： 最短路徑   Gr?bner基   約化  

【Grobner基理論在最短路徑問(wèn)題中的應(yīng)用】相關(guān)文章：

《數(shù)形結(jié)合在解題中的應(yīng)用》電子教案04-25

社會(huì)交換理論在秘書(shū)公關(guān)中的應(yīng)用11-26

端午最短寄語(yǔ)11-02

語(yǔ)文手抄報(bào)：強(qiáng)化理論在語(yǔ)文教學(xué)的應(yīng)用07-01

臨床路徑總結(jié)11-19

《最佳路徑》課文03-05

《最佳路徑》教案04-25

《最佳路徑》教案03-06

最短的辭職書(shū)范文02-23

最短的晚安句子（精選140句）09-19