Primin algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 15.6.2020 tarkistetusta versiosta . tarkastukset vaativat 11 muokkausta .

Primin algoritmi on algoritmi painotetun yhdistetyn suuntaamattoman graafin minimivirittävän puun muodostamiseksi . Algoritmin löysi ensimmäisen kerran vuonna 1930 tšekkiläinen matemaatikko Wojciech Jarnik , myöhemmin Robert Prim vuonna 1957 ja itsenäisesti E. Dijkstra vuonna 1959.

Kuvaus

Algoritmin syöte on yhdistetty ohjaamaton graafi. Jokaiselle reunalle sen hinta on asetettu.

Ensin otetaan mielivaltainen kärkipiste ja löydetään reuna, joka liittyy tähän kärkeen ja jolla on vähiten kustannukset. Löytynyt reuna ja sen yhdistämät kaksi kärkeä muodostavat puun. Sitten otetaan huomioon graafin reunat, joiden toinen pää on jo puuhun kuuluva kärki ja toinen ei; näistä reunoista valitaan edullisimman hinnan reuna. Kussakin vaiheessa valittu reuna lisätään puuhun. Puu kasvaa, kunnes kaikki alkuperäisen graafin kärjet ovat lopussa.

Algoritmin tulos on vähimmäiskustannusten kattava puu.

Esimerkki

Valittujen pisteiden joukko U	Reuna (u, v)	Joukko valitsemattomia pisteitä V \ U	Kuvaus
{}		{A,B,C,D,E,F,G}	Alkuperäinen painotettu kaavio. Reunojen vieressä olevat numerot osoittavat niiden painot, joita voidaan ajatella kärkien välisinä etäisyyksinä.
{D}	(D,A) = 5V (D,B) = 9 (D,E) = 15 (D,F) = 6	{A,B,C,E,F,G}	Huippupiste D valitaan mielivaltaisesti alkupisteeksi . Kukin pisteistä A , B , E ja F on yhdistetty D :hen yhdellä reunalla. Vertex A on lähinnä D :tä ja valitaan toiseksi kärjeksi yhdessä reunan AD kanssa .
{ILMOITUS}	(D,B) = 9 (D,E) = 15 (D,F) = 6V (A,B) = 7	{B,C,E,F,G}	Seuraava kärkipiste on lähinnä valittua D- tai A- pistettä . B on 9 :n päässä D :stä ja 7:n päässä A :sta . Etäisyys E :hen on 15 ja F :hen on 6. F on lähin kärki, joten se sisältyy puuhun F yhdessä reunan DF kanssa .
{A,D,F}	(D,B) = 9 (D,E) = 15 (A,B) = 7 V (F,E) = 8 (F,G) = 11	{B,C,E,G}	Vastaavasti valitaan kärki B , joka on 7 :n päässä A :sta.
{A,B,D,F}	(B,C) = 8 (B,E) = 7 V (D,B) = 9 silmukkaa (D,E) = 15 (F,E) = 8 (F,G) = 11	{C,E,G}	Tässä tapauksessa on mahdollista valita joko C tai E tai G. C on 8 päässä B :stä , E on 7 päässä B :stä ja G on 11 päässä F :stä. E on lähin kärkipiste, joten E ja reuna BE valitaan .
{A,B,D,E,F}	(B,C) = 8 (D,B) = 9 jaksoa (D,E) = 15 jaksoa (E,C) = 5 V (E,G) = 9 (F,E) = 8 jaksoa (F,G ) ) = 11	{C,G}	Vain kärjet C ja G ovat saatavilla täältä . Etäisyys E :stä C :hen on 5 ja G :stä 9. Valitaan kärki C ja reuna EC .
{A B C D E F}	(B,C) = 8 silmukkaa (D,B) = 9 silmukkaa (D,E) = 15 silmukkaa (E,G) = 9 V (F,E) = 8 silmukkaa (F,G) = 11	{G}	Ainoa jäljellä oleva kärkipiste on G . Etäisyys F :stä siihen on 11, pisteestä E - 9. E on lähempänä, joten valitaan kärki G ja reuna EG .
{A,B,C,D,E,F,G}	(B,C) = 8 jaksoa (D,B) = 9 jaksoa (D,E) = 15 jaksoa (F,E) = 8 jaksoa (F,G) = 11 jaksoa	{}	Kaikki kärjet valitaan, pienin virittävä puu rakennetaan (korostettu vihreällä). Tässä tapauksessa sen paino on 39.

Toteutus

Merkintä

$d[i]$ on etäisyys -: nnestä kärjestä rakennettuun puuhun $i$
$p[i]$ on - :nnen kärjen esi-isä, eli sellainen kärki , jossa kevyin kaikista reunoista, jotka yhdistävät i:n rakennetun puun kärkeen. $i$ $u$ ${\näyttötyyli (u,i)}$
$w(i,j)$ - kylkiluiden paino $(i,j)$
$K$ on graafin kärkipisteiden prioriteettijono, jossa avain on $d[i]$
$T$ on vähimmäisvirittävän puun reunojen joukko

Pseudokoodi

T\ gets

{} Jokaiselle huippupisteelle Ei vielä tyhjä

minä V:ssä

d[i]\gets\infty

p[i]\saa nollan

d[1]\saa 0

Q saa V

v\gets\Extract.Min(Q)

K

Jokaiselle If ja : n viereiselle kärjelle

u

v

u\in Q

w(v,u)<d[u]

d[u]\saa w(v,u)

p[u]\gets v

v\gets Extract.Min(Q)

T\saa T+(p[v],v)

Arvio

Algoritmin asymptotiikka riippuu siitä, kuinka graafi on tallennettu ja kuinka ne kärjet, jotka eivät sisälly puuhun, tallennetaan. Jos prioriteettijono toteutetaan tavallisena taulukkona , se kestää ja toimenpiteen hinta on . Jos edustaa binaarista pyramidia , kustannukset laskevat arvoon ja kustannukset kasvavat arvoon . Fibonacci-pyramideja käytettäessä operaatio suoritetaan , ja for . $K$ $d$ $Poimi.min(Q)$ $Päällä)$ $d[u]\saa w(v,u)$ $O(1)$ $K$ $Poimi.min(Q)$ $O(\log n)$ $d[u]\saa w(v,u)$ $O(\log n)$ $Poimi.min(Q)$ $O(\log n)$ $d[u]\saa w(v,u)$ $O(1)$

Tapa esittää prioriteettijono ja kaavio	Asymptotiikka
Taulukko d, vierekkäisyysluettelot (naapurimatriisi)	$O(V^{2})$
Binääripyramidi, vierekkäisyysluettelot	$O((V+E)\log V)=O(E\log V)$
Fibonacci-pyramidi, vierekkäisyysluettelot	$O(E+V\log V)$

Katso myös

Kirjallisuus

V. Jarník: O jistém problému minimálním [Tietästä minimaalisesta ongelmasta], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57-63. (tšekki)
RC Prim: Lyhyimmät yhteysverkot ja joitain yleistyksiä . Julkaisussa: Bell System Technical Journal , 36 (1957), s. 1389-1401 (englanniksi)
D. Cheriton ja RE Tarjan : Vähimmäisvirittävien puiden löytäminen . Julkaisussa: SIAM Journal on Computing , 5 (joulukuu 1976), ss. 724-741 _
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest ja Clifford Stein . Johdatus algoritmeihin , kolmas painos. MIT Press, 2009. ISBN 0-262-03384-4 . Kohta 23.2: Kruskalin ja Primin algoritmit, pp. 631-638. (Englanti)

Linkit

Primin algoritmin kuvaus ja toteutus
DISKREETI MATEMATIIKKA: ALGORITMIT: Vähimmäisvirittävät puut (linkki ei ole käytettävissä) . Haettu 7. heinäkuuta 2009. Arkistoitu alkuperäisestä 11. tammikuuta 2014. (määrätön)

Kaavion hakualgoritmit
Tietämättömät menetelmät	Kaksisuuntainen haku Säteen haku Leksikografinen leveys ensimmäinen haku Leveys ensimmäinen haku Hae kustannuskriteerin mukaan Ensimmäinen syvyyshaku Peruutushaku Hae kiipeämällä huipulle Syvyysrajoitettu haku Syvyys-ensin haku iteratiivisella syventämisellä
Tietoon perustuvat menetelmät	Alfa beta leikkaus Haara- ja sidontamenetelmä Hae ensimmäisen parhaan osuman perusteella A* B* D* Siirtymäkohdan löytäminen IDA* Rekursiivinen haku ensimmäisen parhaan osuman perusteella SMA*
Pikanäppäimet	Aalto-algoritmi Bellman-Ford-algoritmi Dijkstran algoritmi Johnsonin algoritmi Levitin algoritmi Floyd-Warshall-algoritmi Reunahaku
Vähintään ulottuva puu	Boruvkan algoritmi Primin algoritmi Kruskalin algoritmi
muu	British Museum Algorithm Edmondsin algoritmi Puun läpikulku Lähin naapuri -algoritmi matkustavan myyjän ongelmassa