Примов алгоритамВо компјутерските науки, Примовиот алгоритам е алчен алгоритам што ја наоѓа минималната патека на дрво во еден граф. Ова значи дека ќе најде подмножество на рабови од кој се формира едно стебло, кое го вклучува секое теме каде што вкупната тежина на сите на рабови на дрвото е минимална. Алгоритмот е развиен во 1930 година од страна на чешкиот математичар Војтеч Јарник, подоцна независно од компјутерскиот научник Роберт Прим во 1957 година и откриени по Едсгер Дајкстра во 1959 година. Други алгоритми за решавање на овој проблем го вклучуваат и Крускаловиот алгоритам и алгоритамот на Борувка. ОписНеформален
ТехничкиАлгоритамот на Прим има многу голема примена, како на пример во генерирање на овој лавиринт во кој се применува алгоритмот на Прим на случајно одбран граф. Единственото дрво на празен граф (со празен сет на темиња) е повторно празен граф. Следниов опис претпоставува дека овој посебен случај се постапува одделно. Алгоритмот постојано ја зголемува големината на дрвото, еден раб во еден момент, почнувајќи од дрво што се состои од едно теме, сè додека не ги спои сите темиња.
Временска комплексност
Едноставна имплементација на користење на адјунгирана матрична графичка застапеност и потрага за низа на тежини за да го најдете најмалиот раб за да додадете е потребна О, време за извршување. Користејќи едноставна бинарна хип податочна структура и адјунгирана список на застапеност, алгоритмот на Прим може да биде прикажан во времето О(E log V), каде Е е бројот на рабовите и V е бројот на темиња. Со користење на пософистициран Фибоначиев хип, ова може да се сведе на О (Е + V log V), кое е асимптоматично побрзо кога графот е доволно густ, E е Ω (V). Пример
Доказ за точностНека 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 покажува дека е минимално распространето дрво. ПоврзаноНаводи
Надворешни врски
|
Portal di Ensiklopedia Dunia
