К вопросу о нахождении значения маршрутной задачи с ограничениями
Розглянуто задачу послідовного обходу мегаполісів з обмеженнями різних типів. Вважається, що функції вартості, а також «поточні» обмеження можуть залежати від списку завдань (можлива залежність від списку виконаних або, навпаки, ще не виконаних завдань). Запропоновано підхід до визначення глобальног...
Збережено в:
| Опубліковано в: : | Проблемы управления и информатики |
|---|---|
| Дата: | 2016 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/208063 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | К вопросу о нахождении значения маршрутной задачи с ограничениями / А.Г. Ченцов, А.А. Ченцов // Проблемы управления и информатики. — 2016. — № 1. — С. 41-54. — Бібліогр.: 17 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-208063 |
|---|---|
| record_format |
dspace |
| spelling |
Ченцов, А.Г. Ченцов, А.А. 2025-10-18T18:41:51Z 2016 К вопросу о нахождении значения маршрутной задачи с ограничениями / А.Г. Ченцов, А.А. Ченцов // Проблемы управления и информатики. — 2016. — № 1. — С. 41-54. — Бібліогр.: 17 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208063 519.6 10.1615/JAutomatInfScien.v48.i2.30 Розглянуто задачу послідовного обходу мегаполісів з обмеженнями різних типів. Вважається, що функції вартості, а також «поточні» обмеження можуть залежати від списку завдань (можлива залежність від списку виконаних або, навпаки, ще не виконаних завдань). Запропоновано підхід до визначення глобального екстремуму (значення задачі) на основі динамічного програмування в широкому сенсі. Завдяки такому підходу досягається економія пам’яті комп’ютера, що дозволяє визначати экстремум в задачі більшої розмірності та використовувати його для тестування евристичних алгоритмів. Для побудови шарів функції Беллмана використовується скорочена процедура, що дозволяє зменшити складність обчислювань (за умов передування не передбачається побудова всього масиву значень функції Беллмана). The problem of sequential travelling of megapolises with constraints of different types is considered. It is supposed that cost functions and «current» constraints can be dependent on the tasks list (it is possible that dependence on the fulfilled or nonfulfilled tasks arises). Approach to determination of global extremum (the problem value) on the basis of widely interpreted dynamic programming is proposed. Under given approach, economy of computer memory is reached; this permits to determine extremum in problem with larger dimensionality and use it for testing of heuristic algorithms. Under construction of layers of Bellman function, truncated procedure which enables one to decrease computing complexity is used (under preceding conditions, construction of all array of the Bellman function values is not provided). ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Оптимальное управление и методы оптимизации К вопросу о нахождении значения маршрутной задачи с ограничениями До питання про знаходження значення маршрутної задачі з обмеженнями On the problem of obtaining the value of routing problem with constraints Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
К вопросу о нахождении значения маршрутной задачи с ограничениями |
| spellingShingle |
К вопросу о нахождении значения маршрутной задачи с ограничениями Ченцов, А.Г. Ченцов, А.А. Оптимальное управление и методы оптимизации |
| title_short |
К вопросу о нахождении значения маршрутной задачи с ограничениями |
| title_full |
К вопросу о нахождении значения маршрутной задачи с ограничениями |
| title_fullStr |
К вопросу о нахождении значения маршрутной задачи с ограничениями |
| title_full_unstemmed |
К вопросу о нахождении значения маршрутной задачи с ограничениями |
| title_sort |
к вопросу о нахождении значения маршрутной задачи с ограничениями |
| author |
Ченцов, А.Г. Ченцов, А.А. |
| author_facet |
Ченцов, А.Г. Ченцов, А.А. |
| topic |
Оптимальное управление и методы оптимизации |
| topic_facet |
Оптимальное управление и методы оптимизации |
| publishDate |
2016 |
| language |
Russian |
| container_title |
Проблемы управления и информатики |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
До питання про знаходження значення маршрутної задачі з обмеженнями On the problem of obtaining the value of routing problem with constraints |
| description |
Розглянуто задачу послідовного обходу мегаполісів з обмеженнями різних типів. Вважається, що функції вартості, а також «поточні» обмеження можуть залежати від списку завдань (можлива залежність від списку виконаних або, навпаки, ще не виконаних завдань). Запропоновано підхід до визначення глобального екстремуму (значення задачі) на основі динамічного програмування в широкому сенсі. Завдяки такому підходу досягається економія пам’яті комп’ютера, що дозволяє визначати экстремум в задачі більшої розмірності та використовувати його для тестування евристичних алгоритмів. Для побудови шарів функції Беллмана використовується скорочена процедура, що дозволяє зменшити складність обчислювань (за умов передування не передбачається побудова всього масиву значень функції Беллмана).
The problem of sequential travelling of megapolises with constraints of different types is considered. It is supposed that cost functions and «current» constraints can be dependent on the tasks list (it is possible that dependence on the fulfilled or nonfulfilled tasks arises). Approach to determination of global extremum (the problem value) on the basis of widely interpreted dynamic programming is proposed. Under given approach, economy of computer memory is reached; this permits to determine extremum in problem with larger dimensionality and use it for testing of heuristic algorithms. Under construction of layers of Bellman function, truncated procedure which enables one to decrease computing complexity is used (under preceding conditions, construction of all array of the Bellman function values is not provided).
|
| issn |
0572-2691 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/208063 |
| citation_txt |
К вопросу о нахождении значения маршрутной задачи с ограничениями / А.Г. Ченцов, А.А. Ченцов // Проблемы управления и информатики. — 2016. — № 1. — С. 41-54. — Бібліогр.: 17 назв. — рос. |
| work_keys_str_mv |
AT čencovag kvoprosuonahoždeniiznačeniâmaršrutnoizadačisograničeniâmi AT čencovaa kvoprosuonahoždeniiznačeniâmaršrutnoizadačisograničeniâmi AT čencovag dopitannâproznahodžennâznačennâmaršrutnoízadačízobmežennâmi AT čencovaa dopitannâproznahodžennâznačennâmaršrutnoízadačízobmežennâmi AT čencovag ontheproblemofobtainingthevalueofroutingproblemwithconstraints AT čencovaa ontheproblemofobtainingthevalueofroutingproblemwithconstraints |
| first_indexed |
2025-12-07T19:42:22Z |
| last_indexed |
2025-12-07T19:42:22Z |
| _version_ |
1850879815511441408 |