?
Сравнение ресурсных характеристик традиционного и модифицированного метода ветвей и границ для TSP
Современные информационные технологии и ИТ-образование. 2015. Т. 2. № 11. С. 151–159.
Сравниваются ресурсные характеристики модифицированного и классического МВГ для TSP. На основании экспериментальных результатов показано, что по величине затраченного на поиск решения времени модифицированный вариант МВГ эффективнее классического. Исследована стохастическая зависимость между временем работы каждого из двух исследуемых вариантов МВГ при фиксированном порядке матрицы стоимостей. Также описана зависимость затраченной памяти и времени работы алгоритма от порядка матрицы стоимости.
Лола И. С., Информационное общество 2023 № 1 С. 109–115
В работе представлены оценки отраслевого уровня инвестирования в цифровые эко-технологии с помощью специально разработанного Индекса эко-инвестиций, а также исследованы тенденции текущего (2021 г.) и планируемого (на 2022 г.) использования цифровых технологий по отдельным направлениям повышения экологической и ресурсной эффективности на российских промышленных предприятиях. Согласно полученным результатам, в 2021 г. промышленными лидерами по инвестициям в цифровые ...
Добавлено: 29 августа 2022 г.
Игнатов А. Д., Andrei Gorchakov, Open Computer Science 2020 Vol. 10 No. 1 P. 112–116
Добавлено: 11 июня 2020 г.
Фомичев М. И., Системы управления и информационные технологии 2017 № 3 С. 88–92
Алгоритм, реализующий метод ветвей и границ для решения задачи коммивояжёра - один из самых востребованных точных алгоритмов её решения. Метаэвристические алгоритмы решения этой задачи не гарантируют точного решения, но работают «быстро». В данной статье рассматривается комбинация таких алгоритмов с методом ветвей и границ. ...
Добавлено: 23 марта 2020 г.
Фомичев М. И., Информационные технологии моделирования и управления 2018 Т. 109 № 1 С. 47–54
В современном мире промедление в секунду, или даже долю секунды, может стоить миллионы рублей. Заинтересованному лицу важно получить точный ответ на вопрос в кратчайшие сроки. Но, к сожалению, даже при ны- нешних вычислительных мощностях, многие задачи не могут быть решены точно за приемлемое время. ...
Добавлено: 22 марта 2020 г.
Головешкин В. А., Жукова Г. Н., Ульянов М. В. и др., Системы компьютерной математики и их приложения 2017 № 18 С. 136–138
В докладе рассматривается статистическая зависимость числа
порожденных вершин дерева решений и физического времени работы
программной реализации метода ветвей и границ для задачи
коммивояжера (TSP). На основе результатов вычислительного
эксперимента получено приближенное соотношение между числом
порожденных вершин (сложность индивидуальной TSP) и физическим
временем. Предлагается использовать это эмпирическое соотношение
для прогнозирования времени работы программы, решающей TSP с
числом «городов» больше 40. ...
Добавлено: 22 марта 2020 г.
Мищенко Александр Владимирович, Кошелев П. С., Прикладная информатика 2018 № 2 С. 5–21
В статье рассмотрены методы и программные средства оптимизации оптовых закупок. ...
Добавлено: 11 марта 2020 г.
Ульянов М. В., Фомичев М. И., Информационные технологии 2019 Т. 25 № 10 С. 590–595
Алгоритм, реализующий метод ветвей и границ, для решения задачи коммивояжера - один из востребованных точных алгоритмов ее решения. Метаэвристические алгоритмы решения этой задачи не гарантируют получения точного решения, но работают "быстро". Для сокращения числа вершин порожденного дерева решений в методе ветвей и границ можно использовать решение, полученное метаэвристическим алгоритмом. За счет выбора метаэвристического алгоритма и ...
Добавлено: 16 февраля 2020 г.
Фомичев М. И., Ульянов М. В., Информационные технологии 2018 Т. 24 № 11 С. 698–704
Повышение временной эффективности программных реализаций метода ветвей и границ для асимметричной задачи коммивояжера может быть достигнуто как за счет выбора наиболее приемлемой структуры данных, обеспечивающей эффективные по времени операции с листьями поискового дерева решений, так и за счет использования дополнительной памяти для хранения усеченных матриц в листьях поискового дерева решений. Дополнительно могут быть предложены и ...
Добавлено: 26 января 2020 г.
Жукова Г. Н., Ульянов М. В., Фомичев М. И., Automation and Remote Control 2019 Vol. 80 No. 11 P. 2054–2067
Добавлено: 24 ноября 2019 г.
Приведены результаты сравнительного статистического анализа времени решения несимметричной задачи коммивояжера (NTSP) методом ветвей и границ (без предвычисления тура) и комбинированным методом. Комбинированный метод состоит из приближенного алгоритма Lin- Kernighan-Helsgaun, используемого для вычисления начального тура, и метода ветвей и границ. Показано, что использование приближенного решения, найденного с помощью алгоритма Lin-Kernighan-Helsgaun, позволяет существенно уменьшить время поиска точного ...
Добавлено: 10 ноября 2019 г.
Игнатов А. Д., Посыпкин М. А., Communications in Computer and Information Science 2018 P. 511–522
Добавлено: 18 октября 2019 г.
Для практически значимых оптимизационных задач в области экономики и логистики, а также в ряде технических приложений возникает необходимость решения задачи коммивояжера (traveling salesman problem, TSP). Достаточно часто особенности этих задач приводят к задаче коммивояжера в асимметричной постановке (asymmetric traveling salesman problem, ATSP). Более того, в некоторых практических применениях желательно получение точного решения. Одним из известных ...
Добавлено: 11 декабря 2018 г.
Горчаков А. Ю., Посыпкин М. А., Современные информационные технологии и ИТ-образование 2018 Т. 14 № 1 С. 138–148
В последнее время основным способом повышения производительности вычислительных устройств стало увеличение числа вычислительных ядер в процессорах, в связи с чем, системы с общей памятью получили широкое распространение. Поэтому особую актуальность приобретает разработка параллельных приложений, ориентированных на системы с общей памятью. В статье рассматривается один из классов таких приложений – задача поиска глобального экстремума функций многих ...
Добавлено: 31 октября 2018 г.
Добавлено: 18 октября 2018 г.
В статье приведены результаты статистического исследования сложности несимметричной задачи коммивояжера (NTSP), полученные в результате обработки специального сгенерированного пула матриц. Основная цель - вероятностной прогноз сложности индивидуальных задач, для больших значений размерности матрицы стоимостей. Показано, что нормальное распределение удовлетворительно приближает распределение логарифма сложности при фиксированной размерности задачи. Построено семейство вероятностных распределений, являющихся удовлетворительными приближениями распределения сложности ...
Добавлено: 16 июля 2018 г.
G. N. Zhukova, M. V. Ulyanov, M. I. Fomichev и др., Automation and Remote Control 2018 Vol. 79 No. 7 P. 1296–1310
Добавлено: 16 июля 2018 г.
Береснева Е. Н., Горденко М. К., Открытые системы. СУБД 2018 № 01 С. 40–42
Едва научившись ходить, человек начал строить маршруты и сегодня задача прокладки оптимальных трасс актуальна для всех логистических предприятий, хотя ее точного решения до сих пор нет, а есть проблема выбора эвристического алгоритма. ...
Добавлено: 22 июня 2018 г.
Горденко М. К., Коротков Д. А., В кн.: Межвузовская научно-техническая конференция студентов, аспирантов и молодых специалистов им. Е.В. Арменского.: МИЭМ НИУ ВШЭ, 2018. С. 42–44.
В работе рассмотрен меметический алгоритм, являющий-ся комбинацией генетического алгоритма и алгоритмов ло-кального поиска решения ассиметричной задачи коммивоя-жера (A TSP). Приведена математическая постановка задачиA TSP . Кратко описан принцип работы меметического алгорит-ма. Проведено экспериментальное исследование временных и точностных характеристик меметического алгоритма на откры-той базе данных TSPLIB в зависимости от входных параметров с целью выявления оптимальных настроек алгоритма. ...
Добавлено: 5 июня 2018 г.