首頁 > 產(chǎn)品 > 知識 > Prim，prim算法

Prim，prim算法

來源：整理時間：2023-10-07 11:46:35 編輯：智能門戶手機(jī)版

本文目錄一覽

1，prim算法
2，什么是普利姆算法
3，Prim算法求大牛通俗易懂地解釋下為什么成立
4，音標(biāo)prim怎么讀
5，怎么記下prim是呆板的意思trim是整齊的意思啊
6，Prim算法的實(shí)現(xiàn)過程

1，prim算法

不會改變。因?yàn)槊看味际亲援?dāng)前點(diǎn)向外搜索，每個樹的分支搜索，MIX或者M(jìn)AX值。求全部路徑最短 OR 最長這是萬全之策喔

prim算法

2，什么是普利姆算法

Prim算法：是圖的最小生成樹的一種構(gòu)造算法。假設(shè) WN=(V,如果看不懂還可以找一本數(shù)據(jù)結(jié)構(gòu)的書看，這個算法挺簡單的。btw：其實(shí)你有空問，應(yīng)該有空百度啊~百度百科就有了。懶得寫，我還是直接從百度copy過來的~

構(gòu)造最小生成樹的一種算法，具體過程請參見數(shù)據(jù)結(jié)構(gòu)的書籍

什么是普利姆算法

3，Prim算法求大牛通俗易懂地解釋下為什么成立

不會改變。因?yàn)槊看味际亲援?dāng)前點(diǎn)向外搜索，每個樹的分支搜索，mix或者max值。求全部路徑最短 or 最長這是萬全之策喔

prim算法就是把點(diǎn)分成兩個集合，一個集合里面包含已經(jīng)加入生成樹的點(diǎn)，另一個包含未加入的，然后不斷在兩個集合之間找最短的邊，直到所有的點(diǎn)都加入到生成樹中，這時候就構(gòu)成了最小生成樹。

Prim算法求大牛通俗易懂地解釋下為什么成立

4，音標(biāo)prim怎么讀

1 premium [?pri?m??m] [?prim??m] 2 supreme [su??pri?m] [su?prim] 3 prima [?pri?m?] [?prim?] 4 premed [?pri?med] [pri?m?d] 5 primavera

期待看到有用的回答！

5，怎么記下prim是呆板的意思trim是整齊的意思啊

rim——邊，邊緣t（take 拿掉） + rim（邊緣）——trim（拿掉邊緣，“v.修剪，n.整齊”）p（put 安置） + rim（邊緣）——prim（總是放在邊緣地方，“a.拘謹(jǐn)?shù)?，呆板的”）其?shí)這兩個單詞比較一下多看幾遍就認(rèn)識了，一味追求花哨的記法有點(diǎn)舍本求末的味道，呵呵。。不過我的答案希望對你有幫助。。

你好！p開頭的就像一個人流鼻涕，特傻，特呆記住這個就不會混淆了如有疑問，請追問。

6，Prim算法的實(shí)現(xiàn)過程

G=（V,E）①初始化：讀入的數(shù)據(jù)用鄰接矩陣x存儲，一個一維布爾型數(shù)組chosen，記錄第i個節(jié)點(diǎn)是否已選，初始值除1外全部設(shè)為false，記錄權(quán)值的變量cost賦值為0；以下②到④循環(huán)執(zhí)行v-1次（每次生成一條邊，運(yùn)行（點(diǎn)的個數(shù)減1）次后，生成一棵最小生成樹）：②臨時變量p賦值為無限大，用于記錄當(dāng)前最小值；③二重循環(huán)（外循環(huán)i，內(nèi)循環(huán)j）掃描鄰接矩陣：如果chosen[i]=true（也就是說第i個點(diǎn)已選），那么掃描x[i]，如果not(chosen[j])（也就是說第j個點(diǎn)未選），那么如果x[i,j]<p，那么p賦值為x[i,j],臨時變量q賦值為j;④把cost賦值為cost+o，把chosen[q]賦值為true（也就是說第j個點(diǎn)已選）；⑤輸出cost。一、以上給出具體的運(yùn)行過程。這個算法的策略就是貪心，和dijkstra差不多，每次都選擇未選的邊中權(quán)值最小的那一條，直到生成最小生成樹。用chosen的目的就是保證生成過程中沒有環(huán)出現(xiàn)，也就是說保證選擇的邊不會通向一個已經(jīng)包含在生成樹中的點(diǎn)。二、這個只輸出最小生成樹的每條邊權(quán)值之和，如果要輸出整棵最小生成樹，加一個[1..n,1..2]的數(shù)組，在第④步的時候把每次選的邊記錄下來就可以了。三、用小頂堆在第③步優(yōu)化一下的話就不用每次都掃描那么多邊了，只不過建堆維護(hù)堆代碼寫起來很麻煩。四、prim適合用于比較稠密的網(wǎng)，點(diǎn)數(shù)和邊數(shù)差不多的時候效率很惡心，一般都用kruskal。

Prim算法，是指圖論中的一種算法，可在加權(quán)連通圖里搜索最小生成樹。意即由此算法搜索到的邊子集所構(gòu)成的樹中，不但包括了連通圖里的所有頂點(diǎn)，且其所有邊的權(quán)值之和亦為最小。該算法于1930年由捷克數(shù)學(xué)家沃伊捷赫·亞爾尼克發(fā)現(xiàn)，并在1957年由美國計(jì)算機(jī)科學(xué)家羅伯特·普里姆獨(dú)立發(fā)現(xiàn)，1959年，艾茲格·迪科斯徹再次發(fā)現(xiàn)了該算法。因此，在某些場合，普里姆算法又被稱為DJP算法、亞爾尼克算法或普里姆亞爾尼克算法。

有一個背包，背包容量是m=150。有7個物品，物品可以分割成任意大小。要求盡可能讓裝入背包中的物品總價值最大，但不能超過總?cè)萘俊?物品 a b c d e f g 重量 35 30 60 50 40 10 25 價值 10 40 30 50 35 40 30 分析：目標(biāo)函數(shù)： ∑pi最大約束條件是裝入的物品總重量不超過背包容量：∑wi<=m( m=150) （1）根據(jù)貪心的策略，每次挑選價值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？（2）每次挑選所占重量最小的物品裝入是否能得到最優(yōu)解？（3）每次選取單位重量價值最大的物品，成為解本題的策略。 ? 值得注意的是，貪心算法并不是完全不可以使用，貪心策略一旦經(jīng)過證明成立后，它就是一種高效的算法。貪心算法還是很常見的算法之一，這是由于它簡單易行，構(gòu)造貪心策略不是很困難。可惜的是，它需要證明后才能真正運(yùn)用到題目的算法中。一般來說，貪心算法的證明圍繞著：整個問題的最優(yōu)解一定由在貪心策略中存在的子問題的最優(yōu)解得來的。對于例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：（1）貪心策略：選取價值最大者。反例： w=30 物品：a b c 重量：28 12 12 價值：30 20 20 根據(jù)策略，首先選取物品a，接下來就無法再選取了，可是，選取b、c則更好。（2）貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。（3）貪心策略：選取單位重量價值最大的物品。反例： w=30 物品：a b c 重量：28 20 10 價值：28 20 10 根據(jù)策略，三種物品單位重量價值一樣，程序無法依據(jù)現(xiàn)有策略作出判斷，如果選擇a，則答案錯誤。注:貪心算法當(dāng)然也有正確的時候。求最小生成樹的prim算法和kruskal算法都是漂亮的貪心算法。所以需要說明的是，貪心算法可以與隨機(jī)化算法一起使用，具體的例子就不再多舉了。（因?yàn)檫@一類算法普及性不高，而且技術(shù)含量是非常高的，需要通過一些反例確定隨機(jī)的對象是什么，隨機(jī)程度如何，但也是不能保證完全正確，只能是極大的幾率正確）

貪心過程.首先,把圖中的點(diǎn)分成兩種,已連通和未連通的,我把它們分別稱為"黑"和"白"點(diǎn).一開始時,圖中全是白點(diǎn),沒有黑點(diǎn).算法的第一步,隨機(jī)選出一個白點(diǎn),染成黑色.然后開始一個重復(fù)的過程:從當(dāng)前圖的邊中尋找這樣的一些邊:它的其中一個端點(diǎn)是黑點(diǎn),而另一個端點(diǎn)是一個白點(diǎn). 我們可以把這類邊稱為"可擴(kuò)展邊". 然后算法需要從所有的可擴(kuò)展邊之中選出權(quán)值最小的一條.把這條可擴(kuò)展邊加入生成樹之中,且把這條邊的白色端點(diǎn)染成黑色.重復(fù)這個過程,直到全部的節(jié)點(diǎn)都為黑色.算法可以優(yōu)化的地方是,在選擇權(quán)值最小的可行邊時可以使用堆.