5.4. Приближенный алгоритм

Тэйтц и Барт [32] предложили эвристический метод для нахождения -медианы. Метод состоит в следующем: случайным образом выбираются вершин, они и образуют начальное множество аппроксимирующее р-медианное множество Затем выясняется, может ли некоторая вершина заменить вершину (как медианная вершина), для чего строится новое множество и сравниваются передаточные числа и Если то вершина замещается вершиной и из множества получается множество которое лучше аппроксимирует -медианное множество Затем исследуется уже множество аналогично тому как исследовалось пока не будет построено множество такое, что ни одну его вершину нельзя заместить вершиной из и получить при этом множество с меньшим передаточным числом, чем Множество берется в качестве требуемого приближения к множеству

5.4.1. Описание алгоритма

Шаг 1. Выбрать некоторое множество из вершин в качестве начального приближения к -медиане. Назовем все вершины «неопробованными».

Шаг 2. Взять произвольную «неопробованную» вершину и для каждой вершины вычислить «приращение» соответствующее замене вершины вершиной т. е. вычислить

Шаг 3. Найти .

(i) Если назвать вершину «опробованной» и перейти к шагу 2.

(ii) Если то назвать вершину «опробованной» и перейти к шагу 2.

Рис. 6.1. Контрпример к приближенному алгоритму разд. 5.4.

Шаг 4. Повторять шаги 2 и 3 до тех пор, пока все вершины из не будут опробованы. Эта процедура оформляется как цикл. Если при выполнении последнего цикла совсем не будет замещений вершин на шаге то перейти к шагу 5. В противном случае, т. е. если осуществлено некоторое замещение, назвать все вершины «неопробованными» и вернуться к шагу 2.

Шаг 5. Стоп. Текущее множество является подходящей аппроксимацией -медианного множества

Очевидно, что приведенный выше алгоритм не во всех случаях дает оптимальный ответ [18]. Действительно, рассмотрим неориентированный граф, изображенный на рис. 6.1. Числа, стоящие около ребер, равны соответствующим реберным стоимостям. Считаем, что все вершины имеют единичные веса. Если искать -медиану и в качестве начального множества взять с передаточным числом то никакое замещение только одной вершины не приводит к множеству с меньшим передаточным числом. Однако множество не является -медианой данного графа. Существуют два -медианных множества: и с передаточными числами

Алгоритм, описанный в настоящем разделе, является в действительности лишь одним из целого семейства алгоритмов, базирующихся на локальной оптимизации и на идее -оптимальности, впервые введенной Лином [22] для задачи коммивояжера, а впоследствии развитой и использованной в других работах [3, 4, 19] при исследовании различных комбинаторных проблем.

Вернемся к нашей задаче. Множество из вершин называется -оптимальным если замена любых вершин из

множества любыми вершинами, не принадлежащими не может породить нового множества с передаточным числом, меньшим, чем Очевидно, что если является -медианным множеством рассматриваемого графа, то S -оптимально. Совершенно очевидно также, что если является -оптимальным множеством и S" - -оптимальное множество, то при

Согласно приведенным выше определениям решение, полученное с помощью алгоритма из разд. 5.4.1, можно назвать -опти-мальным. Подобные алгоритмы можно дать и для порождения -оптимальных, -оптимальных и т. д. решений. Чтобы убедиться в -оптимальности множества нужно выполнить

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

6. Задачи

(см. скан)

(см. скан)

(см. скан)

7. Список литературы

(см. скан)

(см. скан)