NP-трудность задач оптимизации коллективного преследования
Рассмотрены игры преследования на плоскости с простым движением, в которых принимают участие несколько преследователей и убегающих. Для захвата целей множество преследователей разбивается на группы, причем для каждого убегающего создается одна группа. В качестве критерия используется время захвата....
Збережено в:
| Опубліковано в: : | Проблеми програмування |
|---|---|
| Дата: | 2014 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут програмних систем НАН України
2014
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/113212 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | NP-трудность задач оптимизации коллективного преследования / С.В. Пашко // Проблеми програмування. — 2014. — № 2-3. — С. 44-51. — Бібліогр.: 14 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862596686863400960 |
|---|---|
| author | Пашко, С.В. |
| author_facet | Пашко, С.В. |
| citation_txt | NP-трудность задач оптимизации коллективного преследования / С.В. Пашко // Проблеми програмування. — 2014. — № 2-3. — С. 44-51. — Бібліогр.: 14 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблеми програмування |
| description | Рассмотрены игры преследования на плоскости с простым движением, в которых принимают участие несколько преследователей и убегающих. Для захвата целей множество преследователей разбивается на группы, причем для каждого убегающего создается одна группа. В качестве критерия используется время захвата. Доказаны теоремы о NP-трудности задач оптимизации групп преследования. Приведены результаты численных экспериментов для соответствующих версий метода ветвей и границ и метода случайного поиска с локальной оптимизацией.
The differential pursuitevasion games on a plane are considered. A group of pursuers is created for every evader in a game. The optimization problem of group composition has been formulated. The theorems about NP-completeness and NP-hardness of pursuit optimization problems are proved. Numerical methods for solving such optimization problems are constructed. Numerical experiments have demonstrated high efficiency of the methods.
|
| first_indexed | 2025-11-27T15:36:07Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-113212 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Russian |
| last_indexed | 2025-11-27T15:36:07Z |
| publishDate | 2014 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Пашко, С.В. 2017-02-04T17:33:31Z 2017-02-04T17:33:31Z 2014 NP-трудность задач оптимизации коллективного преследования / С.В. Пашко // Проблеми програмування. — 2014. — № 2-3. — С. 44-51. — Бібліогр.: 14 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/113212 518.9 Рассмотрены игры преследования на плоскости с простым движением, в которых принимают участие несколько преследователей и убегающих. Для захвата целей множество преследователей разбивается на группы, причем для каждого убегающего создается одна группа. В качестве критерия используется время захвата. Доказаны теоремы о NP-трудности задач оптимизации групп преследования. Приведены результаты численных экспериментов для соответствующих версий метода ветвей и границ и метода случайного поиска с локальной оптимизацией. The differential pursuitevasion games on a plane are considered. A group of pursuers is created for every evader in a game. The optimization problem of group composition has been formulated. The theorems about NP-completeness and NP-hardness of pursuit optimization problems are proved. Numerical methods for solving such optimization problems are constructed. Numerical experiments have demonstrated high efficiency of the methods. ru Інститут програмних систем НАН України Проблеми програмування Теоретичні та методологічні основи програмування NP-трудность задач оптимизации коллективного преследования NP-hardness of collective pursuiting optimization problems Article published earlier |
| spellingShingle | NP-трудность задач оптимизации коллективного преследования Пашко, С.В. Теоретичні та методологічні основи програмування |
| title | NP-трудность задач оптимизации коллективного преследования |
| title_alt | NP-hardness of collective pursuiting optimization problems |
| title_full | NP-трудность задач оптимизации коллективного преследования |
| title_fullStr | NP-трудность задач оптимизации коллективного преследования |
| title_full_unstemmed | NP-трудность задач оптимизации коллективного преследования |
| title_short | NP-трудность задач оптимизации коллективного преследования |
| title_sort | np-трудность задач оптимизации коллективного преследования |
| topic | Теоретичні та методологічні основи програмування |
| topic_facet | Теоретичні та методологічні основи програмування |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/113212 |
| work_keys_str_mv | AT paškosv nptrudnostʹzadačoptimizaciikollektivnogopresledovaniâ AT paškosv nphardnessofcollectivepursuitingoptimizationproblems |