автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Применение кластеризации ситуаций в эвристических алгоритмах для задач дискретной оптимизации

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

Мельникова Елена Анатольевна

Применение кластеризации ситуаций в эвристических алгоритмах для задач дискретной оптимизации

05.13.18 —математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Тольятти-2009

003487831

Работа выполнена в Тольяттинском государственном университете

Научный руководитель: доктор физико-математических наук,

профессор Мельников Борис Феликсович

Официальные оппоненты: доктор физико-математических наук,

профессор Смирнов Юрий Геннадьевич

доктор физико-математических наук, доцент Сафронов Александр Иванович

Ведущая организация: НИИ Механики и прикладной математики

им. И.И. Воровича

Южного Федерального Университета

Защита диссертации состоится «29» декабря 2009 года в 12 часов на заседании диссертационного совета Д212.264.03 при Тольяттинском государственном университете по адресу: 445667, Тольятти, ул. Белорусская, 14

С диссертацией можно ознакомиться в библиотеке Тольяттинского государственного университета.

Отзывы по данной работе в двух экземплярах, заверенные печатью организации, просим направлять по адресу: 445667, Тольятти, ул. Белорусская, 14, ТГУ, диссертационный совет Д212.264.03

Автореферат разослан «_» ноября 2009 года

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

к.п.н. ПивневаС.В.

Общая характеристика работы

Актуальность темы

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

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

Цель работы

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

Основные задачи исследования:

• модификация модели вычислений, представляющей собой незавершенный

метод ветвей и границ,

• разработка подхода к формированию метрик на множестве подзадач в различных задачах дискретной оптимизации,

• разработка оригинального алгоритма кластеризации ситуаций в задачах дискретной оптимизации,

• разработка и реализация эвристических алгоритмов для решения задач дискретной оптимизации с применением кластеризации ситуаций,

• разработка подхода для создания соответствующих компьютерных программ.

Объект исследования

Объектом исследования являются несколько конкретных задач дискретной оптимизации:

• вершинная минимизация недетерминированных конечных автоматов,

• минимизация дизъюнктивных нормальных форм,

• псевдогеометрическая версия задачи коммивояжёра,

• игровые программы для недетерминированных игр (версии бэкгеммона).

Предмет исследования

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

Методы исследования

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

Результаты исследования

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

Научная новизна

Разработанный алгоритм кластеризации является новой модификацией алгоритма из группы "Hierarchical Clustering Algorithms". Новизна мультиэвристиче-ского метода решения задач дискретной оптимизации состоит в применении комплекса эвристик, в том числе кластеризации подзадач на основе разработанных автором метрик. Предложен также подход к разработке компьютерных программ на основе этого метода. Также новыми являются эвристики, предназначенные для работы с деревом перебора в недетерминированных антагонистических играх

Практическая значимость исследования

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

Достоверность результатов

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

Основные положения, выносимые на защиту

1. Разработка алгоритма кластеризации и обоснование возможностей его практического применения в некоторых предметных областях.

2. Исследование возможностей применения алгоритма кластеризации в задачах дискретной оптимизации.

3. Разработка конкретных вариантов «матричных» и «списочных» метрик для различных задач дискретной оптимизации.

4. Модификация мультиэвристического подхода решения задач дискретной оптимизации, связанная со включением в работающий в нём незавершённый метод ветвей и границ эвристик для применения кластеризации ситуаций (с использованием «матричной» либо «списочной» метрики).

5. Разработка и' компьютерная реализация алгоритмов с применением всех разработанных автором эвристик для решения нескольких задач дискретной оптимизации (вершинной минимизации недетерминированных конечных автоматов, минимизации дизъюнктивных нормальных форм, псевдогеометрической версии задачи коммивояжёра). Описание подхода к созданию таких программ.

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

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

Апробация работы

Результаты диссертационной работы докладывались и обсуждались на:

• II Всероссийской научно-технической конференции «Искусственный интеллект в XXI веке» (Пенза, 2004);

• XTV Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (Пенза, 2004);

• региональной научно-технической конференции «Научные чтения студентов и аспирантов» (Тольятти, 2005);

• XI международной конференции "Advances in Computer Games Conference", ICGA 2005 (Тайвань, Тайней, 2005);

• Всероссийской научной конференции «Методы и средства обработки информации» (Москва, МГУ, 2005);

• XVI Международной научно-технической конференции «Математические методы и информационные технологии в экономике социологии и образовании» (Пенза, 2005);

• международной конференции "First International Conference on Software and Data Technologies", ICSOFT 2006 (Португалия, Сетубаль, 2006);

• II Международной конференции "Informatics in Secondary Schools: Evolution and Perspectives", ISSEP 2006 (Литва, Вильнюс, 2006);

• IX Международной конференции «Интеллектуальные системы и компьютерные науки» (Москва, МГУ, 2006);

• международной конференции "Infinity in Logic and Computation" (ЮАР, Кейптаун, 2007);

• международной конференции "9th International Workshop on Computer Science and Information Technologies", CSIT2007 (Уфа, 2007);

• научном семинаре в НИИ им. И.И.Воровича при ЮФУ (Ростов-на-Дону, 2009).

Публикации

По теме диссертации опубликовано 14 работ, из них 2 - в изданиях, рекомендованных ВАК.

Личный вклад автора

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

Структура и объём диссертации

Диссертация состоит из введения, 6 глав, 2 приложений и списка литературы, состоящего из 102 наименований источников отечественных и зарубежных авторов. Общий объём диссертации составляет 152 страницы.

Основное содержание работы

В первой главе диссертации содержится описание задач дискретной оптимизации и применяемых методов их решения - как классических, так и разработанных автором диссертации. В первом разделе приведено описание нескольких классических задач дискретной оптимизации. Во втором разделе содержится . обзор классических подходов к созданию эвристических алгоритмов решения задач дискретной оптимизации. В третьем разделе наиболее подроб-но описаны те задачи, на которые делается упор в настоящей диссертации: за-дача вершинной минимизации недетерминированных конечных автоматов (НКА), задача минимизации дизъюнктивных нормальных форм (ДНФ) и псевдогеометрическая версия задачи коммивояжёра (ЗКВ). Рассматривается именно эта версия ЗКВ по следующим причинам:

• псевдогеометрической версия является моделью, которая более точно описывает задачи, возникающие на практике,

• в этом случае один шаг МВГ в среднем не дает значительного упрощения рассматриваемой матрицы ЗКВ,

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

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

Вторая глава посвящена предлагаемому алгоритму кластеризации. Здесь приведены данные о самом алгоритме; в частности, даны ссылки на схожие алгоритмы, разрабатываемые другими авторами. Кратко рассмотрены некоторые возможные прикладные области практического применения подобных алгоритмов. Также приведены априорные эвристические обоснования применения авторского алгоритма для работы «по аналогии» с подзадачами (ситуациями), получаемыми в процессе решения различных ЗДО.

Если говорить неформально, то сходство предлагаемого алгоритма с большинством других алгоритмов (принадлежащих этой же группе, т.е. "Hierarchical Clustering Algorithms") состоит в том, что в качестве «положительной характеристики» используется минимальное расстояние между кластерами. А основное его отличие - в том, что в качестве «отрицательной характеристики» используется не максимальное расстояние среди элементов одного кластера, а минимальный шаг, применяя который можно построить последовательность попарно близких друг к другу элементов, включающую все элементы кластера. Для вычисления расстояния используются несколько вариантов метрик.

Приведём более формальное описание. Пусть Щ - минимальное расстояние между элементами, входящими в кластеры с номерами i и j, аг(- максимальное расстояние между элементами кластера /. Стандартные алгоритмы кластеризации указанной группы - а также алгоритмы для оценки её качества - обычно используют значения

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

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

• г - рассматриваемый кластер,

• Ш1,...,тп - все его элементы,

• /тл-расстояние между его элементами тип,

• (Л/;,..., Мк) - некоторая конечная последовательность, состоящая из элементов кластера т1,...,т„ и включающая каждый элемент кластера по крайней мере 1 раз.

Тогда считаем, что

горитмы вычисления значений построенные на основе этого определения, весьма несложны.

Далее в качестве примера конкретной матричной метрики представлена метрика, применяемая автором при разработке эвристических алгоритмов для задачи вершинной минимизации недетерминированных конечных автоматов.

Третья глава диссертации посвящена разработанному подходу к организации незавершённого метода ветвей и границ, а также подходу к сравнительной

8

(1)

Заметим, что данное определение не является алгоритмом, однако возможные ал-

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

В следующем разделе описан подход к решению ЗДО, развитие которого является фактически предметом данной диссертации. Основное содержание подхода - эвристика, преобразующая завершённый метод ветвей и границ (МВГ) в незавершённый. Тогда построенный на ее основе алгоритм становится апуйте-алгоритмом. Приведём её краткое описание. Каждый раз при получении очередной задачи (назовём её задачей 7) строится последовательность правых подзадач (ППЗ), содержащая саму задачу Г, правую подзадачу задачи Т, правую подзадачу правой подзадачи задачи Т, и так далее. Каждый раз строятся (и включаются в список задач для потенциального решения в дальнейшем) и соответствующие левые задачи - левая подзадача задачи Т, левая подзадача правой подзадачи задачи Т и так далее. Описанный процесс заканчивается:

• либо при построении тривиальной задачи - в этом случае её решение сохраняется в качестве текущего на данный момент времени псевдо-опгимального решения апуйте-алгоритма;

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

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

Следующий раздел представляет собой подробное описание мультиэвристи-ческого алгоритма решения ЗДО1. В настоящем автореферате, в связи с ограничениями на его объём, мы приводим только краткое его описание, схему. Основу алгоритма составляет итеративный шаг, результатом выполнения которого является очередное пседооптимальное решение, с каждым шагом все больше и больше приближающееся к оптимальному. 1оор{

Шаг 1. Выбор очередной подзадачи для рассмотрения, выбор для нее разделяющего элемента и построение описанной выше последовательности ППЗ; т.е. реализация одного шага МВГ. Шаг 2. Накопившиеся при построении последовательности ППЗ левые подзадачи Образуют «малый кластер». Далее в соответствии с (1) выполняется дальнейшая кластеризация, в ходе которой малый кластер может быть объединен с уже имеющимися.

1 Этот алгоритм разрабатывается всеми участниками нашей иаучиой группы. Личный вклад автора связан с кластеризацией подзадач, возникающих в процессе решения некоторой ЗДО с помощью незавершенного МВГ.

9

Цель кластеризации состоит в следующем: если в будущем для одной из подзадач кластера принимается какое-то решение (о разделяющем элементе), то по возможности, то же самое выполняется и для других. За счет решения подзадач одного кластера «по аналогии», обработка всего кластера выполняется быстро.

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

Шаг 3. Генерация очередного потенциального разделяющего элемента (блока, плоскости и т.п.). В отличие от шага 1, этот разделяющий элемент пока не является конкретным разделяющим элементом для какой-либо конкретной подзадачи. Аналогично 1-му «малому» шагу, сам алгоритм соответствующей генерации тоже сильно зависит от конкретной задачи. Этот шаг выполняется с помощью «жадных» алгоритмов и случайного выбора - и обязательно даёт результат. Шаг 4. Один шаг метода ветвей и границ для вспомогательной задачи дискретной оптимизации, которая использует метод ветвей и границ не для решения основной задачи, а для построения близких к максимальным (по какой-либо естественной метрике) потенциальных разделяющих элементов, (т.е. блока, плоскости, и т.п). При этом, в отличие от основной задачи дискретной оптимизации, здесь сохраняются все решения - даже заведомо далёкие от оптимальных, поскольку для дальнейшей работы (для решения основной задачи дискретной оптимизации) нужны, вообще говоря, все потенциальные разделяющие элементы. Поэтому структура вспомогательной подзадачи как объекта другая, но для неё также формируется последовательность ППЗ.

}

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

2Hromkovii J. Algorithmic^ for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. - Springer, 2003. См. также [15].

10

Для проведения вычислительного эксперимента случайно генерируются входные данные рассматриваемой ЗДО. При этом имеется возможность определить некоторую границу (первоначальную оценку) <7 для стоимости псевдооптимального решения, вычисляемую согласно алгоритмам генерации входных данных. Отметим, что эта граница имеет большую аналогию с т.н. границей Хелда-Карпа3, т.к. используется для тех же самых целей, но вычисляется значительно более простым способом.

Входами каждого эксперимента являются:

• размерность оптимизационной задачи

• количество случайно сгенерированных задач (например, для заданной размерности запускается 100 случайно сгенерированных задач; отметим, что, как и ожидалось, от входа «100 случайных задач» итоговые результаты практически не зависят).

• относительная величина превышения границы в (обычно это - величина порядка 0.1, т.е. 10%).

Для каждого конкретного варианта входных данных определяется время работы, в течение которого стоимость текущего псевдооптимального решения достигает этой границы £7. Надо отметить, что в общем случае нельзя гарантировать, что достижение границы действительно произойдёт. Однако в рассматриваемых конкретных задачах дискретной оптимизации (прежде всего - в задачах минимизации ДНФ и вершинной минимизации НКА, но и не только в них), достижение границы для рассматриваемых типичных «входных данных» происходит гораздо чаще, чем в 50% случаев. Это время (усреднённое для тех задач, где граница была достигнута) назовем «обычным временем для данной размерности», «единицей времени» для входов данной размерности. Отметим, что «входы» 100 и 10% здесь уже не имеют значения.

Тогда для каждого конкретного частного случая проблемы можно рассматривать результаты работы алгоритмов, полученные в течение интервалов времени, составляющих некоторую часть такой единицы времени. Были рассмотрены следующие интервалы времени: 0.1 единицы времени, 0.3 единицы времени, 1.0, 3.0, 10.0, 30.0 и 100.0 единиц времени. Наиболее интересным результатом для дальнейшего анализа является отношение стоимости полученного (за выделенный интервал времени) решения к первоначальной оценке б. В заключении главы описано возможное развитие тем, рассмотренных в ней.

3 Held M., Karp R.M. The traveling-salesman problem and minimum spanning trees. Operation Research, 18 (1970)1138-1162.

Четвёртая глава посвящена применению кластеризации ситуаций в задачах дискретной оптимизации. Во введении приведено эвристическое обоснование применения предложенного алгоритма кластеризации - для решения различных ЗДО.

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

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

• Во втором случае метрика на множестве подзадач определяется на основе описания подзадач, которое формируется в процессе работы МВГ и состоит из двух списков, а именно:

- списка выбранных разрешающих элементов;

- списка запрещённых для будущего выбора (т.н. «табуированных») разрешающих элементов.

Далее будем называть такую метрику «списочной эвристикой».

Удачное применение всех эвристик, соответствующих обеим этим метрикам, можно объяснить следующим обстоятельств'ом. Чем ближе одно из вычисленных значений к минимально возможному, тем больше вероятность применения решения «по аналогии» - т.е. выбора того же самого разделяющего элемента. А конкретные функции для вычисления этой вероятности в конкретных алгоритмах нередко формируются с помощью генетических алгоритмов - однако стбит отметить, что на практике часто удачно работают их «упрощённые» варианты, в которых эти функции подобраны априори, «естественным образом».

Далее в этой главе представлены результаты работы мультиэвристического алгоритма, решающего задачу минимизации недетерминированных конечных автоматов (НКА) на основе описанного выше подхода. В таблице 1. содержатся результаты 4 вариантов тестирования: им соответствуют столбцы таблицы. В каждом варианте тестирования выбиралась размерность задачи. В случае минимизации НКА, под размерностью понимается максимум из числа состояний двух канонических конечных автоматов: для заданного регулярного языка и для его зеркального образа. Также для каждого варианта специальным образом выбиралось число случайно сгенерированных блоков. Это же число является первоначальной оценкой стоимости псевдооптимального решения (границей С7). Строки таблицы соответствуют различным интервалам времени работы алгоритма, длительность которых выражена в процентах от специальной единицы времени, описанной выше.

Значение в таблице - это отклонение средних результатов от первоначальной оценки стоимости решения (границы £7), выраженное в процентах от неё. Положительные (отрицательные) величины - означают улучшение (ухудшение) средних результатов по сравнению с используемым числом блоков (т.е. с заданной границей (?). Например, значение -0.17 означает, что стоимость полученного решения в среднем хуже заранее известного псевдооптимального решения на 0.17%. Поскольку точное оптимальное решение не известно, а известна только некоторая его верхняя граница, то среди вычисленных есть решения, стоимость которых лучше чем граница. Здесь улучшение может наблюдаться из-за возможного «склеивания» двух блоков в один блок большей размерности. Но значительно более важен следующий практический вывод: все полученные результаты близки к 100% , т.е. вычисленное псевдооптимальное решение близко к ожидаемому. Этот факт показывает, что применяемый нами подход -является вполне приемлемым и может быть использован в самых разных задачах дискретной оптимизации.

НКА 20-23 40-45 60-65 80-90

1% -1.62 -0.58 -0.02 -0.02

10% -0.58 -0.14 +0.18 +0,23

30% -0.03 +0.45 +1,02 +1,12

100% 0 +1.01 +1,07 +1,21

300% 0 +1.08 +1,19 +1,21

Таблица 1.

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

<

Рис. 1. НКА; матричная метрика; 0.1 единицы времени

Рис. 2. НКА; списочная метрика; 0.1 единицы времени

Рис. 3. НКА; матричная метрика; 3 единицы времени

Рис. 4. НКА; списочная метрика; 3 единицы времени

Во всех 4 случаях были случайно сгенерированы НКА размерности 80-90, имеющие 300-350 блоков разных размерностей. Графики на рис.1 и рис.2 описывают решение, найденное в течение интервала времени, равного 1 специальной единице времени, а графики на рис.3 и рис.4 - в течение интервала времени, равного 3 таким единицам.. Графики на рис.1 и рис.3 соответствуют «матричной» эвристике для вычисления метрики, графики на рис.2 и рис.4 - «списочной» эвристике. На каждом из 4 графиков отмечено по 40 точек, каждая из которых представляет собой описание решения одной из 40 случайно сгенерированных задач минимизации НКА (частных случаев проблемы). Х-координата каждой точки - относительный результат работы алгоритма без применения эвристик для решения подзадач «по аналогии», а ^-координата - относительный результат работы алгоритма с применением одной из эвристик.

Прямые х=1 и у=1. на каждом из графиков соответствует относительным результатам, равным 1, полученным этими алгоритмами. Кроме того, на каждом графике проведена прямая х=у. Тот факт, что большинство точек двух нижних графиков находятся под прямой х=у, свидетельствует об улучшении результатов работы алгоритмов в результате применения каждой из двух эвристик. Отметим также, что вряд ли возникнет необходимость сравнивать эти две эвристики: по-видимому, в anytime-алгоритмах первую из них есть смысл примешпъ при наличии временных ресурсов - т.е. времени, необходимого для вычисления фактического расстояния между подзадачами.

В следующем разделе главы представлены «матричная метрика» и некоторые результаты счёта для задачи минимизации дизъюнктивных нормальных форм (ДНФ); отметим, что организация таблиц и графиков совпадает с представлением результатов для задачи минимизации НКА - и поэтому в тексте автореферата опущены.

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

функции/А казвдая из которых является описанием текущей подзадачи. Тогда расстояние между подзадачами есть число элементов множества fx e{0,lf\f(x)tg(x)}.

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

В качестве примера рассмотрим функцию от переменных х;, х3 и х4, принимающую значения 1 на следующих наборах переменных (и только на них): (0,0,0,0) (1,0,0,0) (0,0,1,0) (1,0,1,0) (1,1,0,0) (0,1,1,0) (0,0,0,1) (1,0,1,1)

Для неё рассмотрим следующие две ДНФ - которые действительно описывают подзадачи в процессе решения:

(-\х2&-[х4) V(-]xl&хЗ&-[х4) и (лх1 &хЗ&лх4) V(xl&лх2&хЗ).

При этом обе ДНФ одновременно принимают значение 1 в следующих 2 точках (и только в них):

(0,0,1,0) (1,0,1,0)

и поэтому первая метрика даёт значение 1/2 (т.е. "значение, обратное к числу совпадающих точек). А вторая метрика при этом может дать значение 1 - значение, обратное к числу общих плоскостей. При этом минимальное (но не равное 0) значение расстояния для случая первой эвристики будет равно 1/7 (т.к. имеется всего 8 точек, значения функции в которых равны 1). А для второй, при дополнительном требовании о вхождении в формируемую ДНФ только максимальных плоскостей, минимальным будет' значение 1/4 (т.к. существуют 5 максимальных плоскостей).

Далее представлены «матричная метрика» и некоторые результаты вычислений для псевдо-геометрической версии задачи коммивояжера. Заранее отметим, что автором ещё не производилось сравнение приводимой в данном разделе «матричной метрики» для ЗКВ с другими возможными вариантами «матричных метрик». Однако улучшение практических результатов работы про:граммы при её применении (см. рис.5,6) говорит о перспективной™ работ в этом направлении.

Тестирование производилось на основе тестов, полученных путём генерации псевдогеометрических версий, являющихся преобразованиями известного геометрического теста ЗКВ "ber52.txt".

Расстояние между подзадачами Г; и Т2 вычисляется по следующему алго-

ритму.

lllarl. badness:=0

Шаг 2. badness:=iacfaes.s+2*AV для каждого i, такого что i-я строка присутствует ровно в одной из матриц подзадач, Шаг 3. badness:=badness+2*N) для каждого j, такого что j-й столбец присутствует ровно в одной из матриц подзадач, Шаг 4. badness:-badness+min(Tl(iJ)-T2(ij), 1.414), для каждых i и j, таких что

(ij)-a клетка присутствует ровно в одной из матриц подзадач4, Шаг 5. р(Т1, Т2): =badness

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

Кроме того, «списочные метрики» (например - их варианты, приведённые в предыдущих разделах, которые возможны и для задачи коммивояжёра) допускают возможность работы с матрицами ЗКВ разных размерностей. При этом подобные метрики (например - число, обратное к числу совпадающих номеров в списках разделяющих элементов) действительно дадут малое итоговое значение.

■В « I*

Рис.5. ЗКВ; матричная метрика; размерность Рис.6. ЗКВ; списочная метрика; размерность

52;(псевдогеометрические варианты тес-Ta«ber52.txt» с дисперсией 0.045)

52; (псевдогеометрические варианты теста «ber52.txt» с дисперсией 0.045)

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

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

4 поскольку ни в одной из «геометрических» постановок не имеет смысла считать что badness превышает диагональ квадрата - причем даже в псевдогеометрическом случае.

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

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

Описание разработанного автором и проверенного при практическом построении игровых программ подхода к организации перебора вершин в дереве поиска, описание применяемых эвристик сопровождается детальными примерами.

Шестая глава диссертации содержит описание применяемого автором подхода к реализации разработанных эвристических алгоритмов. В начале главы приведена программная реализация одной несложной переборной задачи, которая фактически является упрощённым описанием подхода к построению программ для описанных эвристических алгоритмов. Следующие разделы посвящены программной реализации задачи вершинной минимизации НКА и задачи коммивояжёра: описаны основные принципы построения и даны подробные комментарии к программным проектам, тексты которых содержатся в приложениях. В заюпоче-ши приведено описание применяемых методов программирования - с точки зрения современных методов создания прмрамм в различных средах ООП.

В приложении А содержится практически полный текст программного проекта для решения задачи минимизации недетерминированных конечных автоматов. В приложении Б содержится описание основных классов программного проекта для решения задачи коммивояжёра. Оба проекта выполнены на Си++.

Основные результаты работы

1. Разработан алгоритм кластеризации и обоснованы возможности его практического применения в некоторых предметных областях.

2. Обоснована эффективность применения предложенного автором алгоритма кластеризации в задачах дискретной оптимизации.

3. Разработаны конкретные варианта т.н. «матричных» метрик для нескольких различных задач дискретной оптимизации, а также т.н. «списочной» метрики, возможной для каждой из подобных задач.

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

5. Модифицирован мультиэвристический подход к решению задач дискретной оптимизации. Модификации связаны со включением в незавершённый метод ветвей и границ эвристик для применения кластеризации ситуаций (с использованием «матричной» либо «списочной» метрики).

6. Разработаны алгоритмы и реализованы компьютерные программы с применением всех рассмотренных эвристик для решения нескольких задач дискретной оптимизации (вершинной минимизации недетерминированных конечных автоматов, минимизации дизъюнктивных нормальных форм, псевдогеометрической версии задачи коммивояжёра). Описан подход к созданию таких программ.

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

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

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендованных списком ВАК

1. Мельников, Б.Ф. Кластеризация ситуаций в алгоритмах реального времени для задач дискретной оптимизации / Б.Ф-.Мельников, Е.А.Мельникова // Системы управления и информационные технологии. - Москва-Воронеж: «Научная книга», №2,2007. - С. 16-19.

2. Мельникова, Е.А. Применение алгоритмов кластеризации в задаче минимизации дизъюнктивных нормальных форм // Известия Самарского центра Российской академии наук. - Самара, издательство Самарского научного центра РАН, выпуск 10,2008. - С. 242-247

Прочие публикации:

3. Мельников, Б.Ф. «Проблема формирования первого экрана» и функции риска / Б.Ф.Мельников, Е.А.Мельникова // Сборник статей II Всероссийской научно-технической конференции «Искусственный интеллект в XXI веке» -Пенза, ПДЗ, 2004, ноябрь. - С. 89- 91.

4. Мельникова, Е.А. Применение некоторых методов теории принятия решений при поиске информации в Интернете // Сборник статей XIV Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании». -Пенза, ПДЗ, 2004,21-22 декабря. - С. 282-284.

5. Мельникова, Е.А. Специальные алгоритмы для поисковых машин // Сборник материалов региональной научно-технической конференции «Научные чтения студентов и аспирантов». - Тольятти, ТГУ, 2005, 12-13 апреля. - С. 4951.

6. Мельникова, Е.А. Применение некоторых вопросов теории принятия решений при поиске информации в Интернете // Ученые записки Ульяновского государственного университета. Серия «Информационные технологии». Вып.1 -Ульяновск, УлГУ, 2005. - С.30-33.

7. Мельникова, Е.А. Построение классификационной иерархии документов на основе лексико-частотных характеристик с применением функций риска / Е.А.Мельникова, А.Н.Радионов // Труды Всероссийской научной конференции «Методы и средства обработки информации». - Москва, МГУ, 2005, 5-7 октября. - С.103-106.

8. Мельникова, Е.А. Применение специальных алгоритмов для кластеризации результатов поиска в Интернете // Сборник статей XVI Международной на-

19

учно-технической конференции «Математические методы и информационные технологии в экономике социологии и образовании». - Пенза, ПДЗ, 2005,27-28 декабря.-С.197-198.

9. Melnikov, В. Some specific heuristics for situation clustering problems / B.Melnikov, A.Radionov, A.Moseev, E.Melnikova // Proceedings of the First International Conference on Software and Data Technologies». - Setubal, Portugal, INSTICC, 2006,11-14 September. - P. 272-279.

Ю.Мельников, Б.Ф. Некоторые вопросы кластеризации ситуаций в алгоритмах реального времени / Б.Ф.Мельников, Е.А.Мельникова // Материалы IX Международной конференции «Интеллектуальные системы и компьютерные науки». - Москва, МГУ, 2006,23-27 октября. - С.200-202.

11.Melnikov, В. Some Programming Olympiad Problems with Detailed Solutions / B.Melnikov, E.Melnikova // Proceedings of the Second International Conference "Informatics in Secondary Schools: Evolution and Perspectives". - Vilnius, Lithuania, Institute of Mathematics and Informatics, 2006, 7-11 November. - P. 573-584.

12.Melnikov, B. Some competition programming problems as the beginning of artificial intelligence / B.Melnikov, E.Melnikova // Informatics in Education. -v.6, n.2,2007. -P.3 85-396.

13.Melnikov, B. Billiard Languages and Corresponding Forbidden Languages / B.Melnikov, E.MeInikova // International Conference "Infinity in Logic and Computation". - Cape Town, South Africa, University of Cape Town, 2007, 3-5 November.-P.21.

14.Melnikov, B. Some heuristics for working with searh tree in non-deterministic games / B.Melnikov, E.Melnikova, A.Moseev // 9th International Workshop on Computer Science and Information Technologies (CSIT2007). - Ufa, 2007.

Публикации, в которых автор принимала участие в качестве переводчика:

15.Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, деорию алгоритмов, рандомизацию, теорию связи и криптографию. 3 изд.: Пер. с англ. Б.Ф.Мельникова, Е.А.Мельниковой. - СПб.: БХВ-Петербург, 2009. - 336 с. (Учебная литература для вузов).

Подписано в печать 23.11.2009. Формат 60x84/16 Печать оперативная. Усл. п.л. 1,4 Уч.-изд. л. 1,3. Тираж 135 экз № 3-229-09.

Тольяттинский государственный университет 445667, г. Тольятти, ул. Белорусская, 14

О задачах дискретной оптимизации и методах их решения

1.1. Постановка задан дискретной оптимизации

1.2. О возможных подходах к решению

1.3. Задачи дискретной оптимизации - более подробное описание

1.4. Жадные эвристики и метод ветвей и границ

1.5. Возможный мультиэвристический подход

Глава 2.

Описание оригинального алгоритма кластеризации и некоторые предметные области его применения

2.1. Введение

2.2. Описание алгоритма кластеризации

2.3. Некоторые другие предметные области применения

2.4. Пример метрики для задачи вершинной минимизации недетерминированных конечных автоматов

3.2. Об одном подходе к организации незавершённого метода ветвей и границ

38

3.3. Описание общего алгоритма 41

3.4. Предлагаемый подход к сравнительной оценке качества эвристических алгоритмов 43

3.5. Заключение главы 45

Глава 4.

Применение кластеризации ситуаций в задачах дискретной оптимизации 45

4.1. Введение 45

4.2. Задача вершинной минимизации НКА - некоторые результаты счёта 48

4.3. Задача минимизации ДНФ: «матричная метрика» и некоторые результаты счёта 51

4.4. Задача коммивояжёра — «матричная метрика» и результаты счёта 55 4.6. Заключение главы 57

Глава 5.

Кластеризация ситуаций и сопутствующие алгоритмы в недетерминированных играх 59

5.1. Введение 59

5.2. Предварительные сведения 61

5.3. Общие эвристики в недетерминированных играх 65

5.4. Некоторые вспомогательные эвристики 68

5.5. Подход к построению статической оценки с использованием нейросети 69

5.6. Пример использования алгоритма обработки вершин 71

5.7. Заключение главы 76

Глава 6.

Возможный подход к реализации алгоритмов с помощью объектноориентированного программирования 78

6.1. Введение 78

6.2. Программная реализация одной несложной «олимпиадной» проблемы 78

6.3. Подход к программной реализации задачи вершинной минимизации недетерминированных конечных автоматов 86

6.4. Заключение главы 92

Заключение 92

Приложения 93 Приложение А.

Текст программы минимизации недетерминированных конечных автоматов

95

Приложение Б.

Часть текста программы решения задачи коммивояжёра 123

Литература 146

Введение

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

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

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

Основные задачи исследования:

• модификация модели вычислений, представляющей собой незавершенный метод ветвей и границ,

• разработка подхода к формированию метрик на множестве подзадач в различных задачах дискретной оптимизации,

• разработка оригинального алгоритма кластеризации ситуаций в задачах дискретной оптимизации,

• разработка и реализация эвристических алгоритмов для решения задач дискретной оптимизации с применением кластеризации ситуаций,

• разработка подхода для создания соответствующих компьютерных программ.

Объектом исследования являются несколько конкретных задач дискретной оптимизации(3 Д О):

• вершинная минимизация недетерминированных конечных автоматов(НКА),

• минимизация дизъюнктивных нормальных форм (ДНФ),

• псевдогеометрическая версия задачи коммивояжёра(ЗКВ),

• игровые программы для недетерминированных игр (версии бэкгеммона). Научная новизна

Разработанный алгоритм кластеризации 'является новой модификацией алгоритма из группы "Hierarchical Clustering Algorithms". Новизна мультиэвристического метода решения задач дискретной оптимизации состоит в применении комплекса эвристик, в том числе кластеризации подзадач на основе разработанных автором метрик. Предложен также подход к разработке компьютерных программ на основе этого метода. Также новыми являются эвристики, предназначенные для работы с деревом перебора в недетерминированных антагонистических играх

Практическая значимость исследования

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

Краткое содержание

Диссертация состоит из введения, 6 глав, 2 приложений. В первой главе диссертации содержится описание задач дискретной оп-тимизации и применяемых методов их решения - как классических, так и раз-работанных автором диссертации. Вторая глава посвящена предлагаемому алгоритму кластеризации. Здесь приведены данные о самом алгоритме; в частности, даны ссылки на схожие алгоритмы, разрабатываемые другими авторами. Кратко рассмотрены некоторые возможные прикладные области практического применения подобных алгоритмов. Также приведены априорные эвристические обоснования применения авторского алгоритма для работы «по аналогии» с подзадачами (ситуациями), получаемыми,в процессе решения.различных задач дискретной оптимизации.

ввода

CMatrix (int mD) : CMatr(mD) { InitMemoryMatrix(); } обычный конструктор CMatrix (CMatrix* copy); практически - конструктор копии virtual -CMatrix (); деструктор void SetLin (int ml, int mValue); void SetCol (int mJ, int mValue); int GetLin (int ml); int GetCol (int mJ); bool SetByNumbers (int ml, int mJ, int nValue);• friend istream& operator» (istreamS is, CMatrix& matrix) ; ввод матрицы из файла friend istreamS operator»= (istreamS is, CMatrixS matrix) ; // другой вариант ввода матрицы из файла; см. текст методов friend ostreams operator« (ostreamS os, CMatrixS matrix); вывод матрицы в файл int GetNumLinByNumber (int numLin); * int GetNumColByNumber (int numCol); private: void InitMemoryMatrix (); void InitFirstLinCol (); bool operator== (CMatrixS first, CMatrixS second); проверяет только равенство №№ всех строк и столбцов double operatorss (CMatrixS first, CMatrixS second); // "матричная" метрика

Работа с матрицей для ЗКВ, срр-файл ///////

CMatrix::CMatrix (CMatrix* copy) : CMatr(copy) {

InitMemoryMatrix(); for (int i=l; i<=mDim; i++) { SetLin(i,copy->GetLin(i)); SetCol(i,copy->GetCol(i) ) ;

CMatrix::-CMatrix () { delete arrNumLin; delete arrNumCol; void CMatrix::SetLin (int ml, int mValue) { ASSERT(mDim>=2 && ml>=l && mI<=mDim); arrNumLin->SetAt(Makelndex(ml),mValue); void CMatrix::SetCol (int mJ, int mValue) { ASSERT(mDim>=2 && mJ>=l && mJ<=mDim); arrNumCol->SetAt(Makelndex(mJ),mValue); int CMatrix::GetLin (int ml) {

ASSERT(mDim>=2 && ml>=l && mI<=mDim); return arrNumLin->GetAt(Makelndex(ml)); int CMatrix::GetCol (int mJ) {

ASSERT(mDim>=2 && mJ>=l && mJ<=mDim); return arrNumCol->GetAt(Makelndex(mJ)); bool CMatrix::SetByNumbers (int ml, int mJ, int nValue) int i = GetNumLinByNumber(ml); if (i<=0 || i>mDim) return false; строки с таким № может просто уже не быть int j = GetNumColByNumber(mJ); if (j<=0 || j>mDim) return false; // аналогично ' Set(i,j,nValue); return true; istreams operator» (istream& is, CMatrix& matrix) { is » matrix.mDim; is.ignore(1); matrix.InitMemoryMatr(); matrix.InitMemoryMatrix(); for (int j=l; j<=matrix.mDim; j++) { int n; is » n; matrix.SetCol(j,n); for (int i=l; i<=matrix.mDim; i++) { int n; is » n; matrix.SetLin (i,n); for (j=l; j<=matrix.mDim; j++) { IgnoreSpaces (is); if (is .peek ()=='*') { is.ignore(3); n = Getlnfty(); else is » n; matrix.Set(i,j,n); return is; double Delta (double XI,double Yl,double X2,double Y2) { return sqrt((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)); istreamS operdtor»= (istream& is, CMatrixs matrix) { is » matrix.mDim; matrix.InitMemoryMatr(); matrix.InitMemoryMatrix(); for (int i=l; i<=matrix.mDim; i++) { matrix.SetLin(i,i); matrix.SetCol (i,i); for (i=l; i<=matrix.mDim; i++) { int n; is » n; if (i!=n) { cout « "bad input"; exit(l); } is » matrix.rXX[i-1] >> matrix.rYY[i-1]; double rMax = 0.0; for (i=l; i<=matrix.mDim-l; i++) for (int j=i+l; j<=matrix.mDim; j++) rMax = max( rMax, Delta( matrix.rXX[i-l],matrix.rYY[i-l], matrix.rXX[j-1],matrix.rYY[j-l])); for (i=l; i<=matrix.mDim; i++) { matrix.Set(i,i,Getlnfty()); for (int j=i+l; j<=matrix.mDim; j++) { double r = Delta( matrix.rXX[i-1],matrix.rYY[i-l], matrix.rXX[j-1],matrix.rYY[j-1]) / rMax ; int n = Boundslnt(int(r*999999),0,999999); matrix.Set(i,j,n); matrix.Set(j,i,n); return is; ostreams operator« (ostreams os, CMatrix& matr) { os « setw(3) « matr.mDim « ":"; for (int j=l; j<=matr.mDim; j++) os « setw(7) « matr.GetCol(j); os « endl; for (int i=l; i<=matr.mDim; i++) { os « setw(3) « matr.GetLin(i) « " "; for (j=l; j<=matr.mDim; j++) { int n = matr.Get(i,j) ; if (ISlnfty(n)) OS « " ******"; else os « setw(7) « n; os « endl; return os; bool operator== (CMatrix& first, CMatrixs second) { int nDim = first.GetDim(); if (nDim!=second.GetDim ()) return false; for (int i=l; i<=nDim; i++) { if (first.GetLin(i)!=second.GetLin(i)) return false; if (first.GetCol(i)!=second.GetCol(i)) return false; return true; const double rMax = 1000000.0; для перевода целых в вещественные; (по смыслу 1000000 - это "единица", длина стороны квадрата double operator&& (CMatrixs first, CMatrixs second) { int nDim = first.GetDim(); // if (nDim!=second.GetDim ()) MyError(1); double rBadness = 0.0; for (int j=l; j<=nDim; j++) if first.GetNumColByNumber(j)*second.GetNumColByNumber(j)<0) // столбец присутствует ровно в одной матрице rBadness += double(nDim); for (int i=l; i<=nDim; i++) { int ml = first.GetNumLinByNumber(i), m2 = second.GetNumLinByNumber (i); if (ml*m2<0) { // строка присутствует ровно в одной матрице rBadness += 2.0*double(nDim); continue; for (int j=l; j<=nDim; j++) { int nl = first.GetNumColByNumber(j), n2 = second.GetNumColByNumber(j); if (nl<0 I I n2<0) continue; double rl = first.Get(ml,nl)/rMax; ведь сами значения - double double r2 = second.Get(m2,n2)/rMax; rBadness += min (abs (rl-r2) , 1". 414) ; не имеет смысла считать, что ухудшение больше // диагонали квадрата - даже в пседогеометр. случае return rBadness; void CMatrix::InitMemoryMatrix () {

ASSERT(mDim>=2); arrNumLin = new CUIntArray; arrNumLin->SetSize(mDim); arrNumCol = new CUIntArray; arrNumCol->SetSize (mDim) ; int CMatrix::GetNumLinByNumber (int numLin) { for (int i=l; i<=mDim; i++) if (arrNumLin->GetAt(Makelndex(i) ) ==numLin) return i; return -1; int CMatrix::GetNumColByNumber (int numCol) { for (int j=l; j<=mDim; j++) if (arrNumCol->GetAt(Makelndex(j))==numCol) return j; return -1; void CMatrix::InitFirstLinCol () { ASSERT(mDim>=2); for (int i=l; i<=mDim; i++) { SetLin(i,i); SetCol(i,i);

Работа с подзадачей для ЗКВ, h-файл //////////////// CTask - задача с методами переборного решения class CTask { protected: int mDim; CMatrix* matr; CPairArray* parr; int nOtvet; public:

CTask (); // применяется только для последующего ввода CTask (int mD) ; генерация «пустой» задачи заданной размерности CTask (CMatrix* matrlnit); аналог конструктора копии CTask (int mD, CMatrix* matrlnit, CPairArray* parrlnit); полная инициализация virtual -CTask () ; деструктор int GetDim () { return mDim; }

CMatrix* GetMatr () { return matr; } CPairArray* GetParr () { return parr; } void Random () { matr->Random(); } случайная генерация void RandomMetric2 () { matr->RandomMetric2(); } случайная генерация 2-мерного геометрического варианта void RandomQuasiMetric2 () matr->RandomQuasiMetric2(); } // случайная генерация 2-мерного псевдогеометрического варианта virtual void IncLimit (int nine){ } // nothing to do virtual int GetOtvetForPrint () { return nOtvet; } friend istreamS operator» (istreams is, CTaskS task) ; friend ostreams operator« (ostreams os, CTask& task) ; void AddPair (int mF, int ml) { parr->Add(mF,mI); } // virtual незачем void PrintWell (ostreams os) { parr->PrintWell (os); } переборный метод(упрощённый), void RunSearch (); переборный метод с элементами выбора 0 из МВГ void RunStek (); protected: int Minus (); void RunStek (int mDeep, int nCostTmp, CPairArray* parrTmp); private: int MakeCost (CPermutation* P) ; ;

Работа с подзадачей для ЗКВ, ерр-файл extern int nBest; // стоимость текущего псевдооптимального решения ////////////// CTask - задача с методами переборного решения

CTask::CTask () { matr = new CMatrix; parr = new CPairArray;

CTask::CTask (int mD) { mDim = mD; matr = new CMatrix(mDim); parr = new CPairArray; nOtvet = Getlnfty();

CTask::CTask (CMatrix* matrlnit) { mDim = matrInit->GetDim(); matr = new CMatrix(matrlnit) ; parr = new CPairArray; nOtvet = GetlnftyO;

CTask::CTask (int mD, CMatrix* matrlnit, CPairArray* parrlnit) { mDim = mD; matr = new CMatrix(matrlnit); parr = new CPairArray; parr->Copy(parrlnit);

CTask::~CTaski() { if (matr ! =NULL) delete matr; if (parr!=NULL) delete parr; istreamS operator» (istreams is, CTasks task) { is » *(task.matr); task.mDim = task.matr->GetDim(); is » *(task.parr); is.ignore(10,1\n'); IgnoreSpaces(is); if (is.peek()!=•+') is » task.nOtvet; else task.nOtvet = Getlnfty();

IgnoreSpaces(is); is.ignore(1000,'\n'); return is; ostream& operator<< (ostream& os, CTask& task) { os « *(task.matr) « * (task.parr) « endl; if (!Islnfty(task.nOtvet)) os « task.nOtvet; os « " +-F+" « endl; task.PrintWell(os); os « " +++" « endl; return os; void CTask::RunSearch () { parr->DeleteAll();

CPermutation* perm = new CPermutation(mDim-1); nOtvet = Getlnfty(); for (;;) { int newCost = MakeCost(perm); if (newCostCnOtvet) { nOtvet = newCost; parr->DeleteAll(); parr->Add(perm->GetPerm(mDim-1),mDim); parr->Add(mDim,perm->GetPerm(1)); for (int i=l; i<=mDim-2; i++) parr->Add(perm->GetPerm(i),perm->GetPerm(i+1)) if (!perm->MakeNext()) break; delete perm; void CTask:-.RunStek' () { nOtvet = Getlnfty(); parr->DeleteAll();

CPairArray* parrTmp = new CPairArray; RunStek(0,0,parrTmp); delete parrTmp; int CTask::Minus () { int nRet = matr->Minus(); if (!Islnfty(nRet)) IncLimit(nRet); return nRet; void CTask::RunStek (int mDeep, int nCostTmp, CPairArray* parrTmp) { if (nCostTmp>=nOtvet) return; if (mDeep>=mDim) { nOtvet = nCostTmp; parr-^-NewCopy (parrTmp) ; return;

CMatr* matrDoublel = new CMatr(matr); // matrDoublel -исходная

CPredictor* pred = new CPredictor(mDim); int n = Minus(); // *matr меняется if ( !Islnfty(n)) nCostTmp += n;

CMatr* matrDouble2 = new CMatr(matr); // matrDouble2 - после Minus() int k,iMax,jMax,iMaxLin,jMaxCol; if (nCostTmp>=nOtvet) Return; pred->SetGoodman(*matr); for (;;) { if (!pred->GetMax(iMax,jMax)) goto Return; if (matr->Get(iMax,jMax)!=0) goto Return; iMaxLin = matr->GetLin(iMax); jMaxCol = matr->GetCol(jMax); bool bl = mDeep>=m.Dim-l; bool b2 - parrTmp->IsPath(jMaxCol,iMaxLin); if (bl==b2) break; pred->Set(iMax,jMax,-1); теперь идём в глубину по рекурсии; сначала - правая задача for (k=l; k<=mDim; k++) { matr->Set(iMax,k,Getlnfty()); matr->Set(k,jMax,Getlnfty()); parrTmp->Add(iMaxLin,jMaxCol); RunStek(mDeep+1,nCostTmp,parrTmp); теперь возвращаемся в состояние до вызова правой задачи parrTmp->DeleteLast() ; matr->Copy(matrDouble2) ; теперь правая задача matr->Set(iMax,jMax,Getlnfty());

RunStek(mDeep,nCostTmp,parrTmp); matr->Set(iMax,jMax,0);

Return: delete pred; delete matrDouble2; matr->Copy(matrDoublel); delete matrDoublel; int CTask::MakeCost (CPermutation* P) { int nCost = matr->Get(P->GetPerm(mDim-l),mDim) matr->Get(mDim,P->GetPerm(1)); for (int i=l; i<=mDim-2; i++) nCost += matr->Get(P->GetPerm(i),P->GetPerm(i+1)); return nCost; class CTaskMVG : public CTask { такая организация данных позволяет выполнять парал. обработку, вызывая любой из методов (прежде всего - Run()) // из любой получающейся дочерней подзадачи private: int nLimit; // граница bool bMade; // признак полностью обработанной матрицы

CPairArray* ways; public:

CTaskMVG (); // применяется только для последующего ввода CTaskMVG (int mD) : CTask(mD) { InitMVGO; }

CTaskMVG (CMatrix* matrlnit) : CTask (matrlnit) { InitMVGO; } CTaskMVG (int mD, CMatrix* matrlnit, CPairArray* parrlnit, int nL, CPairArray* wayslnit); // полная инициализация void InitMVG () { nLimit = 0; bMade = false; ways = new

CPairArray; } virtual -CTaskMVG () { delete ways; } friend istreamS operator» (istreamS is, CTaskMVGs tmvg) ; friend ostreams operator« (ostreamS os, CTaskMVGs tmvg); void AddPair (int mF, int ml); // virtual незачем friend bool operator< (CTaskMVGs first, CTaskMVGs second); void SetLimit (int nL) { nLimit = nL; } virtual void IncLimit (int nine){ nLimit += nine; } int GetLimit () { return nLimit; } bool ExistsOtvet () { return bMade; } virtual int GetOtvetForPrint () { return nLimit; } ПЕРЕБОРНЫЙ МЕТОД void RunStek (); применение родительского RunStek() и настройка своих полей // Классический метод ветвей и границ в двух следующих функциях считаем, что матрица приведна // такими же оставляем и получившиеся матрицы. CTaskMVG* MakeGoodmanRight (bool bSimmetric); // классический выбор нуля private: bool GoodmanForRight (ints iMax, ints jMax); CTaskMVG* MakeRight (int ml, int mJ, bool bSimmetric); public: bool RunDim2 (); bool RunMemo (bool bMain, bool bMetric); bool RunMemoDisk ();

Работа с подзадачей для ЗКВ с использованием МВГ, ерр-файл ////////////// CTask - задача с методами переборного решения

CTaskMVG::CTaskMVG () : CTask () { ways = new CPairArray;

CTaskMVG::CTaskMVG (int mD, CMatrix* matrlnit, CPairArray* parrlnit, int nL, CPairArray* wayslnit) : CTask(mD,matrlnit,parrlnit) { InitMVG(); nLimit = nL; ways->Copy(wayslnit); istreamS operator» (istreamS is, CTaskMVG& tmvg) { CTasks task = tmvg; is » task; is » tmvg.nLimit; int n; is » n; tmvg.bMade = n==l; is » *(tmvg.ways); return is; ostreams operator« (ostreams os, CTaskMVGS tmvg) { CTasks task = tmvg; os « task; os « tmvg.nLimit « " " « tmvg.bMade « endl; os « *tmvg.ways « endl; return os; void CTaskMVG: :AddPair (int mF, int ml) '{ parr->Add(mF,mI); ways->Add(mF,mI); //int n = ways->CombineLast(); int mFW,mIW; if ( !ways->CombineLast (mFW,mIW)) return; matr->SetByNumbers(mIW,mFW,Getlnfty()); matr->SetByNumbers(mIW,mF, Getlnfty()); matr->SetByNumbers(ml, mFW,Getlnfty() ) ; matr->SetByNumbers(ml, mF, Getlnfty()); /* ниже - более подробный вариант for (;;) { matr->SetByNumbers(ml,mFromWay, Getlnfty()); if (mFromWay==mF) break; mFromWay = parr->GetIntoByFrom(mFromWay); if (mFromWay<=0) break; // in case for (;;) { matr->SetByNumbers(mIntoWay,mF,Getlnfty ()) ; if (mIntoWay==mI) break; mlntoWay = parr->GetFromByInto(mlntoWay); if (mIntoWay<=0) break; // in case */ bool operator< (CTaskMVG& first, CTaskMVG& second) { int nl = first.GetLimit(), n2 = second.GetLimit(); int ml = first.GetDim(), m2 = second.GetDim(); return (nl/10000+ml/300) < (n2/10000+m2/300);

CTaskMVG* CTaskMVG::MakeGoodmanRight (bool bSimmetric) { // считаем, что размерность достаточно велика int ml, mJ; if ( !GoodmanForRight(ml,mJ)) return NULL; return MakeRight(ml,mJ,bSimmetric); bool CTaskMVG::GoodmanForRight (int& iMax, int& jMax) { // считаем, что размерность достаточно велика Minus (); CTask::RunStek())

CPredictor pred(mDim); // ВНИМАНИЕ! Далее 2 варианта но SetGoodmanPlus можно выбирать только в случае установленных координат! pred.SetGoodman(*matr); //pred.SetGoodmanPlus(*matr,*parr); int iMaxL^n,jMaxCol; for (;;) { if (!pred.GetMax(iMax,jMax)) return false; if (matr->Get(iMax,jMax)!=0) return false; // in case iMaxLin = matr->GetLin(iMax); jMaxCol = matr->GetCol(jMax); if ( !parr->IsPath(jMaxCol,iMaxLin)) break; if (!ways->IsPathSimple(jMaxCol,iMaxLin)) return true; pred.Set(iMax,jMax,-1);

CTaskMVG* CTaskMVG::MakeRight (int ml, int mJ, bool bSimmetric) { if (this->matr->Get(mI,mJ)!=0) return NULL; // формирование матрицы для левой подзадачи CTaskMVG* taskRet = new CTaskMVG(mDim-1); for (int i=l; i<=mDim; i++) if (i!=ml) { int il = i<ml ? i : i-1; taskRet->matr->SetLin(il,this->matr->GetLin(i)); for (int j=l; j<=mDim; j++) if (j!=mj) { int jl = j<mJ ? j : j-1; if (il==l) taskRet->matr->SetCol(jl,this->matr

GetCol(j)); taskRet->matr->Set(il,j1,this->matr->Get(i,j)); taskRet->parr->Copy(this->parr); taskRet->ways->Copy(this->ways); taskRet->AddPair(this->matr->GetLin(ml),this->matr->GetCol(mJ)); taskRet->SetLimit(nLimit); taskRet->Minus(); формирование матрицы для правой подзадачи this->matr->Set(ml,mJ,Getlnfty()); if (bSimmetric) this->matr->Set(mJ,mI,Getlnfty()); this->Minus(); return taskRet; void CTaskMVG::RunStek () { CTask: : Rur^Stek () ; в полной версии - надо вызывать её же с параметрами! bool CTaskMVG::RunDim2 () { int mil = matr->GetLin(1), mJl = matr->GetCol(1), ml2 = matr->GetLin(2), mJ2 = matr->GetCol(2); int nl = !Islnfty(matr->Get(1,1)) && !Islnfty(matr->Get(2,2)) && !parr->IsPath(mJl,mIl) && !parr->IsPath(mJ2,mI2) ? matr->Get(1,1)+matr->Get(2,2) : Getlnfty(); int n2 = !Islnfty(matr->Get(1,2)) && !Islnfty(matr->Get (2,1)) && !parr->IsPath(mJ2,mIl) && !parr->IsPath(mJl,ml2) ? matr->Get(1,2)+matr->Get(2,1) : Getlnfty(); if (Islnfty(nl) && Islnfty(n2)) return false; if (nl<n2)' { AddPair (mil, mJl) ; AddPair (ml2,mJ2) ; IncLimit (nl); else { AddPair(mil,mJ2); AddPair(ml2,mJl); IncLimit(n2) bMade = true; // признак полностью обработанной матрицы return true; bool CTaskMVG::RunMemo (bool bMain, bool. bMetric) {

CTaskMVG* taskThis; if (bMainf { nLimit = 0; taskThis = new CTaskMVG(this->matr); else taskThis = new CTaskMVG(this->GetDim(),this->matr, this->parr,this->GetLimit (),thisways); taskThis->Minus();

CTaskArray array (this->matr, bMain) ; if (!bMetric) array.Add(taskThis) ; else for (int i=0;;i++) {

CTaskMVG* taskRight = taskThis->MakeGoodmanRight(true); array.AddTask(taskRight); // sic! годится и для след.строки if (taskRight==NULL) { delete taskThis; break; } if (!array.Run()) return false; this->nLimit = array.GetOtvet(); // это - для дочерних вызовов this->nOtvet = this->nLimit; this->parr->NewCopy(array.GetPairs() ) ; this->bMade = true; return true;

Кластеризация, h-файл //////////////// ClusterRef - класс с параметризуемым предком // используется для присвоения каждому кластеризуемому элементу // номера кластера, к которому он принадежит template Ctypename type> class ClusterRef : public type { наследование от класса кластеризуемого элемента public: int clnumref; // номер кластера, содержащего элемент ClusterRef () {}

ClusterRef (const type &value):type(value) { clnumref = -1; номер кластера = -1 обозначает, что элемент не принадлежит никакому кластеру.

ClusterRefS operator= (double value) { type::operator = (value); (предполагается, что все элементы вектора-предка // после этого присваивания будут равны value) return *this; ; ///////////// FrogClusterizator - класс, выполняющий кластеризацию template ctypename type> class FrogClusterizator{ public: typedef ClusterRef<type> ClusterElement; protected:

CVariableArray <int> clusters; массив целых чисел, в котором хранятся кластеры, double dist; public:

FrogClusterizator(double adist) { dist = adist; int addCluster () { // добавляем новый кластер в массив clusters int result = clusters.getCount(); clusters.add(result); return result; int normalizeClusters () { нормализация" кластеров - удаляем лишние номера кластеров, оставшиеся после объединения близких кластеров, и перенумеровываем оставшиеся; int maxClNum = clusters.getCount(); int current = -1; if (maxClNum>0) { int *map = new int[maxClNum]; for (int k=0; kCmaxClNum; k++) map[k]=-1; int clCount =clusters.getCount(); for (int k=0; kCclCount; k++) { int civ = clusters[k]; if (map[civ]<0) map[civ] = ++current; clusters[k] = map[civ]; delete [] map; return current+1; forceinline void distrib (ClusterElement &pl, ClusterElement p2) { записываем элементы pi и p2 в свой кластер ClusterElement* pntl = &pl; ClusterElement* pnt2 = &p2; if (pntl->clnumref<0 && pnt2->clnumref<0) { если оба элементы не входят ни в один кластер. int newCluster = addCluster О; pntl->clnumref = pnt2->clnumref = newCluster; .то они образуют новый кластер printf("New Cluster %d added \n",newCluster); return; if (pntl->clnumref>pnt2->clnumref) { swap(pntl,pnt2); if (pntl->clnumref < 0 && pnt2->clnumref>=0) { // если только один из элементов входит в какой-то кластер. pntl->clnumref = pnt2->clnumref; // .то и второй элемент включаем в тот кластер //printf("Cluster %d grow \n",clusters[pntl->clnumref]); return; if (clusters[pntl->clnumref] != clusters[pnt2->clnumref])

7 если оба элемента уже в своих кластерах. int from = clusters[pnt2->clnumref]; int to = clusters[pntl->clnumref]; if (from<to) swap(from, to); printf("Cluster %d with cluster %d \n",from,to); int count = clusters.getCount(); for (int k=0;k<count;k++) // .то объединяем оба кластера в один if (clusters[k]==from) clusters[k]=to; ; //////////////// FrogClusterizatorRTree - класс, выполняющий кластеризацию с помощью R-дерева [101]

Для работы кластеризатора предполагается известной на этапе компиляции арность структуры R-tree. Кластеризатор реализует:

- метод добавления нового элемента, размещающий элемент в R-tree и определяющий кластер, к которому элемент будет принадлежать.

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

Класс, описывающий элемент кластера, является наследником класса кластеризуемых элементов template ctypename type, int degree> class FrogClusterizatorRTree: public FrogClusterizator<type>{ public: typedef typename type Element; protected: class RTree:public rtree::RTreeCClusterElement,degree, true>{ public:

FrogClusterizatorRTree *fcrt; // Ссылка на класс-кластеризатор Нужна, чтобы дерево через нее "рассказывало"о близких элементах

RTree () { } void Callback(ClusterElement &vl, ClusterElement &v2){ // Перекрытый метод предка, который вызывается предком, если найдены два // близких элемента fcrt->distrib(vl,v2); Распределяем близкие элементы по кластерам } void perform(ClusterElement &cl){ // Изменяет номер кластера-владельца для элемента. // Исползуется после перенумерации кластеров int clno = cl.clnumref; if (clno>=0) cl.setClusterNo(fcrt->clusters[clno]); else cl.setClusterNo(-1); ;

RTree rt; public:

FrogClusterizatorRTree(double adist):FrogClusterizator(adist) { rt.fcrt = this; void add(const type &value){ // Добавляем и кластеризуем новый элемент. Для этого:

ClusterElement v(value); // Создаем на его основе элемент кластера rt.searchNear(v,dist); // Ищем ближайшие к нему элементы и кластеризуем их //(из searchNear вызывается для этого метод Callback) rt.add(v); // Затем добавляем в R-дерево int build () { Перенумеровываем кластеры и их номера в соответствующих элементах. ' int result = normalizeClusters(); rt.doPerform(); printf("Clusters: %d\n", result); return result;

Класс-кластеризатор в приведенном листинге параметризуется классом кластеризуемых элементов «type» и степенью ветвления (арностью) структуры R-Tree «degree». Обычно её значения достаточно брать из диапазона от 4 до 32. Внутри FrogClusterizatorRTree объявлен класс-потомок RTree, в котором конкретизирован* способ реакции на обнаруженные близкие элементы (метод Callback). А также добавлен метод «perform», отвечающий за актуализацию номеров кластеров в ранее распределенных по кластерам элементах после перенумерации кластеров (используется в методе кластеризатора «build»).

Заключение

1. Адельсон-Вельский Г., Арлазаров В., Битман А., Донской М. Машина играет в шахматы. - М. Наука, 1983.

2. Адельсон-Вельский Г., Арлазаров В., Донской М. Программирование игр. М., Наука, 1978.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов — М., Мир, 1979.

4. Белозёрова А., Мельников Б. Применение комплекса эвристик в задаче составления схемы нуклидных превращений. — Труды II Всеросс. научной конф. «Методы и средства обработки информации», М., Изд-во МГУ, 2005, с.208-212.

5. Беллман Р. Динамическое программирование. — М.: ИЛ, 1960.

6. Беллман Р., Калаба Р. Динамическое программирование и современная теория управления. М.: Наука, 1969.

7. Биркгоф Г., Барти Т. Современная прикладная алгебра. СПб.: Лань, 2005.

8. Брауэр Э. Введение в теорию конечных автоматов. М.: Радио и связь, 1987.

9. Васильев Ф. Численные методы решения экстремальных задач. — М.: Наука, 1988.

10. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. — М.: Мир, 1985.

11. Гермейер Ю. Введение в теорию исследования операций. — М.: Наука, 1971.

12. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981.

13. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

14. Дейкстра Э. Дисциплина программирования. М.: Мир, 1978.

15. Дюк В., Самойленко A. Data Mining. СПб.: Питер, 2001.

16. Карлин С. Математические методы в теории игр, программировании и экономике. М., 1964.

17. Карманов В. Математическое программирование. — М.: Наука, 1975.

18. Карпов Ю. Теория автоматов. СПб.: Питер, 2002.

19. Кини Р.Л., Райфа X. Принятие решений при многих критериях: предпочтения и замещения. М.: Радио и связь 1981г.

20. Классификация и кластер. / Под ред. Дж. Вэн Райзина. М.: Мир, 1980.

21. Ковалев М. Дискретная оптимизация (целочисленное программирование). — М.: УРСС, 2003.

22. Колмогоров А. Теория информации и теория алгоритмов. — М.: Наука, 1987.

23. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности / Хачатуров В. и др. М.: Наука, 2000.

24. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы — построение и анализ. — М.: МЦНМО, 2004.

25. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

26. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. -М.: Энергоатомиздат, 1988.

27. Липпман С. Весь С++. От азов до совершенства. — СПб.: Невский диалект, 2007.

28. Липский В. Комбинаторика для,программистов. М.: Мир, 1988.

29. Люгер Д. Искусственный интеллект стратегии и методы решения сложных проблем. - М.-СПб-Киев: Вильяме, 2003.

30. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981.

31. Мандель И. Кластерный анализ. М.: Финансы и статистика, 1988.

32. Мельников Б. Мультиэвристический подход к задачам дискретной оптимизации. «Кибернетика и системный анализ» (НАН Украины), 2006, №3, с.32^12.

33. Мельников Б. Эвристики в программировании недетерминированных игр. — «Программирование» (Известия РАН), 2001, №5, с.63-80.

34. Мельников Б., Мельникова Е. Кластеризация ситуаций в алгоритмах реального времени для задач дискретной оптимизации. — «Системы управления и информационные технологии», 2007, №2, с. 16-19.

35. Мельников Б., Радионов А. О выборе стратегии в недетерминированных антагонистических играх. — «Программирование» (Известия РАН), 1998, №5, с.55-62.

36. Мельникова Е. Применение алгоритмов кластеризации в задаче минимизации дизъюнктивных нормальных форм. «Известия Самарского центра РАН», 2008, выпуск 10, с. 242-247.

37. Минский М. Вычисления и автоматы. М.: Мир, 1971

38. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990.

39. Моисеев Н. Элементы теории оптимальных систем. М.: Наука, 1975.

40. Оре О. Графы и их применение. - М.: URSS, 2006.

41. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. — М.: Мир, 1985.

42. Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. — М.: Высшая школа, 1998.

43. Пойа Дж. Математика и правдоподобные рассуждения. М., 1975.

44. Полак Э. Численные методы. Единый подход. М.: Мир, 1974.

45. Поляк Б. Введение в оптимизацию. М.: Наука, 1988.

46. Рассел С., Норвиг П. Искусственный интеллект: современный подход. — М.-СПб-Киев: Вильяме, 2006.

47. Рейнгольд Э. Комбинаторные алгоритмы-М.: Мир, 1980.

48. Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике М.: Мир, 1986.

49. Самарский А., Михайлов А. Математическое моделирование. М.: ФИЗМАТЛИТ, 2001.

50. Сачков В. Введение в комбинаторные методы дискретной математики. — М.: Наука, 1982.

51. Сигал И., Иванова А. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмыю. М.: ФИЗМАТ ЛИТ, 2003.

52. Современное состояние теории исследования операций / Под ред. Моисеева Н. — М.: Наука, 1979.

53. Схрейвер А. Теория линейного и целочисленного программирования. — М.: Мир, 1991.

54. Таха X. Введение в исследование операций. — М.: Мир, 1988.

55. Успенский В., Семенов А. Теория алгоритмов: основные открытия и приложения -М.: Наука, 1987.

56. Хаггарти Р. Дискретная математика для программистов М.: Техносфера, 2003.

57. Харари Ф. Теория графов. М.: Мир, 1973.

58. Ху Т., Шинг М. Комбинаторные алгоритмы Нижний Новгород: Изд-во Нижегородского госуниверситета им. Н.И.Лобачевского, 2004.

59. Шень А. Программирование: теоремы и задачи. М.: Изд-во МЦНМО, 2004.

60. Шимко П. Оптимальное управление экономическими системами. — СПб.: Бизнесс-пресса, 2004.

61. Эделстейн Г. Интеллектуальные средства анализа, интерпретации и представления данных в информационных хранилищах ComputerWeek-Москва. 1996. №16. с. 32-33.

62. Яблонский С. Введение в дискретную математику М.: Высшая школа, 2006.

63. Adleman, L. Two theorems on random polynomial time In: Proc. 19th IEEE 1978, pp. 75-83.

64. Aida K., Osumi T. A Case Study in Running a Parallel Branch and Bound Application on the Grid Proc. IEEE/IPS J, SAINT2005.

65. Applegate D., Bixby R., Chvatal V., Cook W. Finding cuts in the TSP (A preliminaryreport), DIMACS Technical Report 95-105, March, t

66. Arora S., Lund C.: Hardness of approximation. In: Approximation Algorithms for NP-hard Problems, PWS Publishing Company, Boston, 1997.

67. Arora, S. Polynomial time approximation shemes for Euclidean TSP and other geometric problems. In: Proc. 37th IEEE FOCS, IEEE, 1996, pp.2-11.

68. Ausiello G., D'Atri A., Protasi M. On the structure of Combinatorial problems and structure preserving reductions. In: Proc. 4th ICALP

69. Ausiello G., D'Atri A., Protasi M. Structure preserving reductions among convex optimization problems. Journal of Computer and System Sciences 21 (1980), 136— 153.

70. Bellare M., Sudan M. The complexity of decision versus search. In: Proc. 26th ACM STOC, ACM, 1994, pp. 184-193.

71. Bellmore M., Nemhauser G. The traveling salesperson problem: A survey. -Operations Research 16 (1968), pp. 538-558.

72. Bentley J. Experiments on traveling salesman heuristics. In: Proc. 1st ACM-SIAM Symposium on Discrete Algorithms, ACM, New York 1990, and SI AM, Philadelphia, 1990, pp. 91-99.

73. Billings D. Algorithms and assessment in computer poker. — University of Alberta (USA), Ph.D. thesis, 2006.

74. Carbonell J. Derivational Analogy and Its Role in Problem Solving, AAAI (1983), pp. 64-69.

75. Champarnaud J., Hansel G., Paranthoen Т., Ziadi D. Random generation models for NFA'S // Journal of Automata, Languages and Combinatorics, 9,2004, pp. 203-216.

76. Chen Q., Ferris M. FATCOP: A fault tolerant Condor-PVM mixed integer program solver. Mathematical Programming Technical Report 99-05, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, 1999.

77. Cook S. The complexity of theorem proving procedures. In: Proc. 3rd ACM STOC, ACM, 1971, pp. 151-158.

78. Dorigo M., Gambardella L. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. — IEEE Transactions on Evolutionary Computation, Vo.l,No.l (1997), pp. 53-66.

79. Hauk D., Buro M., Schaeffer J.: Rediscovering *-minimax search. Computers and Games, 2004, pp. 35-50.

80. Held M., Karp R. The traveling-salesman problem and minimum spanning trees. -Operation Research, 18 (1970), pp. 1138-1162.

81. Hromkovic J. Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer, 2003.

82. Hromkovic J. An Introduction to Automata, Computability, Complexity, Algorithmics, Randomization,Communication and Cryptography. Springer, 2003.

83. Pohi I. Bi-directional search. In: B.Meltzer and D.Michie (Eds.) Machine Intelligence, 6, Edinburg University Press, Edinburg, Scotland (1971), pp. 127—140.

84. Lifschitz Y. Frames in the Space of Situations. In: Artificial Intelligence 46 (1990), pp. 365-376.

85. Melnikov В., Gumayunov V., Radionov A. Some special heuristics for discrete optimization problems. — 8th International Conference on Enterprise Information Systems, Paphos (Cyprus) (ICEIS-2006), pp. 360-364.

86. Melnikov B. On an expansion of nondeterministic finite automata. The Korean Journal of Computational and Applied Mathematics, Vo.14, No. 1-2 (2007), pp. 155— 166.

87. Melnikov B. Once more about the state-minimization of the nondeterministic finite automata The Korean Journal of Computational and Applied Mathematics, Vo.7, No.3 (2000), pp. 655-662.

88. Melnikov В., Melnikova E., Moseev A. Some heuristics for working with search tree in non-deterministic games. 9th International Workshop on Computer Science and Information Technologies (CSIT'2007), Ufa, 2007.

89. Melnikov В., Melnikova E., Moseev A., Radionov A. Some specific heuristics for situation clustering problems. 1st International Conference on Software and Data Technologies, Setubal (Portugal) (ICSOFT-2006), Vol.2, pp.272-279.

90. Melnikov B. Discrete optimization problems some new heuristic approaches. - 8th International Conference on High Performance Computing and Grid in Asia Pacific Region, IEEE Computer Society Press Ed., Beijing~(China) (HPC-Asia-2005), pp.7380.

91. Melnikov В., Melnikova E. Some programming olympiad problems with detailed solutions. International Conference on Informatics in Secondary Schools, Evolution and Perspectives (ISSEP-2006, Lithuania), pp.573-584.

92. Michie D. Game-playing and game-learning automata. Advanced in Programming . and Non-Numerical Computation, Pergamon Ed. (Oxford), 1966, pp. 183-200.

93. Samuel: Some studies in machine learning using the game of checkers. — IBM Journal, 11 (1967) 601—617.

94. Tesauro G. Neurogammon wins computer olympiad. — Neural Computation, Vo.l, No.3 (1989), pp.321-323.

95. Tesauro G. Temporal difference learning and TD-Gammon. — Commun. ACM, Vo.38, No.3 (1995), p.58-68.

96. Гончаров M. Кластеризация на основе нечётких отношений. -www.spellabs.ru/FuzzyRelationClastering.htm

97. Норенков И. Оптимизация выбора эвристик при решении сложных задач проектирования и логистики http://technomag.edu.ru/doc/44140.html100. 2007WorldFinalProblemSet.pdf- http://icpc.baylor.edu/icpc/Finals/

98. R-Trees: A Dynamic Index Structure for Spatial Searching. http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf

99. Hierarchical cluster analysis http://www.clustan.com/1.