пользователей: 30398
предметов: 12406
вопросов: 234839
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

СИшники:
» МтЗвУП
» ТПКС
» БЕЗКОРЬ

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

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

 


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