Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 75

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 69 70 71 72 73 74 < 75 > 76 77 78 79 80 81 .. 84 >> Следующая


10.2.7. Последовательная (древовидная) декомпозиция.

Предположим, что ^nmax < Ti и задача о декомпозиции решена по одному из описанных выше алгоритмов, при этом \S{\ > пт-ш > 0 для всех і = 1,2,... ,к. Рассмотрим множества Si, удовлетворяющие условию I Si I > nmax. Для каждого из них можно решить задачу о разбиении на кі множеств Sj, Sf,..., Ski. Такая процедура может повторяться многократно. Обозначим через Si все множества, не подвергавшиеся разбиению, і = 1,2,..., Л^о - Тогда

ко

U & = P-,

Si Р\ Sj = 0, і ф j, і, j = 1, 2,..., ко;

О <С ^min ^ I Si j < ^maxj ^ = 1, 2, . . . ,

Полученные в результате такой процедуры подмножества образуют дерево подмножеств. На первом его уровне находится вершина, соответствующая множеству P, на втором — вершины, соответствующие подмножествам Si, полученным после разбиения множества P на подмножества. Вершина первого уровня связана ребрами со всеми вершинами второго уровня. Рассмотрим некоторое подмножество, вершина которого а находится на уровне s, и разобьем его
214

Разд. IV. Задачи большой размерности

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

10.2.8. Практическое решение задачи разбиения. Как видно из описанного выше подхода, решение задачи разбиения содержит следующие основные этапы: задание или построение начального разбиения; корректировка разбиения и его оптимизация. После задания или построения начального разбиения (см. пп. 10.2.2, 10.2.3) можно выполнить процедуры его корректировки или перейти к его оптимизации. Решив задачу оптимизации, можно снова выполнить процедуры корректировки, а затем повторно решать задачу оптимизации; при этом можно сменить критерий оценки разбиения в целом или оценки подмножеств, либо оба критерия.

Далее может снова последовать корректировка и оптимизация и, наконец, построение нового разбиения и т.д. Используя диалоговые и графические средства, можно довести процесс разбиения до получения приемлемого решения.

10.3. Решение подзадач

10.3.1. Построение начальных решений. Для построения начальных решений этой задачи применяются:

— различные варианты алгоритма перехода в ближайшую точку;

— алгоритм многоугольника для симметричных задач с правилом треугольника;

— модификация оболочки для задач на плоскости;

— устранение пересечений в маршруте (для задач на плоскости).

Все эти алгоритмы описаны в гл. 7. Применяется также алгоритм

одностороннего ветвления, описанный в гл. 3.

Начальные маршруты для каждой из подзадач (как и для задачи в целом) могут быть заданы в режиме диалога.

Для устранения пересечений в задаче на плоскости в гл. 7 описан специальный алгоритм. Здесь описан другой алгоритм для решения задачи устранения пересечений.

Рассмотрим вопрос о пересечении двух отрезков, заданных координатами концевых точек (хі,Уі]Хі+і,Уі+і) и (Xj1 у у, XjJrX, 2/j+i). Обозначим:

Xflin = min (Xi, xi+1), Pflin = min (yh yi+1),

xmin _ min .; Xj+1) ^ ymin _ min (y.; y.+i) ;
Гл. 10. Алгоритмы решения задачи коммивояжера 215

жтах _ тах(ЖьЖі+1) ; у™ах _ тах (уи уі+1) ;

Xfax = max (xj}xj+1), yfax = max (yj,yj+1).

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

^min ^ ^min < ^max ЖШІП < ЖШІП < ЖШаХ

и хотя бы одного из неравенств

min ^ min ^ max min ^ min ^ max

Уі ^ yj ^ Уі 5 yj ^ Уі ^ yj

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

max (xfn, xfn) <x<min (^ax,^max) , max (yfn, yfn) <y< min (y“ax, y“ax) .

Рассмотрим маршрут z = .,is,is+1, • • .,ik,ik+1, • • • ,?), для

которого необходимо выявить пересечения переходов и устранить их, если они существуют. Проверим, пересекаются ли переходы (is,is+i) м. (ik,ik+i) («5 = 1,2,.. .,гг — 3, к = s + 2,..., п — 1). Вычислим х™ах, ж™ш, ж™ах и проверим, пересекаются ли проекции на ось ОХ. Если они пересекаются, то вычислим у™1П, 2/™ах, 2/™ш, 2/™ах и проверим, пересекаются ли проекции на ось OY. Если пересекаются проекции на оси OX VL OY, то найдем координаты точки пересечения прямых, проверив ее принадлежность обоим отрезкам. Если отрезки пересекаются, то построим новый маршрут без пересечения z = = («1,.. .,is,ik,ik-1,... ,Ь+1,. ¦ ¦ ,ік+1, ¦ ¦ -,in), длина которого не боль-ше, чем длина маршрута z. Все пересечения устраняются за конечное число просмотров маршрута. При этом процедура определения пересечения переходов применяется (п — 2)(п — 3)/2 раз.
Предыдущая << 1 .. 69 70 71 72 73 74 < 75 > 76 77 78 79 80 81 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100