Оптимизация параметров полиномиального рандомизированного алгоритма для асимметричной задачи коммивояжера
Рассматривается асимметричная задача коммивояжера, в которой надо найти гамильтонов цикл с минимальной суммарной стоимостью дуг в полном ориентированном графе. Для решения данной задачи на основе алгоритма, построенного автором в статье «Полиномиальный рандомизированный алгоритм для задачи “Асимметр...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | Belarusian |
| Published: |
Belarusian State University
2024-07-01
|
| Series: | Журнал Белорусского государственного университета: Математика, информатика |
| Subjects: | |
| Online Access: | https://journals.bsu.by/index.php/mathematics/article/view/6327 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849737849972195328 |
|---|---|
| author | Максим Сергеевич Баркетов |
| author_facet | Максим Сергеевич Баркетов |
| author_sort | Максим Сергеевич Баркетов |
| collection | DOAJ |
| description | Рассматривается асимметричная задача коммивояжера, в которой надо найти гамильтонов цикл с минимальной суммарной стоимостью дуг в полном ориентированном графе. Для решения данной задачи на основе алгоритма, построенного автором в статье «Полиномиальный рандомизированный алгоритм для задачи “Асимметричный коммивояжер”» (Доклады Национальной академии наук Беларуси. 2022. Т. 66, № 5. С. 489 – 494), разработан новый параметризованный полиномиальный рандомизированный алгоритм. Его отличие состоит в другой параметризации. Однако основным результатом является препроцессинговый полиномиальный алгоритм линейного программирования для определения оптимальных параметров. |
| format | Article |
| id | doaj-art-aa1333f9c65c4c9f86c02bd9d6d5a4e5 |
| institution | DOAJ |
| issn | 2520-6508 2617-3956 |
| language | Belarusian |
| publishDate | 2024-07-01 |
| publisher | Belarusian State University |
| record_format | Article |
| series | Журнал Белорусского государственного университета: Математика, информатика |
| spelling | doaj-art-aa1333f9c65c4c9f86c02bd9d6d5a4e52025-08-20T03:06:48ZbelBelarusian State UniversityЖурнал Белорусского государственного университета: Математика, информатика2520-65082617-39562024-07-0121131186327Оптимизация параметров полиномиального рандомизированного алгоритма для асимметричной задачи коммивояжераМаксим Сергеевич Баркетов0Объединенный институт проблем информатики НАН Беларуси, ул. Сурганова, 6, 220012, г. Минск, БеларусьРассматривается асимметричная задача коммивояжера, в которой надо найти гамильтонов цикл с минимальной суммарной стоимостью дуг в полном ориентированном графе. Для решения данной задачи на основе алгоритма, построенного автором в статье «Полиномиальный рандомизированный алгоритм для задачи “Асимметричный коммивояжер”» (Доклады Национальной академии наук Беларуси. 2022. Т. 66, № 5. С. 489 – 494), разработан новый параметризованный полиномиальный рандомизированный алгоритм. Его отличие состоит в другой параметризации. Однако основным результатом является препроцессинговый полиномиальный алгоритм линейного программирования для определения оптимальных параметров.https://journals.bsu.by/index.php/mathematics/article/view/6327комбинаторная оптимизациятеория вероятностейрандомизированный алгоритмприближенный алгоритмзадача коммивояжера |
| spellingShingle | Максим Сергеевич Баркетов Оптимизация параметров полиномиального рандомизированного алгоритма для асимметричной задачи коммивояжера Журнал Белорусского государственного университета: Математика, информатика комбинаторная оптимизация теория вероятностей рандомизированный алгоритм приближенный алгоритм задача коммивояжера |
| title | Оптимизация параметров полиномиального рандомизированного алгоритма для асимметричной задачи коммивояжера |
| title_full | Оптимизация параметров полиномиального рандомизированного алгоритма для асимметричной задачи коммивояжера |
| title_fullStr | Оптимизация параметров полиномиального рандомизированного алгоритма для асимметричной задачи коммивояжера |
| title_full_unstemmed | Оптимизация параметров полиномиального рандомизированного алгоритма для асимметричной задачи коммивояжера |
| title_short | Оптимизация параметров полиномиального рандомизированного алгоритма для асимметричной задачи коммивояжера |
| title_sort | оптимизация параметров полиномиального рандомизированного алгоритма для асимметричной задачи коммивояжера |
| topic | комбинаторная оптимизация теория вероятностей рандомизированный алгоритм приближенный алгоритм задача коммивояжера |
| url | https://journals.bsu.by/index.php/mathematics/article/view/6327 |
| work_keys_str_mv | AT maksimsergeevičbarketov optimizaciâparametrovpolinomialʹnogorandomizirovannogoalgoritmadlâasimmetričnojzadačikommivoâžera |