?
Pareto-optimal Algorithms for Metric TSP: Experimental Research
International Journal of Open Information Technologies. 2017. Vol. 5. No. 5. P. 16-24.
Научное направление:
Компьютерные науки
Приоритетные направления:
компьютерно-математическое
Язык:
английский
M.K. Gordenko, S.M. Avdoshin, Proceedings of the Institute for System Programming of the RAS 2017 Vol. 29 No. 4 P. 107-122
Задачи маршрутизации важны для областей логистики и управления трансортом. Задачи маршрутизации в основном связаны с определением оптимального набора путей в мультиграфе. Задача китайского почтальона (CPP) является особым случаем задачи маршрутизации, имющим много потенциальных приложений. Мы предлагаем решение MCPP (специального NP-полного случая CPP на смешанном мультиграфе) с использованием редуцирования исходной задачи к обобщенной задаче коммивояжера (General ...
Добавлено: 27 сентября 2017 г.
Aleksander V. Belov, Загуменнов Ф. Д., , in : Proceedings of the 2018 IEEE International Conference "Quality Management, Transport and Information Security, Information Technologies" (IT&QM&IS). : IEEE, 2018. P. 308-311.
В данной работе основной целью ставится построение алгоритмов оценки эффективности применения системы передачи финансовых сообщений для систем ДБО. В работе рассматриваются два вида взаимодействий юридического лица с банком: «Банк - Клиент» и «Интернет – Клиент». Рассматриваемые взаимодействия осуществляются посредствам двух типов систем: Системы классического дистанционного банковского обслуживания и Системы передачи финансовых сообщений. Входными параметрами построенных ...
Добавлено: 27 ноября 2018 г.
Береснева Е. Н., Горденко М. К., Открытые системы. СУБД 2018 № 01 С. 40-42
Едва научившись ходить, человек начал строить маршруты и сегодня задача прокладки оптимальных трасс актуальна для всех логистических предприятий, хотя ее точного решения до сих пор нет, а есть проблема выбора эвристического алгоритма. ...
Добавлено: 22 июня 2018 г.
Ульянов М. В., Фомичев М. И., Головешкин В. А. и др., 2017 Т. 13 № 1 С. 19-24
Проведен статистический анализ сложности индивидуальных задач коммивояжера, определяемой как число вершин дерева решений, порожденного алгоритмом ветвей и границ. Получены приближенные представления зависимости параметров вероятностного распределения натурального логарифма сложности от размерности задачи. Линейная зависимость используется для построения оценки сверху квантилей натурального логарифма сложности уровня больше 0.5 и снизу для квантилей уровня меньше 0.5. Нелинейная зависимость параметра ...
Добавлено: 26 сентября 2017 г.
Развитие информационно-коммуникационных технологий и вычислительной техники приводит к расширению инструментария для моделирования политических процессов. Если в предыдущие десятилетия математические модели разрабатывались в основном в теоретико-игровой постановке, то сегодня появляется все большее количество работ, реализующих агентное (агентно-ориентированное, agent-based) моделирование. Этот тренд вполне закономерен. Произошли изменения в политическом участии и в формах коллективного взаимодействия индивидов и групп, ...
Добавлено: 3 марта 2021 г.
G. N. Zhukova, M. V. Ulyanov, M. I. Fomichev и др., Automation and Remote Control 2018 Vol. 79 No. 7 P. 1296-1310
Добавлено: 16 июля 2018 г.
S.M. Avdoshin, E.N. Beresneva, Proceedings of the Institute for System Programming of the RAS 2017 Vol. 29 No. 4 P. 123-138
Добавлено: 27 сентября 2017 г.
Жукова Г. Н., Ульянов М. В., Фомичев М. И. и др., Автоматизация. Cовременные технологии 2016 № 10 С. 22-29
Рассмотрено новое обобщённое представление для классов индивидуальных задач коммивояжёра - матрица номеров порядка, предназначенное для выделения классов задач, обладающих близкой сложностью. Полученный результат направлен на решение задачи прогнозирования сложности для индивидуальных задач коммивояжёра. Сформулированы две гипотезы относительно мощности предложенного обобщения. Приведены метод получения матрицы номеров порядка и ряд предварительных экспериментальных результатов, не противоречащих одной из ...
Добавлено: 5 октября 2017 г.
Жукова Г. Н., Ульянов М. В., Фомичев М. И. и др., International Journal of Open Information Technologies 2016 Т. 4 № 12 С. 7-12
Исследуется сложность индивидуальных задач коммивояжера, т.е. число порожденных вершин поискового дерева в классическом методе ветвей и границ. Вероятностное распределение логарифма сложности аппроксимируется нормальным распределением. На основе экспериментальных данных рассчитаны значения параметров линейного преобразования, обеспечивающих минимальное среднеквадратическое отклонение выборочных квантилей логарифма сложности от соответствующих квантилей стандартного нормального распределения, получена формула зависимости этих параметров от числа вершин ...
Добавлено: 5 октября 2017 г.
Фомичев М. И., Ульянов М. В., Головешкин В. А. и др., International Journal of Open Information Technologies 2016 Т. 4 № 12 С. 131-137
На основе статистического анализа сложности индивидуальной задачи коммивояжера, решаемой методом ветвей и границ, показано, что распределение логарифма сложности удовлетворительно аппроксимируется нормальным распределением. Коэффициенты линейной регрессии выборки логарифма сложности на стандартное нормальное распределение использовались для оценки значений параметров аппроксимирующего нормального распределения. Даны оценки границ 90% интервала сложности. ...
Добавлено: 19 августа 2017 г.
Maria K. Gordenko, Авдошин С. М., International Journal of Open Information Technologies 2017 Vol. 5 No. 6 P. 6-11
Добавлено: 1 июня 2017 г.
Жукова Г. Н., Ульянов М. В., Фомичев М. И. и др., Современные информационные технологии и ИТ-образование 2016 Т. 12 № 3-2 С. 131-137
На основе статистического анализа сложности индивидуальной задачи коммивояжера, решаемой методом ветвей и границ, показано, что распределение логарифма сложности удовлетворительно аппроксимируется нормальным распределением. Коэффициенты линейной регрессии выборки логарифма сложности на стандартное нормальное распределение использовались для оценки значений параметров аппроксимирующего нормального распределения. Даны оценки границ 90% интервала сложности.
<img /> ...
Добавлено: 5 октября 2017 г.
Фомичев М. И., Информационные технологии моделирования и управления 2018 Т. 109 № 1 С. 47-54
В современном мире промедление в секунду, или даже долю секунды, может стоить миллионы рублей. Заинтересованному лицу важно получить точный ответ на вопрос в кратчайшие сроки. Но, к сожалению, даже при ны- нешних вычислительных мощностях, многие задачи не могут быть решены точно за приемлемое время. ...
Добавлено: 22 марта 2020 г.
В статье приведены результаты статистического исследования сложности несимметричной задачи коммивояжера (NTSP), полученные в результате обработки специального сгенерированного пула матриц. Основная цель - вероятностной прогноз сложности индивидуальных задач, для больших значений размерности матрицы стоимостей. Показано, что нормальное распределение удовлетворительно приближает распределение логарифма сложности при фиксированной размерности задачи. Построено семейство вероятностных распределений, являющихся удовлетворительными приближениями распределения сложности ...
Добавлено: 16 июля 2018 г.
Иванова Е. М., М. : Московский государственный институт электроники и математики, 2012
Составлено в соответствии с рабочей программой курса и содержит подробное изложение лекционного материала в объёме, достаточном для изучения студентами-бакалаврами данного направления в рамках дисциплины «Вычислительная математика». Включает разделы о теоретических основах численных методов, решении нелинейных, дифференциальных и интегральных уравнений, а также систем линейных, нелинейных и дифференциальных уравнений, приближенного вычисления производных и интегралов, аппроксимации функций, методах ...
Добавлено: 12 октября 2012 г.
Pei J., Liu X., Пардалос П. О. и др., International Journal of Systems Science 2015 Vol. 47 No. 4 P. 765-776
Motivated by applications in manufacturing industry, we consider a supply chain scheduling problem, where each job is characterised by non-identical sizes, different release times and unequal processing times. The objective is to minimise the makespan by making batching and sequencing decisions. The problem is formalised as a mixed integer programming model and proved to be ...
Добавлено: 28 сентября 2015 г.
Жукова Г. Н., Ульянов М. В., Фомичев М. И., Automation and Remote Control 2019 Vol. 80 No. 11 P. 2054-2067
Добавлено: 24 ноября 2019 г.
Приведены результаты сравнительного статистического анализа времени решения несимметричной задачи коммивояжера (NTSP) методом ветвей и границ (без предвычисления тура) и комбинированным методом. Комбинированный метод состоит из приближенного алгоритма Lin- Kernighan-Helsgaun, используемого для вычисления начального тура, и метода ветвей и границ. Показано, что использование приближенного решения, найденного с помощью алгоритма Lin-Kernighan-Helsgaun, позволяет существенно уменьшить время поиска точного ...
Добавлено: 10 ноября 2019 г.
Головешкин В. А., Жукова Г. Н., Ульянов М. В. и др., Системы компьютерной математики и их приложения 2017 № 18 С. 136-138
В докладе рассматривается статистическая зависимость числа
порожденных вершин дерева решений и физического времени работы
программной реализации метода ветвей и границ для задачи
коммивояжера (TSP). На основе результатов вычислительного
эксперимента получено приближенное соотношение между числом
порожденных вершин (сложность индивидуальной TSP) и физическим
временем. Предлагается использовать это эмпирическое соотношение
для прогнозирования времени работы программы, решающей TSP с
числом «городов» больше 40. ...
Добавлено: 22 марта 2020 г.
Чусовлянкин А. А., Морозенко В. В., Вестник Пермского университета. Серия: Математика. Механика. Информатика 2016 Т. 4 № 35 С. 68-75
Предложен новый «антижадный» алгоритм для решения задачи коммивояжера, имеющий меньшую погрешность, чем известные приближенные полиномиальные алгоритмы. Идея «антижадного» алгоритма заключается в том, что из графа последовательно удаляются ребра наибольшей длины при одновременном соблюдении для оставшегося графа двух правил. Во-первых, из каждой его вершины должно выходить, как минимум, два ребра. Во-вторых, в нем не должно возникать ...
Добавлено: 23 января 2017 г.
Ульянов М. В., Фомичев М. И., Информационные технологии 2019 Т. 25 № 10 С. 590-595
Алгоритм, реализующий метод ветвей и границ, для решения задачи коммивояжера - один из востребованных точных алгоритмов ее решения. Метаэвристические алгоритмы решения этой задачи не гарантируют получения точного решения, но работают "быстро". Для сокращения числа вершин порожденного дерева решений в методе ветвей и границ можно использовать решение, полученное метаэвристическим алгоритмом. За счет выбора метаэвристического алгоритма и ...
Добавлено: 16 февраля 2020 г.
М. : Издательский центр «Российский государственный гуманитарный университет», 2019
Сборник включает 27 докладов международной конференции по компьютерной лингвистике и интеллектуальным технологиям «Диалог 2019», не вошедшие в ежегодник «Компьютерная лингвистика и интеллектуальные технологии», но рекомендованные Программным Комитетом к представлению на конференции. Для специалистов в области теоретической и прикладной лингвистики и интеллектуальных технологий. ...
Добавлено: 10 декабря 2019 г.
Карпов В. Э., Карпова И. П., Procedia Engineering 2015 Vol. 100 P. 1459-1468
Добавлено: 14 марта 2015 г.
Chernyshev S. V., Cherepanov E. A., Pankratiev E. V. и др., Journal of Mathematical Sciences 2005 Vol. 128 No. 6 P. 3487-3495
Добавлено: 27 января 2014 г.