О решении игровой задачи динамического коммивояжера

Досліджено ігрову задачу почергового зближення при простих рухах гравців. Критерієм якості є сумарний час упіймання переслідувачем кожного з групи втікачів. Вважається, що переслідувач в своїх діях керується законом паралельного переслідування. Тоді оптимальною відповіддю втікачів буде прямолінійний...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2010
Hauptverfasser:	Белоусов, А.А., Бердышев, Ю.И., Ченцов, А.Г., Чикрий, А.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2010
Schriftenreihe:	Кибернетика и системный анализ
Schlagworte:	Системный анализ
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/45623
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:	О решении игровой задачи динамического коммивояжера / А.А. Белоусов, Ю.И. Бердышев, А.Г. Ченцов, А.А. Чикрий // Кибернетика и системный анализ. — 2010. — № 5. — С. 40-45. — Бібліогр.: 21 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-45623
record_format	dspace
spelling	irk-123456789-456232013-06-17T03:12:54Z О решении игровой задачи динамического коммивояжера Белоусов, А.А. Бердышев, Ю.И. Ченцов, А.Г. Чикрий, А.А. Системный анализ Досліджено ігрову задачу почергового зближення при простих рухах гравців. Критерієм якості є сумарний час упіймання переслідувачем кожного з групи втікачів. Вважається, що переслідувач в своїх діях керується законом паралельного переслідування. Тоді оптимальною відповіддю втікачів буде прямолінійний рух з максимальною швидкістю. Це дає можливість звести початкову нескінченно-вимірну задачу оптимізації до двох скінченновимірних. The game problem of alternate capture of a team of evaders by a single pursuer under conditions of “simple motions” of the players. The performance criterion is the total time of alternate capture of all evaders. It is assumed that the pursuer sticks to the “Parallel Pursuit Law”. In such a case, the optimal response of the evaders is the straightforward motion with maximum velocity. The original infinite-dimensional problem can therefore be reduced to two finite-dimensional problems. 2010 Article О решении игровой задачи динамического коммивояжера / А.А. Белоусов, Ю.И. Бердышев, А.Г. Ченцов, А.А. Чикрий // Кибернетика и системный анализ. — 2010. — № 5. — С. 40-45. — Бібліогр.: 21 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/45623 518.9 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Системный анализ Системный анализ
spellingShingle	Системный анализ Системный анализ Белоусов, А.А. Бердышев, Ю.И. Ченцов, А.Г. Чикрий, А.А. О решении игровой задачи динамического коммивояжера Кибернетика и системный анализ
description	Досліджено ігрову задачу почергового зближення при простих рухах гравців. Критерієм якості є сумарний час упіймання переслідувачем кожного з групи втікачів. Вважається, що переслідувач в своїх діях керується законом паралельного переслідування. Тоді оптимальною відповіддю втікачів буде прямолінійний рух з максимальною швидкістю. Це дає можливість звести початкову нескінченно-вимірну задачу оптимізації до двох скінченновимірних.
format	Article
author	Белоусов, А.А. Бердышев, Ю.И. Ченцов, А.Г. Чикрий, А.А.
author_facet	Белоусов, А.А. Бердышев, Ю.И. Ченцов, А.Г. Чикрий, А.А.
author_sort	Белоусов, А.А.
title	О решении игровой задачи динамического коммивояжера
title_short	О решении игровой задачи динамического коммивояжера
title_full	О решении игровой задачи динамического коммивояжера
title_fullStr	О решении игровой задачи динамического коммивояжера
title_full_unstemmed	О решении игровой задачи динамического коммивояжера
title_sort	о решении игровой задачи динамического коммивояжера
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2010
topic_facet	Системный анализ
url	http://dspace.nbuv.gov.ua/handle/123456789/45623
citation_txt	О решении игровой задачи динамического коммивояжера / А.А. Белоусов, Ю.И. Бердышев, А.Г. Ченцов, А.А. Чикрий // Кибернетика и системный анализ. — 2010. — № 5. — С. 40-45. — Бібліогр.: 21 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT belousovaa orešeniiigrovojzadačidinamičeskogokommivoâžera AT berdyševûi orešeniiigrovojzadačidinamičeskogokommivoâžera AT čencovag orešeniiigrovojzadačidinamičeskogokommivoâžera AT čikrijaa orešeniiigrovojzadačidinamičeskogokommivoâžera
first_indexed	2025-07-04T04:26:55Z
last_indexed	2025-07-04T04:26:55Z
_version_	1836689094121357312
fulltext	ÓÄÊ 518.9 À.À. ÁÅËÎÓÑÎÂ, Þ.È. ÁÅÐÄÛØÅÂ, À.Ã. ×ÅÍÖÎÂ, À.À. ×ÈÊÐÈÉ Î ÐÅØÅÍÈÈ ÈÃÐÎÂÎÉ ÇÀÄÀ×È ÄÈÍÀÌÈ×ÅÑÊÎÃÎ ÊÎÌÌÈÂÎßÆÅÐÀ Êëþ÷åâûå ñëîâà: äèôôåðåíöèàëüíàÿ èãðà, èãðà ñî ìíîãèìè óáåãàþùèìè, ïîðÿ- äîê ïîèìêè, ïàðàëëåëüíîå ïðåñëåäîâàíèå. ÂÂÅÄÅÍÈÅ Â òåîðèè äèôôåðåíöèàëüíûõ èãð ñóùåñòâóåò ðÿä ôîðìàëèçàöèé, îïðåäåëÿþùèõ ïðîöåäóðó ïîñòðîåíèÿ îïòèìàëüíûõ ñòðàòåãèé èãðîêîâ [1–5]. Ââèäó áîëüøîé ñëîæ- íîñòè èãðîâûõ çàäà÷ ÷àñòî îãðàíè÷èâàþòñÿ äîñòàòî÷íûìè óñëîâèÿìè ðàçðåøèìîñòè, èíà÷å ãîâîðÿ, ïîëó÷åíèåì íåêîòîðîãî ãàðàíòèðîâàííîãî ðåçóëüòàòà. Äëÿ èññëåäîâà- íèÿ öåíòðàëüíûõ â ýòîé îáëàñòè ïðîáëåì ïðåñëåäîâàíèÿ–óáåãàíèÿ «îäèí íà îäèí» ðàçðàáîòàí ðÿä ýôôåêòèâíûõ ìåòîäîâ, ïîçâîëÿþùèõ ðåøàòü øèðîêèé êðóã çà- äà÷ [1–3]. Åñòåñòâåííûì îáîáùåíèåì ýòîãî ñïåêòðà ïðîáëåì ñòàëè çàäà÷è ïðåñëåäî- âàíèÿ–óáåãàíèÿ ñ ãðóïïàìè ó÷àñòíèêîâ ñ òîé èëè äðóãîé ñòîðîíû, òàê íàçûâàåìûå çàäà÷è ãðóïïîâîãî èëè ïîî÷åðåäíîãî ïðåñëåäîâàíèÿ è óáåãàíèÿ îò ãðóïïû. Èññëå- äîâàíèå èãðîâûõ çàäà÷ íà÷àëîñü â ñåðåäèíå 70-õ ãîäîâ ÕÕ ñò. Ðåçóëüòàòû ïî ãðóï- ïîâîìó ïðåñëåäîâàíèþ ñîäåðæàòñÿ â ðàáîòàõ [1, 6–8], ïî óáåãàíèþ — â [4, 9]. Â äàííîé ñòàòüå ðàññìàòðèâàåòñÿ çàäà÷à ïîî÷åðåäíîãî ïðåñëåäîâàíèÿ (èãðîâàÿ çàäà÷à äèíàìè÷åñêîãî êîììèâîÿæåðà), â êîòîðîé êðèòåðèåì êà÷åñòâà ÿâëÿåòñÿ ñóì- ìàðíîå âðåìÿ ïîèìêè âñåõ óáåãàþùèõ. Çàäà÷à ñîñòîèò èç äâóõ íåðàçðûâíî ñâÿçàí- íûõ ÷àñòåé: ïåðåáîðíîé — äëÿ îïðåäåëåíèÿ ïîðÿäêà ïîèìêè è íåïîñðåäñòâåííîãî ïðåñëåäîâàíèÿ ïðè çàäàííîì ïîðÿäêå îáñëóæèâàíèÿ. Ïåðâàÿ èç íèõ îòíîñèòñÿ ê ïðîáëåìå öåëåðàñïðåäåëåíèÿ, õîðîøî èçâåñòíîé ïðîåêòèðîâùèêàì ðàêåòíîé è êîñìè÷åñêîé òåõíèêè, è ïðåäñòàâëÿåòñÿ íàèáîëåå òðóäíûì çâåíîì â ðåøåíèè èñ- õîäíîé çàäà÷è. Ìíîãèå ïîëåçíûå ðåêîìåíäàöèè ïî ýòîé òåìå ñîäåðæàòñÿ â ðàáî- òå [10], èñïîëüçóþùåé ìåòîä äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ äëÿ ðåøåíèÿ çàäà÷ ìàðøðóòèçàöèè. Áëèçêèå ïðîáëåìû èçó÷àþòñÿ â [11]. Êîãäà ïîðÿäîê ïîèìêè óáåãà- þùèõ îïðåäåëåí, òî öåëåñîîáðàçíî ïðèìåíåíèå óïîìÿíóòûõ ðàíåå ýôôåêòèâíûõ ìåòîäîâ ïðåñëåäîâàíèÿ. Ñëåäóåò ïîä÷åðêíóòü, ÷òî êëþ÷åâàÿ òðóäíîñòü ïðîáëåìû ñîñòîèò â òîì, ÷òî îáå ÷àñòè èñõîäíîé çàäà÷è (ïåðåáîðíàÿ è óïðàâëåí÷åñêàÿ) íåðàç- ðûâíû è ðåøàòü èõ íóæíî òîëüêî âî âçàèìîñâÿçè. Â èññëåäîâàíèè çàäà÷è ïîî÷åðåäíîãî ïðåñëåäîâàíèÿ îòìåòèì ðàáîòû Å.Ï. Ìàñëîâà è åãî êîëëåã [12–14]. Ïîäîáíûìè ïðîáëåìàìè çàíèìàëèñü ñàíêò-ïå- òåðáóðãñêèå [15] è åêàòåðèíáóðãñêèå [16] ó÷åíûå. Îñîáûé èíòåðåñ ïðåäñòàâëÿåò ñòàòüÿ [17], â êîòîðîé ïîðÿäîê ïðåñëåäîâàíèÿ îïðåäåëÿåòñÿ ïîçèöèîííûì îáðàçîì. Ê ìåòîäèêå äàííîé ðàáîòû íàèáîëåå áëèçêè èññëåäîâàíèÿ [18, 19], ãäå, ñëåäóÿ ðàíåå âûñêàçàííîé èäåå, ïðèìåíÿåòñÿ ìåòîä ðàçðåøàþùèõ ôóíêöèé [1], äàþùèé íà îñíîâå ââåäåííûõ îáðàòíûõ ôóíêöèîíàëîâ Ìèíêîâñêîãî îáîñíîâàíèå ïàðàëëåëüíîãî ñáëèæåíèÿ. Òàêèì îáðàçîì, êîãäà ïðåñëåäîâàòåëü èñïîëüçóåò àëãîðèòì ïàðàëëåëüíîãî ñáëèæåíèÿ ïðè çàäàííîì ïîðÿäêå ïîèìêè óáåãàþùèõ, òî îñòàåòñÿ îïðåäåëèòü îïòè- ìàëüíûé îòâåò êàæäîãî óáåãàþùåãî. Ïðè ýòîì äèíàìèêà êàæäîãî èç èãðîêîâ ïðåäïî- ëàãàåòñÿ ïðîñòîé è èìååòñÿ íåêîòîðîå ïðåèìóùåñòâî ïðåñëåäîâàòåëÿ íàä êàæäûì óáå- ãàþùèì. Ïîñëåäíåå îáñòîÿòåëüñòâî ïîçâîëÿåò ñâåñòè èñõîäíóþ áåñêîíå÷íîìåðíóþ îïòèìèçàöèîííóþ ïðîáëåìó ê äâóì âçàèìíî çàâèñèìûì êîíå÷íîìåðíûì çàäà÷àì: íå- ïðåðûâíîé îïòèìèçàöèè ñóììàðíîãî âðåìåíè ïîèìêè ïî ïîñòîÿííûì óïðàâëåíèÿì óáåãàþùèõ è äèñêðåòíîé îïòèìèçàöèè ïî ïîðÿäêó ïîèìêè. Íàñòîÿùàÿ ñòàòüÿ ïðèìûêàåò ê ðàáîòàì [1, 10, 12–19] è ðàçâèâàåò èññëåäîâà- íèÿ [18–20]. 40 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 © À.À. Áåëîóñîâ, Þ.È. Áåðäûøåâ, À.Ã. ×åíöîâ, À.À. ×èêðèé, 2010 ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È Ðàññìàòðèâàåòñÿ çàäà÷à ïîî÷åðåäíîé ïîèìêè îäíèì èãðîêîì-ïðåñëåäîâàòåëåì (x) N óáåãàþùèõ èãðîêîâ ( yi ), êîòîðûå ñòðåìÿòñÿ èçáåæàòü ñáëèæåíèÿ. Äèíàìèêà îáúåêòîâ çàäàåòñÿ äèôôåðåíöèàëüíûìè óðàâíåíèÿìè � , , ( ) , \| \| \| \| ,x u x R x x un� � � �0 10 � , , ( ) , \| \| \| \| , , , ,y y R y y i Ni i i n i i i i� � � � � �� 0 1 1 � (1) ãäå óïðàâëåíèÿ u i( ), ( )� �� — èçìåðèìûå ïî Ëåáåãó ôóíêöèè. Ïîä ïîèìêîé ïî- íèìàåòñÿ ñîâïàäåíèå êîîðäèíàò îáúåêòîâ x T y Ti i i( ) ( )� â íåêîòîðûé ìîìåíò âðå- ìåíè Ti . Ïåðåä ïðåñëåäîâàòåëåì ñòàâèòñÿ çàäà÷à êàê ìîæíî ñêîðåå ïîéìàòü âñåõ óáåãàþùèõ, óáåãàþùèå èãðîêè, â ñâîþ î÷åðåäü, ñòðåìÿòñÿ ýòîìó ïîìåøàòü. Ðàçëè÷íûå ôîðìàëèçàöèè èãðîâûõ çàäà÷ ñáëèæåíèÿ ñ ãðóïïîâîé öåëüþ ïðèâåäåíû â ðàáîòàõ [1, 12–15, 18, 19]. Èç ýòèõ èññëåäîâàíèé ìîæíî çàêëþ÷èòü, ÷òî êîíñòðóêòèâíûå àíàëèòè÷åñêèå ðåøåíèÿ óäàåòñÿ ïîñòðîèòü ëèøü äëÿ èãð ñ äâó- ìÿ óáåãàþùèìè. Äëÿ áîëüøåãî ÷èñëà óáåãàþùèõ îïòèìàëüíîå ïîâåäåíèå èãðîêîâ íàõîäèòñÿ òîëüêî ÷èñëåííî. Íî è ÷èñëåííîå èññëåäîâàíèå âîçìîæíî òîëüêî äëÿ íå- áîëüøèõ çíà÷åíèé N , à äëÿ N � 5 òàêèå çàäà÷è óæå òðóäíîðàçðåøèìû [18]. Ñëîæ- íîñòü ýòèõ çàäà÷ ñòàíîâèòñÿ î÷åâèäíîé, åñëè ó÷åñòü òîò ôàêò, ÷òî ïðèíÿòèå ðåøå- íèé â íèõ äîëæíî ïðîèñõîäèòü â ðåæèìå ðåàëüíîãî âðåìåíè. Ñëåäîâàòåëüíî, ìåòî- äû è àëãîðèòìû, ðåàëèçóþùèå ïðèíÿòèå ðåøåíèé, äîëæíû áûòü âåñüìà áûñòðûìè. Â äàííîé ðàáîòå ïðåäëàãàåòñÿ ìåòîä èññëåäîâàíèÿ èãðîâîé çàäà÷è êîììèâîÿæåðà, ïîçâîëÿþùèé äîñòàòî÷íî ýôôåêòèâíî ðåøàòü çàäà÷ó ïîèìêè (1) äëÿ áîëüøîãî ÷èñëà óáåãàþùèõ. ÏÎÄÕÎÄÛ Ê ÐÅØÅÍÈÞ Ïîäðîáíîå îïèñàíèå çàäà÷è (1) è ïîäõîäîâ ê åå ðåøåíèþ äàíî â ðàáîòå [1]. Îñíîâíûå ðåçóëüòàòû ïðîâåäåííûõ â íåé èññëåäîâàíèé ìîæíî êðàòêî ñôîðìóëè- ðîâàòü ñëåäóþùèì îáðàçîì. Î÷åðåäíîñòü ïîèìêè îïðåäåëÿåòñÿ ïðåñëåäîâàòåëåì ïðîãðàììíî, ò.å. â íà÷àëå èãðû è äàëåå íå èçìåíÿåòñÿ. Ïðè ôèêñèðîâàííîì ïî- ðÿäêå ïîèìêè ïðåñëåäîâàòåëåì èñïîëüçóåòñÿ ñòðàòåãèÿ ïàðàëëåëüíîãî ñáëèæåíèÿ ñ êàæäûì ïîñëåäóþùèì óáåãàþùèì èãðîêîì u x y e e e( , , ) , , ,� � � � �� 2 21 e x y x y � � �\| \| \| \| , ãäå x y, — ïîëîæåíèÿ ïðåñëåäîâàòåëÿ è óáåãàþùåãî â ìîìåíò íà÷àëà ïîãîíè çà ýòèì èãðîêîì. Ïðè óêàçàííûõ ïðåäïîëîæåíèÿõ â ðàáîòå [1] äîêàçàíî, ÷òî, âî-ïåðâûõ, ïðåñëåäîâàòåëü ìîæåò ïîéìàòü âñåõ óáåãàþùèõ ïðè ëþáûõ èõ äî- ïóñòèìûõ óïðàâëåíèÿõ (1); âî-âòîðûõ, äëÿ ìàêñèìèçàöèè âðåìåíè ïîèìêè TN óáåãàþùèå äîëæíû äâèãàòüñÿ ñ ïîñòîÿííûìè ïî íàïðàâëåíèþ è ìàêñèìàëüíûìè ïî âåëè÷èíå ñêîðîñòÿìè (� � � �i i i it t i N( ) , [ , ), \| \| \| \| , , ,� � � � �0 1 � ). Òàêèì îáðàçîì, ïåðâîíà÷àëüíàÿ èãðîâàÿ çàäà÷à, êîòîðàÿ, âîîáùå ãîâîðÿ, áåñ- êîíå÷íîìåðíà, ñâîäèòñÿ ê äâóì êîíå÷íîìåðíûì îïòèìèçàöèîííûì çàäà÷àì: ìàêñè- ìèçàöèè ñóììàðíîãî âðåìåíè ïîèìêè ïðè ôèêñèðîâàííîì ïîðÿäêå TN N( , , )� �1 � íà ìíîæåñòâå âåêòîðîâ {� i nR� : \| \| \| \|� �i i� , i N�1, ,� }; äèñêðåòíîé îïòèìèçàöèè ïî âûáîðó ïîñëåäîâàòåëüíîñòè ïîèìêè, êîòîðàÿ ìèíèìèçèðóåò ýòè ìàêñèìàëüíûå âðåìåíà ïîèìêè. Äàííàÿ ðàáîòà ïîñâÿùåíà èçó÷åíèþ ïåðâîé çàäà÷è — ìàêñèìèçàöèè ñóììàð- íîãî âðåìåíè ïîèìêè ïðè ôèêñèðîâàííîì ïîðÿäêå. Ñâÿçàíî ýòî ñ òåì, ÷òî áîëüøàÿ ÷àñòü ïðîáëåì ïîðîæäàåòñÿ èìåííî ýòîé çàäà÷åé, è îò ýôôåêòèâíîñòè åå ðåøåíèÿ ãëàâíûì îáðàçîì çàâèñèò ñêîðîñòü è òî÷íîñòü ðåøåíèÿ âñåé ïðîáëåìû. Îòíîñèòåëüíî âòîðîé çàäà÷è îòìåòèì, ÷òî â íåé ðå÷ü èäåò î ïåðåáîðå N! âàðè- àíòîâ î÷åðåäíîñòè ïîèìêè (âîîáùå ãîâîðÿ). Ïðè÷åì äëÿ êàæäîãî òàêîãî âàðèàíòà ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 41 ñóììàðíîå âðåìÿ ïîèìêè íàõîäèòñÿ íåçàâèñèìî îò äðóãèõ. Çíà÷èò, â ýòîé ÷àñòè àë- ãîðèòì ðåøåíèÿ ìîæåò áûòü õîðîøî ðàñïàðàëëåëåí è ïðè åãî ðåàëèçàöèè íà ìíî- ãîïðîöåññîðíîé âû÷èñëèòåëüíîé ñèñòåìå âðåìÿ îïòèìèçàöèè áóäåò ïðàêòè÷åñêè ëèíåéíî çàâèñåòü îò ÷èñëà èñïîëüçóåìûõ ïðîöåññîðîâ. ÎÏÒÈÌÈÇÀÖÈÎÍÍÀß ÇÀÄÀ×À Èñõîäíàÿ èãðîâàÿ çàäà÷à (1) ïðè ôèêñèðîâàííîì ïîðÿäêå ïîèìêè ñâîäèòñÿ ê çà- äà÷å óñëîâíîé îïòèìèçàöèè [21], ôóíêöèîíàë è îãðàíè÷åíèÿ êîòîðîé â íàèáîëåå ïðîñòîì âèäå ìîæíî çàïèñàòü ñëåäóþùèì îáðàçîì: T x yN N N N� � �� \| \| \| \| max, (2) G x x x y x y x xk k k k k k k k k k k( , ) \| \| \| \| \| \| \| \| \| \|� � � � �� 1 1 1 1� � 1 0 1\| \| , ,... , ,� �k N y x k k0 0 0 0 1� � �, , / .� � � (3) Â ýòîé ôîðìóëèðîâêå ìàêñèìèçàöèÿ ïðîâîäèòñÿ ïî âåêòîðàì x Rk n� , êîòîðûå îáîçíà÷àþò òî÷êè ïîèìêè k-ãî óáåãàþùåãî: x x T T u y T k Nk k k k k k k k� � � � � �� 1 1 1( ) , , ,� � . (4) Çäåñü Tk — ìîìåíò ïîèìêè k-ãî óáåãàþùåãî, �k — óïðàâëåíèå k-ãî óáåãàþùåãî (�k nR� , \| \| \| \|� �k k� ), uk — óïðàâëåíèå ïðåñëåäîâàòåëÿ íà èíòåðâàëå [ , )T Tk k�1 (u Rk n� , \| \| \| \|uk �1) . Îòìåòèì î÷åâèäíîå ñîîòíîøåíèå T x yk k k k� �� \| \| \| \| . Çíà÷èò, ôóíêöèîíàë TN (2) îïðåäåëÿåò ñóììàðíîå âðåìÿ ïîèìêè, à îãðàíè÷åíèÿ (3) îò- ðàæàþò ñîîòíîøåíèÿ ìåæäó ñêîðîñòÿìè îáúåêòîâ, ìîìåíòàìè è ãåîìåòðè÷åñêè- ìè êîîðäèíàòàìè òî÷åê ïîèìêè. Ïî ñóòè, â îïòèìèçàöèîííîé çàäà÷å (2), (3) ðå÷ü èäåò î ìàêñèìèçàöèè ôóíêöèè TN N( , , )� �1 � íà ìíîæåñòâå S Sn n N � �� 1 1 � � �� (äåêàðòîâîì ïðîèçâåäåíèè N ýêçåì- ïëÿðîâ ( )n �1 -ìåðíûõ ñôåð). Òðåáóåòñÿ íàéòè ãëîáàëüíûé ìàêñèìóì ýòîé ôóíêöèè. Îäíàêî ñëåäóåò îòìåòèòü, ÷òî âû÷èñëèòåëüíûå ìåòîäû îïòèìèçàöèè ëîêàëüíû, ò.å. îíè ïîçâîëÿþò íàéòè ëèøü ëîêàëüíûé ìàêñèìóì ôóíêöèè â îêðåñòíîñòè íà- ÷àëüíîé òî÷êè àëãîðèòìà. Ïîýòîìó, êàê ïðàâèëî, îïòèìèçàöèîííûé àëãîðèòì íà÷è- íàåò ðàáîòó èç íåñêîëüêèõ òî÷åê (èç íåêîòîðîãî äîñòàòî÷íî ïðåäñòàâèòåëüíîãî ìíîæåñòâà íà÷àëüíûõ òî÷åê), à ïîëó÷åííûé îïòèìóì ñ÷èòàåòñÿ ãëîáàëüíûì. Íî òà- êîé îáùèé ïîäõîä ïîðîæäàåò ñåðüåçíóþ ïðîáëåìó â äàííîé îïòèìèçàöèîííîé çà- äà÷å. Ñóòü åå ñîñòîèò â ñëåäóþùåì: åñëè M — ÷èñëî íà÷àëüíûõ òî÷åê íà êàæäîé èç N ñôåð S n�1, òî îáùåå êîëè÷åñòâî íà÷àëüíûõ òî÷åê îïòèìèçàöèîííîãî àëãîðèòìà íà ìíîæåñòâå îãðàíè÷åíèé ñîñòàâëÿåò M N , à ýòî ÷èñëî ìîæåò îêàçàòüñÿ îãðîìíûì ïðè äîñòàòî÷íî áîëüøèõ çíà÷åíèÿõ M è N . Äëÿ ïðåîäîëåíèÿ ýòîé ïðîáëåìû ïðåäëàãàåòñÿ ïðèìåíèòü íåîáõîäèìûå óñëî- âèÿ ýêñòðåìóìà â âèäå ïðàâèëà ìíîæèòåëåé Ëàãðàíæà [21]. Çàìåòèì, ÷òî â îáùåì ñëó÷àå ïåðåõîä îò îïòèìèçàöèîííîé çàäà÷è ê ðåøåíèþ ñèñòåìû íåëèíåéíûõ óðàâ- íåíèé íå äàåò îñîáûõ ïðåèìóùåñòâ â ïëàíå ÷èñëåííîãî ðåøåíèÿ. Îäíàêî â äàííîì ñëó÷àå íåîáõîäèìûå óñëîâèÿ ïîçâîëÿþò èçâëå÷ü âàæíóþ àíàëèòè÷åñêóþ èíôîðìàöèþ îá îáùåì âèäå ýêñòðåìàëüíûõ òî÷åê. ÍÅÎÁÕÎÄÈÌÛÅ ÓÑËÎÂÈß ÝÊÑÒÐÅÌÓÌÀ Äëÿ çàäà÷è (2), (3) ïðàâèëî ìíîæèòåëåé Ëàãðàíæà [21] ìîæíî ñôîðìóëèðîâàòü â ñëåäóþùåì âèäå. Åñëè âåêòîð ( , , ) ( )* x x RN n N 1 � � ÿâëÿåòñÿ ëîêàëüíûì ìàêñèìóìîì ôóíêöèî- íàëà (2) ïðè îãðàíè÷åíèÿõ (3), òî ñóùåñòâóåò íåíóëåâîé âåêòîð ( , , )� �1 � N NR� òàêîé, ÷òî äëÿ ôóíêöèè 42 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 f x x x y G x xN N N N k k k k k N ( , , , , , ) \| \| \| \| ( , )1 1 1 1 � �� ïðîèçâîäíûå � � � x f x x k N N( , , , , , ) * 1 1 0� �� ïðè k N�1, ,� . Âûïèøåì ïîñëåäíèå ñîîòíîøåíèÿ â ÿâíîì âèäå: � � � � � � � � � �f x G x G xk k k k k k k � �1 1 � � �k k k k k k k k k k x y x y x x x x � � � � � � � � � � � � � � �1 1 1\| \| \| \| \| \| \| \| � � � � � � � � � � � � � �� k k k k k k k k k k x y x y x x x x k \| \| \| \| \| \| \| \| ,1 1 0 1 1, , ,� N � (5) � � � � � � � � � � �f x x y x y x y x y x x xN N N N N N N N N N N N N \| \| \| \| \| \| \| \| \| \| � � 1 N Nx� � � � � � � �1 0 \| \| . (6) Ó÷èòûâàÿ (4), ñîîòíîøåíèÿ (5) çàïèøåì ñëåäóþùèì îáðàçîì: � � � � � �k k k k k k k ku u k N� �� 1 2 1 2 1 1( ) ( ), , , .� (7) Îòìåòèì, ÷òî \| \| \| \| \| \| \| \| \| \| \| \|� � � k k k k ku u2 11� � � � � , ïîýòîìó ìîæíî óòâåðæäàòü, ÷òî â ñêîáêàõ â ôîðìóëå (7) ñòîÿò íåíóëåâûå âåêòîðû. Çíà÷èò, åñëè ïðåäïîëîæèòü, ÷òî îäíî èç ÷èñåë � k � 0, òî è âñå îñòàëüíûå ÷èñëà � i i N( , , )�1 � äîëæíû áûòü ðàâíû íóëþ, à ýòî ïðîòèâîðå÷èò óòâåðæäåíèþ ïðàâèëà ìíîæèòåëåé Ëàãðàíæà. Ñëå- äîâàòåëüíî, âñå � k � 0 ( , , )k N�1 � . Óðàâíåíèå (7) ìîæíî ïåðåïèñàòü â âèäå u u wk k k k k� � � � � � � �� 1 1 1 � � , w uk k k k� � �� 2 0. Ýòî óðàâíåíèå, ñ ó÷åòîì \| \| \| \| \| \| \| \|u uk k� � �1 1, èìååò äâà ðåøåíèÿ: u uk k� �1 , u u u e ek k k k k� � � 1 2 , , e w w k k k � \| \| \| \| . (8) Ïåðâîå ðåøåíèå, î÷åâèäíî, íå ïîäõîäèò — îíî äàåò ìèíèìóì âðåìåíè ïðè äâè- æåíèè îò òî÷êè xk�1 äî xk�1. Âèä îïòèìàëüíîãî óïðàâëåíèÿ (8) îòìå÷àëñÿ ðàíåå (íàïðèìåð, [12]) ïîä íàçâàíèåì «çàêîí îòðàæåíèÿ îò îêðóæíîñòè». Òàêèì îáðàçîì, íåîáõîäèìûå óñëîâèÿ ýêñòðåìóìà ïîçâîëÿþò óñòàíîâèòü îïòè- ìàëüíîå óïðàâëåíèå uk�1 ïî çàäàííûì çíà÷åíèÿì u Tk k, , xk (ôîðìóëû (8) è (4)). Äëÿ íàõîæäåíèÿ Tk�1, ñîîòâåòñòâóþùåãî óïðàâëåíèþ uk�1, ñëåäóåò ïåðåïèñàòü îãðàíè- ÷åíèÿ (3) â âèäå �k k k k k k kx T T u y T� � � � �� 1 1 1 1 1 0\| \| ( ) \| \| . Ýòî óðàâíåíèå ÿâëÿåòñÿ êâàäðàòíûì îòíîñèòåëüíî Tk�1, à åãî êîðíè ðàâíû T T u a T u a a uk k k k k k k k k� � � � � � � � � � � � 1 1 2 1 2 1 1 1 2 2 1 � � � , ( � � � � � � � � � � 1 2, ) ,a (9) ãäå a y xk k� ��1 . Èç ýòèõ êîðíåé ñëåäóåò âûáðàòü áîëüøèé, òàê êàê (ïðè ïðî÷èõ ðàâ- íûõ óñëîâèÿõ) îí äàåò áîëüøåå âðåìÿ ïîèìêè. Òî÷íåå, ìîæíî ôîðìàëüíî ïîêàçàòü, ÷òî â ñëó÷àå âûáîðà äðóãîãî êîðíÿ îáùåå âðåìÿ ïîèìêè TN ìîæåò áûòü óâåëè÷åíî ïðè ñî- õðàíåíèè òåõ æå çíà÷åíèé x x x xk k N1 1 1, , , , ,! !� � ïóòåì íàäëåæàùåãî âûáîðà xk . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 43 Îòìåòèì, ÷òî ïîäêîðåííîå âûðàæåíèå â ôîðìóëå (9) ìîæåò îêàçàòüñÿ îòðèöà- òåëüíûì. Ýòî áóäåò îçíà÷àòü, ÷òî äëÿ ïðåäëîæåííûõ çíà÷åíèé u T xk k k, , íå ñóùåñ- òâóåò óïðàâëåíèÿ uk�1, óäîâëåòâîðÿþùåãî îäíîâðåìåííî è íåîáõîäèìûì óñëîâè- ÿì îïòèìàëüíîñòè (5) è îãðàíè÷åíèÿì (3). ÑÂÅÄÅÍÈÅ ÎÏÒÈÌÈÇÀÖÈÎÍÍÎÉ ÇÀÄÀ×È Ê ÐÅØÅÍÈÞ ÎÄÍÎÃÎ ÓÐÀÂÍÅÍÈß Ñäåëàåì äâà ïðîñòûõ çàìå÷àíèÿ. Âî-ïåðâûõ, ìíîæåñòâîì òî÷åê, êîòîðûå óäîâ- ëåòâîðÿþò îãðàíè÷åíèþ (3) ïðè k �1, ò.å. �1 1 1 1 0\| \| \| \| \| \| \| \|x y x x� � � , ÿâëÿåòñÿ ñôå- ðà (òàê íàçûâàåìàÿ ñôåðà Àïîëëîíèÿ) \| \| \| \| ,x d R1 � � (10) ãäå d y x � � � � � 1 2 1 0 1 2 1 , R y x� � � � � 1 1 2 1 0 1 \| \| \| \|. Âî-âòîðûõ, èç íåîáõîäèìûõ óñëîâèé (6) ñëåäóåò, ÷òî îïòèìàëüíûé âåêòîð u N äîëæåí áûòü ïàðàëëåëåí âåêòîðó x yN N� . Ó÷èòûâàÿ ñîîòíîøåíèÿ (4), ìîæíî çàêëþ÷èòü, ÷òî u N äîëæåí áûòü ïàðàëëåëåí x yN N� �1 . Ïðè÷åì äëÿ óâåëè÷åíèÿ âðåìåíè ïîèìêè N-é óáåãàþùèé èãðîê äîë- æåí äâèãàòüñÿ â íàïðàâëåíèè îò òî÷êè xN �1 ê yN . Çíà÷èò, äëÿ ìàêñèìèçàöèè ñóììàðíîãî âðåìåíè ïîèìêè äîëæíî âûïîëíÿòüñÿ ðàâåíñòâî u y x y x N N N N N , \| \| \| \| � � �� 1 1 1. Òàêèì îáðàçîì, èñõîäíàÿ îïòèìèçàöèîííàÿ çàäà÷à (2), (3) ñ ïîìîùüþ íåîáõî- äèìûõ óñëîâèé îïòèìàëüíîñòè ñâåäåíà ê íàõîæäåíèþ âñåõ êîðíåé îäíîãî íåëèíåé- íîãî óðàâíåíèÿ F x( ) � 0 , çàäàííîãî íà ñôåðå Àïîëëîíèÿ (10). Ôóíêöèÿ F x( ) äëÿ ïðîèçâîëüíîãî âåêòîðà x, ëåæàùåãî íà ñôåðå Àïîëëîíèÿ (10), çàäàåòñÿ ðåêóððåíòíî ñëåäóþùèì îáðàçîì: 1) ïîëàãàåì x x1 � , T x x1 1 0� �\| \| \| \| , u x x T 1 1 0 1 � � ; 2) (øàã ðåêóðñèè) ïî çàäàííûì x T uk k k, , (k N� �1 1, ,� ) íàõîäèì (ñì. (8) è (9)) w x y T uk k k k k� � �� , u u u w w w w k k k� � �1 2 , \| \| \| \| \| \| \| \| , a y xk k� ��1 , D T u a a u ak k k k� � � � � � � 1 1 2 2 1 2 � ( , ) , åñëè D � 0 , òî ôîðìàëüíî ïîëàãàåì F x( ) � �1 è âû÷èñëåíèå îñòàíàâëèâàåì, åñëè D � 0 , òî ïðîöåññ îïðåäåëåíèÿ ôóíêöèè ïðîäîëæàåòñÿ, T T u a Dk k k k k� � � �� 1 1 2 1 2 1 1 � � , , x x T T uk k k k k� � �� 1 1 1( ) , ïîâòîðÿåì øàã ðåêóðñèè äëÿ k N� �1 1, ,� ; 3) F x u y x y x N N N N N ( ) , \| \| \| \| � � � �� 1 1 1. Èç âñåõ êîðíåé óðàâíåíèÿ F x( ) � 0 âûáèðàåì òå, êîòîðûå äàþò íàèáîëüøåå çíà÷å- íèå TN . Ýòî çíà÷åíèå TN ÿâëÿåòñÿ ðåøåíèåì èñõîäíîé îïòèìèçàöèîííîé çàäà÷è, ñî- îòâåòñòâóþùèå óïðàâëåíèÿ óáåãàþùèõ èãðîêîâ èìåþò âèä �k k k k x y T � � (k N� !1, , ) . Òàêèì îáðàçîì, âìåñòî íàõîæäåíèÿ ãëîáàëüíîãî ìàêñèìóìà ôóíêöèè ñóììàð- íîãî âðåìåíè TN N( , , )� �1 � íà äåêàðòîâîì ïðîèçâåäåíèè N ñôåð ( )S n N�1 ïðåä- ëàãàåòñÿ èñêàòü âñå êîðíè óðàâíåíèÿ F x( ) � 0 íà îäíîé ñôåðå S n�1 âèäà (10). Ýòî 44 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 ïðåäñòàâëÿåòñÿ çíà÷èòåëüíî áîëåå ïðîñòîé çàäà÷åé, íåñìîòðÿ íà òî, ÷òî ôóíêöèÿ F èìååò äîâîëüíî ñëîæíûé âèä è çàäàåòñÿ ðåêóððåíòíî. Îñíîâíîé ðåçóëüòàò ðàáîòû ìîæíî êðàòêî ñôîðìóëèðîâàòü â âèäå ñëåäóþùåãî óòâåðæäåíèÿ. Òåîðåìà. Ðåøåíèå èãðîâîé çàäà÷è êîììèâîÿæåðà (1) ïðè âûáðàííîé î÷åðåä- íîñòè ïîèìêè ñâîäèòñÿ ê íàõîæäåíèþ âñåõ êîðíåé óðàâíåíèÿ F x( ) � 0 (äëÿ ïîñòðî- åííîé óêàçàííûì îáðàçîì ôóíêöèè F), ëåæàùèõ íà ñôåðå Àïîëëîíèÿ (10). ÇÀÊËÞ×ÅÍÈÅ Ïðåäëîæåííûé ïîäõîä ê ðåøåíèþ èãðîâîé çàäà÷è äèíàìè÷åñêîãî êîììèâîÿæåðà ïðîãðàììíî ðåàëèçîâàí äëÿ êëàñòåðíîãî ìíîãîïðîöåññîðíîãî êîìïëåêñà â Èíñòèòóòå êèáåðíåòèêè èì. Â. Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû. Ïðîâåäåííûå ÷èñëåííûå ðàñ÷åòû ïî- êàçàëè âûñîêóþ ýôôåêòèâíîñòü ïîñòðîåííîãî àëãîðèòìà. Â èãðîâîé çàäà÷å ïîî÷åðåä- íîãî ïðåñëåäîâàíèÿ íà ïëîñêîñòè îïòèìàëüíàÿ î÷åðåäíîñòü ñáëèæåíèÿ ñ 11–12 èãðî- êàìè ñèíòåçèðîâàíà ïðàêòè÷åñêè â ðåæèìå ðåàëüíîãî âðåìåíè. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. × è ê ð è é À . À . Êîíôëèêòíî óïðàâëÿåìûå ïðîöåññû. — Êèåâ: Íàóê. äóìêà, 1992. — 384 ñ. 2. Ê ð à ñ î â ñ ê è é Í . Í . , Ñ ó á á î ò è í À . È . Ïîçèöèîííûå äèôôåðåíöèàëüíûå èãðû. — Ì.: Íàóêà, 1974. — 480 ñ. 3. Ï î í ò ð ÿ ã è í Ë . Ñ . Èçáðàííûå íàó÷íûå òðóäû. — Ì.: Íàóêà, 1988. — Ò. 2. — 576 ñ. 4. Ï ø å í è ÷ í û é Á . Í . , Î ñ ò à ï å í ê î Â . Â . Äèôôåðåíöèàëüíûå èãðû. — Êèåâ: Íàóê. äóìêà, 1992. — 260 ñ. 5. Ñ ó á á î ò è í À . È . , × å í ö î â À . Ã . Îïòèìèçàöèÿ ãàðàíòèè â èãðîâûõ çàäà÷àõ óïðàâëåíèÿ. — Ì.: Íàóêà, 1981. — 288 ñ. 6. Ã ð è ã î ð å í ê î Í . Ë . Ìàòåìàòè÷åñêèå ìåòîäû óïðàâëåíèÿ íåñêîëüêèìè äèíàìè÷åñêèìè ïðî- öåññàìè. — Ì.: Èçä-âî ÌÃÓ, 1990. — 198 ñ. 7. Á ë à ã î ä à ò ñ ê è õ À . È . , Ï å ò ð î â Í . Í . Êîíôëèêòíîå âçàèìîäåéñòâèå ãðóïï óïðàâëÿåìûõ îáúåêòîâ. — Èæåâñê: Èçä-âî Óäì. ãîñ. óí-òà, 2009. — 265 ñ. 8. L e d y a e v Y u . S . Optimal robust discontinuous feedback control in differential games of group pur- suit // Int. Conf. Differential Equations and Topology, ded. 100 Anniversary L. S. Pontryagin (Moscow, June 17-22, 2008). — Moscow: Lomonosov State Univ., 2008. — P. 265. 9. C h i k r i i A . A . The problem of avoidance for controlled dynamic objects // J. Math., Game Theory and Algebra. — 1998. — 7, N 2/3. — P. 81–94. 10. × å í ö î â À . Ã . Ýêñòðåìàëüíûå çàäà÷è ìàðøðóòèçàöèè è ðàñïðåäåëåíèÿ çàäàíèé: âîïðîñû òåîðèè. — Ì.; Èæåâñê: ÍÈÖ «Ðåãóëÿðíàÿ è õàîòè÷åñêàÿ äèíàìèêà», 2008. — 240 ñ. 11. Ê à ñ ï ø è ö ê à ÿ Ì . Ô . , Ã ë ó ø ê î â à Â . Â . Îá óñòîé÷èâîñòè ðåøåíèÿ çàäà÷è êîììèâîÿæåðà // Êèáåðíåòèêà. — 1986. — ¹ 3. — Ñ. 26–32. 12. Ì à ñ ë î â Å . Ï . , Ð ó á è í î â è ÷ Å . ß . Äèôôåðåíöèàëüíûå èãðû ñ ãðóïïîâîé öåëüþ // Èòîãè íàóêè è òåõíèêè. Ñåð. Òåõí. êèáåðíåòèêà. — Ì.: ÂÈÍÈÒÈ, 1991. — 32. — Ñ. 32–59. 13. Ø å â ÷ å í ê î È . È . Ãåîìåòðèÿ àëüòåðíàòèâíîãî ïðåñëåäîâàíèÿ. — Âëàäèâîñòîê: Èçä-âî Äàëüíå- âîñò. óí-òà, 2003. — 240 ñ. 14. Ø å â ÷ å í ê î È . È . Ñòðàòåãèè ñáëèæåíèÿ ñ êîàëèöèÿìè â öåëîì. — Âëàäèâîñòîê: Èçä-âî Äàëüíåâîñò. óí-òà, 2004. — 132 ñ. 15. Ï å ò ð î ñ ÿ í Ë . À . , Ø è ð ÿ å â Â . Ä . Ãðóïïîâîå ïðåñëåäîâàíèå îäíèì ïðåñëåäîâàòåëåì íåñêîëüêèõ ïðåñëåäóåìûõ // Âåñòí. ËÃÓ. — 1980. — 13, ¹ 3. — Ñ. 50–57. 16. Á å ð ä û ø å â Þ . È . Îá îäíîé íåëèíåéíîé çàäà÷å ïîñëåäîâàòåëüíîãî óïðàâëåíèÿ ñ ïàðàìåòðîì // Èçâ. ÐÀÍ. Òåîðèÿ è ñèñòåìû óïðàâëåíèÿ. — 2008. — Âûï. 3. — Ñ. 58–63. 17. B r e a k w e l l J . V . , H a g e d o r n P . Point capture of two evaders in succession // J. Optim. Theory and Appl. — 1979. — 27, N 1. — P. 90–97. 18. × è ê ð è é À . À . , Ñ î á î ë å í ê î Ë . À . , Ê à ë à ø í è ê î â à Ñ . Ô . ×èñëåííûé ìåòîä ðåøåíèÿ çàäà÷è ïîî÷åðåäíîãî ïðåñëåäîâàíèÿ // Êèáåðíåòèêà. — 1988. — ¹ 1. — Ñ. 44–49. 19. × è ê ð è é À . À . , Ê à ë à ø í è ê î â à Ñ . Ô . Ïðåñëåäîâàíèå óïðàâëÿåìûì îáúåêòîì ãðóïïû óáåãà- þùèõ // Òàì æå. — 1987. — ¹ 4. — Ñ. 1–8. 20. B e l o u s o v A . , C h i k r i i A . On solution of traveling salesman game problem // 12-th Intern. Symp. on Dynamic Games and Applications (3–6 July 2006, Sophia-Antipolis, France): Abstracts. — 2006. — P. 31. 21. È î ô ô å À . Ä . , Ò è õ î ì è ð î â Â . Ì . Òåîðèÿ ýêñòðåìàëüíûõ çàäà÷. — Ì.: Íàóêà, 1974. — 479 ñ. Ïîñòóïèëà 17.02.2010 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 45

О решении игровой задачи динамического коммивояжера

Institution

Ähnliche Einträge