Rešitev: Primov algoritem (Mathematica)

Iz MaFiRaWiki

Naloga: Primov algoritem

Vsebina

Kaj je Primov algoritem?

 
Primov algoritem je postopek, ki nam omogoča na preprost način poiskati najcenejše vpeto drevo v grafu.

Osnovna ideja Prima?


Ideja je izbrati si poljubno vozlišče (izbira vozlišča vpliva le na to katero poddrevo bomo dobili ne pa tudi na 
končno ceno poddrevesa - s Primovim postopkom vselej dobimo najcenejšo pot) in mu nato dodajati najcenejše povezave
(povezava je lahko dodana v drevo samo enkrat). Ta postopek ponavljamo (gradimo poddrevo grafa) dokler niso vsa
vozlišča dodana v naše poddrevo. Ko se le ta konča, dobimo najcenejše vpeto drevo.

Primov algoritem v mathematici


(*vhodni podatki bodo predstavljeni z matriko sosednosti*)

Clear[PrimovAlgoritem]
  
PrimovAlgoritem[graf_List] := Module[{n := Length[graf], 
poddrevo, CenaPoti,PovezanDel, NepovezanDel, dodaj, mesto, najcenejsa, v1, v2},
      
  poddrevo = {};    (*na začetku še nimamo poddrevesa*)

  CenaPoti = 0;   (*ker nimamo še poddrevesa tudi povezav nimamo torej
  nimamo cene povezav*)

  PovezanDel = {1};
(*Za začetek si izberemo eno (katerokoli) vozlišče (predstavljamo 
si vozlišča, ki so oštevilčena t.j. 1 = prvo vozlišče, n = n - to volišče)*)    

NepovezanDel = Rest[Range[n]];(*V preostalem delu t.j. nepovezanem so
vsa ostala vozlišča*)   
      
      
 While[Length[NepovezanDel] > 0, (*naša zanka teče dokler niso vsa
 vozlišča  dodana v povezan del*)
 dodaj = {First[PovezanDel], First[NepovezanDel]};
 mesto = 1; (*kje v grafu se nahajmo*)
 najcenejsa = ∞;

 For[i = 1, i ≤ Length[PovezanDel], i++,
   For[j = 1, j ≤ Length[NepovezanDel], j++,
    v1 = PovezanDel〚i〛;     
    v2 = NepovezanDel〚j〛;
    If[graf〚v1, v2〛 < najcenejsa, 
(*pogledamo vse povezave med vozliščem v1 (ki je v povezanem delu) in 
vozliščem v2 (v nepovezanem delu), in sicer tako, da je v1 "fiksna" v2 pa 
preteče vse j in nato izberemo najcenejšo ...šele nato preidemo na "novi 
v1"(i se poveča)*)
dodaj = {v1, v2}; (*povezavo, ki se izkaže, da je
najcenejša, dodamo v graf*)
najcenejsa = graf〚v1, v2〛;
mesto = j;
   ];
  ];
 ];
        
CenaPoti += graf〚First[dodaj], Last[dodaj]〛;
poddrevo = Append[poddrevo, dodaj]
PovezanDel = Append[PovezanDel, Last[dodaj]];
NepovezanDel = Delete[NepovezanDel, mesto];
 ];
 Return[{poddrevo, CenaPoti}];
];

Primer

Clear[PrimovAlgoritem]

 A = {{0,4, 8, ∞, ∞, ∞, ∞, ∞, ∞}, {4, 0, 11, ∞, 8, ∞, ∞, ∞, ∞}, 
{8,11, 0, 7, ∞, 1, ∞, ∞, ∞}, {∞, ∞, 7, 0, 2, 6, ∞, ∞, ∞}, 
{∞, 8,∞, 2, 0, ∞, 7, 4, ∞}, {∞, ∞, 1, 6, ∞, 0, ∞, 2, ∞}, 
{∞, ∞, ∞, ∞, 7, ∞, 0, 14, 9}, {∞, ∞, ∞, ∞, 4, 2, 14, 0, 12}, 
{∞, ∞, ∞, ∞, ∞, ∞, 9, 12, 0}};

MatrixForm[{{0, 4, 8, ∞, ∞, ∞, ∞, ∞, ∞}, {4, 0, 11, ∞, 8, ∞, ∞, ∞, ∞}, 
{8, 11, 0,7, ∞, 1, ∞, ∞, ∞}, {∞, ∞, 7, 0, 2, 6, ∞, ∞, ∞}, 
{∞, 8, ∞, 2,0, ∞, 7, 4, ∞}, {∞, ∞, 1, 6, ∞, 0, ∞, 2, ∞}, 
{∞, ∞, ∞, ∞,7, ∞, 0, 14, 9}, {∞, ∞, ∞, ∞, 4, 2, 14, 0, 12},
{∞, ∞, ∞, ∞, ∞, ∞, 9, 12, 0}}]

PrimovAlgoritem[A] (*1.del : pari povezav v najcenejšem
 vpetem drevesu, 2.del: cena povezav v najcenejšem vpetem drevesu*)
 
Primov algoritem nam vrne:
{{{1, 2}, {1, 3}, {3, 6}, {6, 8}, {8, 5}, {5, 4}, {5, 7}, {7, 9}}, 37}

Zgled z grafom

Na tem grafu bomo izvedli Primov postopek:

Za začetek moramo izbrati poljubno vozlišče- npr: a. Iz slednjega gresta dve povezavi...izberemo cenejšo:

Sedaj imamo že dve vozlišči (a in e) v našem poddrevesu. Pogledamo katere povezave gredo iz njiju (in so še v nepovezanem delu) ter izberemo najcenejšo:

Spet analogno nadaljujemo... V povezanem delu imamo vozlišča a, e in d in ponovno nas zanimajo povezave, ki gredo iz naših treh vozlišč pa so še v nepovezanem delu. Izberemo najcenejšo možnost:

Pred nami je še zadnji korak. Samo še eno vozlišče manjka v našem povezanem delu, tako da bomo imeli vpeto drevo. Izbrati moramo med povezavami (najcenejša je med d in b):

Osebna orodja