пользователей: 21251
предметов: 10459
вопросов: 177801
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

СИшники:
» МтЗвУП
» ТПКС

Методы построения кольцевых структур.

1)метод ветвей и границ (алг. Литтла): В начале определяется некоторое допустимое решение, после чего множество всех оставшихся вариантов разбиваются на мелкие подмножества. На каждом шаге разбиения вычисляется нижняя граница текущего разбиения.  С помощью найденных границ происходит дальнейшее разбиение подмножеств допустимых маршрутов и в конечном итоге определяется конечный маршрут. Если находится маршрут, длина которого не превосходит наименьших нижних границ других маршрутов, то данное промежуточное решение становится наилучшим допустимым решением. 2) «иди в ближайший»: Что построить кольцевую структуру, необходимо последовательно к существующей части добавлять ближайший, не вошедший еще в маршрут, пункт.  Данный алгоритм оперирует разомкнутым маршрутом с исходным пунктом. Другой подход заключается в том, чтобы иметь изначально замкнутую подструктуру и вставлять в нее очередной пункт на пустое место. Различные модификации алгоритма связаны с выбором пункта и места вставки. 3) алг. минимальной вставки: сформировать начальный маршрут; для каждой вершины v найти такие i и j, чтобы Сiv+Сvj–Сij->min; для данной вершины найти такую другу вершину, при добавлении которой в маршрут,  минимально увеличивается маршрут относительно удаленного ребра; вставить вершину; повторить сначала, если есть еще вершины n^2*lg(n)-кол-во вычислений. Есть методы ближайшей вставки и дальней вставки.

 


17.06.2015; 19:05
хиты: 13
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь