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

 

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

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

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


Wv (Si, S2, ...,Sk)= max Qp (Si).

1 <г<к

Остановимся на способах вычисления значений gp(Si):

9l (Si) Yj ГДЄ ШІП Cjr,

JeSi r^Si

б) 92 (Si) = max Ctji

в) 9з (Si) = max Qj- - min Qj-;

г) g±(Si) = max сц/ min сц, min сц > 0;

j eSi,te Si, j Ф t.

10.2.2. Задание начального разбиения. Пусть

^min = min Xj, жтах = max Xj, ymin = min у$, ^ymax = max у$.

3 3 3 3

Разбиение с постоянным шагом по осям координат. Пусть Si > 1 и $2 > 1 — число шагов по оси OX и по оси OY соответственно,

hi — (^max %min) /^l, ЇІ2 — (^/тах 2/min) /•

В результате разбиения отрезков [жтіп,жтах] и [ут-ш, утах\ с шагами hi и Zi2 соответственно по осям координат получается S1S2 прямоугольников:

Xi<x< Xi-|_i, Xi — жтіп H- (і I) hi, і — I, 2,..., Si;

Vj <У < Vj+1, Vj = 2/min + (j - 1) h2, j = 1,2,..., S2.

Может оказаться, что некоторые из прямоугольников не содержат ни одной точки. Эти прямоугольники исключаются из списка множеств, k < SiS2.

Задание промежуточных точек по осям координат. Пусть Si > Ohs2 > 0 — число промежуточных точек по оси OX и по
Гл. 10. Алгоритмы решения задачи коммивояжера 207

оси OY соответственно, причем Si + S2 > 1:

^min < < ^2 < • • • < X81 <С ^max,

У min < 2/1 < 2/2 < - - - < Vs 2 ^ У теж]

получаем (si + 1)(^2 + 1) прямоугольников:

Xi<X< Xi-|_і, І — 0, 1, 2, . . . , Si, Xq — Жтіп, Xsi-^-I — ^maxj

Vj < У < Vj+li j = 0? I5 2, . . . , S21 У0 = Утіш Vs2 + 1 = 2/тах-

Как и в предыдущем случае, некоторые из прямоугольников могут не содержать ни одной точки; эти прямоугольники исключаются из списка множеств, k < (s 1 + 1)(^2 + 1)-

Задание прямоугольников со сторонами, параллельными осям координат. Каждый из к таких прямоугольников задается координата-ми вершин X1min < х < X1max, Vtmin < У < t/max> * = 1,2,...,*. При этом прямоугольник хт[п < X < жтах, Утт < У < 2/тах разбивается

к

на к прямоугольников Si, |*Si| = п, причем соседние прямоугольни-

І— 1

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

Задание произвольных многоугольников. Каждый из таких к мно-

к

гоугольников Si задается координатами своих вершин, ^1*?! = п-

і— 1

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

Рассмотрим некоторые из алгоритмов определения принадлежности точки с координатами ж, у многоугольнику (см. [31]). Возьмем точку с координатами жо, 2/о, не принадлежащую многоугольнику, например Xo = хт[п— є, уо = Утіп — ?5 є > 0. Рассмотрим отрезок, определяемый концевыми точками с координатами (х,у) и (хо,Уо)- Найдем все точки пересечения этого отрезка со сторонами многоугольника. Пусть эти точки не совпадают ни с одной из вершин многоугольника. При нечетном числе таких пересечений точка с координатами (ж, у) является внутренней, а при четном числе пересечений (или при их отсутствии) эта точка является внешней. Если хотя бы одна из точек совпадает с вершиной многоугольника, то повернем отрезок вокруг точки (ж, у) на такой угол, при котором совпадение исчезает.

Описанные ниже подходы применимы лишь для выпуклых многоугольников. Определим угол, под которым «виден» многоугольник
208

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

из точки с координатами (х,у). Для внешней точки величина этого угла меньше 7г, а для внутренней он равен 2тг.

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

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

Задание подмножеств номерами входящих в них точек. Для каждого из к подмножеств Si задаются номера точек ... ,jls ,

к

входящих в Si, Y 1*?! = тг, Si П Sj = 0 при і ф j.

і= I

Разрезание на полосы. Задается уо > 0 — ширина полосы по оси OY. В каждой из полос ут-ш + (t - 1) у0 < у < ^min + ty0, t = = I, 2,..., to? упорядочим точки по возрастанию значений абсцисс; параметр определяется так, что

2/min H- toVo < 2/max ^ Утіп H- (^0 H- I) 2/0 -

Множества Si образуются с помощью набора в фиксированной полосе ?7/min точек в порядке возрастания значений абсцисс. Если число точек меньше птіги т0 они могут быть присоединены к последнему из подмножеств или учтены при наборе в следующей полосе. Если ширина последней полосы меньше у о /2, то все ее точки рассматриваются при наборе вместе с точками предыдущей полосы.

Все описанные здесь способы задания начального разбиения применяются для задачи в координатной форме. Для задачи в матричной форме применим лишь способ задания подмножеств номерами входящих в них точек. Из описания видно, что при задании начального разбиения не всегда гарантируется выполнение условий:
Предыдущая << 1 .. 66 67 68 69 70 71 < 72 > 73 74 75 76 77 78 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100