NP-трудность задач оптимизации коллективного преследования
Рассмотрены игры преследования на плоскости с простым движением, в которых принимают участие несколько преследователей и убегающих. Для захвата целей множество преследователей разбивается на группы, причем для каждого убегающего создается одна группа. В качестве критерия используется время захвата....
Saved in:
| Published in: | Проблеми програмування |
|---|---|
| Date: | 2014 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут програмних систем НАН України
2014
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/113212 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | NP-трудность задач оптимизации коллективного преследования / С.В. Пашко // Проблеми програмування. — 2014. — № 2-3. — С. 44-51. — Бібліогр.: 14 назв. — рос. |
Institution
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 |