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

Рис. 5.18. Блок-схема Алгоритма-1 получение всех п-перестановок.

Получение первых нескольких перестановок по этому алгоритму отображено в табл. 5.4.

Таблица 5.4

Первые 6 перестановок, которые получены согласно Алгоритму-1

Нетрудно убедиться в том, что Алгоритм-1 действительно решает поставленную задачу. Этот факт, очевиден для п=1, можно проверить и для п =2. Пусть это верно для (п— 1), т. е. алгоритм действительно получает все различные перестановки в случае п—1 элементов. Но если применить этот алгоритм для п элементов, то цифра 1, стоящая на первом месте в исходной перестановке, будет заменена на 2, только тогда, когда она станет обрывающим числом, т. е. когда будут получены все ( п—1)! различных перестановок других чисел. Точно так же цифра 2 на первом месте в перестановках будет заменена на 3 только после получения всех (п—1)! различных перестановок других элементов и т. д. Это и означает, что алгоритм получает все п·(п—1)! перестановок, при этом среди них не будет совпадающих.

Другой алгоритм — Алгоритм-2 — получение всех п-перестановок представлены блок-схемой на рис. 5.19.

Только один термин к блок-схеме рис. 5.19 нуждается в пояснении.

Назовем «вращением» некоторой последовательности А чисел замену ее другой последовательностью В, где число, стоящее в А на первом месте, оказывается в В на последнем месте, взаимное расположение других чисел не меняется. Так вращение (1, 2, 3) приводит к (2, 3, 1).

Рис. 5.19. Блок-схема Алгоритма-2 получение всех п-перестановок.

Табл. 5.5 поясняет ход решения по этому алгоритму при получении первых нескольких перестановок.

Таблица 5.5

Первые перестановки, полученные6 согласно Алгоритму-2

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

И все же существует единообразный прием представления последовательного построения всех возможных вариантов в самих разнообразных задачах дискретной оптимизации. Его мы и продемонстрируем сейчас на примере образования всех возможных п-перестановок. Изобразим графически кружочком множество всех возможных п-перестановок. Разобьем это множество на п подмножеств, отнеся к одному подмножеству все те перестановки, у которых на первом месте стоит одно и то же число i1. В первое подмножество попадут все перестановки, у которых на первом месте расположена 1 (i1 = l), во второе подмножество попадут σп с i1= 2 и т. д. Изобразим эти подмножества графически также кружочками, внутри кружочков запишем значения i1, соединим стрелками кружочки со знаком множества всех возможных п-перестановок, как это показано на рис. 5.20.

Рис. 5.20

В свою очередь каждую из этих подмножеств можно еще разделить на непересекающиеся подмножества в зависимости от того, какое число размещено в перестановке на втором месте (рис. 5.21), вновь образованные подмножества можно разбить на части в зависимости от того, какое число расположено на третьем месте и т. д.

Рис. 5.21

Процесс такой последовательной разбиения множеств оборвется тогда, когда мы дойдем до отдельных, единичных перестановок. На рис. 5.22 представлен результат такой последовательной разбиения множества всех перестановок чисел 1, 2, 3.

Рис. 5.22

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

Каждая вершина в порфириане располагается, как мы будем говорить, на некотором уровне. В нашем примере вершины, соответствующие фиксации i1, расположены на первому уровне, фиксации i2 — на втором уровне. Вершине, которая расположенной на k-м уровне, соответствуют отрезки длины k п-перестановок

σk= i1, i2,…,ik

Вершинам, расположенным на n-м уровне, соответствуют «полные» перестановки σг.

Построение вершин (k + 1)-го уровня порфириана, исходя из некоторой вершины k-го уровня, будем в дальнейшем называть операцией разветвления, или ветвлением.

Умение правильно определить операцию ветвления равносильно знанию способа конструирования всего порфириана, т. е. знанию алгоритма построения всех возможных вариантов решения задачи (возможными вариантами считаются те перестановки, которые удовлетворяют всем условиям задачи, за исключением условия приводить к экстремуму функции-критерии).

На порфириан можно также смотреть как на представление последовательной классификации множества всех возможных вариантов, т. е. процесса разбиения его на все более мелкие подмножества, вплоть до отдельных вариантов.

Для нас важнее, что порфириан задает способ построения (точнее, им определяется этот способ) - конструирования - всех возможных вариантов, которые удовлетворяют условиям задачи (за исключением, еще раз подчеркнем, условия приводить к экстремуму функции-критерия).

В этом смысле каждая вершина порфириана (кроме начальной) замыкает собой как бы некоторый фиксированный фрагмент в представлении некоторого возможного решения. Так отмеченная на рис. 5.21 знаком + вершина соответствует, если проследить путь от исходной вершины до отмеченной, последовательному закреплению сначала i1 = 2, потом i2 = 1. Таким образом, будем считать, что отмеченная вершина представляет собой фрагмент σ2 =2, 1 ( В аспекте классификации это означает, что отмеченная вершина представляет то подмножество вариантов, которое начинается с чисел 2 и 1 (i1 = 2, i2 = 1), и 2, 1 есть классификационный код, введенное классификацией имя этого множества).

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

5.16. Общая схема построения порфириана

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

Для такой постановки оказываются справедливыми следующие утверждения.

Утверждение 1. Путь бродячего торговца (в задаче на плоскости) не имеет самопересечений.

Назовем отрезок пути σk= i1, i2,…,ikразделяющим, если

1) он разбивает множество всех городов — точек на плоскости, отличных от i1, i2,…,ik, на две части такие, что

2) не существует отрезка, соединяющего точку из одной части множества и точку из другой части множества и не пересекает при этом σk.

Утверждение 2. Оптимальный маршрут не содержит разделяющих отрезков σk (k < n).

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

Так для совокупности пунктов на плоскости, представленных рис. 5.23, где внутри выпуклого многоугольника расположен всего один пункт, заведомо ясно, что решением будет контур, близко подходящий к границе многоугольника (согласно утверждению 3).

Рис. 5.23

Чисто визуально оценив, что в пункт 4 можно зайти из пунктов 3, 5 или 6, а из других пунктов явно нецелесообразно, легко получить множество возможных решений в таком случае - усього три варианта, представленных порфирианом на рис. 5.24:

1,2, 3,4, 5,6,7,8 ,

1,2,3,5, 4,6,7,8 ,

1,2,3,5, 6,4,7,8 .

(Допустимо и прохождение маршрута в обратном порядке, в «плоской» постановке такие маршруты можно считать эквивалентными).

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