Дискретно-непрерывная математика (стр. 51 )

Мы будем называть правилами доминирования процедуры, позволяющие относительно некоторых σ1k и σ2k устанавливать, что какое-то из них лучше в указанном выше смысле.

В предыдущей фразе акцентировано внимание на том, что правила доминирования устанавливаются только для некоторых σ1k и σ2k . Обычно сравнивать можно только те σ1k и σ2k, которые приводят в одно и тот же состояние, в том понимании, что как результат какого-то процесса их можно считать идентичными.

Так в задаче коммивояжера в одно и тот же состояние приводят два пути σ1k и σ2k , если

а) они начинаются в одном и том же пункте, т. е.

і1(σ1k )= і1 (σ2k);

б) они заканчиваются в одном и том же пункте, т. е.

іk (σ1k )= іk (σ2k);

в) эти пути проходят через одно и то же множество пунктов (только в разном порядке).

Последнее мы будем обозначать символом

M (σ1k )= M (σ2k);

M(σk) -это множество пунктов і, через которые проходит σk (σk, таким образом, — это некоторое упорядочение M(σk)). Такие варианты σ1k и σ2k мы назовем сравнимыми.

Так, пути σ15 = 2, 1, 3, 5, 4 и σ25 = 2, 5, 3, 1, 4 приводят в одинаковые состояния, пути σ15 = 2, 1, 3, 4, 5 и σ25= 2, 3, 1, 5, 4 - в разные.

В дальнейшем (упражнение 1) станет ясно, что в некоторых случаях варианты σ14 = 2, 1, 3, 4) и σ25= 2, 3, 1,5,4) также могут стать сравнимыми.

Пусть в задаче бродячего торговца

Утверждение (правило доминирования). В задаче бродячего торговца, если σ1k и σ2k сравнимы и при этом F (σ1k) ≤ F (σ2k), то σ1k лучше σ2k в том смысле, что среди продолжений σ1k найдется σ1п, для которого F (σ1п) < F (σ2п) для всех σ2п, являющихся продолжениями σ2k.

Тем самым дальнейшие ветвления σ2k при построении порфириана явно нецелесообразны — в этом и состоит последовательное отсеивание вариантов в процессе построения порфириана согласно правилам доминирования.

Пусть

— лучшее решение среди продолжений σ2k = ,

где

Построим теперь решение

продолжение σ1k = i11 .....i1k которого совпадает с продолжением σ2k, т. е. i1l = i2l для всех l > k.

Тогда нетрудно видеть, что так как

то

что и доказывает наше утверждение.

2. Решение задачи бродячего торговца. Рассмотрим пример, заданный табл. 5.15, представляющий матрицу (aij) расстояний между пунктами i и j.

Таблица 5.15

Матрица аij

Рис. 5.36 иллюстрирует схему решения задачи (упрощенно изложенный алгоритм) бродячего торговца методом отсеивания вариантов в процессе построения порфириана согласно правилам доминирования.

Рис. 5.36. Схема решения задачи бродячего торговца последовательным отсеиванием вариантов.

1. Подготовка матрицы аij к решению. 2. Разветвление σ1=1, построение множества Р2 всех σ2. 3. k=2. 4. Операция ветвления; каждому σk из Аk ставятся в соответствие всевозможные σk+1 = σk , j, j не принадлежит M σk, тем самым образуется множество Рk+1 таких σk+1. 5. Группировка сравнимых σk+1. 6. Отбор «лучших» σk+1 согласно правилам доминирования, создание Рk+1 всех «перспективных» σk+1. 7. k + 1 k. 8. Проверка: k > n? 9. Решение закончено: - решение.

Объясним некоторые блоки этой схемы.

В блоке «группировка сравнимых σk» собирают вместе все σk, приводящие в одно и то же состояние.

Нетрудно показать, что число таких различных подмножеств — группировок — будет равно числу сочетаний из п элементов по k — 2 элементов:

Так как у всех сравнимых вариантов σk фиксированы начальный и конечный элементы i1 и ik. (Напомним, что сочетанием из п элементов по k называется число всех различных подмножеств, которые состоят из k элементов, взятых из фиксированного множества, которое состоит из п элементов). В блоке «отбора лучших σk» выполняется перебор всех элементов, попавших в одну и ту же группировку сравнимых вариантов, и в множестве оставляется по одном лучшему элементу из каждой такой группировки. Ветвление не попавших в вариантов σk в дальнейшем запрещается. В блоке «операция ветвления» происходит последовательный просмотр всех σk k-го уровня, не запрещенных для ветвления, от каждого такого σk (из ) выполняется построение всевозможных σk+1 = σk, i — как и при построении порфириана. Процесс решения приведенного в табл. 5.15 примера по схеме, представленной на рис. 5.36, воспроизводится в табл. 5.16. В табл. 5.16, как и ранее, крестиком × отмечены «бесперспективные» согласно правилам доминирования варианты, т. е. отсеиваемые (запрещаемые для ветвления) блоком «отбора лучших вариантов». Плюс (+) отмечает «перспективные» варианты.

Таблица 5.16

Этапы решения примера (при равенстве F (σk) лучшим считается

первый вариант)

Таблица 5.16 (продолжение)

σ4 (группирование и отбор лучших — отмечены знакомый +)

Таблица 5.16 (продолжение)

Таблица 5.16 (продолжение)

3. Поиск «критического пути». Определение «критического пути» в сетевом графике п. 5.13 можно также провести с помощью построения порфириана.

По-прежнему путь в сетевом графике есть произвольная последовательность работ

σk = i1, i2 ,…,ik

если только любые две соседние работы в σk соединены на сетевом графике стрелками.

Для наглядности (образности) можно считать, что работы іk в сетевом графике есть некоторые «города», и интерпретировать задачу поиску критического пути на сетевом графике как требование определить самый длинный путь, который может пройти турист, между исходным пунктом (начальной работой) и конечным (заключительной работой).

Будем обозначать через F(σk) общую длину пути σk, т. е.