К вопросу о нахождении значения маршрутной задачи с ограничениями
Розглянуто задачу послідовного обходу мегаполісів з обмеженнями різних типів. Вважається, що функції вартості, а також «поточні» обмеження можуть залежати від списку завдань (можлива залежність від списку виконаних або, навпаки, ще не виконаних завдань). Запропоновано підхід до визначення глобальног...
Gespeichert in:
| Veröffentlicht in: | Проблемы управления и информатики |
|---|---|
| Datum: | 2016 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/208063 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | К вопросу о нахождении значения маршрутной задачи с ограничениями / А.Г. Ченцов, А.А. Ченцов // Проблемы управления и информатики. — 2016. — № 1. — С. 41-54. — Бібліогр.: 17 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862734401495891968 |
|---|---|
| author | Ченцов, А.Г. Ченцов, А.А. |
| author_facet | Ченцов, А.Г. Ченцов, А.А. |
| citation_txt | К вопросу о нахождении значения маршрутной задачи с ограничениями / А.Г. Ченцов, А.А. Ченцов // Проблемы управления и информатики. — 2016. — № 1. — С. 41-54. — Бібліогр.: 17 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| 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).
|
| first_indexed | 2025-12-07T19:42:22Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-208063 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T19:42:22Z |
| publishDate | 2016 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| 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 |
| spellingShingle | К вопросу о нахождении значения маршрутной задачи с ограничениями Ченцов, А.Г. Ченцов, А.А. Оптимальное управление и методы оптимизации |
| title | К вопросу о нахождении значения маршрутной задачи с ограничениями |
| title_alt | До питання про знаходження значення маршрутної задачі з обмеженнями On the problem of obtaining the value of routing problem with constraints |
| title_full | К вопросу о нахождении значения маршрутной задачи с ограничениями |
| title_fullStr | К вопросу о нахождении значения маршрутной задачи с ограничениями |
| title_full_unstemmed | К вопросу о нахождении значения маршрутной задачи с ограничениями |
| title_short | К вопросу о нахождении значения маршрутной задачи с ограничениями |
| title_sort | к вопросу о нахождении значения маршрутной задачи с ограничениями |
| topic | Оптимальное управление и методы оптимизации |
| topic_facet | Оптимальное управление и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/208063 |
| 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 |