WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 14 |
АЛГОРИТМЫ И ПРОГРАММНЫЕ СРЕДСТВА ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ Вып. 10 2010 ЕКАТЕРИНБУРГ АЛГОРИТМЫ И ПРОГРАММНЫЕ СРЕДСТВА ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ Вып. 10 2010 УДК 519.6 ЭМПИРИЧЕСКИЙ МЕТОД DropBy МАСШТАБИРОВАННОГО РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА Е. Е. Иванко Введение Задача коммивояжера (TSP) является одной из актуальных вычислительно сложных задач в области современной алгоритмистики. В простейшем варианте формулируется задача поиска оптимального обхода множества вершин по заданной матрице попарных стоимостей перемещений между этими вершинами. Обычно при этом каждую вершину необходимо посетить только один раз. Постановка задачи допускает большое количество вариаций. Например, функция стоимости перемещений на вершинах может быть метрикой. Матрица попарных стоимостей перемещений может быть заменена списком координат вершин в некотором метрическом пространстве. Вместо обхода с возвратом может быть предложена задача обхода всех вершин, начиная с некоторой вершины A и заканчивая некоторой вершиной B. В задачу могут быть введены дополнительные условия, например условие предшествования, когда некоторые из вершин должны быть посещены в определенном порядке [7].

Существуют разнообразные подходы к решению задачи коммивояжера. Методы, обеспечивающие нахождение точного решения задачи коммивояжера, вычислительно затратны и часто оказываются непригодны в задачах, где количество входных вершин исчисляется тысячами [2,5]. Приближенные методы позволяют относительно быстро находить некоторый путь обхода, обычно не более чем на 50% превышающий стоимость оптимального пути. Существуют приближенные методы, гарантирующие нахождение решения, отличающегося от оптимального не более, чем на заданную величину [1].

Поиск новых эмпирических методов решения задачи коммивояжера является как интересной теоретической задачей, так и полезным в ряде областей прикладным исследованием [2]. В настоящей статье рассматривается один эмпирический метод решения задачи коммивояжера с помощью вставок (insertion techniques [4]). В основе настоящего метода лежит идея понижения размерности исходной задачи коммивояжера с помощью удачного разбиения множества входных вершин на непересекающиеся подмножества. При этом исходная задача разбивается на две последовательных: 1) поиск оптимального порядка обхода подмножеств; 2) поиск оптимального порядка обхода вершин внутри каждого подмножества. Мощности подмножеств можно выбирать такими, чтобы вторая задача решалась точными методами за приемлемое время.

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

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

На первом шаге мы имеем заданную начальную вершину s и заданную конечную вершину e.

Соединим их отрезком – это будет прямой путь из начальной в конечную вершину. По условиям задачи на пути из начальной в конечную вершину необходимо обойти все вершины, а значит и зайти в самую удаленную от прямого пути из s в e вершину c. Изменим прямой путь из s в e – зайдем по дороге в вершину c. Для этого заменим отрезок [s, e] на два отрезка [s, c] и [c, e].

Далее разобьем все вершины задачи на два подмножества: те вершины, которые расположены ближе к отрезку [s, c] и те, которые расположены ближе к отрезку [c, e]. Первое подмножество вершин мы обойдем на пути из s в c, второе на пути из c в e. Далее будем действовать аналогично. На каждом шаге очередное подмножество, у которого определены начальная и конечная вершины, также разбивается на два подмножества: вершины, которые нужно обойти на пути из начальной вершины в “самую удаленную... ”, и вершины, которые нужно обойти на пути из “самой удаленной... ” вершины в конечную. Рекурсивно будем повторять описанную процедуру разбиения для всех подмножеств содержащих более чем n элементов, где n задано заранее.

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

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

А л г о р и т м 1. Пусть на входе задано множество входных вершин A, начальная точка s и конечная точка e. Начальными условиями будем считать упорядоченный набор подмножеств ({s}, A \ {s, e}, {e}).

2. Если |A \ {s, e}| > 1, подадим упорядоченный набор подмножеств ({s}, A \ {s, e}, {e}), являющийся начальными условиями, на вход функции DropBy. Полученный выход будем считать новыми условиями.

3. До тех пор, пока в упорядоченном наборе подмножеств будет существовать подмножество, содержащее более n элементов: (..., {xi}, Xi, {xi+1},...), где |Xi| > n будем применять функцию DropBy к найденному подмножеству, расщепляя его на два подмножества меньшей 1 2 1 мощности: DropBy({xi}, Xi, {xi+1}) = ({xi}, Xi, {x0}, Xi, {xi+1}), где |Xi | < |Xi| и |Xi | < |Xi|.

Ф у н к ц и я DropBy 1. Пусть задан упорядоченный набор подмножеств ({a1}, A, {a2}).

2. Пусть c = maxdA{Dist(d, [a1, a2])} самая удаленная (в смысле некоторой заданной метрики Dist) от отрезка [a1, a2] вершина, из принадлежащих множеству A.



3. Разделим множество A \ {c} на два подмножества A1 и A2 так, что для всякого d A \ {c} d A1, если Dist(d, [a1, c]) < Dist(d, [c, a2]), иначе d A2.

4. В итоге имеем два множества A1 и A2: A1 A2 =, A1 A2 {c} = A.

5. Выходом функции является следующий упорядоченный набор подмножеств ({a1}, A1, {c}, A2, {a2}).

2. Вычислительная сложность Для нахождения вершины подмножества, наиболее удаленной от отрезка, соединяющего начальную и конечную точки этого подмножества, необходимо перебрать все вершины данного Эмпирический метод DropBy масштабированного решения задачи коммивояжера подмножества (шаг 2 функции DropBy). Еще один, на единицу меньший, перебор нужно сделать, чтобы распределить вершины текущего подмножества за минусом найденной удаленной на два меньших подмножества (шаг 3 функции DropBy). В худшем случае при каждом разбиении одно из подмножеств будет оказываться пустым, так что дробление подмножеств будет происходить самым медленным образом, и каждый раз от числа анализируемых на следующем шаге будет отниматься лишь одна вершина та, что признана самой удаленной вершиной в непустом подмножестве. На первом шаге нам нужно проанализировать n - 2 вершины. На втором шаге n - 3 и т. д. В итоге имеем:

n- O (n - i) = O(n2).

i=Однако если считать, что каждый раз подмножества делятся приблизительно поровну, то количество шагов составит не более [log2(n-2)]+1. При этом на каждом i-том шаге из анализа будут исключаться 2i-1 вершин, которые становятся наиболее удаленными точками соответствующих подмножеств и выпадают из дальнейшего перебора. Общее количество операций в этом случае можно выразить как:

[log2(n-2)]+ N = (n - 2) - (2i-1 - 1).

i=Несложно видеть, что O(N) = n log2 n.

3. Эксперименты Оценим точность решений, получаемых с помощью рассмотренного метода. Для этого проведем следующий вычислительный эксперимент: для всякого n {10, 20, 25, 50, 75, 100, 125, 150, 175, 200, 225, 250, 275, 300, 400, 500} сгенерируем по 100 случайных расположений n вершин внутри квадрата [0 x 1] [0 y 1].

Для каждого i-того расположения n городов рассчитаем длину маршрута обхода всех городов данного расположения с помощью рассмотренного выше эмпирического алгоритма, используя в качестве метрики Dist стандартную евклидову метрику на плоскости. Далее для каждого n высчитаем среднюю (среди 100 соответствующих случайных расположений городов) длину маршрута, составленного с помощью рассматриваемого эмпирического метода DropBy, обозначим ее Drop(n). Для оценки точности величины Drop(n) используем нижнюю границу Хельда Карпа [3,4] для длины оптимального пути, рассчитываемую в нашем случае непосредственно по приближенной формуле:

0.7078 n + 0.551.

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

Известные методы, основанные на конструировании пути обхода с помощью последовательных вставок новых вершин в имеющийся путь, асимптотически отклоняются от нижней границы Хельда Карпа в среднем на 17-28% в зависимости от конкретного метода [6]. По нижеприведенному рисунку можно предположить, что рассматриваемый в статье метод имеет аналогичную точность в асимптотике.

6 Е. Е. Иванко % n 0 100 200 300 400 Cредний процент отклонения длины пути, рассчитанного с помощью эмпирического алгоритма DropBy, от величины нижней границы Хельда Карпа, рассчитанной по формуле 0.7078 n + 0.551.

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

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

Развитие настоящего исследования планируется вести по следующим направлениям:

• детальное экспериментальное исследование “плохих” случаев, когда решение, найденное с помощью предложенного метода, существенно отклоняется от оптимального; последующий анализ причин отклонения и доработка алгоритма;

• углубленное исследование вычислительной сложности предложенного метода;

• доработка метода с учетом возможности поиска оптимального обхода вершин в условиях предшествования [7].

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

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

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





СПИСОК ЛИТЕРАТУРЫ 1. Berman P., Karpinski M. 8/7-Approximation Algorithm for (1,2)-TSP. // Proc. 17th ACM-SIAM SODA. 2006. P. 641–648.

Эмпирический метод DropBy масштабированного решения задачи коммивояжера 2. Gutin G. and Punnen A.P. The traveling salesman problem and its variations. Dordrecht: Kluwer Acad. Publishes, 2002. 848 p.

3. Held M., Karp R. A dynamic programming approach to sequencing problems // J. Soc. Indust.

Appl. Math. 1962. Vol. 10. P. 196–210.

4. Johnson D., McGeoch L., Rothberg E. Asymptotic experimental analysis for the Held–Karp traveling salesman bound // Proc. of the seventh annual ACM-SIAM symposium on Discrete algorithms.

1996. P. 341–350.

5. Nilsson C. Heuristics for the traveling salesman problem // Technic. Report. of Linkoping University.

2003. 6 p.

6. Valenzuela C., Jones A. Estimating the Held–Karp lower bound for the geometric TSP // Europ.

J. Operat. Research. 1997. Vol. 102, iss. 1. P. 157–175.

7. Ченцов А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории.

М; Ижевск: НИЦ “Регулярная и хаотическая динамика”, 2007. 240 с.

Иванко Евгений Евгеньевич канд. физ.-мат. наук науч. сотрудник Ин-т математики и механики УрО РАН e-mail: ivanko@ural.ru АЛГОРИТМЫ И ПРОГРАММНЫЕ СРЕДСТВА ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ Вып. 10 УДК 519.ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ДЛЯ НАХОЖДЕНИЯ РАНГОВ ГРУПП ЦЕНТРАЛЬНЫХ ЕДИНИЦ ЦЕЛОЧИСЛЕННЫХ ГРУППОВЫХ КОЛЕЦ ЗНАКОПЕРЕМЕННЫХ ГРУПП А. В. Каргаполов В статье дано описание параллельного алгоритма для нахождения рангов групп центральных единиц целочисленных групповых колец знакопеременных групп, также приводится оценка трудоемкости предложенного алгоритма.

Введение Целью данной работы является нахождение рангов групп U (Z (ZAn)) центральных единиц целочисленных групповых колец знакопеременных групп для как можно б степеней n.

ольших Предлагается параллельный алгоритм, который позволил достичь значения n = 600. Ранее результаты были меньше, примерно 240 после многочасовой работы компьютера. Продвижение является существенным, поскольку количество вычислений очень сильно возрастает с ростом n, об этом будет подробнее сказано ниже.

Для достижения описанной цели воспользуемся результатом Ферраза [1].

Лемма 1 [1, теорема 4.5]. Ранг группы U (Z (ZAn)) равен количеству разбиений a = (a1,..., am) натурального числа n, удовлетворяющих следующим свойствам:

(1) ai нечетно при 1im;

(2) ai=aj при i =j;

(3) n m (mod 4);

m (4) ai не является квадратом натурального числа.

i=Число разбиений a со свойствами (1) - (4) леммы 1 обозначим через r(n). Напомним, что разбиением натурального числа n называется последовательность a1, a2,..., am натуральных чисел такая, что a1a2...am и a1 + a2 +... + am = n.

Для функции p (n) (количество разбиений числа n) в [4] приведена формула Радемахера:

2n p(n) e 3.

4n Для r(n) характер роста остается таким же; не смотря на то, что перебираются не все n разбиения, число их все равно порядка e. Поэтому вычисление рангов достаточно трудоемкая задача. Использование параллельных вычислений позволяет вычислить значения рангов, которые без супер ЭВМ найти проблематично.

1. Разработка алгоритма Разработку алгоритма вычисления r(n) начнем с анализа условий, накладываемых на разбиения в лемме 1. Случаи, подобные (1), (2) и (3), рассмотрены в [4], но для проверки произведения элементов на квадрат натурального числа не удалось найти эффективной формулы.

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

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

Будем отталкиваться от довольно простой реализации вычисления r(n):

1: RankCount(n, k, length, factors) 2: если (n = 0) то 3: если (length = n)(mod 4) И (factors = 0) то 4: return 1;{разбиение удовлетворяет всем условиям} 5: иначе 6: return 0;{не учитываем данное разбиение} 7: иначе 8: result := 0;

9: для (i := k; i n; i := i + 2) 10: {перебираем все нечетные числа, такие что k i n} 11: newN := n - i; {оставшаяся часть} 12: newK := i + 2; {следующий минимальный элемент} 13: newLength := length + 1; {количество уже выбранных элементов} 14: newF actors := factors xor decomposition(i); {новый вектор степеней по модулю 2} 15: result := result + RankCount(newN, newK, newLength, newF actors);

16: return result;

Обход разбиений идет в лексикографическом порядке. В целом алгоритм похож на построение разбиений в [2], хотя там и используется обратный порядок обхода. Чтобы получить r(n), нужно вызвать RankCount(n, 1, 0, 0).

Заметим, что при выборе очередного элемента разбиения не учитывается условие (3) леммы 1, проверка на это условие происходит для уже построенного разбиения. Попытаемся перенести проверку условия (3) леммы 1 в процесс построения очередного разбиения. Для этого введем обозначения:

элементарная операция выбор очередного элемента разбиения в рекурсии;

Pages:     || 2 | 3 | 4 | 5 |   ...   | 14 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.