• 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 2, 2026
Researchers Discover How Spelling Errors Slow Down Reading in Russian
Psycholinguists from the Centre for Language and Brain at HSE University–St Petersburg have shown that words that are frequently misspelled are processed more slowly by readers, even when presented with the correct spelling. The researchers confirmed this effect for the first time using Russian-language materials and found that response speed is most strongly linked to how confidently individuals can distinguish the correct spelling of a word from an incorrect one. The study has been published in The Mental Lexicon.
July 2, 2026
HSE Develops App for Assessing Phonological Processing in Children
Researchers at the HSE Centre for Language and Brain have developed a new digital tool for assessing children's phonological processing skills—the ZARYA (Sound Analysis of the Russian Language) test battery. It is the first standardised application in Russia designed to provide a fast and reliable assessment of children's ability to distinguish speech sounds, retain them in working memory, and perform phonemic analysis. The app runs on Android tablets and smartphones and is available for download from RuStore. Details of the test validation have been published in the Journal of Speech, Language, and Hearing Research.
July 1, 2026
Scientists Discover Why Europium 'Misbehaves'
Europium is a rare-earth metal responsible for the pure red glow in displays and other luminescent materials. For a long time, however, it refused to emit light when surrounded by certain organic molecules known as acylpyrazolone ligands. Chemists have now uncovered the reason: in europium complexes with these ligands, a 'black window' appears—a charge-transfer state in which the energy absorbed by the ligand is dissipated as heat rather than emitted as light. Understanding this mechanism opens the way to designing more efficient red-emitting materials for displays, fluorescent thermometers, and chemical sensors. The results have been published in Dalton Transactions.

 

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