NP-трудность задач оптимизации коллективного преследования
Рассмотрены игры преследования на плоскости с простым движением, в которых принимают участие несколько преследователей и убегающих. Для захвата целей множество преследователей разбивается на группы, причем для каждого убегающего создается одна группа. В качестве критерия используется время захвата....
Gespeichert in:
| Veröffentlicht in: | Проблеми програмування |
|---|---|
| Datum: | 2014 |
| ISSN: | 1727-4907 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут програмних систем НАН України
2014
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/113212 |
| 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: | 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 |