• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • Сравнение ресурсных характеристик традиционного и модифицированного метода ветвей и границ для TSP
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
July 8, 2026
HSE Researchers Discover Who Eats Out in Russia-And Why
Around one-third of Russians (31.3%) rarely eat out or buy ready-made meals. The core group of active consumers—those who eat out or purchase prepared food almost every day or several times a week—accounts for only about 9% of the population. These are the findings of a study conducted by the HSE Institute for Social Policy. According to the researchers eating out is no longer a marker of high social status in Russia.
July 8, 2026
HSE University and RREDA Join Forces to Support 2026 Renewable Energy of the Planet Competition
HSE University and the Russia Renewable Energy Development Association (RREDA) have signed a partnership and information cooperation agreement to support Renewable Energy of the Planet—2026, a national competition with international participation for students and early-career researchers. Applications are open on the competition's website until September 20, 2026.
July 6, 2026
Ancient Craniiform Brachiopod: A Newly Discovered Species with a Unique Shell Shape and Lifestyle
Scientists from HSE University, MSU, and Tallinn University of Technology have studied a fossil species of ancient brachiopods that lived in a warm sea in what is now northern Estonia more than 445 million years ago. These ancient brachiopods developed a cup-shaped shell with a protective 'cap' that shielded them from overgrowth by other marine organisms. The study has been published in Palaeogeography, Palaeoclimatology, Palaeoecology.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Сравнение ресурсных характеристик традиционного и модифицированного метода ветвей и границ для TSP

Современные информационные технологии и ИТ-образование. 2015. Т. 2. № 11. С. 151–159.
Головешкин В. А., Zhukova G., Ulyanov M., Fomichev M.
Language: Russian
Full text
Text on another site
Keywords: ресурсная эффективностьметод ветвей и границзадача коммивояжеравремя работы алгоритма
Similar publications
Тенденции технологической экологизации промышленности: тренды и точки роста
Lola I. S., Информационное общество 2023 № 1 С. 109–115
В работе представлены оценки отраслевого уровня инвестирования в цифровые эко-технологии с помощью специально разработанного Индекса эко-инвестиций, а также исследованы тенденции текущего (2021 г.) и планируемого (на 2022 г.) использования цифровых технологий по отдельным направлениям повышения экологической и ресурсной эффективности на российских промышленных предприятиях. Согласно полученным результатам, в 2021 г. промышленными лидерами по инвестициям в цифровые ...
Added: August 29, 2022
Tool for Simulating Branch and Bound Computations
Ignatov A., Andrei Gorchakov, Open Computer Science 2020 Vol. 10 No. 1 P. 112–116
The paper describes a simulator of parallel Branch and Bound (BnB) method. Several subdomain trees for benchmark functions are analyzed, a characteristic Gaussian-like distribution is discovered. An algorithm of artificial tree generation is formulated according to this criterion. The process of simulator modeling is described, several computational experiments are conducted. Their results show a hyperbolic ...
Added: June 11, 2020
Сравнительный анализ метаэвристических алгоритмов решения несимметричной задачи коммивояжёра
Fomichev M., Системы управления и информационные технологии 2017 № 3 С. 88–92
Branch-and-bound algorithm for solving Traveling Salesman Problem is one of the most applied accurate algorithms to solve it. Metaheuristic algorithms for solving asymmetric Traveling Salesman Problem do not assure finding optimal solution, although they work “fast”. The combination of such algorithms with the branch-and-bound algorithm is analyzed in this article. ...
Added: March 23, 2020
Интеграция метаэвристических алгоритмов решения несимметричной задачи коммивояжёра с методом ветвей и границ
Fomichev M., Информационные технологии моделирования и управления 2018 Т. 109 № 1 С. 47–54
В современном мире промедление в секунду, или даже долю секунды, может стоить миллионы рублей. Заинтересованному лицу важно получить точный ответ на вопрос в кратчайшие сроки. Но, к сожалению, даже при ны- нешних вычислительных мощностях, многие задачи не могут быть решены точно за приемлемое время. ...
Added: March 22, 2020
Коррeляция сложности и времени решения TSP
Головешкин В. А., Zhukova G., Ulyanov M. et al., Системы компьютерной математики и их приложения 2017 № 18 С. 136–138
В докладе рассматривается статистическая зависимость числа порожденных вершин дерева решений и физического времени работы программной реализации метода ветвей и границ для задачи коммивояжера (TSP). На основе результатов вычислительного эксперимента получено приближенное соотношение между числом  порожденных вершин (сложность индивидуальной TSP) и физическим временем. Предлагается использовать это эмпирическое соотношение для прогнозирования времени работы программы, решающей TSP с числом «городов» больше 40. ...
Added: March 22, 2020
Разработка программного средства для поиска оптимального портфеля оптовых закупок торгового предприятия
Мищенко Александр Владимирович, Кошелев П. С., Прикладная информатика 2018 № 2 С. 5–21
В статье рассмотрены методы и программные средства оптимизации оптовых закупок. ...
Added: March 11, 2020
Сравнительный анализ комбинаций метода ветвей и границ с метаэвристическими алгоритмами для решения асимметричной задачи коммивояжёра
Ulyanov M., Fomichev M., Информационные технологии 2019 Т. 25 № 10 С. 590–595
The algorithm that implements the Branch and Bound method for solving the Traveling Salesman Problem is one of the common exact algorithms for solving it. Metaheuristic algorithms for solving this problem do not guarantee obtaining an exact solution, however they work "quickly". In order to reduce the nodes number of the generated decision tree in ...
Added: February 16, 2020
Подходы к организации поискового дерева решений в методе ветвей и границ для асимметричной задачи коммивояжера
Fomichev M., Ulyanov M., Информационные технологии 2018 Т. 24 № 11 С. 698–704
Повышение временной эффективности программных реализаций метода ветвей и границ для асимметричной задачи коммивояжера может быть достигнуто как за счет выбора наиболее приемлемой структуры данных, обеспечивающей эффективные по времени операции с листьями поискового дерева решений, так и за счет использования дополнительной памяти для хранения усеченных матриц в листьях поискового дерева решений. Дополнительно могут быть предложены и ...
Added: January 26, 2020
A Hybrid Exact Algorithm for the Asymmetric Traveling Salesman Problem: Construction and a Statistical Study of Computational Efficiency
Zhukova G., Ulyanov M., Fomichev M., Automation and Remote Control 2019 Vol. 80 No. 11 P. 2054–2067
We present the results of a comparative statistical analysis of the time for solving the asymmetric traveling salesman problem (ATSP) with the branch-and-bound method (without precalculation of the tour) and with a hybrid method. The hybrid method consists of the Lin–Kernighan–Helsgaun approximate algorithm used to calculate the initial tour and the branch-and-bound method. We show ...
Added: November 24, 2019
Комбинированный точный алгоритм для асимметричной задачи коммивояжера: построение и статистическое исследование временной эффективности
Zhukova G., Ulyanov M., Fomichev M., Автоматика и телемеханика 2019 № 11 С. 155–172
We present the results of a comparative statistical analysis of the time for solving the asymmetric traveling salesman problem (ATSP) with the branch-and-bound method (without precalculation of the tour) and with a hybrid method. The hybrid method consists of the Lin-Kernighan-Helsgaun approximate algorithm used to calculate the initial tour and the branch-and-bound method. We show ...
Added: November 10, 2019
BOINC-based Branch-and-Bound
Ignatov A., Posypkin M., Communications in Computer and Information Science 2018 P. 511–522
The paper proposes an implementation of the Branch-and-Bound method for an enterprise grid based on the BOINC infrastructure. The load distribution strategy and the overall structure of the developed system are described with special attention payed to some specific issues such as incumbent updating and load distribution. The implemented system was experimentally tested on a ...
Added: October 18, 2019
Эффективный по времени точный комбинированный алгоритм для асимметричной задачи коммивояжера
Zhukova G., Ulyanov M., Fomichev M., Бизнес-информатика 2018 Т. 45 № 3 С. 20–28
For practical, important tasks in the fi elds of economics and logistics, as well as in a number of technical applications, it becomes necessary to solve the traveling salesman problem (TSP). Quite often, the features of these problems lead to the traveling salesman problem in asymmetric formulation (asymmetric traveling salesman problem, ATSP). Moreover, in some ...
Added: December 11, 2018
СРАВНЕНИЕ ВАРИАНТОВ МНОГОПОТОЧНОЙ РЕАЛИЗАЦИИ МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ МНОГОЯДЕРНЫХ СИСТЕМ
Gorchakov A., Posypkin M., Современные информационные технологии и ИТ-образование 2018 Т. 14 № 1 С. 138–148
В последнее время основным способом повышения производительности вычислительных устройств стало увеличение числа вычислительных ядер в процессорах, в связи с чем, системы с общей памятью получили широкое распространение. Поэтому особую актуальность приобретает разработка параллельных приложений, ориентированных на системы с общей памятью. В статье рассматривается один из классов таких приложений – задача поиска глобального экстремума функций многих ...
Added: October 31, 2018
Exact time-efficient combined algorithm for solving the asymmetric traveling salesman problem
Zhukova G., Ulyanov M., Fomichev M., Business Informatics 2018 Vol. 45 No. 3 P. 20–28
For practical, important tasks in the fi elds of economics and logistics, as well as in a number of technical applications, it becomes necessary to solve the traveling salesman problem (TSP). Quite often, the features of these problems lead to the traveling salesman problem in asymmetric formulation (asymmetric traveling salesman problem, ATSP). Moreover, in some practical applications it ...
Added: October 18, 2018
Вероятностный прогноз сложности индивидуальных задач коммивояжера на основе идентификации распределения сложности по экспериментальным данным // Автоматика и телемеханика
Ulyanov M., Zhukova G., Fomichev M. et al., Автоматика и телемеханика 2018 № 7 С. 149–166
We show the results of a statistical study of the complexity of the asymmetric traveling salesman problem (ATSP) obtained by processing a specially generated pool of matrices. We show that the normal distribution can serve as an approximation to the distribution of the logarithm of complexity for a fixed problem dimension. We construct a family ...
Added: July 16, 2018
Probabilistic Prediction of the Complexity of Traveling Salesman Problems Based on Approximating the Complexity Distribution from Experimental Data
G. N. Zhukova, M. V. Ulyanov, M. I. Fomichev et al., Automation and Remote Control 2018 Vol. 79 No. 7 P. 1296–1310
We show the results of a statistical study of the complexity of the asymmetric traveling salesman problem (ATSP) obtained by processing a specially generated pool of matrices. We show that the normal distribution can serve as an approximation to the distribution of the logarithm of complexity for a fixed problem dimension. We construct a family ...
Added: July 16, 2018
Куда послать коммивояжера?
Beresneva E., Gordenko M., Открытые системы. СУБД 2018 № 01 С. 40–42
Едва научившись ходить, человек начал строить маршруты и сегодня задача прокладки оптимальных трасс актуальна для всех логистических предприятий, хотя ее точного решения до сих пор нет, а есть проблема выбора эвристического алгоритма. ...
Added: June 22, 2018
Экспериментальное исследование временных и точностных характеристик меметического алгоритма решения ассиметричной задачи коммивояжера в зависимости от входных параметров алгоритма
Gordenko M., Коротков Д. А., В кн.: Межвузовская научно-техническая конференция студентов, аспирантов и молодых специалистов им. Е.В. Арменского.: МИЭМ НИУ ВШЭ, 2018. С. 42–44.
В работе рассмотрен меметический алгоритм, являющий-ся комбинацией генетического алгоритма и алгоритмов ло-кального поиска решения ассиметричной задачи коммивоя-жера (A TSP). Приведена математическая постановка задачиA TSP . Кратко описан принцип работы меметического алгорит-ма. Проведено экспериментальное исследование временных и точностных характеристик меметического алгоритма на откры-той базе данных TSPLIB в зависимости от входных параметров с целью выявления оптимальных настроек алгоритма. ...
Added: June 5, 2018
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit