• Primo algoritmi
    		•

    Minimal narxli daraxtlar skeleti




    Download 0,98 Mb.
    bet3/4
    Sana14.05.2024
    Hajmi0,98 Mb.
    #230833
    1   2   3   4
    Bog'liq
    MBma`ruza1

    Minimal narxli daraxtlar skeleti

    Minimal narxli skeletni topish masalasi ko’pincha quyidagicha xolatlarda uchraydi: masalan, n ta shaxar mavjud va ular orasiga yo’llarni shunaqa qurish kerakki, istalgan shaxardan ixtiyoriy boshqasiga bevosita yoki bilvosita borish mumkin bo’lsin va ular orasiga yo’l qurish sarf xarajatlari ma’lum bo’lsin. Yo’llarni qurishni shunday rejalashtirish kerakki, natijada sarf xarajat minimal bo’lsin.

    algoritmlar

    • Primo algoritmi
    • Kraskala (Kruskala) algoritmi
    • Boruvka algoritmi

    Primo algoritmi

    • algoritm dastlab 1930 yilda chesh matematigi Voysex Yarnik tomonidan taklif etilgan. Keyin Robert Primo tomonidan 1957 yilda qayta ko’rib chiqilgan va ulardan tashqari E. Deykstra tomonidan 1959 yilda ishlab chiqilgan.
    • Algoritm kirishiga yo’naltirilmagan og’irlikka ega bo’lgan graf uzatiladi.
    • Algoritm natijasi bo’lib minimal narxli daraxt tugunlari to’plami xisoblanadi
    • minimal narxli daraxtlarni xosil qilishda xalqa paydo bo’lishiga yo’l qo’ymaslik kerak

    Primo algoritmi

    • Boshida istalgan tugun olinadi va unga tegishli bo’lgan eng kam vaznga ega insident yoy topiladi. Topilgan yoy va unga tegishli tugunlar daraxtni shakllantira boshlaydi.
    • Keyin bir uchi bilan daraxtga tegishli bo’lgan tugunlariga tutashgan va ikkinchi uchi esa tutashmagan boshqa yoylar xam tekshiriladi. Ulardan og’irligi kami tanlanadi.
    • Xar bir qadamdagi yoy daraxtga qo’shilib boraveradi. Daraxtning balandligi xam 1 taga oshib boraveradi. Grafning barcha tugunlari ko’rib chiqilmaguncha algoritm davom etaveradi.

    tasvir

    U tanlangan tugunlar to’plami

    (u,v) yoylar

    v\u tanlanmagan tugunlar

    izox

    {}


    {A,B,C,D,E,F,G}

    Dastlab daraxt tugunlar to’plami bo’sh

    {D}

    (D,A) = 5 V (D,B) = 9 (D,E) = 15 (D,F) = 6

    {A,B,C,E,F,G}

    Ilk tugun sifatida D olindi. Unga tegishli yoylar A,B,E,F tugunlarga olib boradi. Ularning minimal yoyligini tanlaymiz. ya’ni A

    {A,D}

    (D,B) = 9 (D,E) = 15 (D,F) = 6 V (A,B) = 7

    {B,C,E,F,G}


    {A,D,F}

    (D,B) = 9 (D,E) = 15 (A,B) = 7 V (F,E) = 8 (F,G) = 11

    {B,C,E,G}


    {A,B,D,F}

    (B,C) = 8 (B,E) = 7 V (D,B) = 9 цикл (D,E) = 15 (F,E) = 8 (F,G) = 11

    {C,E,G}

    (D,B)ёй танланса халқа хосил бўлади. Шунинг учун уни танлай олмаймиз.

    {A,B,D,E,F}

    (B,C) = 8 (D,B) = 9 цикл (D,E) = 15 цикл (E,C) = 5 V (E,G) = 9 (F,E) = 8 цикл (F,G) = 11

    {C,G}


    {A,B,C,D,E,F}

    (B,C) = 8 цикл (D,B) = 9 цикл (D,E) = 15 цикл (E,G) = 9 V (F,E) = 8 цикл (F,G) = 11

    {G}


    {A,B,C,D,E,F,G}

    (B,C) = 8 цикл (D,B) = 9 цикл (D,E) = 15 цикл (F,E) = 8 цикл (F,G) = 11 цикл

    {}

    Графдаги барча тугунлар текшириб бўлди.

    Download 0,98 Mb.
    1   2   3   4




    Download 0,98 Mb.