Википедија

Примов алгоритам

алгоритам

Во компјутерските науки, Примовиот алгоритам е алчен алгоритам што ја наоѓа минималната патека на дрво во еден граф. Ова значи дека ќе најде подмножество на рабови од кој се формира едно стебло, кое го вклучува секое теме каде што вкупната тежина на сите на рабови на дрвото е минимална. Алгоритмот е развиен во 1930 година од страна на чешкиот математичар Војтеч Јарник, подоцна независно од компјутерскиот научник Роберт Прим во 1957 година и откриени по Едсгер Дајкстра во 1959 година. Други алгоритми за решавање на овој проблем го вклучуваат и Крускаловиот алгоритам и алгоритамот на Борувка.

Опис

уреди

Неформален

уреди
  • Создава дрво кое содржи едно теме, избран произволно од графот
  • Создава група која ги содржи сите рабови во графот
  • Поврзува сè додека секој раб поврзува две темиња во дрво
  • Отстранува од граф раб со минимална тежина кој поврзува теме од дрвото со теме кое не е во дрвото
  • Го додава тој раб во дрвото

Технички

уреди

Алгоритамот на Прим има многу голема примена, како на пример во генерирање на овој лавиринт во кој се применува алгоритмот на Прим на случајно одбран граф. Единственото дрво на празен граф (со празен сет на темиња) е повторно празен граф. Следниов опис претпоставува дека овој посебен случај се постапува одделно. Алгоритмот постојано ја зголемува големината на дрвото, еден раб во еден момент, почнувајќи од дрво што се состои од едно теме, сè додека не ги спои сите темиња.

  • Влез: Не-празен граф, поврзан со темиња V и рабови Е(тежините неможат да бидат негативни).
  • Иницијализира: Vnew = {x}, каде x е произволен јазол (почетна точка) од V, Enew = {}
  • Повторете сè додека Vnew = V
    • Изберете раб (u, v) со минимална тежина, како што U е во Vnew и V не е (ако постојат повеќе рабовите со иста тежина, некој од нив може да се подигнат)
    • Додај v за да Vnew, и (u, v) да Enew
  • Излез: Vnew и Enew опише минимална опфаќа дрво

Временска комплексност

уреди
Minimum edge weight data structure Time complexity (total)
adjacency matrix, searching O(V2)
binary heap and adjacency list O((V + E) log V) = O(E log V)
Fibonacci heap and adjacency list O(E + V log V)

Едноставна имплементација на користење на адјунгирана матрична графичка застапеност и потрага за низа на тежини за да го најдете најмалиот раб за да додадете е потребна О, време за извршување. Користејќи едноставна бинарна хип податочна структура и адјунгирана список на застапеност, алгоритмот на Прим може да биде прикажан во времето О(E log V), каде Е е бројот на рабовите и V е бројот на темиња. Со користење на пософистициран Фибоначиев хип, ова може да се сведе на О (Е + V log V), кое е асимптоматично побрзо кога графот е доволно густ, E е Ω (V).

Пример

уреди
Слика U Раб(u,v) V \ U Опис
  {} {A,B,C,D,E,F,G} Ова е нашиот оригинален граф. Броевите во близина на рабовите ја означуваат неговата тежина.
  {D} (D,A) = 5 V
(D,B) = 9
(D,E) = 15
(D,F) = 6		 {A,B,C,E,F,G} Темето D е произволно избран како почетна точка. Вертиците A, B, E и F се поврзани со D преку еден раб. A е теме најблиску до D и ќе биди одбран како второ теме покрај работ AD.
  {A,D} (D,B) = 9
(D,E) = 15
(D,F) = 6 V
(A,B) = 7		 {B,C,E,F,G} Следното одбрано теме е темето најблиску до D или A. B е 9 подалеку од D и 7 подалеку од A, E е 15, и F е 6. F е најмалку оддалечен, па го означуваме темето F и работ DF.
  {A,D,F} (D,B) = 9
(D,E) = 15
(A,B) = 7 V
(F,E) = 8
(F,G) = 11		 {B,C,E,G} Алгоритамот продолжува како и погоре. Темето B, кое е 7 оддалечено од A, е означено.
  {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} Во овој случај, можеме да одбереме помеѓу C, E, и G. C е 8 оддалечено од B, E е 7 оддалечено од B, и G е 11 away fromоддалечено од F. E е најблиску, па го обележуваме темето E и работ BE.
  {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} Овде, единственте можни вертици се C и G. C е 5 оддалечено од E, и G е 9 оддалечено од E. C е одбрано, па тоа е обележано по работ EC.
  {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} Темето G е единственото теме кое останува. ТОа е 11 оддалечено F, и 9 оддалечено од E. E е поблиску, па го обележуваме G и работ EG.
  {A,B,C,D,E,F,G} (B,C) = 8 циклус
(D,B) = 9 циклус
(D,E) = 15 циклус
(F,E) = 8 циклус
(F,G) = 11 циклус		 {} Сега сите вертици се селектирани и минимално распространетото дрво е обоено зелено. Во овој случај тежината е 39.

Доказ за точност

уреди

Нека P е сврзан, тежински граф. На секоја итерација на Примовиот алгоритам, работ мора да биде поврзан со теме во подграф со теме надвор од подрафот. Штом P поврзан, секогаш има пат до секое теме. Резултатот Y од Примовиот алгоритам е дрво бидејќу секој раб и теме додадени на дрвото Y се поврзани. Нека Y1 е минимално распространето дрво од графот P. Ако Y1 = Y тогаш Y е минимално распространето дрво. Инаку, нека е првиот раб додаден во конструкцијата кој не е во дрвото Y1, и V нека биде множесто од вертици кои се сврзани со рабови додадени пред работ Е. Тогаш еден крај на работ е во множестовото V, а другиот не е. Бидејќи Y1 не е распространето дрво на графот P,има пат во дрвото Y1 кој поврзува два краја. Додека некој се движи по патот, мора да сретне раб f кој поврзува теме во множеството V со теме коешто не е во множеството V. Сега, на итерацијата кога раот е додаден во дрвото Y,работ ‘f’, исто така може да се додаде и би бил додаден наместо работ e доколку тежи помалку од ‘е’ (знаеме дека сме имале можност да во земеме ‘f’ пред ‘e’ бидејќи ‘f’ е сврзан со V и го посетивме секое теме на V пред темето со кое го поврзуваме ‘e’). Затоа што работ ‘f’ не е додаден, заклучуваме дека:

 

Нека дрвото Y2 е граф создаден со одземање на рабовите ‘f’ и додавање на работ ‘e’ во дрвото Y1. Лесно е да се покаже дека дрвото Y2 е сврзано, го има истиот број на рабови како дрвото Y1 и вкупната тежина на сите рабови не е поголем од тој на Y1, што значи дека исто така е и минимално распространето дрво на графот P и ги содржи рабовите ‘e’ и сите рабови додадени во текот на конструкцијата на множеството V. Повторувајќи ги претходните стапки ќе стигнеме до минималното распространето дрво на графот P што е идентично на дрвото Y. Овај Y покажува дека е минимално распространето дрво.

Поврзано

уреди

Наводи

уреди

Надворешни врски

уреди
Преземено од „https://mk.wikipedia.org/w/index.php?title=Примов_алгоритам&oldid=5258386“