Функциональное программирование в алгоритмах перебора тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

)

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

СТУКАЛОВ Дмитрий Юрьевич

ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ В АЛГОРИТМАХ ПЕРЕБОРА 01.01.09 — теоретическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой стеиеии кандидата физико-математических наук

САНКТ-ПЕТЕРБУРГ. 1997.

Рабо та выполнена на кафедре исследования операций Санкт-Петербургского государственного университета.

Научный руководитель

доктор физико-математических паук, профессор И.В.РОМАНОВСКИЙ

Официальные оппоненты

доктор физико-математических наук, профессор С.Н.БАРАНОВ

кандидат технических наук, доцент Ю.А.СУШКОВ

Ведущая организация

Санкт-Петербургский экономико-математический институт Российской Академии Наук

Защита состоится ДЛО/\ 1997 г. в час. на заседании диссер-

тационного совета К OG3.57.49 по защите диссертаций на соискание ученой степени кандидата наук в Санкт-Петербургском государственном университете ПО адресу: 198904, Санкт-Петербург, Ст. Петергоф, Библиотечная нл., д.2, математико-механический факультет.

С диссертацией можно ознакомиться в Научной библиотеке имени М. Горького Санкт-Петербургского государственного университета: Санкт-Петербург, Университетская наб., Д.7/9.

Автореферат разослан "_"_1997 г.

Ученый секретарь диссертационного совета, доцент

А.И.Шепелявый

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

АКТУАЛЬНОСТЬ ТЕМЫ. В данной работе рассматривается применение языков функционального программирования к решению задач перебора. Такие задачи, и особенно задачи перебора субоптимальных решений в дискретных экстремальных задачах ставились и решались в научной литературе многократно, например, в работах Е. Лаулера [6], в статье Мшшеки и Шира [5], в статье Катта Мурти [12]. Однако, идея применения языков функционального программирования для составления алгоритмов перебора появилась не так давно. Одной из первых работ, где упоминается о возможности применения данных языков для организации перебора, была работа [2], в которой автор, И.В.Романовсхий, вводит и рассматривает некоторые операции над процессами, типичные для языков функционального программирования.

ЦЕЛЬ РАБОТЫ. Целью настоящей работы была разработка не только и не столько новых алгоритмов решения конкретных задач, сколько общих подходов и методов для их решения применительно к языкам функционального программирования. На протяжении всей работы показывается, что рассматриваемые языки удивительно хорошо подходят именно для решения задач перебора.

НАУЧНАЯ НОВИЗНА. В настоящей работе пекоторые известные алгоритмы приобретают новую трактовку, исходя из свойств языков функционального программирования. Разработаны и новые алгоритмы, которые также ориентированы на применение подобных языков.

ТЕОРЕТИЧЕСКАЯ И ПРАКТИЧЕСКАЯ ЦЕННОСТЬ. Методы программировапия, рассмотренные в данной работе имеют важное практическое применение. Действительно, при решении практических задач дискретной оптимизации часто возникает необходимость не учитывать какое-либо ограничение. Это связано либо с недостаточной мощностью вычислительной техники, либо с невозможностью точно описать это ограничение. Вот тогда-то и возникает желание найти не только оптимальное решение, но и решения, близкие к нему, или, точнее, возникает желание перебирать допустимые решения в порядке ухудшения целевой функции.

ОБЩАЯ МЕТОДИКА ИССЛЕДОВАНИЯ. В качестве инструмента для реализации алгоритмов взят язык функционального программирования Шгапс1а [1].

ПУБЛИКАЦИИ. Часть результатов диссертации содержатся в работах [15] и [15].

СТРУКТУРА И ОБЪЕМ РАБОТЫ. Диссертация состоит из введения, шести глав и трех приложений и занимает, включая библиографию 79 страниц. Библиография содержит 16 наименований работ.

СОДЕРЖАНИЕ РАБОТЫ

Язык функционального программирования Miranda еще не получил достаточно широкого распространения в России, и поэтому в Главе 2 дан его краткие обзор. Более полное описание этого языка можно найти в первоисточнике [1]. В чем же различие между языками функционального программирования и «обычными» языками программирования? Покажем это на примере. Вот код на языке С, вычисляющий сумму натуральных чисел от 1 до п:

result = 0;

for (i=l; i<=n; i++) do result += i;

а вот пример аналогичной функции на Miranda:

sum 0=0

sum n = n + sum (n-1)

На этом примере видно основное различие — в программах, написанных на «обычных» языках, явно предписываются к выполнению некоторые действия, в то время как в языках функционального программирования происходит декларирование функций.

Языка функционального программирования делятся па «чисто функциональными» (Miranda, Haskel), в которых любые вычисления происходят только путем выполнения функций, и на «вполце функциональные» языки, которые допускают некоторые эффекты, свойственные «обычным» языкам (Scheme, Standard ML).

Языки функционального программирования можно разделить па две основные группы по методу выполнения вычисление. Первая из них — языки «прямого» выполнения. К ним отпосятся, например, ASpecT, ML, НОРЕ. Такие языки характерны тем, что при выполнении программ аргументы вызываемых функций всегда вычисляются до конца, вне зависимости от того, потребуются они или нет. Вторая группа — языки «ленивого» выполнения. Это такие языки, как Miranda, Haskell, Gofer. В них, при выполнении какого-либо выражения, никакое подвыражение пе станет вычисляться, покуда оно не понадобилось. Отдельно в этом разделении стоит язык Clean, в котором используются оба рассмотренных метода выполнения, и метод выполнения может быть выбран пользователем для каждого аргумента функции отдельно.

Используемый в этой работе язык функционального программирования Miranda был разработан в 1985-86 годах под руководством Д. Тернера. Это чисто функциональный язык, использующий «ленивое» выполнение. Miranda — это коммерческий продукт компании Research Software Ltd и не имеет свободно распространяемой версии. Miranda работает под операционной системой UNIX Этот язык очень удобен для проверки и тестирования алгоритмов.

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

1. Задача перебора числа на слагаемые (с точностью до перестановки слагаемых).

'Наряду с языком Miranda использовалась и его разновидность Amanda, для которой существует интерпретатор в системе MS-DOS. Различия в их синтаксисе незначительны.

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

3. Перебор сумм элементов массивов. Здесь реализован прием явного выделения первого элемента в списке результата. Такой метод приносит значительную выгоду в производительности, поскольку некоторые процессы слияния могут пе начаться вообще из-за «ленивости» выполнения в Miranda. Для сравнения приводится аналогичная функция, но без выделепия первого элемента в решении. Разница в их производительности более чем заметна. Подобный прием явного указания начальных элементов часто используется в этой работе при реализации алгоритмов перебора субоптимальных решений.

Далее приведена универсальная функция для перебора соединений списков путем какой-либо операции ор. На примере такой функции видна унифицированность подходов Miranda к близким по постановке задачам.

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

Функция partit п выдает список разбиений числа п на слагаемые сгруппированно по слагаемым одного размера, так что разбиение 6+6+4+4+4+4+4+2+1 + 1 + 1 числа 37 задается списком [(6,2), (4,5), (2,1),(1,3)]. Функция partit выдает список разбиений но возрастанию максимального слагаемого в разбиении.

Нами введепа новая операция — прямая сумма списков деревьев. Операндами являются списки деревьев (пусть количество списков n), а результат выполнения этой операции — список всевозможных объединений n деревьев — по одному из каждого исходного списка деревьев. Функция dault вычисляет прямую сумму списков деревьев.

dtmult a n а вычисляет все n-элементные подмножества списка деревьев а и объединяет элементы (т.е. деревья) в получившихся подмножествах в один граф со сдвигом номеров всех вершин в каждом дереве на я относительно предыдущего присоединенного дерева.

mapt k а увеличивает номер каждой вершины в списке деревьев а на значение к, задаваемое в виде параметра.

Опишем алгоритм. Пусть требуется построить корневые деревья из п дуг. Будем перебирать разбиения числа n в том виде, как они генерируются функцией partit. Множество искомых деревьев разбивается на непересекающиеся классы, соответствующие этим разбиениям. Так, класс деревьев, соответствующий разбиению [(ej, 6j), (a2,6j),..., (a*, 6*)] определяется следующим образом:

Из корневой вершины выходят 61 + 62-)----+ Ьц дуг, концы Ь\ из этих дуг являются

корневыми вершинами поддеревьев из Oj -1 дуг, концы 62 из этих дуг являются корневыми вершинами поддеревьев из aj — 1 дуг,..., концы 6* из этих дуг являются корневыми

вершинами поддеревьев из а* — 1 дуг.

Таким образом, внутри класса получено ¡>1 + Ь2 Ч-----(- Ьк задач меньшей размерности,

среди которых к различных. Результаты каждой из этих к задач обрабатываются функцией <1гтиН (сИ.пш1г <деревья-нз-(а| — 1)-дуг> Ь/). Полученные к списков обработаем функцией йтиИЛ.

Второй параграф данпой главы посвящен перебору некорневых деревьев. Приводятся определения и теоремы, близкие к рассмотренным в работе Камила Жордана [10] (см. [8], [9]). Здесь формулировки этих определений и теорем несколько изменены (для применения к нашей конкретпой задаче) и дается более подробное, чем в [10] их доказательство, конструкции которого служат основой для алгоритма перебора.

Пусть имеется дерево Т. Пусть V — некоторая вершина этого дерева, из которой выходят к дуг, и Т\, Гг, ..., Т* — разбиение исходного дерева на поддеревья, выходящие из вершины V. Пусть — некоторые вершины дерева Т.

Определение 1. Вершина V называется центровой, если |7(| < для любого г из

1: Л.

Определение 2. Дуга (г^кг) называется медианой, если при удалепии этой дуги из исходного дерева полученные два поддерева будут иметь одинаковое число дуг. Утверждение 1. Дерево Т может иметь не более одной центровой вершины. Утверждение 2. Дерево Т может иметь ие более одной медианы.

Утверждение 3. Дерево Т не может одновременно иметь медиану и центровую вершину. Утверждение 4. Дерево Т имеет хотя бы одну центровую вершину или медиану. Утверждение 5. В дереве с четным числом дуг медианы быть не может.

Предложенный алгоритм основан на Утв.1-5 Заметим, что множество неизоморфных деревьев является подмножеством множества неизоморфных корпевых деревьев. Исходя из этого, а также из Утв.1-4 можно неизоморфные деревья получать из множества корневых деревьев, беря из него только те элементы, у которых корневая вершина являются центровой и те, у которых корневая вершина инцидентна медиане. Классы деревьев, описанные в алгоритме перебора корневых деревьев, устроены таким образом, что нам не нужно проверять, будет ли корневая вершина каждого построенного дерева центровой. А именно, либо у всех деревьев данного класса корневая вершина является цептровой, либо ни у одного дерева данного класса корневая вершина не является центровой. Таким образом, получив список разбиений, которые порождают классы деревьев, мы фильтруем его, отбрасывая разбиения, не порождающие деревья с центровой корневой вершиной. Деревья с корневой вершиной, инцидентной медиане, отсеянные на предыдущем этапе, мы включаем следующим образом. Пусть рассматриваются деревья из п дуг. Согласно Утв.5 неизоморфные деревья с медианой существуют только при нечетном п. Рассмотрим всевозможные пары корневых деревьев из (и — 1)/2 дуг (упорядоченные, для того чтобы пе было повторов). Соединяя корни деревьев дугой в каждой паре, получим список всех неизоморфных деревьев из п дуг с медианой.

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

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

В Главе 5 рассмотрены алгоритмы нахождения кратчайшего пути и перебора fe-оптимальных путей в ориентированном графе с положительными длинами дуг в нескольких разновидностях. В основе всех этих алгоритмов лежит известный алгоритм Дейкстры для нахождения кратчайшего пути [3]. Постановку задачи см. напр. в [2, 4], упомянутый алгоритм см. напр. в [11].

Задача перебора fe-оптимальных путей встречалась в литературе многократно, однако, как правило, речь шла о решении этой конкретной задачи. Представляется более правильным развивать общие подходы к решению задач перебора дискретных объектов и считать задачу о путях важным примером, на котором опробуются эти общие подходы. В этой связи следует особо назвать статьи Лаулера [6J, в которой приводится общий для таких задач принцип слияния списков решений, получаемых из подзадач. В [7] развивается такой общий подход и упоминается об удобстве языков функционального программирования для реализации алгоритмов перебора. В отличие от указанной работы, здесь приводится подход к решению поставленной задачи, ориентированный на применение языков функционального программирования и показывается универсальность такого подхода для решения близких по постановке задач, причем алгоритмические схемы в сравнении с [7] значительно изменены.

Рассмотрены шесть алгоритмов для решения задач, связанных с перебором путей. Точнее, алгоритм практически один, мы лишь рассматриваем его вариации при различных постановках задачи. Во-первых, это сделано для того, чтобы показать, как хорошо подходит язык Miranda для реализации алгоритмов перебора — видно, что алгоритм перебора путей на Miranda почти не отличается от алгоритма нахождения кратчайшего пути. Во-вторых, нам хотелось показать мобильность этого языка, а именно, па нем легко переключаться между различными, но сходными по постановке задачами. Итак, алгоритм dijkstra — находит длину кратчайшего пути, с него удобнее начать как с основы, на которой строится все остальное. Реализуя возврат по произведенным ветвлениям получим алгоритм dijkstrap, который находит сам кратчайший путь. Далее мы перейдем к нашей главной цели — к составлению списков путей или их длип. В работе [7] был предложен естественный подход к решению этой задачи, — для каждой вершины хранится упорядоченный список значений путей до нее; список путей до некоторой вершины получается путем слияния списков путей до вершин, инцидентных входящим дугам, с соответствующими сдвигами. Здесь предлагается подход, более привычный для функционального программирования. Все вычисленные значения путей до вершин графа располагаются не в нескольких, соответствующих вершинам, списках, а в одном, упорядоченном по возрастанию потенциала. На каждой итерации алгоритма мы берем «голову» этого списка, вычисляем новые значения потенциалов вершин, инцидентных дугам, выходящим из «головы», и сливаем полученный список с «хвостом»; в случае, если «голова» окажется конечной вершиной пути, то берем ее потенциал, как очередное значепие искомого списка. Функция enuovals находит список длин всех путей в порядке их возрастания. Незначительно изменив основную функцию получим cnnnptha — алгоритм для нахождения списка самих путей в порядке возрастания их длин. Потом мы займемся

поиском простых путей, то есть путей пе содержащих контуров. Длины простых путей находит функция aiaplvals в которую мы поставим фильтр для отбрасывания ненужных решений. И, наконец, для исчерпания проблемы описана функция eieplpttm, которая перебирает сами простые пути.

Все описанные в этой главе функции внешне мало отличаются друг от друга. Основной функцией среди них можно считать di jketra — остальные получаются путем некоторых изменений этой функции. В этом, несомненно, большая заслуга языка Miranda, который предлагает унифицированный подход ко многим типам данных. Также видно, что этот язык «немногословен», выражения, требующие на других языках страницы кода, здесь занимают лишь несколько строк.

Глава 6 посвящена задаче перебора перестановок.

Пусть заданы два вектора а[1:п] и Ь[1:п]. Требуется найти несколько первых элементов списка перестановок вектора Ь (или, при достаточно малых п, весь список), элементы которого упорядочены по неубыванию скалярного произведения на вектор а. Эта задача интересна тем, что во-первых мы точно знаем количество всех решений (оно равняется п!) и следовательно при выполнении алгоритмов мы можем оценить, какую часть весго списка мы нашли. Во-вторых трудность этой задачи очень сильно растет при увеличении ее размерности и этот факт вынуждает создавать как можно более эффестивкые алгоритмы. В-третьих данная задача может иметь применение в качестве оценочной задачи при решении более сложной квадратичной задачи о назначениях.

Не умаляя общности считаем, что элементы массива а расположены в порядке неубывания.

Первый подхсщ> Простейший алгоритм заключается в следующем: перебирая всевозможные значения последнего элемента в перестановке получаем задачу меньшей размерности и сливаем получившиеся списки. Для каждой задачи меньшей размерности проделываем аналогичную операцию.

Очевидно, что работающая таким образом функция (pernal) может выдать либо все, либо ничего. (И нужно признаться, что она испытывает трудности уже при размерности задачи равной семи.) Такая малая производительность связала с тем, что для вычисления даже первого значения искомого списка требуется вычислить весь этот список целиком. Однако, нам нужды не все, а только начальные элементы Д{1:п!). Применим метод, который уже встречался при описании функции слияния нескольких списков. Именно, в каждой подзадаче явно укажем первый элемент в списке решений. Его мы знаем — он получается при перестановке элементов массива Ь в порядке неубывания. Остаток списка решений будем получать слиянием списков для подзадач с зафиксированной частью перестановки (в конце).

Опишем на примере итерацию основной функции регав2. Пусть начальные данные таковы:

bega=[8,7,5,4,2] begb=[l,3,6.8,9]

Тогда (учитывая, что8-1+7-3 + 5- 6 + 4- 8 + 2- 9= 109)

ротш2 [1,3,6,8,9] с

109:(lmerge [ пир (+( 1»7+6«5+8*4+9«2 )) lmerge [ репш [3] ],

тар (+(3*4*9*2 ))

lmerge [ (вар (+(3«Б)) peras [1,6]),

(map (+(1*5)) puns [3,6]) ],

map (+(9*2 ))

lmerge [ (вар (+(6*4)) perns [1,3,8]), (вар (+(3*4)) perns [1,6,8]), (map (+(1*4)) perns [3,6,8]) ],

map ( +0)

lmerge [ (map (+( 8*2)) perns [1,3,6,9]), (вар (+( 6*2)) perms [1,3,8,9]), (map (+( 3*2)) perns [1,6,8,9]), (map (+( 1*2)) perms [3,6,8,9] ] )

На следующих итерациях вычисления происходят аналогично.

Как первая, так и вторая процедура имеют тот недостаток, что происходит повторное вычисление уже вычислявшихся когда-то частичных решений. Поэтому представляется разумным хранить уже вычисленные частичные решения в некоторой базе данных. При необходимости вызвать процесс вычисления какого-либо частичного решения, мы вначале должны посмотреть, не вычислялось ли оно уже, и если оно уже вычислялось, то просто взять его из базы данных. Если же оно еще не вычислялось, то вызываем процесс вычисления и, после получения результата для данного частичного решения, заносим его в базу данных. Линейная структура базы данных нам не подойдет, т.к. если мы будем нумеровать перестановки, то даже в начале вычислений могут появиться слишком большие номера, а если мы будем записывать в нее значения перестановок по мере поступления, то на поиск нужного значения будет затрачиваться слишком мпого времени. Поэтому мы решили остановиться на древовидной структуре базы данных. Дерево t имеет следующую структуру. Оно бинарное и состоит из уровней. В вершине каждого не последнего уровня находится пустой список. Ветвление организовано по включению и невключению i-ro элемента начального списка Ь в частичное решение. Таким образом, на последнем уровне дерева t, мы имеем все подмножества списка бив вершины последнего уровня записываем частичные решения, соответствующие этим подмножествам.

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

Второй подход. Этот подход был предложен И.В.Романовским. Вначале рассматривается функция, практически аналогичная по строению с ранее рассмотренной, но позволяющая, с помощью незначительных ее модернизаций добиваться поразительных результатов. Главное ее отличие состоит в том, что ветвление на каждой итерации осуществляется не по всем возможным значениям последнего элемента в перестановке, соответствующей очередной подзадаче, а по альтернативе, является ли некоторый элемент последним элементом в перестановке или нет. Таким образом, дерево ветвлений получается бинарным, и на каждом уровне этого дерева мы производим слияние следующих двух списков решений подзадач:

(1) Список решений таких подзадач, в которых зафиксирован последний элемент исходной перестановки.

(2) Список решений таких подзадач, в которых на последнее место в запрещено ставить последний элемент исходной перестановки.

Проиллюстрируем действие основной функции на примере:

а=[7,5,4,2] Ъ=[3,6,8,9]

Здесь, для краткости, р [<спнсок>] обозначим как 1<список>], операцию сдвига иа х • у, как х - у+, фигурной скобкой обозначим операцию слияния.

{3,6,8,9)

2 ■ 9 + [3,6,8]

4-8+ [3,6] = [7.3 + 5-6,7.6 + 5-3]

8 + 5-3] 6 + 5-8,7-8 + 5-6]

Г4-6 + [3,8] = [7-3 + 5.8,7-[3,8,6] {

|М,31 = 4-3 + [6,8] = [7-6

2-8 +[3,6,9]

[3,6,9,8]

4 • 9 + [3,6] = [7 • 3 + 5 • 6,7 ■ 6 + б - 3]

{4-6 + [3,9] = 17 - 3 + 5-9,7-9 + 5- 3] [6,9,3] = 4 - 3 + [6,9] = [7* 0 + 5- 9,7-

9 + 5-6]

[3,8,9,6]

2 • 6 + [3,8,9]

[4-9 +[3,8] = [7-3 + 5-8,7-8+ 5-3]

U-8 + [3,8] = [7-3 + 5- 9,7-9 + 5-3] ('3 |[8,9,3] = 4-3+ [8,9] = [7-8+ 5-9,7-9+ 5-8]

[6,8,9,3] = 2 - 3 + [6,8,9]

4-9+ [6,8] = [7-6+ 5-8,7-8+ 5-6]

8 + [6,9] = [7-6 + 5-9,7-9 + 5-6) 6+ [8,9] =

[7-8 + 5-9,7-9 + 5-8]

i 4-8 + [6,8] = [8,9,6] = 4-i

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

Можно заметить, что первый элемент списка (1) заведомо меньше, чем первый элемент списка (2). Поэтому, при слиянии этих двух списков, в качестве первого элемента результата можно заведомо брать первый элемент списка (1), а потом уже сливать остаток списка (1) и список (2) обычным образом.

Следующий шаг в улучшении этого алгоритма основан на том, что, на самом деле, мы знаем, на сколько первый элемент списка (1) меньше, чем первый элемент списка (2). Тем самым, мы можем реализовать отсроченное слияние в полном объеме.

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

На нулевой итерации алгоритма мы имеем список, состоящий Из одного элемента — это начальная (оптимальная) перестановка (список а) и ее значение. Пусть на некоторой итерации имеется список перестановок и их значений (z:lst) и он упорядочен по возрастанию значений. Возьмем его первый элемент в качестве очередного элемента в итоговом списке. Вычислим список последователей элемента х, сольем его со списком 1st (по значению перестановки) и перейдем к следующей итерации, беря в качестве очередного списка перестановок результат произведенного слияния.

Алгоритм вычисления списка последователей некоторой перестановки, должен удовлетворять условиям: 1) множество пересечений последователей любых различных пе-

рестановок пусто; 2) при начальной (оптимальной) перестановке н при описанных выше действиях на каждой итерации, в качестве первого элемента списка (х: Ist) будет очередной элемент (без пропусков) искомого списка. (На самом деле, упорядоченность первых элементов (x:lst) на каждой итерации получится автоматически, по способу построения этого списка (слияние), нас же в основном интересует, чтобы в итоговом списке не было пропущенных элементов.) Иначе говоря, эти два условия требуют, чтобы оптимальная перестановка, множество последователей оптимальной перестановки, множества последователей всех последователей оптимальной перестановки, и т.д. образовывали разбиение множества всех перестановок.

Предъявим алгоритм построения последователей перестановки и покажем, ч го он удовлетворяет описанным выше условиям.

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

Пусть имеется некоторая перестановка, и активная ее часть имеет п элементов. Пусть известно значение дапной перестановки.

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

B) С исходной перестановкой (а точнее с ее активной частью) проделываем аналогичную операцию, начиная со второго элемента, потом, начиная с третьего элемента, с четвертого, . . . , с п — 1-го.

C) Получившиеся списки последователей сливаем в один.

Заметим, что множество последователей перестановки с одноэлементной активной частью будет полагаться пустым.

Рассмотрим пример: а= [8,7,5,4,2]

Списки, полученные при указанных преобразованиях списка а:

[2.8,5,4,2] [§¿5.7,4,2] [8,7,4.5,2] [8,7.6,2,4]

[7^5,8,4,2] [8,5,4,7,2] [8,7,4,2,5]

[7,5,4,8,2] [8,5,4,2,7] [7,5,4,2,8]

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

В работе доказано, что с помощью описанной процедуры, из начальной перестановки можно получить любую перестановку.

Среди перестановок, генерируемых алгоритмом, одинаковых нет. Для этого достаточно показать, что количество элементов, выдаваемых алгоритмом, равно п!. Этот факт доказывается индукцией по размерности задачи.

Эгот, последний, подход был реализован также на языке С, текст программы находится в Приложении А. Так же была написана программа, работающая с несколько другой постановкой задачи, а именно, в пей в качестве начальных данных требуется указать не количество требуемых значений, а величину последнего требуемого значения. Исходный текст этой программы приведен в Приложении Б. Заметим, что цель написания всех программ на языке С, приведенных в данной работе, была пе в разработке методов программирования задач перебора на данном языке, по достижение максимальных результатов но производительности. Поэтому данные программы не претендуют на детальное изучение, но показывают практическую эффективность рассматриваемых алгоритмов. Программы написаны на языке MS Visual C/C++.

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

Все алгоритмы были реализованы таким образом, что движение по перестановке в процессе итераций выполнялось от конца к началу. Это делалось специально для того, чтобы можно было адекватно сравнивать производительности алгоритмов.

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

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

Было замечено, что производительность предложенных функций в основном зависит от некоторых характеристик следующего списка.

d=[a!i*b!(i+l) + a!(i+l)»b!i - a!i*b!i

- a!(i+l)*b!(i+l) I i<-[0..#a-2]l

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

Несколько лучшие результаты получим, если вместо половин списков брать начальную и конечпую треть.

Для сравнения эффективности предложенных подходов проводилось их тестирование па 48, случайным образом выбранных, начальных данных размерности 14, также прово-

дилось тестирование на увеличение размерности задачи.

Кроме большей продуктивности, последний подход к решению поставленной задачи удобен тем, что при незначительных изменениях исходного «рода можно находить пе только значения перестановок, но н сами перестановки. (И, кстати, в программах на С сделано именно так.) Существенное изменение претерпит только структура данных. Также, программу, написанную на основе этого подхода, можно легко изменить таким образом, чтобы выдавались только четные или нечетные перестановки. Нахождение самих перестановок и перебор четных и нечетных перестановок реализованы в последнем параграфе шестой главы.

Теспо перекликается с задачей перебора перестановок задача перебора назначении. Она рассматривается в Главе 7. Рассмотрены два различных алгоритма решения этой задачи. Первый из них предложен Katta G. Murty в работе [12]. Второй основан на алгоритме, показавшем наилучшие результаты при решении задачи о переборе перестановок. Их общая черта в том, что и в одном и в другом алгоритме реализован итеративный процесс без ветвлений.

Итак, вначале опишем алгоритм, изложенный в [12]. Точнее, мы лишь немного изменим его, для более удобного программирования на Miranda.

Как известно, начальные данные в задаче о назначениях представляются в виде матрицы. Каждый (i,_j)-ufl элемент этой матрицы — это убыток от назначения ¿-го претендента на j'-ю должность. Пусть матрица исходных данных для задачи о назначениях задана списком списков вО, причем вО — это список строк, а каждая строка — это список элементов в строке.

Найдем оптимальное решение задачи о назначениях. Пусть оптимальна перестановка (ах,ai,...,в„). Это решение есть первый элемент результирующего списка. Рассмотрим следующие подзадачи, порожденные этим элемептом: все задачи, у которых на первом месте зафиксирован a j, a на втором не стоит элемент aj; все задачи, у которых на первом и втором местах зафиксированы a¡ и а2 соответственно, а на третьем месте пе стоит элемент о5; все задачи, у которых па первом, втором и третьем местах зафиксированы <¡¡, ог и а3 соответственно, а на четвертом месте не стоит элемент aj и т.д. Очевидно, что таким образом мы разделили все множество решений на оптимальное и все остальные. В каждой из рассмотренных выше п ■ (п —1)/2 задач найдем оптимальное решение и запомним его. В качестве второго элемента в результирующем списке возьмем наименьшее оптимальное решение рассмотренных задач. С этим решением, а точнее с еще не зафиксированной его частью, проделаем ту же операцию, что и с оптимальным решением исходной задачи.

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

Теперь предложим алгоритм, который в отличие от алгоритма, изложенного в [12], не требует решения задачи о назначениях на каждой итерации. Нас не интересует нахождение оптимального решения этой задачи, будем считать, что оно известно. Ищем следующие по оптимальности решения в порядке возрастания значения. Предположим, что дан список списков яО — условие задачи о назначениях оптимальное решение кото-

ров получается «жадным» способом. Предположим, что >0 отсортирован таким образом, что оптимальным решением является следующая перестановка: [0. .#»0-1].

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

На каждой итерации алгоритма имеем два списка (х:1в11) и (у :1аг2). Элементы этих списков имеют вид ({перестановка!), (оценка), (значение)). Здесь, как и раньше рассматривается только активная часть перестановки. Список (х:1вг1) отсортирован в порядке неубывания оценки и состоит из элементов, для которых последователи еще не вычислялись, (у:18Ъ2) отсортирован в порядке неубывания значения и состоит из элементов, для которых последователи уже вычислены.

Нулевая итерация: Список (х:1вЪ1) состоит из одного элемента ([0. .#т0-1] ,п,п). Список (у:1вг2) пуст.

К- я итерация: Вычислим список последователей элемента х и отсортируем его в порядке неубывапия оценки. Введем обозначения для трех величин: еагх — оценка элемента х, гпх — значение элемента х, гпу — значение элемента у. Если евЪх меньше каждого из гпх и гну, то в решение на данной итерации ничего не добавляется, из списка (х:1зИ) удаляется первый элемент и в оставшуюся часть вливается вп1а, элемент х вливается в список (у:1зг2). В противном случае сравниваем гпх я гау. Если гпх меньше, чем гпу, то гпх добавляем в решение, в качестве нового (х:1вЪ1) берем результат слияния 181:1 и вп1а, (у оставляем без изменений. Если гпх не меньше, чем гпу, то добавляем в

решение гну , (х:1вг.1) оставляем без изменений, из (у :1вг2) удаляем первый элемент.

При пустых Сх:1вг1) и (у :1вг2) алгоритм заканчивает работу. Если пуст только (у :1вг2), то сравниваются евЪх и гпх и предпринимаются аналогичные действия. Если пуст только (х:1аг1), то в решение включаем гпу, из (у:1в12) удаляем первый элемент, (х:1вЪ1) оставляем без изменения.

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

Далее, путем тестирования сравниваются эффективности алгоритма, предложенного КаНа в. Мийу и последнего алгоритма. При больших разбросах в начальных данных более эффективен алгоритм Каиа в. Мийу, при малых — алгоритм основанный на последнем подходе в исследовании задачи о перестановках.

В Приложении В приведена программа на языке С для решеявж этой задачи последним из рассмотренных методом.

ЛИТЕРАТУРА

1. Turner D. Л. An overview of Miranda // Research Topics in Functional Programming, D. A. Turner, cd., Addison-Wesley, 1990, pp. 1-16.

2. Romanovsky J. V. On Enumeration of Near to Best Solutions ill Discrete and Dynamic Programming // DIMACS report 93-64, 1993.

3. Dijkstra E.W. A note on two problems in connection with graphs // Numerishe Math., 1959, vol. 1, pp. 109-121.

4. Rosen, ./. B-, Su S.-Z., Xue G.-L. Algorithms for the quickest path problem and the enumeration of quickest paths // Computers and Operations Research, 1991, 18, pp. 579584.

5. Minieka E., Shier D. A note on au algebra for the к best routes in a network // Journ. Inst. Math. Appl., 1973, 11, 2, pp. 145-149.

f>. Lawltr E. L. A procedure for computing the К best solutions to discrete optimization problems and its application to the shortest path problem // Management Science, 1972, vnl. 18, pp. 401-405.

7. Гомаиоиский И. В., Скурипа JI. Л. Л"-оптимальные решения в задачах дискретного и динамического программирования // Исследование операций и статистическое .чодслирошшис, Санкт-ПетербургекиИ университет, 1993, с. 23-31.

8. Харари Ф. Теория графов. М. «Мир», 1973, 300 с.

9. Харари Ф., Палмер 9. Перечисление графов. М. «Мир», 1977, 324 с.

10. Joixlan С. Sur les assemblages de lignes // J. Tbine. Angew. Math., 1869, 70, S. 185-190.

11. Романовский И. В. Алгоритмы решения экстремальных задач- М., 1977, 436 п.

12. Kattn G. Marty An algorithm for ranking all the assignments in order of increasing cost // J. of the Operations Research Society of America, 1968, v.16, num.3, pp.682-687

13.Ромапоаский И.В. Лекции о субоптимальных решениях, в печати.

14. R.Plasmrijer, M.Eekelen Functional programming and parallel graph rewriting. Addiso-Wesley, 1993, 571p.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

15. PoMattoocKuÜ И.В., Стукалов Д.Ю. Использование языка функционального программирования Miranda в алгоритмах перебора ^-оптимальных путей // Вестник СПбГУ. Сер.1, 1996, Вып.4 (N 22), с.42-51.

16. Ромаиооский И.В., Стукалов Д.Ю. Алгоритмы перебора цеиэоморфных деревьев // Вестшгк СПбГУ. Сер.1, 1997, Вып.1 (N 1), г.46-52.