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

В качестве примера эвристического метода приведем алгоритм Прима. Для связи средств вычислительной техники в больших сетях традиционно применяется модемная техника, однако качество и надежность получаемой системы передачи данных существенно зависят от выбора каналов - выделенных или коммутируемых. Проектировщику такой распределенной системы традиционно приходится разрешать дилемму между обеспечением требуемого качества сети и ее стоимости, что связано со значительной разницей в оплате указанных каналов связи.

Пусть имеется множество территориально распределенных объектов X=x_i{}, характеризуемых: географическими координатами (a_i,b_i); объемом информации f_i, генерируемой объектом. Предполагается, что одним из объектов является "центральный" (главный) узел, выделенный в соответствии с некоторыми правилами - административными, территориальными и пр.

Пусть, кроме того, известны приведенные затраты C_пер,ij на передачу информации от объекта x_i к объекту x_j, зависящие от трафика f_ij в данном направлении и длины линий связи l_ij. Требуется синтезировать структуру минимальной стоимости в классе древовидных структур при ограничениях на максимальный трафик f_ij в каждой ветви (f_ij,d_max), где f_ij определяется как сумма информационных потоков от всех узлов, предшествующих узлу i на путях от концевых вершин к корню дерева, и потока h_i, формируемого объектом x_i.

Задача синтеза древовидной сети впервые рассматривалась в работе Прима, в которой предложен точный алгоритм синтеза сети минимальной стоимости, но без учета ограничений на пропускные способности линий связи и, как следствие, на суммарный поток, передаваемый по ветвям. Вместе с тем доказано, что алгоритм доставляет оптимальное решение и состоит из следующих шагов. Пусть первоначально рассматривается исходное множество несвязанных объектов (вершин) X=x_i{}.

1. Выбирается произвольная вершина (подграф) x_i и определяется стоимость введения ребра (i, j), связывающего x_i с некоторым подграфом x_j: c_ij.

2. Если подграфы x_i и x_j состоят из нескольких вершин, то выбирается ребро, доставляющее топологическое расстояние между подграфами (минимум из всех пар возможных расстояний): среди всех пар (i, j) определяется такая пара (i^*, j^*), для которой

c_i*j* = min cij.

" (i,j)

3. Подграфы x_i* и x_j* объединяются в один: x_ij*= x_i*È x_j*. На этом итерация алгоритма Прима завершается, а сами итерации повторяются до тех пор, пока имеются изолированные подграфы (их количество на каждой итерации уменьшается на единицу).