?
Exact time-efficient combined algorithm for solving the asymmetric traveling salesman problem
Business Informatics. 2018. Vol. 45. No. 3. P. 20-28.
Научное направление:
Компьютерные науки
Приоритетные направления:
бизнес-информатика
Язык:
английский
Ulyanov M.V., Fomichev M.I., Business Informatics 2015 No. 4 (34) P. 38-46
Добавлено: 5 ноября 2016 г.
Приведены результаты сравнительного статистического анализа времени решения несимметричной задачи коммивояжера (NTSP) методом ветвей и границ (без предвычисления тура) и комбинированным методом. Комбинированный метод состоит из приближенного алгоритма Lin- Kernighan-Helsgaun, используемого для вычисления начального тура, и метода ветвей и границ. Показано, что использование приближенного решения, найденного с помощью алгоритма Lin-Kernighan-Helsgaun, позволяет существенно уменьшить время поиска точного ...
Добавлено: 10 ноября 2019 г.
Для практически значимых оптимизационных задач в области экономики и логистики, а также в ряде технических приложений возникает необходимость решения задачи коммивояжера (traveling salesman problem, TSP). Достаточно часто особенности этих задач приводят к задаче коммивояжера в асимметричной постановке (asymmetric traveling salesman problem, ATSP). Более того, в некоторых практических применениях желательно получение точного решения. Одним из известных ...
Добавлено: 11 декабря 2018 г.
Ульянов М. В., Фомичев М. И., Информационные технологии 2019 Т. 25 № 10 С. 590-595
Алгоритм, реализующий метод ветвей и границ, для решения задачи коммивояжера - один из востребованных точных алгоритмов ее решения. Метаэвристические алгоритмы решения этой задачи не гарантируют получения точного решения, но работают "быстро". Для сокращения числа вершин порожденного дерева решений в методе ветвей и границ можно использовать решение, полученное метаэвристическим алгоритмом. За счет выбора метаэвристического алгоритма и ...
Добавлено: 16 февраля 2020 г.
Фомичев М. И., Ульянов М. В., Головешкин В. А. и др., International Journal of Open Information Technologies 2016 Т. 4 № 12 С. 131-137
На основе статистического анализа сложности индивидуальной задачи коммивояжера, решаемой методом ветвей и границ, показано, что распределение логарифма сложности удовлетворительно аппроксимируется нормальным распределением. Коэффициенты линейной регрессии выборки логарифма сложности на стандартное нормальное распределение использовались для оценки значений параметров аппроксимирующего нормального распределения. Даны оценки границ 90% интервала сложности. ...
Добавлено: 19 августа 2017 г.
Жукова Г. Н., Ульянов М. В., Фомичев М. И., Automation and Remote Control 2019 Vol. 80 No. 11 P. 2054-2067
Добавлено: 24 ноября 2019 г.
Фомичев М. И., Информационные технологии моделирования и управления 2018 Т. 109 № 1 С. 47-54
В современном мире промедление в секунду, или даже долю секунды, может стоить миллионы рублей. Заинтересованному лицу важно получить точный ответ на вопрос в кратчайшие сроки. Но, к сожалению, даже при ны- нешних вычислительных мощностях, многие задачи не могут быть решены точно за приемлемое время. ...
Добавлено: 22 марта 2020 г.
Головешкин В. А., Жукова Г. Н., Ульянов М. В. и др., Системы компьютерной математики и их приложения 2017 № 18 С. 136-138
В докладе рассматривается статистическая зависимость числа
порожденных вершин дерева решений и физического времени работы
программной реализации метода ветвей и границ для задачи
коммивояжера (TSP). На основе результатов вычислительного
эксперимента получено приближенное соотношение между числом
порожденных вершин (сложность индивидуальной TSP) и физическим
временем. Предлагается использовать это эмпирическое соотношение
для прогнозирования времени работы программы, решающей TSP с
числом «городов» больше 40. ...
Добавлено: 22 марта 2020 г.
Ульянов М. В., Фомичев М. И., Головешкин В. А. и др., 2017 Т. 13 № 1 С. 19-24
Проведен статистический анализ сложности индивидуальных задач коммивояжера, определяемой как число вершин дерева решений, порожденного алгоритмом ветвей и границ. Получены приближенные представления зависимости параметров вероятностного распределения натурального логарифма сложности от размерности задачи. Линейная зависимость используется для построения оценки сверху квантилей натурального логарифма сложности уровня больше 0.5 и снизу для квантилей уровня меньше 0.5. Нелинейная зависимость параметра ...
Добавлено: 26 сентября 2017 г.
Головешкин В. А., Жукова Г. Н., Ульянов М. В. и др., В кн. : CEUR Workshop Proceedings. Vol. 1761: SITITO 2016. Modern Information Technologies and IT-Education. Selected Papers of the XI International Scientific-Practical Conference Modern Information Technologies and IT-Education (SITITO 2016). Moscow, Russia, November 25-26, 2016.: CEUR Workshop Proceedings, 2016. С. 304-310.
На основе статистического анализа сложности индивидуальной задачи коммивояжера, решаемой методом ветвей и границ, показано, что распределение логарифма сложности удовлетворительно аппроксимируется нормальным распределением. Коэффициенты линейной регрессии выборки логарифма сложности на стандартное нормальное распределение использовались для оценки значений параметров аппроксимирующего нормального распределения. Даны оценки границ 90% интервала сложности. ...
Добавлено: 30 марта 2017 г.
G. N. Zhukova, M. V. Ulyanov, M. I. Fomichev и др., Automation and Remote Control 2018 Vol. 79 No. 7 P. 1296-1310
Добавлено: 16 июля 2018 г.
Игнатов А. Д., Посыпкин М. А., Communications in Computer and Information Science 2018 P. 511-522
Добавлено: 18 октября 2019 г.
Фомичев М. И., Вестник Волжской государственной академии водного транспорта 2017 № 49 С. 68-78
Классический алгоритм, реализующий метод ветвей и границ для решения задачи коммивояжёра, предложенный в 1963 году Дж. Литл, К. Мурти, Д. Суини и К. Кэрол, остаётся по настоящее время самым востребованным алгоритмом при решении задачи нахождения гамильтонового цикла минимальной стоимости в полном графе. Существует много различных источников, в которых представлен псевдокод алгоритма с текстовыми комментариями. Однако ...
Добавлено: 19 августа 2017 г.
Игнатов А. Д., Andrei Gorchakov, Open Computer Science 2020 Vol. 10 No. 1 P. 112-116
Добавлено: 11 июня 2020 г.
Wien : DAAAM International Vienna, 2017
Использование облачных вычислений для обеспечения взаимодействия государства и граждан позволяет ускорить информационное взаимодействие, реализовать государственные услуги, снизить затраты на обеспечение такого взаимодействия, но в то же время это взаимодействие ставит важные вопросы о надежности облачного провайдера и безопасности взаимодействия. Поставщиками облака могут быть как государственные органы, так и частные организации. В случае, если Облачный провайдер ...
Добавлено: 1 февраля 2018 г.
Самодуров В. А., Корнилов В. В., Исаев Е. А., Вопросы оборонной техники. Серия 16: Технические средства противодействия терроризму 2016 № 7-8 С. 139-145
Делается обзор существующих облачных технологий. Рассматривается основные проблемы обеспечения их безопасности - технические и законодательные. Обсуждаются способы повышения безопасности облачных вычислений: выбор наиболее безопасной модели облачных вычислений, законодательные пути повышения безопасности облачных вычислений. ...
Добавлено: 16 октября 2016 г.
Пермь : Пермский государственный национальный исследовательский университет, 2018
В сборник включены статьи, относящиеся к следующим направлениям научной работы: моделирование и анализ процессов и систем; разработка, анализ и тестирование программных систем, методы и инструментальные средства разработки программных систем.
Представлены результаты выполнения проектов, поддержанных грантами РФФИ (проекты № 18-01-00359, № 18-37-00070) и научного фонда НИУ ВШЭ (проект № 17-05-0020).
Материалы сборника могут представлять интерес для научных работников, специалистов ...
Добавлено: 16 декабря 2018 г.
Силаков Д. В., Системный администратор 2018 № 6 С. 24-28
CentOS 7 вышел еще в 2014 году, однако многие системные администраторы не спешат на него переходить - благо выпуск обновлений для CentOS 6.x обещан до ноября 2020 года. Причин оставаться на предыдущей версии много, и не последнее место среди них занимает радикальность многих изменений, пришедших в релизе. ...
Добавлено: 19 октября 2018 г.
The paper examines the choice problem when the total number of observations and criteria is too large. There are many different procedures, which are used for decision-making process under multiple criteria; however, most of them cannot be applied to large datasets due to their computational complexity while others provide sufficient accuracy. To solve the problem, ...
Добавлено: 20 февраля 2020 г.
NY : IEEE Computer Society, 2018
WF-IoT 2018, the 4th IEEE World Forum on Internet of Things, is the premier IEEE Forum for the Internet of Things. It is where conference attendees, from around the globe - including research institutes, academia, industry and the public sector -- share their knowledge, expertise and experiences about IoT technologies, applications, economic impacts, and social ...
Добавлено: 14 февраля 2018 г.
Васильева Т. П., Мызникова Б. И., Русаков С. В., Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. Информатика. Телекоммуникации. Управление 2012 № 1(140) С. 73-79
Предложена модель, включающая описание двух взаимодействующих подсистем: «население» и «градообразующая база». Представлено построение матрицы вероятностей распределения потоков характеристик между отраслевыми блоками, а также матрицы вероятностей миграции населения между федеральными округами. Дана интерпретация результатов моделирования, полученных с помощью реальных статистических данных. ...
Добавлено: 10 марта 2015 г.
Хивинцев М. А., Акопов А. С., Бизнес-информатика 2013 № 3(25) С. 35-41
В статье представлен новый подход к решению многокритериальных оптимизационных задач большой размерности, реализуемых, в частности, в системах имитационного моделирования класса AnyLogic с помощью распределенных вычислений. Предложена новая концепция построения распределенной эволюционной сети, основанная на разбиении пространства искомых переменных на кластеры и присвоения каждому вычислительному элементу сети своего кластера, по которому осуществляется поиск промежуточных результатов с ...
Добавлено: 3 октября 2013 г.
Баранов П. А., Системы высокой доступности 2014 № 4 С. 94-98
При решении задачи создания IT-сервиса централизованного управления правами пользователей в организации группа менеджеров проекта оказывается перед необходимостью принятия ряда решений, которые влияют на ход всего IT-проекта в целом и во много предопределяют его успех. Указанные решения включают выбор автоматизируемых процессов по централизованному созданию, удалению, модификации учетных записей пользователей и согласованию предоставляемых прав доступа, формирование ролевой ...
Добавлено: 11 февраля 2015 г.
Серова Е. Г., Guryeva I., Khvatova T., International Journal of Technology and Human Interaction 2018
Добавлено: 15 марта 2018 г.