📄Работа №102468

Тема: ЭФФЕКТИВНЫЕ АЛГОРИТМЫ С ГАРАНТИРОВАННЫМИ ОЦЕНКАМИ ТОЧНОСТИ ДЛЯ НЕКОТОРЫХ ОБОБЩЕНИЙ ЗАДАЧИ КОММИВОЯЖЕРА

Характеристики работы

≡
Тип работы Авторефераты (РГБ)
Математика
Предмет Математика
📄
Объем: 19 листов
📅
Год: 2017
👁️
Просмотров: 257
2000 руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
ℹ️ Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание 📖 Введение 📕 Литература 🔍 Похожие 🛒 Купить

📋 Содержание

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Публикации автора по теме диссертации
Статьи, опубликованные в журналах из списка ВАК

📖 Введение

Актуальность темы. Предмет исследования диссертационной работы составляют труднорешаемые оптимизационные задачи, являющиеся обобщениями классической задачи коммивояжера (Traveling Salesman
Problem, TSP). В работе исследуются: задача о цикловом покрытии
фиксированной мощности 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-k-GC).
Результаты для близких постановок маршрутных задач были получены в работах Э.Х. Гимади, А.А. Агеева, Б. Манти, А.Г. Ченцова,
А. Григорьева и др.
Задача о цикловом покрытии графа фиксированного размера k минимального веса — это задача комбинаторной оптимизации, заключающаяся
в поиске оптимального покрытия полного взвешенного графа k вершиннонепересекающимися циклами. На содержательном уровне каждый цикл в
покрытии может трактоваться как маршрут для некоторого транспортного средства, посещающего соответствующее множество клиентов. С этой
точки зрения задача о цикловом покрытии близка к известной задаче
маршрутизации транспорта (Vehicle Routing Problem, VRP). С другой
стороны, при фиксированной единичной мощности циклового покрытия
задача совпадает с классической задачей коммивояжера. Кроме того, задача о цикловом покрытии мощности k занимает промежуточное положение в сложностной иерархии между эффективно разрешимой задачей
о назначениях и труднорешаемой задачей коммивояжера, что индуцирует дополнительный теоретический интерес к исследованию сложности и
аппроксимируемости Min-k-SCCP.
Постановка обобщенной задачи коммивояжера (Generalized Traveling
Salesman Problem, GTSP), известной в отечественной литературе под названием «задача обхода мегаполисов», задается полным взвешенным графом, множество вершин которого разбито на k непересекающихся кластеров, и заключается в поиске цикла минимального веса посещающего
каждый кластер.

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

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

👨‍🎓 Помощь в написании
🎓 Дипломные 📘 Магистерские 📙 Диссертации 📗 Курсовые 📝 Статьи 📄 ВКР
Нужна своя уникальная работа?
Срочная разработка под ваши требования
Рассчитать стоимость
ИЛИ
Поиск аналога

📕 Список литературы

[1] Khachay M., Neznakhina K. Approximability of the minimum-weight k-size cycle cover problem //Journal of Global Optimization. - 2016. - Vol. 66. - №. 1. - P. 65-82. DOI: 10.1007/s10898-015-0391-3. (Web of science, Scopus)
[2] Хачай М.Ю., Незнахина Е.Д. Аппроксимируемость задачи о ми¬нимальном по весу цикловом покрытии графа // Доклады ака¬демии наук. - 2015. - Т. 461. - №. 6. - С. 644-649. DOI: 10.7868/S086956521512004X. (РИНЦ)
Khachai M.Y., Neznakhina E.D. Approximability of the problem about a minimum-weight cycle cover of a graph // Doklady Mathematics. - Pleiades Publishing, 2015. - Vol. 91. - №. 2. - P. 240-245. DOI: 10.1134/S1064562415020313. (Web of science, Scopus)
Neznakhina E.D. A PTAS for Min-k-SCCP in Euclidean space of arbitrary fixed dimension //Proceedings of the Steklov Institute of Mathematics. - 2016. - Vol. 295. - №. 1. - P. 120-130. DOI: 10.1134/S0081543816090133. (Web of science, Scopus)
[4] Хачай М.Ю., Незнахина Е.Д. Разрешимость обобщенной задачи коммивояжера в классе квази- и псевдопирамидальных маршрутов // Труды Института математики и механики УрО РАН. - 2017. - Т. 22. - №. 3 - С. 280-291. DOI: 10.21538/0134-4889-2017-23-3-280-291. (РИНЦ)
[5] Хачай М.Ю., Незнахина Е.Д. Приближенные схемы для обобщенной задачи коммивояжера //Труды Института математики и механики УрО РАН. - 2016. - Т. 22. - №. 3. - С. 283-292. DOI: 10.21538/0134¬4889-2016-22-3-283-292. (РИНЦ)
[6] Khachay M., Neznakhina K. Towards a PTAS for the generalized TSP in grid clusters //AIP Conference Proceedings. - AIP Publishing, 2016. - Vol. 1776. - №. 1. - P. 050003. DOI: 10.1063/1.4965324. (Web of science, Scopus)
[7] Khachay M., Neznakhina K. Polynomial Time Approximation Scheme for the Minimum-weight k-Size Cycle Cover Problem in Euclidean space of an arbitrary fixed dimension //IFAC-PapersOnLine. - 2016. - Vol. 49.
- №. 12. - P. 6-10. DOI: 10.1016/j.ifacol.2016.07.541. (Web of science, Scopus)
[8] Хачай М.Ю., Незнахина Е.Д. Полиномиальная приближенная схе¬ма для евклидовой задачи о цикловом покрытии графа // Труды Института математики и механики УрО РАН. - 2014. - Т. 20. - №. 4.
- С. 297-311. (РИНЦ)
Khachai M.Y., Neznakhina E.D. A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph // Proceedings of the Steklov Institute of Mathematics. - 2015. - Vol. 289.
- №. 1. - P. 111-125. DOI: 10.1134/S0081543815050107. (Web of science, Scopus)
Другие публикации
[9] Khachay M., Neznakhina K. Approximation Schemes for the Generalized TSP in Grid Clusters // VIII International Conference on Optimization Methods and Applications (Petrovac, Montenegro, October 2-7, 2017) :тез.докл. - Moscow, 2017, P. 81.
[10] Khachay M., Neznakhina K. Efficient optimal algorithm for the Quasipyramidal GTSP // 17th Baikal international school-seminar "Methods of Optimization and Their Applications"(Maksimikha, Russia, July 31 - August 6, 2017) :тез.докл. - Irkutsk, 2017, P. 109.
[11] Khachay M., Neznakhina K. Approximation Schemes for the Generalized TSP in Grid Clusters // VII International Conference on Optimization Methods and Applications (Petrovac, Montenegro, September 25 - October 2, 2016) :тез.докл. - Moscow, 2016, P. 88.
[12] Khachay M., Neznakhina K. Approximation Algorithms for Generalized TSP in Grid Clusters // CEUR Workshop Proceedings. - 2016. - Vol. 1623. - P. 39-48. (Scopus)
[13] Khachay M., Neznakhina K. Polynomial Time Approximation Scheme forEuclidean Minimum-weight k-Size Cycle CoverProblem in Rd// VI International Conference on Optimization Methods and Applications (Petrovac, Montenegro, September 27 - October 3, 2015) :тез.докл. - Moscow, 2015, P. 104.
[14] Khachay M., Neznakhina K. Polynomial Time Approximation Scheme for Euclidean Minimum-weight k-Size Cycle Cover Problem on the plane // 28th Conference of the European Chapter on Cobinatorial Optimization (Catania, Italy, 28-30 May 2015):тез.докл. - 2015, P. 29.
[15] Незнахина Е.Д., Хачай М.Ю. PTAS для евклидовой задачи Min- k-SCCP на плоскости для произвольных фиксированных значений параметра к // XV Всероссийская конференция "Математическое программирование и приложения"(Екатеринбург, Россия, 2-6 мар¬та 2015 г.) : тез.докл. - Екатеринбург, 2015, C. 151.
[16] Незнахина Е.Д. Аппроксимируемость евклидовой задачи о цикло¬вом покрытии графа произвольного фиксированного размера // Со¬временные проблемы математики и её приложений (г. Екатеринбург, 25-31 января 2015 г.) : Труды 46-й Международной молодежной школы-конференции - Екатеринбург, 2015, С. 115.
[17] Khachay M., Neznakhina E. Polynomial-time approximability of geometric multiple traveling salesmen problem // 10-я международная конференция Интеллектуализация обработки информации (о.Крит, Греция , 4-11 октября 2014 г.) : тез.докл. - Москва, 2014, P. 99.
[18] Khachay M., Neznakhina E. k-Minimum Hamiltonian Cycles Problem. Complexity and Approximability // V International Conference on Optimization Methods and Applications (Petrovac, Montenegro, September 2014) :тез.докл. - Moscow, 2014, P. 112.
[19] Khachay M., Neznakhina E. Approximation of k-Minimum Hamiltonian Cover Problem // 15th International Conference on Operational Research (Osijek, Croatia, 24-26 September 2014) :тез.докл. - 2014, P. 41.
[20] Хачай М.Ю., Незнахина Е.Д. Полиномиальная приближенная схе¬ма для задачи о разбиении полного евклидова графа на два гамиль¬тоновых цикла минимального веса // XVI Байкальская междуна¬родная школа-семинар, Методы оптимизации и их приложения (о. Ольхон, Байкал, 30 июня - 6 июля 2014 г.) : тез.докл. - Красноярск, 2014, С. 88.
[21] Незнахина Е.Д. PTAS для некоторых обобщений евклидовой задачи TSP // Современные проблемы математики и её приложений (г. Екатеринбург, 2-8 февраля 2014 г.) : Труды 45-й Международной молодежной школы-конференции - Екатеринбург, 2014, С. 181.

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

⚡ Работу высылаем в течении 5 минут после оплаты.
Предоставляемые услуги, в том числе данные, файлы и прочие материалы, подготовленные в результате оказания услуги, помогают разобраться в теме и собрать нужную информацию, но не заменяют готовое решение.
Укажите ник или номер. После оформления заказа откройте бота @workspayservice_bot для подтверждения. Это нужно для отправки вам уведомлений.

🔍 ПОХОЖИЕ РАБОТЫ ПО ТЕМЕ

Эффективные алгоритмы с гарантированными оценками точности для некоторых обобщений задачи коммивояжера ▣Диссертация ∑Математика 2017 г. 5720 руб. Задачи составления расписаний с временами поступления и директивными сроками ▣Дипломные работы, ВКР ∑Прикладная информатика 2017 г. 4700 руб. Построение гарантированных оценок показателей функционирования сложных технических систем в условиях ограниченного объема информации ▣Магистерская диссертация ∑Информационные системы 2016 г. 4900 руб. Вычислительный эксперимент по оценке эффективности алгоритма работы пастушьей собаки ▣Дипломные работы, ВКР ∑Программирование 2017 г. 4900 руб. ДВУХУРОВНЕВОЕ МОДЕЛИРОВАНИЕ ДИСКРЕТНЫХ ЭВОЛЮЦИОННЫХ ПРОЦЕССОВ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ ▣Диссертация ∑Математика 2004 г. 500 руб. РАЗРАБОТКА И ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ИНТЕЛЛЕКТУАЛЬНОГО АЛГОРИТМА ОБРАБОТКИ ЭКСПЕРТНЫХ ОЦЕНОК ▣Магистерская диссертация ∑Информатика и вычислительная техника 2019 г. 4900 руб. Алгоритмы минимаксной и калмановской фильтрации в задаче оценивания вектора состояния линейной динамической системы для единственной реализации измерений ▣Дипломные работы, ВКР ◈Автоматика и управление 2019 г. 4395 руб. ИССЛЕДОВАНИЕ ПРИБЛИЖЕННОГО АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ МИНИМИЗАЦИИ СУММАРНОГО ЗАПАЗДЫВАНИЯ ◩Бакалаврская работа ∑Информатика и вычислительная техника 2017 г. 4760 руб. МЕТОД И АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ ДЛЯ ПОСТРОЕНИЯ ОБЪЕМНЫХ МОДЕЛЕЙ ГЕОЛОГИЧЕСКОЙ СРЕДЫ ▣Диссертация ✿Геология и минералогия 2022 г. 700 руб. АВТОНОМНАЯ ПЕРСОНАЛЬНАЯ ИНФОРМАЦИОННО- ИЗМЕРИТЕЛЬНАЯ СИСТЕМА НАЗЕМНОГО ПОЗИЦИОНИРОВАНИЯ С КОРРЕКЦИЕЙ УГЛОВ НАКЛОНА ПО ОПОРНОЙ ПОВЕРХНОСТИ ▣Магистерская диссертация ▤Машиностроение 2019 г. 5700 руб.

📎 АВТОРЕФЕРАТЫ (РГБ) ПО ПРЕДМЕТУ «МАТЕМАТИКА»

Найдено работ: 58

Геометрическая теория инерциальных многообразий для компактных коциклов в банаховых пространствах и её приложения ≡Авторефераты (РГБ) ∑Математика 2022 г. 2000 руб. Рандомизированные алгоритмы оценивания параметров инкубационных процессов в условиях неопределенностей и конечного числа наблюдений ≡Авторефераты (РГБ) ∑Математика 2018 г. 250 руб. Эффективные алгоритмы анализа закономерностей в строках ≡Авторефераты (РГБ) ∑Математика 2016 г. 2000 руб. Вычислительная сложность некоторых задач обработки строк ≡Авторефераты (РГБ) ∑Математика 2016 г. 2000 руб. О комбинаторных свойствах бесповторных языков Список литературы ≡Авторефераты (РГБ) ∑Математика 2016 г. 2000 руб. ИДЕАЛЬНЫЕ ЯЗЫКИ И СИНХРОНИЗИРУЕМЫЕ АВТОМАТЫ ≡Авторефераты (РГБ) ∑Математика 2015 г. 2200 руб. Маршрутно-распределительные задачи: теория и приложения ≡Авторефераты (РГБ) ∑Математика 2015 г. 2200 руб. ИССЛЕДОВАНИЕ КРАЕВЫХ ЗАДАЧ ДЛЯ УРАВНЕНИЙ СОБОЛЕВСКОГО ТИПА В НЕЦИЛИНДРИЧЕСКИХ ОБЛАСТЯХ ≡Авторефераты (РГБ) ∑Математика 2006 г. 250 руб. СУЩЕСТВОВАНИЕ И УСТОЙЧИВОСТЬ РЕШЕНИЙ КРАЕВЫХ ЗАДАЧ ЭЛЛИПТИЧЕСКОГО ТИПА С РАЗРЫВНЫМИ НЕЛИНЕЙНОСТЯМИ ≡Авторефераты (РГБ) ∑Математика 2005 г. 250 руб. ПОСТРОЕНИЕ И ИССЛЕДОВАНИЕ МЕТОДОВ РЕГУЛЯРИЗАЦИИ ДЛЯ ЗАДАЧИ СВЯЗАННОГО ПСЕВДООБРАЩЕНИЯ ≡Авторефераты (РГБ) ∑Математика 2006 г. 250 руб. МАГНИТНЫЕ, ЭЛЕКТРИЧЕСКИЕ И ТЕПЛОВЫЕ СВОЙСТВА ИНТЕРКАЛИРОВАННОГО 3д- МЕТАЛЛАМИ ДИСЕЛЕНИДА ТИТАНА ≡Авторефераты (РГБ) ∑Математика 2006 г. 250 руб. Методы и алгоритмы построения негладких решений краевых задач теории позиционных дифференциальных игр и оптимального управления ≡Авторефераты (РГБ) ∑Математика 2017 г. 2500 руб. АНАЛИТИЧЕСКИЕ ПРЕДСТАВЛЕНИЯ И УСТОЙЧИВОСТЬ РЕШЕНИЙ ЛИНЕЙНЫХ СИСТЕМ ФУНКЦИОНАЛЬНО-РАЗНОСТНЫХ УРАВНЕНИЙ ≡Авторефераты (РГБ) ∑Математика 2004 г. 250 руб. УСТОЙЧИВОСТЬ СТОХАСТИЧЕСКИХ СИСТЕМ СО СЛУЧАЙНЫМИ СКАЧКАМИ ФАЗОВЫХ ТРАЕКТОРИЙ ≡Авторефераты (РГБ) ∑Математика 2004 г. 250 руб. УПРАВЛЯЕМЫЕ И ЧИСЛЕННЫЕ МОДЕЛИ СИСТЕМ С ПОСЛЕДЕЙСТВИЕМ ≡Авторефераты (РГБ) ∑Математика 2001 г. 250 руб.
📋 Содержание 📖 Введение 📕 Литература 🔍 Похожие 🛒 Купить ⬆️

Оценка стоимости

Пожалуйста, выберите предмет работы.
Пожалуйста, выберите тип работы.
Пожалуйста, укажите объем работы.
Пожалуйста, укажите срок выполнения.

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

Каталог работ (211285)

Поиск работ


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