• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • Национальный исследовательский университет «Высшая школа экономики»
  • Публикации ВШЭ
  • Статьи
  • The Mixed Chinese Postman Problem
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Приоритетные направления
  • бизнес-информатика
  • государственное и муниципальное управление
  • гуманитарные науки
  • инженерные науки
  • компьютерно-математическое
  • математика
  • менеджмент
  • право
  • социология
  • экономика
по году
  • 2028
  • 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
  • еще
Тематика
Новости
30 сентября 2026 г.
Ученые НИУ ВШЭ - Санкт-Петербург нашли способ ускорения нейросетей при помощи микролазеров
Ученые Международной лаборатории квантовой оптоэлектроники НИУ ВШЭ — Санкт-Петербург и Лазерного института Академии наук Шаньдунь (Китай) смогли напрямую сопоставить скорость микродисковых лазеров, работающих от оптической и электрической энергии. Результаты позволят оптимизировать работу источников излучения в фотонных чипах для нейросетей и дата-центров. Исследование опубликовано в журналеJournal of Lightwave Technology.
30 сентября 2026 г.
ВШЭ создала веб-приложение для оценки эффекта биочар-проектов
Центр цифровых технологий для природно-климатических проектов НИУ ВШЭ разработал веб-приложение для предварительной оценки проектов по производству биочара из растительных остатков и его внесению в почву. Инструмент позволяет рассчитать потенциальный объем производства биочара и углеродных единиц, определить необходимую площадь сельскохозяйственных земель, оценить объем инвестиций и ожидаемый экономический эффект проекта.
30 сентября 2026 г.
«Нужно быть готовым отстаивать свою позицию перед более опытными исследователями»
Татьяна Багриновцева занялась нейробиологией, потому что интересовалась устройством человеческого мозга. В интервью проекту «Молодые ученые Вышки» она рассказала о новой методике маркировки нейронов, работе с клеточными культурами и о любимом месте в Самаре — городской набережной.

 

Нашли опечатку?
Выделите её, нажмите Ctrl+Enter и отправьте нам уведомление. Спасибо за участие!

Публикации
  • Книги
  • Статьи
  • Главы в книгах
  • Препринты
  • Верификация публикаций
  • Расширенный поиск
  • Правила использования материалов
  • Наука в ВШЭ

?

The Mixed Chinese Postman Problem

Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 107–122.
M.K. Gordenko, S.M. Avdoshin

Задачи маршрутизации важны для областей логистики и управления трансортом. Задачи маршрутизации в основном связаны с определением оптимального набора путей в мультиграфе. Задача китайского почтальона (CPP) является особым случаем задачи маршрутизации, имющим много потенциальных приложений. Мы предлагаем решение MCPP (специального NP-полного случая CPP на смешанном мультиграфе) с использованием редуцирования исходной задачи к обобщенной задаче коммивояжера (General Traveling Salesman Problem, GTSP). Указываются варианты CPP. Представлены математические формулировки некоторых проблем. Показан алгоритм редуцирования MCPP в мультиграфе к GTSP. Приводятся экспериментальные результаты решения MCPP в мультиграфе посредством редуцирования к GTSP.

Научное направление: Математика Компьютерные науки
Приоритетные направления: компьютерно-математическое
Язык: английский
Полный текст
DOI
Текст на другом сайте
Ключевые слова: задача коммивояжераTraveling Salesman Problemheuristic algorithmэвристический алгоритмMixed Chinese Postman ProblemArc Routing ProblemСмешанная задача китайского почтальонаЗадача маршрутизации дуг
Похожие публикации
Asymptotics of Spectrum and Quantum Averages of the Hydrogen Atom in a Magnetic Field Near the Upper Boundaries of Spectral Clusters
A. V. Pereskokov, Journal of Mathematical Sciences 2026 Vol. 302 No. 4 P. 531–545
Добавлено: 1 октября 2026 г.
Ensemble-based Prototype-Augmented Multimodal Fusion for Ambivalence/Hesitancy Recognition
Рюмина Е. В., Аксёнов А. А., Сысоев Д. С. и др., IEEE Computer Society, 2026.
Добавлено: 30 сентября 2026 г.
Simultaneous approximation of the score function and its derivatives by deep neural networks
Яковлев К. Д., Пучкин Н. А., Journal of Complexity 2026 Vol. 97
Добавлено: 30 сентября 2026 г.
Conservative Entropy and Energy Correct Difference Methods for One-Dimensional Quasi-Gasdynamic Systems of Equations
Злотник А. А., Mathematical notes 2026 Vol. 120 No. 6 P. 1005–1009
Добавлено: 30 сентября 2026 г.
О числе Пикара и размерности алгебраических однородных пространств
Бельдиев И. С., Тимашёв Д. А., Алгебра и анализ 2026 Т. 38 № 5 С. 1–10
Алгебраическое многообразие X называется однородным пространством, если на X существует транзитивное регулярное действие алгебраической группы. Мы доказываем неравенства, связывающие размерность однородного пространства линейной алгебраической группы и его число Пикара. ...
Добавлено: 30 сентября 2026 г.
Decoding Algorithms for Binary U-UV Codes: A Unified Survey of Performance and Complexity
Иванов Ф. И., Котов Ф. И., IEEE Access 2026 Vol. 14 P. 104662–104679
Добавлено: 30 сентября 2026 г.
An archaic reference-free method to jointly infer Neanderthal and Denisovan introgressed segments in modern human genomes,
Planche L., Ильина А. В., Jay F. и др., Molecular Biology and Evolution 2026 Article 235
Добавлено: 30 сентября 2026 г.
Uniqueness theorem for completely non-degenerate B-groups
Глуцюк А. А., Ильяшенко Ю. С., Izvestiya. Mathematics 2026 Vol. 90 No. 1 P. 73–89
Добавлено: 30 сентября 2026 г.
The EG-TD3 Machine Learning Architecture: Evolutionary-Guided Twin Delayed Deep Deterministic Policy Gradient
Джамбонг Тенке Х., Institute for System Programming of the RAS, 2026.
Добавлено: 29 сентября 2026 г.
Серия инвариантных характеристик реальных сетей
Тужилин М. А., Автоматика и телемеханика 2026 № 11 С. 84–97
Предлагается обобщение двух известных инвариантов реальных сетей: степени и кси-центральности. Строится серия центральностей, основанная на матрице Лапласа сети и параметризованная параметром j со следующими свойствами: во-первых, при j = 0, 1 эти центральности совпадают со степенью и ксицентральностью; во-вторых, их распределение хорошо приближается распределением Вейбулла; в-третьих, для реальных сетей они имеют правостороннюю асимметрию, а для ...
Добавлено: 29 сентября 2026 г.
Нетривиальное поведение пирамидальных уединенных волн в обобщенном уравнении Гарднера
Мельников И. Е., Пелиновский Е. Н., Доклады Российской академии наук. Физика, технические науки (ранее - Доклады Академии Наук. Физика) 2026 Т. 529 С. 29–36
Представлены условия для появления пирамидальных уединенных волн (уединенных волн, с количеством точек перегиба больше двух) в семействе обобщенного уравнения Кортевега – де Фриза (КдФ). Для обобщенного уравнения Гарднера показано, что пирамидальные солитоны неустойчивы. Продемонстрирован численно распад начальных возмущений, близких к пирамидальным уединенным волнам. В зависимости от возмущения пирамидальный солитон либо расщепляется на два солитона (толстый ...
Добавлено: 29 сентября 2026 г.
Pre-Calabi-Yau algebras and oriented gravity properad
Меркулов С. А., Journal of Pure and Applied Algebra 2026 Vol. 230 P. 1–19
Добавлено: 29 сентября 2026 г.
Нижние множества и свойства замкнутости классов функций подсчета
Иванашев Я. М., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2026 Т. 529 С. 93–101
Язык L является нижним для релятивизируемого сложностного класса C, если CL=C. Для классов #P, GapP и SpanP известны точные нижние классы языков: Low(#P) = UP ∩ coUP, Low(GapP) = SPP и Low(SpanP) = NP ∩ coNP. В этой статье мы доказываем, что Low(TotP) = P, и приводим характеризации нижних классов функций для #P, GapP, TotP ...
Добавлено: 28 сентября 2026 г.
Combinatorics on finite words and the length of a finite-dimensional associative algebra
Хрыстик М. А., European Journal of Combinatorics 2026 Vol. 136 P. 104393–104393
Добавлено: 28 сентября 2026 г.
Role of dislocations in the mobility of pinned helium bubbles: Molecular dynamics simulations in aluminum
Piliugin L., Antropov A., Lobashev E. и др., Journal of Nuclear Materials 2026 Vol. 632 Article 156876
Добавлено: 28 сентября 2026 г.
MPI+OpenMP implementation of resolution-of-the-identity Hartree-Fock method exploiting permutational symmetry of three-center electron repulsion integrals
Kashpurovich I., Oleynichenko A., Стегайлов В. В., Supercomputing Frontiers and Innovations 2026 Vol. 13 No. 1 P. 52–73
Добавлено: 28 сентября 2026 г.
A Three-Party W-State Quantum Secret Sharing Protocol with X-Gate Encoding and Forbidden-Outcome Detection
Терегулов Т. Р., Лубенец Е. Р., / Series Quantum Physics "arXiv". 2026. No. 2609.31472.
Добавлено: 28 сентября 2026 г.
Bytedance и Open Source - открытые проекты от разработчика TikTok
Силаков Д. В., Системный администратор 2026 С. 84–89
Пользователи социальных сетей редко задумываются о том, что стоит за красивым фасадом с лентами активностей, пестрящими фотографиями и видеоисториями. Однако массовое увлечение подобными платформами порождает огромное количество всевозможного контента, который надо хранить, оперативно обрабатывать и отображать, а в эру ИИ — еще и активно помогать в его создании и адаптации. Неудивительно, что последние десятилетия разработчики ведущих социальных сетей стабильно являются поставщиками инфраструктурных программных продуктов, многие из которых распространяются ...
Добавлено: 28 сентября 2026 г.
Shape-aware deep learning for models of production
Prokhorov A., Wei Z., Sang H. и др., Journal of Productivity Analysis 2026 Vol. 65 P. 1–16
Добавлено: 28 сентября 2026 г.
On calibration of remote sensing retrievals of ecosystem respiration (Reco) with tower measurements over,Russian forests and wetlands
Shabanov N., Kuricheva O., Kurbatova J. и др., / Series Working Papers SSRN "Department of Economics Ca’ Foscari University of Venice". 2026.
Добавлено: 21 августа 2026 г.
Three Algorithms for Merging Hierarchical Navigable Small World Graphs
Пономаренко А. А., / Series Computer Science "arxiv.org". 2025.
Добавлено: 30 июля 2026 г.
Growth in noncommutative algebras and entropy in derived categories
Пионтковский Д. И., / Series arXiv "math". 2026.
Добавлено: 23 июня 2026 г.
Multilinear nilalgebras and the Jacobian theorem
Пионтковский Д. И., / Series arXiv "math". 2025.
Добавлено: 23 июня 2026 г.
ML-based Fast Simulation of FARICH Responses
Шипилов Ф. А., Barnyakov A., Ivanov A. и др., / Series Physics "arxiv.org". 2026.
Добавлено: 19 мая 2026 г.
  • О ВЫШКЕ
  • Цифры и факты
  • Руководство и структура
  • Устойчивое развитие в НИУ ВШЭ
  • Преподаватели и сотрудники
  • Корпуса и общежития
  • Закупки
  • Обращения граждан в НИУ ВШЭ
  • Фонд целевого капитала
  • Противодействие коррупции
  • Сведения о доходах, расходах, об имуществе и обязательствах имущественного характера
  • Сведения об образовательной организации
  • Людям с ограниченными возможностями здоровья
  • Единая платежная страница
  • Работа в Вышке
  • ОБРАЗОВАНИЕ
  • Лицей
  • Довузовская подготовка
  • Олимпиады
  • Прием в бакалавриат
  • Вышка+
  • Прием в магистратуру
  • Аспирантура
  • Дополнительное образование
  • Центр развития карьеры
  • Бизнес-инкубатор ВШЭ
  • Образовательные партнерства
  • Обратная связь и взаимодействие с получателями услуг
  • НАУКА
  • Научные подразделения
  • Исследовательские проекты
  • Мониторинги
  • Диссертационные советы
  • Защиты диссертаций
  • Академическое развитие
  • Конкурсы и гранты
  • Внешние научно-информационные ресурсы
  • РЕСУРСЫ
  • Библиотека
  • Издательский дом ВШЭ
  • Книжный магазин «БукВышка»
  • Типография
  • Медиацентр
  • Журналы ВШЭ
  • Публикации
  • http://www.minobrnauki.gov.ru/
    Министерство науки и высшего образования РФ
  • https://edu.gov.ru/
    Министерство просвещения РФ
  • https://elearning.hse.ru/mooc
    Массовые открытые онлайн-курсы
  • НИУ ВШЭ1993–2026
  • Адреса и контакты
  • Условия использования материалов
  • Политика обработки персональных данных
  • Правила применения рекомендательных технологий в НИУ ВШЭ
  • Карта сайта
Редактору