🔍 Поиск образцов работ

Учебно-методический материал.
Предоставляется в ознакомительных и исследовательских целях
📄 Образец работы №102470

Эффективные алгоритмы с гарантированными оценками точности для некоторых обобщений задачи коммивояжера

ℹ️ Материал размещён в информационных целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки пользователем.
📝 Тип работы Диссертация
📚 Предмет математика
📄 Объем 101 листов
📅 Год подготовки 2017
👁️ Просмотров 274
5720 руб.
🛒 Купить работу
📋 Содержание 📖 Введение ✅ Заключение 📕 Литература 🛒 Купить

📋 Содержание (образец)

Введение 6
1 Постановки исследуемых задач 17
1.1 Задачи комбинаторной оптимизации 17
1.2 Предварительные сведения об исследовании задачи коммивояжера 19
1.3 Задача о цикловом покрытии графа фиксированного размера 25
1.4 Обобщенная задача коммивояжера 28
1.5 Пирамидальные маршруты 32
2 Задача о цикловом покрытии графа 35
2.1 Вычислительная сложность задачи Min-k-SCCP 35
2.2 Принадлежность задачи Metric Min-k-SCCP классу APX 37
2.2.1 Алгоритм построения минимального остовного к-леса 37
2.2.2 2-приближенный алгоритм для задачи Metric Min-k-SCCP 39
2.3 Полиномиальная приближенная схема для задачи Euclidean Min-k-SCCP в Rd 42
2.3.1 Декомпозиция евклидовой задачи о цикловом покрытии графа 43
2.3.2 Округленная задача Euclidean Min-k-SCCP 48
2.3.3 Рекурсивное разбиение объемлющего гиперкуба S 50
2.3.4 Теорема существования 53
2.3.5 Динамическое программирование 55
2.3.6 Дерандомизация 57
3 Обобщенная задача коммивояжера 59
3.1 Квази- и псевдопирамидальные маршруты 59
3.2 Полиномиально разрешимый подкласс 66
3.3 Приближенные схемы для случая медленно растущих значений параметра к . 71
3.3.1 Применение метода динамического программирования при построении
приближенной схемы 72
3.3.2 Обобщение схемы Ароры для задачи коммивояжера на плоскости на
случай EGTSP-k-GC 74
3.4 Приближенная схема для случая быстро растущих значений параметра к ... 80
Заключение 82
Публикации автора по теме диссертации 84
Благодарности 88
Литература 89

📖 Введение (образец)

Предмет исследования диссертационной работы1 составляют труднорешаемые оптимизационные задачи, являющиеся обобщениями классической задачи
коммивояжера (Traveling Salesman Problem, TSP) [83, 63]. В работе исследуются: задача о цикловом покрытии фиксированной мощности k минимального
веса (Minimum-weight k-Size Cycle Cover Problem, Min-k-SCCP), обобщенная
задача коммивояжера (Generalized Traveling Salesman Problem, GTSP) и её геометрическая постановка евклидова обобщенная задача коммивояжера на сетке
(Euclidean Generalized Traveling Salesman Problem in k Grid Clusters, EGTSP-kGC).
Задача о цикловом покрытии графа фиксированного размера k минимального веса — это задача комбинаторной оптимизации, заключающаяся
в поиске оптимального покрытия полного взвешенного графа k вершиннонепересекающимися циклами. На содержательном уровне каждый цикл в покрытии может трактоваться как маршрут для некоторого транспортного средства, посещающего соответствующее множество клиентов. С этой точки зрения
задача о цикловом покрытии близка к известной задаче маршрутизации транспорта (Vehicle Routing Problem, VRP) [113]. С другой стороны, при фиксированной единичной мощности циклового покрытия задача совпадает с классической
задачей коммивояжера. Кроме того, задача о цикловом покрытии мощности k
1Работа поддержана грантами РНФ 14-11-00109, РФФИ 13-07-00181, 16-07-00266, стипендией Президента
Российской Федерации
6занимает промежуточное положение в сложностной иерархии между эффективно разрешимой задачей о назначениях и труднорешаемой задачей коммивояжера, что индуцирует дополнительный теоретический интерес к исследованию
сложности и аппроксимируемости Min-k-SCCP.
Цикловые покрытия играют важную роль при разработке приближенных
алгоритмов для задачи коммивояжера [27, 26, 32, 34, 36], задачи о кратчайшей
суперстроке [31, 111] и задачи маршрутизации транспорта [64]. В случае задачи
коммивояжера при построении указанных алгоритмов в качестве начального
приближения выступает цикловое покрытие, элементы которого соединяются в
гамильтонов цикл с помощью той или иной техники объединения фрагментов
маршрута.
Помимо выполнения вспогательной роли при построении приближенных алгоритмов, поиск оптимальных цикловых покрытий является интересной независимой задачей. Паросочетания и факторизация графов — это важные разделы
теории графов, наряду с этим поиск циклового покрытия эквивалентен стесненной дополнительным ограничением на количество компонент связности задаче
построения 2-фактора, то есть остовного подграфа, каждая вершина которого
инцидентна в точности двум ребрам.
Все перечисленные выше аргументы обуславливают актуальность алгоритмического анализа Min-k-SCCP и уточнения статуса вычислительной сложности данной задачи при k > 1, то есть в случае, когда Min-k-SCCP отлична от
классической задачи коммивояжера.
Обобщенная задача коммивояжера (Generalized Traveling Salesman Problem,
GTSP), известная в отечественной литературе под названием «задача обхода
мегаполисов», задается полным взвешенным графом, множество вершин которого разбито на k непересекающихся кластеров, и заключается в поиске цикла
минимального веса посещающего каждый кластер.
7Что касается алгоритмов с гарантированными оценками точности, даже для
метрической постановки GTSP известно не так много результатов. В [109] представлен 3ρ/2-приближенный алгоритм, где ρ — это число вершин в наибольшем по мощности кластере (ρ = maxi=1,...,k(|Vi|)). К сожалению, в худшем случае данная оценка точности оказывается очень слабой, и алгоритм неприменим для практических целей. Н. Гарг и Дж. Коньевод построили рандомизированный приближенный алгоритм для обобщенной задачи о штейнеровском
дереве, побочным результатом этой работы стал O(log2(n) log(log(n)) log k)-
приближенный алгоритм для GTSP [58]. Таким образом, исследования в области сложности (в том числе параметрической) и аппроксимируемости задачи
GTSP представляются актуальными.
Кроме того, представляется актуальной задача исследования вычислительной сложности и аппроксимируемости геометрических постановок GTSP. Данные постановки наряду с теоретическим вызывают и большой практический
интерес, обладая рядом приложений, например, в задачах оптимальной доставки почтовых отправлений и задачах о демонтаже отработанных энергоблоков
АЭС.
При фиксированном числе кластеров общая постановка GTSP обладает точным полиномиальным алгоритмом с трудоемкостью O((k − 1)!n3). Задачи построения точного алгоритма меньшей трудоемкости либо обоснование подклассов, в которых GTSP разрешима за полиномиальное по n и k время, также
представляются актуальными.

Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании работ!

Дипломные Магистерские Диссертации Курсовые Статьи ВКР

✅ Заключение (образец)

В диссертационной работе исследованы несколько задач маршрутизации, являющихся обобщениями классической задачи коммивояжера. Основные результаты диссертации заключаются в следующем:
1. Для задачи о цикловом покрытии фиксированного размера k (Min-kSCCP):
(a) обоснована NP-трудность в сильном смысле даже в частной евклидовой
постановке;
(б) для метрической постановки задачи при условии, что значение параметра
k является частью входа, построен 2-приближенный алгоритм c асимптотически
достижимой оценкой точности;
(в) для евклидовой постановки задачи в пространстве произвольной фиксированной размерности d предложена эффективная полиномиальная приближенная схема с трудоемкостью O(nO(d)(log n)(O(√εd))d−1).
Таким образом, исследование сложностного статуса и аппроксимируемости в
классе детерминированных алгоритмов задачи Min-k-SCCP можно считать завершенным. В качестве интересного открытого вопроса отметим вопрос неулучшаемости оценки точности 2 для алгоритма из п. 1(б).
2. Для обобщенной задачи коммивояжера (GTSP):
(а) введены понятия l-квазипирамидального и l-псевдопирамидального
маршрутов;
(б) построен алгоритм поиска оптимального l-квазипирамидального марш-
82рута с трудоемкостью O(4ln3), тем самым показано, что обобщенная задача
коммивояжера с неотрицательной симметричной матрицей весов принадлежит
классу FPT;
(в) предложен FPT-алгоритм (относительно параметров k и l) построения
оптимального l-псевдопирамидального маршрута с трудоемкостью O(2lkl+4n3).
3. Для обобщенной задачи коммивояжера на сетке (EGTSP-k-GC):
(а) показано, что при дополнительном ограничении на высоту сетки H ≤ 2
задача разрешима за время O(n3);
(б) для евклидовой постановки задачи построены три приближенные схемы для случая быстро k = n − O(log n) и медленно k = O(log n) растущих
значений параметра k. Для случая медленно растущего значения k две предложенные схемы являются линейными приближенными схемами с трудоемкостью
O(k2(O(1/ε))2k)+O(n) и 2O(k)k4(log k)O(1/ε)+O(n) соответственно и представляют практический интерес при фиксированном значении параметра, несмотря на
полиномиальную разрешимость задачи в этом случае, так как известный точный алгоритм имеет кубическую трудоемкость. При фиксированном значении
параметра k третья схема является эффективной полиномиальной приближенной схемой с трудоемкостью nk(log k)O(1/ε) и сохраняет полиномиальность при
k = n − O(log n).
Статусы вычислительной сложности обобщенной задачи коммивояжера на
сетке при промежуточных значениях параметра k (между O(log n) и n −
O(log n)) и при высоте сетки H > 2 являются важными открытыми вопросами.

📕 Список литературы (образец)

[1] Гимади Э.Х., Истомин А.М., Рыков И.А., Цидулко О.Ю. Вероятностный анализ приближенного алгоритма для решения задачи о нескольких ком-мивояжерах на случайных входных данных, неограниченных сверху // Тр. ИММ УрО РАН, 20(2):88—98, 2014.
[2] Гимади Э.Х., Кельманов А.В., Пяткин А.В., Хачай М.Ю. Эффективные алгоритмы с оценками точности для некоторых задач поиска нескольких клик в полном неориентированном взвешенном графе // Тр. Ин-та ма-тематики и механики УрО РАН, 20(2):99—112, 2014.
[3] Гимади Э.Х., Перепелица В.А. Асимптотически точный подход к решению задачи коммивояжера // Управляемые системы: сб. науч. тр., 12:35-45, 1974.
[4] Гимади Э.Х., Хачай М.Ю. Экстремальные задачи на множествах пере-становок // Издательство УМЦ УПИ, 2016.
[5] Гимади Э.Х., Цидулко О.Ю. Асимптотически точный алгоритм для зада¬чи нескольких коммивояжёров на случайных входных данных с дискрет¬ным распределением // Дискретн. анализ и исслед. опер., 24(3):5—19, 2017.
[6] Сесекин А.Н., Ченцов А.А., Ченцов А.Г. Задачи маршрутизации переме-щений // Лань, Санкт-Петербург, 2011.
[7] Ченцов А.Г. Задача последовательного обхода мегаполисов с условиями предшествования // Автомат. и телемех., 4:170-190, 2014.
[8] Ченцов А.Г., Хачай М.Ю., Хачай Д.М. Точный алгоритм с линейной тру-доемкостью для одной задачи обхода мегаполисов // Тр. ИММ УрО РАН, 21(3):309—317, 2015.
[9] Ченцов А.Г., Ченцов П.А. Маршрутизация в условиях ограничений: зада¬ча о посещении мегаполисов // Автомат. и телемех., 11:96-117, 2016.
[10] Эндрюс Г. Теория разбиений // М.: Наука, 1982.
[11] Ageev A. Constant-Factor Approximations for Cycle Cover Problems. LNCS, 9869:93-104, 2016.
[12] Aizenshtat V., Kravchuk D. Algorithms for finding the extremum of a linear form on the set of all cycles in special cases // Dokl. Akad. Nauk BSSR, 12:401—404, 1968.
[13] Applegate D., Bixby R., Chvatal V., Cook. W On the solution of traveling salesman problems // Documenta Mathematica, 111:645—656, 1998.
[14] Arkin E.M. and Hassin R. Approximation algorithms for the geometric covering salesman problem // Discrete Appl. Math., 55(3):197—218, 1994.
[15] Arora S. Polynomial-time approximation schemes for euclidean traveling salesman and other geometric problems // Journal of the ACM, 45:753—782, 1998.
[16] Arora S., Lund C., Motwani R., Sudan M., Szegedy M. Proof verification and the hardness of approximation problems // Journal of the ACM, 45(3):501— 555, 1998.
[17] Arora S., Safra S. Probabilistic checking of proofs: a new characterization of NP // Journal of the ACM, 45:70-122, 1 1998.
[18] Baburin A.E., Della Croce F., Gimadi E.Kh., Glazkov Yu.V., Paschos V.Th. Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2 // Discrete Applied Mathematics, 157(9):1988-1992, 2009.
[19] Baki F., Kabadi S. Some sufficient conditions for pyramidal optimal traveling
salesman tours // Working paper #95-021, Faculty of Administration,
University of New Brunswick, 1995.
[20] Bellman R. Dynamic programming treatment of the travelling salesman problem // J. ACM, 9(1):61-63, 1962.
[21] Ben-Arieh D., Gutin G., Penn M., Yeo A. Transformations of Generalized ATSP into ATSP // Operations Research Letters, 31:357-365, 2003.
[22] Buchin K., Jansen B., Woeginger G., Berg M. Fine-grained complexity analysis of two classic TSP variants // Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 55:5:1—-5:14, 2016.
[23] Bhattacharya B., Custic A., Rafiey A., Sokol V. Combinatorial Optimization and Applications: 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings, chapter Approximation Algorithms for Generalized MST and TSP in Grid Clusters, pages 110-125. LNCS. Springer International Publishing, Cham, 2015.
[24] Bjorklund A. Determinant sums for undirected hamiltonicity // SIAM J. Comput., 43(1):280-299, 2010.
[25] Blaser M. A 3/4-approximation algorithm for maximum ATSP with weights zero and one // LNCS, 3122:61-71, 2004.
[26] Bläser M., Manthey B., Sgall J. An improved approximation algorithm for the Asymmetric TSP with strengthened triangle inequality // Journal of Discrete Algorithms, 4(4):623-632, 2006.
[27] Blaser M., Ram S., Sviridenko M. Improved approximation algorithms for metric maximum ATSP and maximum 3-Cycle Cover Problems // LNCS, 3608:350-359, 2005.
[28] Blaser M., Manthey B. Approximating maximum weight cycle covers in directed graphs with weights zero and one // Algorithmica, 42:121-139, 06 2005.
[29] Blaser M., Manthey B., Sgall J. An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality // Journal of Discrete Algorithms, 4:623-632, 2006.
[30] Blaser M., Siebert B. Computing cycle covers without short cycles // In Algorithms—ESA 2001, pages 368-379. Springer, 2001.
[31] Blum A., Jiang T., Li M., Tromp J., Yannakakis M. Linear approximation of shortest superstrings // Journal of the ACM, 41(4):630-647, 1994.
[32] Bockenhauer H., Hromkovic J., Klasing R., Seibert S., Unger W. Approximation algorithms for the TSP with sharpened triangle inequality // Information Processing Letters, 75(3):133-138, 2000.
[33] Burkard R., Deineko V., Van Dal R., Van Der Veen J., Woeginger J. Well- solvable special cases of the traveling salesman problem: a survey // SIAM Rev., 40(3):496-546, 1998.
[34] Chandran L., Ram L. On the relationship between ATSP and the Cycle Cover Problem // Theoretical Computer Science, 370(1-3):218-228, 2007.
[35] Chandran L., Ram L. On the relationship between ATSP and the cycle cover problem. Theoretical Computer Science, 370:218-228, 2007.
[36] Chen Z., Nagoya T. Improved approximation algorithms for Metric Max TSP // Journal of Combinatorial Optimization, 13(4):321-336, 2007.
[37] Chen Z., Okamoto Y., Wang L. Improved deterministic approximation algorithms for Max TSP // Information Processing Letters, 95(2):333-342, 2005.
[38] Christofides N. Worst-case analysis of a new heuristic for the traveling salesman problem // In Symposium on New Directions and Recent Results in Algorithms and Complexity, page 441, 1975.
[39] Cook S. The complexity of theorem-proving procedures // Proceeding STOC ’71 Proceedings of the third annual ACM symposium on Theory of computing, pages 151-158, 1971.
[40] Cormen T., Leiserson C., Rivest R., Stein C. Introduction to Algorithms // MIT, 3ed. edition, 2009.
[41] Cormen T., Stein C., Rivest R., Leiserson C. Introduction to Algorithms // McGraw-Hill Higher Education, 2nd edition, 2001.
[42] Cutler M. Efficient special case algorithms for the n-line planar traveling salesman problem // Networks, 10:183-195, 1980.
[43] Danzig G., Fulkerson R., Johnson S. Solution of a large scale traveling salesman problem // The RAND corporation, pages 1-33, 1954.
[44] Danzig G., Ramser J. The truck dispatching problem // Management Science, 6(1):80-91, 1959.
[45] De Kort J. Lower bounds for symmetric k-Peripatetic Salesman Problems // Optimization, 20:113-122, 1991.
[46] DimitrijeviC V., "Saric Z. An efficient transformation of the Generalized Traveling Salesman Problem into the Traveling Salesman Problem on digraphs // Information Sciences, 102(1-4):105 - 110, 1997.
[47] Dinur I. The PCP theorem by gap amplification // Journal of the ACM, 54(3):70-122, 2007.
[48] Dror M., Orlin J. Combinatorial optimization with explicit delineation of the ground set by a collection of subsets // SIAM J. Discrete Math., 21(4):1019- 1034, 2008.
[49] Dumitrescu A., Mitchell J. Approximation algorithms for TSP with neighborhoods in the plane // In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’01, pages 38-46, Philadelphia, PA, USA, 2001. Society for Industrial and Applied Mathematics.
[50] Dumitrescu A., Toth C. The traveling salesman problem for lines, balls, and planes // ACM Trans. Algorithms, 12(3):43:1-43:29, April 2016.
[51] Enomoto H., Oda Y., Ota K. Pyramidal tours with step-backs and the asymmetric traveling salesman problem // Discrete Appl. Math., 87(1-3):57- 65, 1998.
[52] Feige U., Goldwasser S., Lovasz L., Safra S., Szegedy M. Approximating clique is almost np-complete // In Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science, pages 2-12, 1991.
[53] Feremans C., Grigoriev A., Sitters R. The geometric generalized minimum spanning tree problem with grid clustering // fOR, 4(4):319-329, 2006.
[54] Finkel R., Bentley J. Quad trees: a data structure for retrieval on composite keys // Acta Informatica, 4(1):1—9, 1974.
[55] Fischetti M., Gonzalez J., Toth P. A branch-and-cut algorithm for the symmetric Generalized Traveling Salesman Problem // Operations Research, 45(3):378-394, 1997.
[56] Gan G., Ma C., Wu J. Data Clustering: Theory, Algorithms, and Applications // ASA-SIAM Series on Statistics and Applied Probability. SIAM, Society for Industrial and Applied Mathematics, 2007.
[57] Garey M., Johnson D. Computers and Intractability: A Guide to the Theory of NP-Completeness // W. H. Freeman & Co., New York, NY, USA, 1979.
[58] Garg N., Konjevod G. A polylogarithmic approximation algorithm for the group steiner tree problem // Journal of Algorithms, 37:66-84, 2000.
[59] Gimadi E. Asymptotically optimal algorithm for finding one and two edge- disjoint traveling salesman routes of maximal weight in euclidean space // Proc. of the Steklov institute of Mathematics, 263:S57-S67, 2008.
[60] Gimadi E.Kh., Glebov A.N., Skretneva A.A., Tsidulko O.Yu. and Zambalaeva D.Zh. Combinatorial algorithms with performance guarantees for finding several hamiltonian circuits in a complete directed weighted graph // Discrete Applied Mathematics, 196:54-61, 2015.
[61] Golden B., Raghavan S., Wasil E. The vehicle routing problem : latest advances and new challenges // Operations research/Computer science interfaces series, 43. Springer, 2008.
[62] Grotschel M., Holland O. Solution of large-scale symmetric travelling salesman problems // Mathematical Programming, 51:141-202, 1991.
[63] Gutin G., Punnen A. and (eds.). The Traveling Salesman Problem and Its Variations // Springer, 2007.
[64] Hassin R., Rubinstein S. On the complexity of the k-customer vehicle routing problem // Operations Research Letters, 33(1):71—76, 2005.
[65] Held M., Karp R. A dynamic programming approach to sequencing problems //In Proceedings of the 1961 16th ACM National Meeting, ACM ’61, pages 71.201-71.204, New York, NY, USA, 1961. ACM.
[66] Helsgaun K. An effective implementation of the Lin-Kernighan traveling salesman heuristic // Oper. Res., 126(1):106-130, 2000.
[67] Helsgaun K. General k-opt submoves for the Lin-Kernighan TSP heuristic // Math. Prog. Comput., 1(2-3):119-163, 2009.
[68] Helsgaun K. Solving the equality generalized traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm // Math. Prog. Comput., 7(3):269- 287, 2015.
[69] Henry-Labordere A. The record balancing problem: a dynamic programming solution of a generalized traveling salesman problem //In RIBO, B-2, pages 736-743, 1969.
[70] Huang H., Yang X., Hao Z., Wu C., Liang Y., Zhao X. Hybrid chromosome genetic algorithm for generalized traveling salesman problems // LNCS, 3612:137-140, 2005.
[71] Jung H. Uber die kleinste kugel, die eine räumliche figur einschliesst // J. reine und angew. Math., 123:241-257, 1901.

🛒 Оформить заказ

⚡ Работу высылаем на протяжении 30 минут после оплаты.

Заказать работу

Заявка на оценку стоимости

Это краткая форма заказа. После ее заполнения вы перейдете на полную форму заказа работы

Каталог образцов работ (205880)

Поиск образцов работ

©2026 Cервис помощи студентам в выполнении работ
.