Ñàíêò-Ïåòåðáóðãñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò
Íàïðàâëåíèå: Ìàòåìàòèêà, ìåõàíèêà
Ñïåöèàëèçàöèÿ: Àëãåáðà
Ïåéñàõîâñêèé ϼòð Îëåãîâè÷
Ìîäåëèðîâàíèå óêëîíåíèÿ â çàäà÷å ïîèñêà íà ãðàôå
Äèïëîìíàÿ ðàáîòà
Íàó÷íûé ðóêîâîäèòåëü:
êàíäèäàò ôèç-ìàò. íàóê, ñòàðøèé ïðåïîäàâàòåëü
Àáðàìîâñêàÿ Ò.Â.
Ðåöåíçåíò:
êàíäèäàò ôèç.-ìàò. íàóê, ïðîôåññîð
Áåøêî Ì. Þ.
Ñàíêò-Ïåòåðáóðã
2016
SAINT-PETERSBURG STATE UNIVERSITY
Main Field of Study: Mathematics, mechanics
Area of Specialisation: Algebra
Pejsahosvky Petr Olegovich
Modelling deviation in a problem of graph search
Graduation Thesis
Scienti c supervisor:
Senior Lecturer T. V. Abramovskaia
Reviewer:
Associate Professor M. Y. Beshko
Saint-Petersburg
2016
Ñîäåðæàíèå
1
Ïåðå÷åíü óñëîâíûõ îáîçíà÷åíèé
2
2
Ââåäåíèå
4
2.1
Ìîòèâàöèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.2
Ïðàâèëà èãðû è ïîñòàíîâêà çàäà÷è . . . . . . . . . . . . . .
9
3
Íåêîòîðûå ôàêòû î ïîëèöåéñêîì ÷èñëå
11
4
Ïîñòðîåíèå àëãîðèòìîâ óêëîíåíèÿ
13
5
6
7
4.1
Ïðîñòåéøåå óêëîíåíèå ìåòîäîì ïîòåíöèàëîâ . . . . . . . . 13
4.2
Óëó÷øåíèå àëãîðèòìà äëÿ íåêîòîðûõ ÷àñòíûõ ñëó÷àåâ . . . 18
4.3
Ñîïðÿæåííûé àëãîðèòì (äëÿ ïîëèöåéñêèõ) . . . . . . . . . 20
Ìîäåëèðîâàííèå C&R íà JavaScript
22
5.1
Âèçóàëüíîå ìîäåëèðîâàíèå . . . . . . . . . . . . . . . . . . . 22
5.2
Êîíñîëüíîå ïðèëîæåíèå . . . . . . . . . . . . . . . . . . . . . 24
Îöåíêà ýôôåêòèâíîñòè ïàð àëãîðèòìîâ ñ ïîìîùüþ ýìïèðè÷åñêîãî ïîëèöåéñêîãî ÷èñëà
27
Çàêëþ÷åíèå
32
1
1
Ïåðå÷åíü óñëîâíûõ îáîçíà÷åíèé
|C|
Êîëè÷åñòâî ïîëèöåéñêèõ
|V |
Êîëè÷åñòâî âåðøèí ãðàôà
E
Ìàòåìàòè÷åñêîå îæèäàíèå
C
Èãðîê, èãðàþùèé çà ïîëèöåéñêèõ
R
Èãðîê, èãðàþùèé çà ãðàáèòåëÿ
σC
Ôóíêöèÿ, êîòîðàÿ â ðàìêàõ îïðåäåëåííîé ñòðàòåãèè ñîïîñòàâëÿåò íîâóþ ïîçèöèþ ïîëèöåéñêèõ C 0 êàæäîé êîíôèãóðàöèè èãðû
σR
Ôóíêöèÿ, êîòîðàÿ â ðàìêàõ îïðåäåëåííîé ñòðàòåãèè ñîïîñòàâëÿåò íîâóþ ïîçèöèþ ãðàáèòåëÿ r0 êàæäîé êîíôèãóðàöèè
èãðû
AC
Àëãîðèòì äëÿ C
AC (G)
Ìíîæåñòâî ñòðàòåãèé äëÿ C íà ãðàôå G, ñîîòâåòñòâóþùåå
àëãîðèòìó AC
AR
Àëãîðèòì äëÿ R
AR (G)
Ìíîæåñòâî ñòðàòåãèé äëÿ R íà ãðàôå G, ñîîòâåòñòâóþùåå
àëãîðèòìó AR
C = (c1 , ..., ck ) Ñïèñîê âåðøèí, çàíèìàåìûõ ôèøêàìè ïîëèöåéñêèõ
C&R
Èãðà ¾ïîëèöåéñêèå è ãðàáèòåëü¿
cn0 (G)
Ýìïèðè÷åñêîå ïîëèöåéñêîå ÷èñëî
cn(G)
Ïîëèöåéñêîå ÷èñëî ãðàôà
2
E
Ìíîæåñòâî ðåáåð ãðàôà G
G = G(V, E) Ñâÿçíûé (åñëè íå óêàçàíî îáðàòíîå) íåîðèåíòèðîâàííûé
ãðàô
girth(G)
Ìèíèìàëüíàÿ äëèíà èíäóöèðîâàííîãî öèêëà
IC
Ïåðâûé õîä ïîëèöåéñêèõ äëÿ íåêîòîðîé ñòðàòåãèè íà ãðàôå
G
IR
Ïåðâûé õîä ãðàáèòåëÿ äëÿ íåêîòîðîé ñòðàòåãèè íà ãðàôå G
k
Êîëè÷åñòâî ôèøåê ó èãðîêà, èãðàþùåãî çà ïîëèöåéñêèõ
N (v)
Ìíîæåñòâî âåðøèí, ñìåæíûõ ñ v (ñîåäèíåííûõ ñ v ðåáðîì)
PC (v)
Ïîòåíöèàë âåðøèíû v ∈ V , ïðè ðàñïîëîæåíèè ïîëèöåéñêèõ
C
r
Âåðøèíà çàíèìàåìàÿ ãðàáèòåëåì
S
Òåêóùàÿ êîíôèãóðàöèÿ èãðû
SC
Ñòðàòåãèÿ äëÿ C
SR
Ñòðàòåãèÿ äëÿ R
V
Ìíîæåñòâî âåðøèí ãðàôà G
v1 ↔ v2
Îáîçíà÷åíèå, îçíà÷àþùåå, ÷òî âåðøèíû v1 è v2 ñìåæíû
(ò.å. ñîåäèíåíû ðåáðîì)
W (C, R)
Ôóíêöèÿ îöåíêè ïîçèöèè
3
2
Ââåäåíèå
 äàííîé ðàáîòå ðàññìàòðèâàþòñÿ îäèí èç ÷àñòíûõ ñëó÷àåâ çàäà÷è ïîèñêà íà ãðàôàõ èãðà ¾ïîëèöåéñêèå è ãðàáèòåëü¿. Çäåñü è äàëåå âìåñòî
¾ïîëèöåéñêèå è ãðàáèòåëü¿ áóäåò èñïîëüçîâàòüñÿ àíãëîÿçû÷íîå ñîêðàùåíèå C&R (cops and robber).
Âïåðâûå îïðåäåëåíèå èãðû C&R áûëî äàíî â ðàáîòå Winkler & Nowakowski
[NW83], òàì ðàññìàòðèâàëñÿ òîëüêî ñëó÷àé ñ îäíèì ïîëèöåéñêèì, è íåçàâèñèìî Alain Quilliot.
 íàèáîëåå îáùåì ñëó÷àå C&R ìîæíî îïèñàòü êàê êëàññ ïîøàãîâûõ
èãð íà ãðàôàõ, â êîòîðûõ äâà èãðîêà â êàæäûé ìîìåíò âðåìåíè çàíèìàþò íåêîòîðîå ìíîæåñòâî âåðøèí ñâîèìè ôèøêàìè, è îäèí èç äâóõ
èãðîêîâ (èãðàþùèé çà
) ñâîèìè õîäàìè (ïåðåäâèæåíèÿìè
ïîëèöåéñêèõ
ôèøåê) ¾ïðåñëåäóåò¿ äðóãîãî (ãðàáèòåëÿ) è ïûòàåòñÿ åãî ¾ïîéìàòü¿.
Êîëè÷åñòâî ôèøåê èãðîêîâ, èõ íà÷àëüíàÿ ðàñòàíîâêà, ïðîöåññ ïðåñëåäîâàíèÿ, ïðàâèëà çàõâàòà ãðàáèòåëÿ è ïðî÷åå çàâèñèò îò êîíêðåòíûõ
ïðàâèë èãðû.
Íàèáîëåå ðàñïðîñòðàí¼ííûå ïðàâèëà (è â òî æå âðåìÿ íàèáîëåå ïðîñòûå) ìîæíî êðàòêî îïèñàòü òàê:
ó ãðàáèòåëÿ 1 ôèøêà, ó ïîëèöåéñêèõ íåñêîëüêî.  íà÷àëå èãðû
èãðîêè ðàññòàâëÿþò ñâîè ôèøêè â âûáðàííûå èìè âåðøèíû è äàëåå ïî
î÷åðåäè ïåðåäâèãàþò èõ âäîëü ð¼áåð ãðàôà, ïîêà ãðàáèòåëü íå áóäåò
ïîéìàí. Åñëè èãðà íå çàêàí÷èâàåòñÿ çà êîíå÷íîå êîëè÷åñòâî õîäîâ, òî
ïîáåäà ïðèñóæäàåòñÿ ãðàáèòåëþ. Äëÿ èçáåæàíèÿ ïóòàíèöû ñ äðóãèìè
âîçìîæíûìè ïðàâèëàìè, ýòà âàðèàöèÿ èãðû íàçûâàåòñÿ â ðàáîòå
ñòîé
ïðî-
C&R-èãðîé.
Êðîìå
ïðîñòîé
C&R-èãðû ñóùåñòâóåò äîâîëüíî ìíîãî å¼ ðàçíîâèä-
íîñòåé, îäíàêî áîëüøèíñòâî èç íèõ ëèøü íåìíîãî äîïîëíÿþò å¼ ïðàâèëà.
Âîò íåêîòîðûå ïðèìåðû ìîäèôèêàöèé èãðû C&R:
1. Èãðà ñ ¾áûñòðûìè¿ ãðàáèòåëÿìè è/èëè ïîëèöåéñêèìè (ò.å. èãðîê
ìîæåò ïåðåäâèãàòü ñâîè ôèøêè âäîëü íåñêîëüêèõ ð¼áåð çà îäèí
õîä)
2. Èãðà ñ íåïîëíîé èíôîðìàöèåé (ïîëèöåéñêèå è ãðàáèòåëü èìåþò
îïðåäåë¼ííûé ¾ðàäèóñ âèäèìîñòè¿)
4
3. Èãðà ñ ¾ðàäèóñîì çàõâàòà¿ (ïîëèöåéñêèå çàõâàòûâàþò ãðàáèòåëÿ
íà ðàñòîÿíèè)
4. ¾Ñòðåëÿþùèé¿ ãðàáèòåëü (è/èëè ïîëèöåéñêèå)
 ñòàòüå [NS14] ñîäåðæèòñÿ áîëåå ïîëíûé ñïèñîê ìîäèôèêàöèé èãðû, à òàêæå îïèñàíèÿ èõ ïðàâèë è äëÿ íåêîòîðûõ èç íèõ äîêàçûâàþòñÿ ñîäåðæàòåëüíûå òåîðåìû (â ÷àñòíîñòè òàì äîêàçûâàåòñÿ íåñêîëüêî
óòâåðæäåíèé ïðî èãðó ñ áûñòðûì ãðàáèòåëåì).
Ðèñ. 1: Ïðèìåð C&R-èãðû ñ äâóìÿ ïîëèöåéñêèìè è îäíèì ãðàáèòåëåì
íà ñëó÷àéíî ñãåíåðèðîâàííîì ñâÿçíîì íåîðèåíòèðîâàííîì ãðàôå.
 äàííîé ðàáîòå áóäåò ðàññìàòðèâàòüñÿ íàèáîëåå ïðîñòàÿ âàðèàöèÿ
èãðû ïðîñòàÿ C&R-èãðà.
 ýòîé ðàáîòå äëÿ ïðîñòîé C&R-èãðû ñòðîÿòñÿ íåêîòîðûå ýìïèðè÷åñêèå àëãîðèòìû (¾ïîòåíöèàëüíûé àëãîðèòì¿) äëÿ óêëîíåíèÿ è ïîèìêè
ãðàáèòåëÿ (¾ñîïðÿæåííûé àëãîðèòì¿), à òàêæå äëÿ íèõ äàþòñÿ íåêîòîðûå ÷èñëîâûå õàðàêòåðèñòèêè (¾ýìïèðè÷åñêîå ïîëèöåéñêîå ÷èñëî¿).
Ïîñòðîåííûé â ðàáîòå ¾ïîòåíöèàëüíûé àëãîðèòì¿ íå ÿâëÿåòñÿ óíèâåðñàëüíûì ðåøåíèåì çàäà÷è, îäíàêî, îí ìîæåò îêàçàòüñÿ ïðèãîäíûì â
5
íåêîòîðûõ ÷àñòíûõ ñëó÷àÿõ.  ÷àñòíîñòè, â ðàáîòå ïîêàçûâàåòñÿ ðàáîòîñïîñîáíîñòü àëãîðèòìà â íàèáîëåå ïðîñòûõ ñëó÷àÿõ: öèêëû, äåðåâüÿ,
ñåòêè, ãðàôû ñ íåêîòîðûìè äðóãèìè õàðàêòåðèñòèêàìè âåðøèí è ìèíèìàëüíûõ öèêëîâ, è ò.ï.  ðàáîòå òàêæå ÷èñëåííûìè ìåòîäàìè ñòðîÿòñÿ
íåêîòîðûå ñòàòèñòèêè äëÿ ñëó÷àéíî ñãåíåðèðîâàííûõ ãðàôîâ.
 ðàìêàõ ðàáîòû ðàçðàáîòàíî ïðèëîæåíèå, ìîäåëèðóþùåå ïîâåäåíèå
ïîëèöåéñêèõ è ãðàáèòåëåé. Ïðèëîæåíèå ñîñòîèò èç òð¼õ ÷àñòåé: îñíîâíîé ìîäóëü game.js (ïðîãðàììà, íàïèñàííàÿ íà ÿçûêå JavaScript), è
äâà ôðîíòåíäà: âåá-ñòðàíè÷êà index.html, èñïîëüçóåìàÿ äëÿ íàãëÿäíîé
âèçóàëèçàöèè èãðû, è ìîäóëü äëÿ çàïóñêà ïðîãðàììû â êîíñîëüíîì ðåæèìå ng.js.
Ðèñ. 2: Ïðèìåð ðàáîòû ïðîãðàììû: âèçóàëèçàöèÿ C&R íà òåññåðàêòå.
Ïðè çàïóñêå â âèçóàëüíîì ðåæèìå ïðîãðàììà ãåíåðèðóåò ãðàô (ëèáî
ñëó÷àéíûé, ëèáî îäèí èç âûáðàííûõ ÷àñòíûõ ñëó÷àåâ) è äà¼ò âîçìîæíîñòü ïîëüçîâàòåëþ äåëàòü õîäû çà ïîëèöåéñêîãî. Õîäû çà ãðàáèòåëÿ
6
äåëàþòñÿ ïî óïîìÿíóòîìó âûøå ïîòåíöèàëüíîìó àëãîðèòìó. Ó ïîëüçîâàòåëÿ åñòü âîçìîæíîñòü òåñòèðîâàòü ¾äâîéñòâåííûé àëãîðèòì¿ ïîëèöåéñêèõ, íàæèìàÿ êíîïêó ¾àâòîõîä¿.
 êîíñîëüíîì ðåæèìå ïðîãðàììà çàïóñêàåòñÿ ïîñðåäñòâîì óòèëèòû
node.js. Êîíñîëüíûé ðåæèì èñïîëüçóåòñÿ äëÿ ïîñòðîåíèÿ ñòàòèñòèê ÷èñëåííûì ìåòîäîì (ò.å. äëÿ çàïóñêà áîëüøîãî êîëè÷åñòâà èãð íà ñëó÷àéíî
ñãåíåðèðîâàííûõ ãðàôàõ è ïîäâåäåíèÿ ñòàòèñòèê).
7
2.1
Ìîòèâàöèÿ
Íà äàííûé ìîìåíò ñóùåñòâóþò òî÷íûå àëãîðèòìû äëÿ ïîèìêè ãðàáèòåëÿ â C&R-èãðå ëèøü â íåêîòîðûõ ÷àñòíûõ ñëó÷àÿõ. Òàê, íàïðèìåð, â
[NW83] ðàññìàòðèâàåòñÿ ñëó÷àé îäíîãî ïîëèöåéñêîãî è ñòðîèòñÿ íåîáõîäèìîå è äîñòàòî÷íîå óñëîâèå ñóùåñòâîâàíèÿ àëãîðèòìà äëÿ ïîèìêè
ãðàáèòåëÿ (êîòîðîå äà¼ò êëþ÷ ê ïîñòðîåíèþ àëãîðèòìà).
 ðàáîòå [AF84] ðàññìàòðèâàåòñÿ ñïîñîá ïîèìêè ãðàáèòåëÿ äâóìÿ ïîëèöåéñêèìè ñ ïîìîùüþ êîíòðîëÿ êàæäûì èç ïîëèöåéñêèõ îäíîãî íàèêðàò÷àéøåãî ïóòè (íà ãðàôàõ, íà êîòîðûõ ýòî âîçìîæíî). Òàê, íàïðèìåð, â ñëó÷àå ñåòêè äîñòàòî÷íî äâóõ ïîëèöåéñêèõ: îäèí êîíòðîëèðóåò
ñòðîêó, äðóãîé ñòîëáåö. Ïîî÷åð¼äíî ñäâèãàÿ êîíòðîëèðóåìûå ñòîëáöû
è ñòðîêè, ãðàáèòåëü ïðèæèìàåòñÿ â óãîë è òàì çàõâàòûâàåòñÿ.
Îäíàêî, ñïîñîá ïðåäëàãàåìûé â [AF84] íå ìîæåò áûòü èñïîëüçîâàí â
îáùåì ñëó÷àå. Ñòîëêíóâøèñü ñ çàäà÷åé C&R-èãð, ìíå â ïåðâóþ î÷åðåäü
ñòàëî èíòåðåñíî, êàê ìîãëè áû âûãëÿäåòü àëãîðèòìû óêëîíåíèÿ èëè ïîèìêè ãðàáèòåëÿ, ðàáîòàþùèå ïóñòü è íå òî÷íî, íî â êàêîé-òî ñòåïåíè
ýôôåêòèâíî íà ïðîèçâîëüíûõ ãðàôàõ è ñ ïðîèçâîëüíûì êîëè÷åñòâîì
ïîëèöåéñêèõ.
 ýòîé ðàáîòå ñòðîÿòñÿ ýìïèðè÷åñêèå àëãîðèòìû äëÿ ïîñòðîåíèÿ ñòðàòåãèé ïîèìêè è óêëîíåíèÿ ãðàáèòåëåì.
8
2.2
Ïðàâèëà èãðû è ïîñòàíîâêà çàäà÷è
Êàê óæå óïîìèíàëîñü â ââåäåíèè, ñóùåñòâóåò îãðîìíîå ìíîæåñòâî âàðèàöèé èãðû ¾ïîëèöåéñêèå è ãðàáèòåëü¿. Äàäèì äåòàëüíîå îïèñàíèå íàèáîëåå ïðîñòîé âàðèàöèè:
Îïðåäåëåíèå 1.
Ïðîñòàÿ
C&R-èãðà.
Ïóñòü, äàí ñâÿçíûé íåîðèåíòèðîâàííûé ãðàô G = G(V, E), ãäå V
ìíîæåñòâî âåðøèí ãðàôà, à E ìíîæåñòâî åãî ð¼áåð.  èãðå äâà ó÷àñòíèêà. Ïåðâûé èç íèõ èãðàåò çà ïîëèöåéñêèõ, âòîðîé çà ãðàáèòåëÿ. Äëÿ
êðàòêîñòè â íåêîòîðûõ ñëó÷àÿõ äëÿ îáîçíà÷åíèÿ èãðîêîâ áóäóò èñïîëüçîâàòüñÿ ñîêðàùåíèÿ C (cops ïîëèöåéñêèå), R (robber ãðàáèòåëü). Ó
C èìååòñÿ k ôèøåê, à ó R îäíà (÷èñëî ôèøåê ó êàæäîãî èç èãðîêîâ â
òå÷åíèå èãðû íå ìåíÿåòñÿ). Îò íà÷àëà è äî êîíöà èãðû îáà èãðîêà ïîëíîñòüþ âèäÿò òåêóùåå ñîñòîÿíèå èãðû, ò.å. ýòî èãðà ñ ïîëíîé èíôîðìàöèåé.
Èãðîêè äåëàþò õîäû ïî î÷åðåäè.
 ïåðâûé õîä, îñíîâûâàÿñü òîëüêî íà ãðàôå G, C ðàññòàâëÿåò ñâîè
ôèøêè C = (c1 , ..., ck ), ãäå c1 , ..., ck ∈ V â ïðîèçâîëüíûå âåðøèíû ãðàôà.
Âî âòîðîé õîä, îñíîâûâàÿñü íà ãðàôå G è ðàñïîëîæåíèè ôèøåê ñîïåðíèêà, R âûáèðàåò ïðîèçâîëüíóþ âåðøèíó r ∈ V äëÿ ñâîåé ôèøêè. Âî âñå
ïîñëåäóþùèå õîäû èãðîêè äâèãàþò ñâîè ôèøêè âäîëü ð¼áåð ãðàôà. Çà
ñâîé õîä C ìîæåò ïîäâèíóòü âñå ñâîè ôèøêè, à r òîëüêî ñâîþ åäèíñòâåííóþ. Äîïóñòèìûì òàêæå ñ÷èòàåòñÿ îñòàâèòü îäíó èëè íåñêîëüêî ôèøåê
íà ìåñòå. Äâå èëè áîëåå ôèøåê C ìîãóò çàíèìàòü îäíó è òó æå âåðøèíó.
Èãðà çàêàí÷èâàåòñÿ â ìîìåíò, êîãäà õîòÿ áû îäíà èç ci îêàçûâàåòñÿ ðàâíîé r, ò.å. êîãäà îäèí èç ïîëèöåéñêèõ îêàçûâàåòñÿ íà òîé æå âåðøèíå,
÷òî è ãðàáèòåëü. Åñëè ãðàáèòåëü áûë ïîéìàí, òî ïîáåäà ïðèñóæäàåòñÿ
ïîëèöåéñêèì. Åñëè èãðà íå çàêàí÷èâàåòñÿ çà êîíå÷íîå êîëè÷åñòâî õîäîâ,
òî ïîáåäà ïðèñóæäàåòñÿ ãðàáèòåëþ.
Îïðåäåëåíèå 2.
Ñòðàòåãèÿ
SR
äëÿ
R åñòü ïàðà (IR , σR ), ãäå IR ∈ V
íà÷àëüíàÿ ïîçèöèÿ ãðàáèòåëÿ, è σR : V k × V → V ôóíêöèÿ, êîòîðàÿ
ñîïîñòàâëÿåò íîâóþ ïîçèöèþ ãðàáèòåëÿ r0 êàæäîé êîíôèãóðàöèè èãðû
S = (c1 , ..., ck , r) ∈ V k × V .
9
Îïðåäåëåíèå 3.
Ñòðàòåãèÿ äëÿ
C åñòü ïàðà SC = (IC , σC ), ãäå IC ∈
V íà÷àëüíûå ïîçèöèè k ïîëèöåéñêèõ, è σC : V k × V → V k ôóíêöèÿ, êîk
òîðàÿ ñîïîñòàâëÿåò íîâûå ïîçèöèè ïîëèöåéñêèõ (c01 , ..., c0k ) êàæäîé êîíôèãóðàöèè èãðû S = (c1 , ..., ck , r) ∈ V k × V
Îïðåäåëåíèå 4.
Ïîëèöåéñêîå ÷èñëî
(cop number) cn(G) ñâÿçíîãî ãðàôà
åñòü ìèíèìàëüíîå êîëè÷åñòâî ïîëèöåéñêèõ íåîáõîäèìîå äëÿ äîñòîâåðíîé ïîèìêè R, â íåçàâèñèìîñòè îò ïîâåäåíèÿ R.
Ïîëèöåéñêèì ÷èñëîì
íåñâÿçíîãî ãðàôà áóäåì íàçûâàòü ñóììó ïîëèöåéñêèõ ÷èñåë åãî êîìïîíåíò ñâÿçíîñòè.
Çàìåòèì, ÷òî ïîëèöåéñêîå ÷èñëî ÿâëÿåòñÿ õàðàêòåðèñòèêîé ãðàôà è
íå çàâèñèò îò ñòðàòåãèé èãðîêîâ.
 äàííîé ðàáîòå ñòàâèòñÿ çàäà÷à ïîñòðîåíèÿ àëãîðèòìîâ óêëîíåíèÿ
äëÿ ãðàáèòåëÿ ïðè cn(G) > |C|.
10
3
Íåêîòîðûå ôàêòû î ïîëèöåéñêîì ÷èñëå
Ïðèâåä¼ì íåêîòîðûå èçâåñòíûå ôàêòû î ïîëèöåéñêîì ÷èñëå.  ýòîì ðàçäåëå âñå óòâåðæäåíèÿ ïðèâîäÿòñÿ áåç äîêàçàòåëüñòâ, íî ïðè ýòîì êî âñåì
äàíû ññûëêè íà èñòî÷íèê, â êîòîðîì ýòè äîêàçàòåëüñòâà ïðè íåîáõîäèìîñòè ìîæíî íàéòè.
Îïðåäåëåíèå 5. Ðîä ãðàôà (ñì. [NS14])
Ðîä ãðàôà åñòü ìèíèìàëüíûé ðîä îðèåíòèðîâàííîãî ìíîãîîáðàçèÿ, íà êîòîðîì ãðàô ìîæíî ïðåäñòàâèòü áåç ñàìîïåðåñå÷åíèé (ò.å. áåç
ïåðåñå÷åíèé åãî ð¼áåð).  ñâîþ î÷åðåäü ðîä îðèåíòèðîâàííîãî ìíîãîîáðàçèÿ (èëè ðîä ïîâåðõíîñòè) åñòü òàêîå ÷èñëî n, ÷òî ýòà ïîâåðõíîñòü
ãîìåîìîðôíà ñôåðå ñ n ðó÷êàìè.
Óòâåðæäåíèå 1. (ñì. [NS14])
Åñëè G äåðåâî, òî cn(G) = 1.
Óòâåðæäåíèå 2. (ñì. [NS14])
Åñëè G öèêë è |G| > 3, òî cn(G) = 2.
Óòâåðæäåíèå 3. (ñì. [NS14])
Äëÿ ñåòêè cn(G) < 3.
Óòâåðæäåíèå 4. (ñì. [AF84])
Åñëè G ïëàíàðíûé ãðàô, òî cn(G) < 4.
Óòâåðæäåíèå 5. (ñì. [Sch01])
Äëÿ ëþáîãî ãðàôà ðîäà g , cn(G) ≤
3
g + 3.
2
Íà äàííûé ìîìåíò îöåíêà ïîëèöåéñêîãî ÷èñëà ÷åðåç ðîä ãðàôà ÿâëÿåòñÿ îäíîé èç ñàìûõ ýôôåêòèâíûõ (ñðåäè äîêàçàííûõ).
Ãèïîòåçà 1. (ïîêà íå äîêàçàíà) (ñì. [NS14])
Äëÿ ëþáîãî ãðàôà ðîäà g , cn(G) ≤ g + 3.
Óòâåðæäåíèå 6. (ñì. [NS14])
Äëÿ ëþáîãî N ñóùåñòâóåò ãðàô ñ cn(G) áîëüøèì N .
11
Îïðåäåëåíèå 6. Îáõâàò ãðàôà (ñì. [NS14])
Îáõâàòîì ãðàôà
girth(G) íàçîâ¼ì ìèíèìàëüíóþ äëèíó åãî èíäóöè-
ðîâàííîãî öèêëà.
Óòâåðæäåíèå 7. (ñì. [Fra87a])
Åñëè G ãðàô ñ ìèíèìàëüíîé ñòåïåíüþ âåðøèí δ è girth(G) ≥ 5,
òîãäà cn(G) ≥ δ
Ãèïîòåçà 2. Ãèïîòåçà Ìýéíåëà (ñì. [BB12])
Åñëè G ãðàô ñ ìèíèìàëüíîé ñòåïåíüþ âåðøèí δ è girth(G) ≥ 5,
òîãäà cn(G) ≥ δ
Îïðåäåëåíèå 7. Ëîâóøêà (pitfall) [AF84]
Íàçîâ¼ì âåðøèíó p ëîâóøêîé, òîãäà è òîëüêî òîãäà, êîãäà ∃d : N (p) ∪
p ⊂ N (d).
Ìîæíî ñêàçàòü, ÷òî ëîâóøêà ýòî âåðøèíà êîòîðàÿ âìåñòå ñî âñåìè
ñâîèìè ñîñåäÿìè íàõîäèòñÿ ¾ïîä óäàðîì¿ èç íåêîòîðîé âåðøèíû d.
Òåîðåìà 1. Òåîðåìà Àéãíåðà-Ôðîìà (î ðåäóöèðîâàíèè ãðàôà) [AF84]
Ïîëèöåéñêîå ÷èñëî ãðàôà G ðàâíî åäèíèöå òîãäà è òîëüêî òîãäà, êîãäà ïîî÷åð¼äíî îòíèìàÿ îò ãðàôà ëîâóøêè (è ñâîáîäíûå ð¼áðà), ãðàô
ìîæíî ðåäóöèðîâàòü äî òî÷êè.
12
4
Ïîñòðîåíèå àëãîðèòìîâ óêëîíåíèÿ
 ýòîé ñåêöèè ñòðîÿòñÿ àëãîðèòìû óêëîíåíèÿ è ïîèìêè. Ïîä
ìîì óêëîíåíèÿ
àëãîðèò-
áóäåì ïîäðàçóìåâàòü ôóíêöèþ, ñîïîñòàâëÿþùóþ ïðîèç-
âîëüíîìó ãðàôó íåêîòîðîå ìíîæåñòâî ñòðàòåãèé íà ýòîì ãðàôå:
AR : G 7→ {SR }
àíàëîãè÷íî äëÿ C , àëãîðèòì ïîèìêè åñòü îòîáðàæåíèå âèäà:
AC : G 7→ {SC }
4.1
Ïðîñòåéøåå óêëîíåíèå ìåòîäîì ïîòåíöèàëîâ
Îäíà èç íàèáîëåå èíòåðåñíûõ çàäà÷, ñâÿçàííûõ ñ èãðàìè C&R ýòî
çàäà÷à ïîèñêà îïòèìàëüíûõ (ò.å. ïðèíîñÿùèõ ïîáåäó èãðîêó íà òåõ ãðàôàõ, íà êîòîðûõ ýòî âîçìîæíî) ñòðàòåãèé. Êàê ïîêàçûâàåò ïðàêòèêà,
çàäà÷à ïîèñêà îïòèìàëüíîé ñòðàòåãèè íà äîñòàòî÷íî áîëüøèõ ãðàôàõ
íå ïîääà¼òñÿ òî÷íîìó ðåøåíèþ â îáùåì ñëó÷àå (ïîêà îáùåãî ðåøåíèÿ
äàþùåãî ðåçóëüòàò çà êîðîòêîå âðåìÿ íèêòî íå íàøåë). Ïîëíûì ïåðåáîðîì èñêàòü ñòðàòåãèè ìîæíî òîëüêî äëÿ î÷åíü íåáîëüøèõ ãðàôîâ è ïðè
íå áîëüøîì êîëè÷åñòâå ïîëèöåéñêèõ, òàê êàê ñëîæíîñòü çàäà÷è îáûñòðî ðàñò¼ò ïðè óâåëè÷åíèè ïàðàìåòðîâ çàäà÷è. Íàïðèìåð, äëÿ ãðàôà ñ
çàäàííîé ìèíèìàëüíîé ñòåïåíüþ âåðøèíû, êàê íå òðóäíî óáåäèòüñÿ, êîëè÷åñòâî ñòðàòåãèé îöåíèâàåòñÿ ñëåäóþùèì îáðàçîì:
Êîëè÷åñòâî ñòðàòåãèé ≥ (min deg(v))(|V |
|C|+1
)
v∈V
Ó÷èòûâàÿ íàñòîëüêî áûñòðî ðàñòóùóþ îöåíêó äëÿ êîëè÷åñòâà ñòðàòåãèé, åñòåñòâåííî âîçíèêàåò âîïðîñ î ïîèñêå ýìïèðè÷åñêîãî àëãîðèòìà,
êîòîðûé äàâàë áû õîðîøèå ðåçóëüòàòû â ñðåäíåì èëè õîòÿ áû â êàêèõ-òî
÷àñòíûõ ñëó÷àÿõ.
Ïåðåä òåì êàê ñòðîèòü àëãîðèòì, ìîäåëèðóþùèé ïîâåäåíèå ãðàáèòåëÿ (èëè ãåíåðèðóþùèé ñòðàòåãèþ), ñäåëàåì íåñêîëüêî çàìå÷àíèé. Âîïåðâûõ, åñëè ãðàáèòåëü â ñâîé õîä ðåøàåò ïîäâèíóòü ñâîþ ôèøêó èç
îäíîé âåðøèíû â äðóãóþ, çíà÷èò ïîçèöèÿ ïîñëå åãî õîäà äëÿ íåãî
ëåå ïðåäïî÷òèòåëüíà
áî-
. Èíà÷å ãîâîðÿ, â ìíîæåñòâå âñåõ ïîçèöèé èãðû
13
ñóùåñòâóåò íåêîòîðûé ÷àñòè÷íûé ïîðÿäîê (âîçìîæíî, íåñòðîãèé), ïðè÷åì êàæäîé ñòðàòåãèè ñîîòâåòñòâóåò ñâîé ÷àñòè÷íûé ïîðÿäîê. Àíàëîãè÷íî íàîáîðîò, åñëè ó íàñ åñòü ÷àñòè÷íûé ïîðÿäîê, äàþùèé âîçìîæíîñòü
ñðàâíèâàòü ñîñåäíèå ïîçèöèè (ò.å. òàêèå, ÷òî èç îäíîé ìîæíî ïåðåéòè
â äðóãóþ õîäîì ãðàáèòåëÿ), òî òàêîìó ïîðÿäêó, î÷åâèäíî, ñîîòâåòñòâóåò íåêîòîðàÿ ñòðàòåãèÿ (â ÷àñòíîñòè, åñëè ìíîæåñòâî ñòðàòåãèé âïîëíå
óïîðÿäî÷åíî).
Äëÿ ïðîñòîòû â ðàáîòå ðàññìàòðèâàþòñÿ ñòðàòåãèè, ïîðîæäàåìûå
ïîëíûì ïîðÿäêîì â ìíîæåñòâå ïîçèöèé.
Èòàê, ïóñòü ó íàñ åñòü âïîëíå óïîðÿäî÷åííîå ìíîæåñòâî ïîçèöèé èãðû. Òàê êàê èãðîâûõ ïîçèöèé êîíå÷íîå êîëè÷åñòâî, òî ìû ìîæåì ñîïîñòàâèòü êàæäîé ïîçèöèè íåêîòîðîå ÷èñëî (î÷åâèäíî, ÷òî ìîæíî öåëîå, íî
äàëåå ìíå áóäåò óäîáíåå èñïîëüçîâàòü âåùåñòâåííûå ÷èñëà). Ýòî ÷èñëî,
ñîîòâåòñòâóþùåå èãðîâîé ïîçèöèè áóäåì íàçûâàòü
.
îöåíêîé ïîçèöèè
Ñëåäóþùåå çàìå÷àíèå çàêëþ÷àåòñÿ â òîì, ÷òî íà ïðàêòèêå äëÿ ìîäåëèðîâàíèÿ C&R (ò.å. ïðè ñîçäàíèè ïðîãðàììû), äàæå ïðåäïîëàãàÿ äåòåðìèíèðîâàííîñòü õîäîâ èãðîêîâ (ò.å. òî, ÷òî îíè õîäÿò â ñîîòâåòñòâèè
ñ íåêîòîðîé ñòðàòåãèåé), íàì âîâñå íå íóæíî çíàòü èõ ñòðàòåãèþ öåëèêîì, òàê êàê äàëåêî íå âñå èãðîâûå ïîçèöèè ìîãóò îêàçàòü âîçìîæíû
(ïðè ôèêñèðîâàííîé ïàðå ñòðàòåãèé èãðîêîâ). Èíà÷å ãîâîðÿ, âìåñòî òîãî,
÷òîáû äåëàòü ïðîãðàììó, êîòîðàÿ ñòðîèò ñòðàòåãèþ, êîòîðàÿ êàê ìíîæåñòâî áóäåò ñîäåðæàòü äîâîëüíî áîëüøîå êîëè÷åñòâî ýëåìåíòîâ, óäîáíåå
èìåòü ïðîãðàììó, êîòîðàÿ áóäåò âû÷èñëÿòü ñëåäóþùèé õîä, íà îñíîâå
òåêóùåé èãðîâîé ñèòóàöèè ïî õîäó èãðû, ïîäîáíî òîìó, êàê øàõìàòíûå
êîìïüþòåðû íå ïðîñ÷èòûâàþò âñå âîçìîæíûå èãðîâûå ñèòóàöèè, òðàòÿ
âû÷èñëèòåëüíûå ìîùíîñòè ëèøü íà òå èç íèõ, êîòîðûå ðåàëüíî ïðîèçîøëè â èãðå.
Îïðåäåëåíèå 8.
Ôóíêöèåé îöåíêè ïîçèöèè
íàçîâåì ïðîèçâîëüíîå îòîá-
ðàæåíèå èç W : V × V → R Ò.å. îòîáðàæåíèå, ñîïîñòàâëÿþùåå âåùåk
ñòâåííîå ÷èñëî êàæäîé èãðîêîâ ïîçèöèè.
Îïðåäåëåíèå 9.
Ïîòåíöèàëîì
PC âåðøèíû v ∈ V ïðè ôèêñèðîâàí-
íîì ðàñïîëîæåíèè ïîëèöåéñêèõ C = (c1 , ..., ck ) áóäåì íàçûâàòü çíà÷åíèå
ôóíêöèè îöåíêè ïîçèöèè W íà (C, v). Ò.å. PC (v) = W (C, v), ïðè ôèêñèðîâàííûõ c1 , ..., ck .
14
Îïðåäåëåíèå 10.
Ïîòåíöèàëüíûé àëãîðèòì
(äëÿ ãðàáèòåëÿ)
Ïóñòü ðàññìàòðèâàåòñÿ ãðàô G è ôóíêöèÿ îöåíêè ïîçèöèè W . Íà
êàæäîì øàãå áóäåì âûáèðàòü õîä ñëåäóþùèì îáðàçîì:
1. Åñëè äåëàåì ïåðâûé õîä:
1.1. Ñ ïîìîùüþ ôóíêöèè îöåíêè ïîçèöèè W c÷èòàåì ïîòåíöèàëû âñåõ âåðøèí è õîäèì â âåðøèíó ñ ìàêñèìàëüíûì ïîòåíöèàëîì
2. Åñëè äåëàåì íå ïåðâûé õîä:
2.1. Ñ ïîìîùüþ W ñ÷èòàåì ïîòåíöèàëû ñîñåäíèõ ñ ãðàáèòåëåì
âåðøèí v ∈ N (r) è âåðøèíû r
2.2. Åñëè ïîòåíöèàë r áîëüøå ïîòåíöèàëîâ ñîñåäíèõ âåðøèí, òî
ïðîïóñêàåì õîä
2.3. Èíà÷å âûáèðàåì ñîñåäíþþ âåðøèíó ñ ìàêñèìàëüíûì ïîòåíöèàëîì è äåëàåì õîä â íå¼
Çàìå÷àíèå 1.  ïîòåíöèàëüíîì àëãîðèòìå, î÷åâèäíî, ïðèñóòñòâóåò íåêî-
òîðûé ïðîèçâîë, ñâÿçàííûé ñ òåì, ÷òî ïîòåíöèàëû íåñêîëüêèõ ñîñåäíèõ
âåðøèí ìîãóò ñîâïàäàòü. Ìîæíî ñêàçàòü, ÷òî êàæäîìó ïîòåíöèàëüíîìó
àëãîðèòìó ñîîòâåòñòâóåò íåêîòîðîå ìíîæåñòâî ñòðàòåãèé.
Îïðåäåëåíèå 11.
Íàçîâåì
Àëãîðèòì 1
Àëãîðèòìîì 1
(äëÿ ãðàáèòåëÿ)
ïîòåíöèàëüíûé àëãîðèòì äëÿ êîòîðîãî
PC (v) = min dist(v, ci ),
ci ∈C
ãäå dist(v1 , v2 ), v1 , v2 ∈ V åñòü ðàññòîÿíèå îò v1 äî v2 , ò.å. ÷èñëî ð¼áåð
êðàò÷àéøåãî ïóòè ñîåäèíÿþùåãî ýòè äâå âåðøèíû è ïîëíîñòüþ ëåæàùåãî â ãðàôå.
 ýòîì àëãîðèòìå ïîòåíöèàë êàæäîé âåðøèíû ðàâåí ðàññòîÿíèþ îò
ýòîé âåðøèíû äî áëèæàéøåãî ïîëèöåéñêîãî.
Òåîðåìà 2. Ãðàáèòåëü, èñïîëüçóþùèé ¾Àëãîðèòì 1¿ íà öèêëå äëèíû
áîëüøå 3-õ ïðè îäíîì ïîëèöåéñêîì, íå ìîæåò áûòü ïîéìàí
15
I Òàê êàê äëèíà öèêëà áîëüøå èëè ðàâíà ÷åòûð¼ì, òî ïîòåíöèàë ïîçèöèè R ïîñëå ïåðâîãî õîäà ãðàáèòåëÿ áóäåò êàê ìèíèìóì 2 (íàïîìíèì,
÷òî ïåðâûé õîä ãðàáèòåëÿ äåëàåòñÿ ïîñëå ïåðâîãî õîäà ïîëèöåéñêîãî).
Ïðè ýòîì ïîñëå ïåðâîãî õîäà ãðàáèòåëÿ r áóäåò íàõîäèòñÿ íà ìàêñèìàëüíîì óäàëåíèè îò c1 (ïî îïðåäåëåíèþ ïîòåíöèàëüíîãî àëãîðèòìà).
Î÷åâèäíî, ÷òî ïîñëå ëþáîãî õîäà C âåðøèíà ñ ìàêñèìàëüíûì ïîòåíöèàëîì áóäåò ëèáî r ëèáî ñîñåäíåé âåðøèíîé è ïî îïðåäåëåíèþ
1
àëãîðèòìà
R çàéì¼ò å¼ ñëåäóþùèì õîäîì (âåðøèí ñ ìàêñèìàëüíûì ïîòåíöèàëîì
ìîæåò áûòü äâå, íî ýòî ñîâåðøåííî íåâàæíî â äàííîì ñëó÷àå). Òàêèì
îáðàçîì, ïîñëå õîäà R ïîòåíöèàë åãî òåêóùåé ïîçèöèè âñåãäà áóäåò ìàêñèìàëüíûì. Òàê êàê C çà îäèí õîä íå ìîæåò óìåíüøèòü ðàññòîÿíèå äî
R áîëüøå ÷åì íà åäèíèöó, òî ïîòåíöèàë âåðøèíû çàíèìàåìîé R âñåãäà
áóäåò êàê ìèíèìóì ðàâåí äâóì.
Çàìå÷àíèå 2. Ïåðåä òåì, êàê äîêàçûâàòü ñëåäóþùóþ òåîðåìó çàìåòèì,
÷òî âñÿêàÿ ñåòêà ñîäåðæèò ïðîñòîé öèêë äëèíû 4, áîëåå òîãî, âñÿêîå
ðåáðî ñåòêè ñîäåðæèòñÿ â íåêîòîðîì ïðîñòîì öèêëå äëèíû 4, è ÷òî â
ñåòêå íåò öèêëîâ äëèíû 3.
Òåîðåìà 3. Ãðàáèòåëü, èñïîëüçóþùèé ¾àëãîðèòìà 1¿ íà ñåòêå íå ìîæåò
áûòü ïîéìàí îäíèì ïîëèöåéñêèì
I Òàê êàê ñåòêà ñîäåðæèò ïðîñòîé öèêë äëèíû 4, òî, î÷åâèäíî, ÷òî
ïîñëå ïåðâîãî õîäà ãðàáèòåëÿ åãî ïîòåíöèàë áóäåò êàê ìèíèìóì ðàâåí
äâóì. Äàëåå, ïóñòü ïîñëå íåêîòîðîãî õîäà ïîëèöåéñêèõ ïîòåíöèàë r ñòàë
ðàâåí åäèíèöå, ò.å. r è c1 ñîåäèíåíû ðåáðîì. Íî â ýòîì ñëó÷àå C è r áóäóò
íàõîäèòñÿ â îäíîì öèêëå äëèíû 4. Ïîéäåì â ñîñåäíþþ ñ r âåðøèíó v0 â
ýòîì öèêëå (íî íå ðàâíóþ c1 ). Òàê êàê â ñåòêå íåò öèêëîâ äëèíû 3, òî C íå
ñìîæåò çàõâàòèòü R ñëåäóþùèì õîäîì.  ïðîòèâíîì ñëó÷àå ïîëó÷àåì,
÷òî c1 ↔ R, c1 ↔ v0 , R ↔ v0 , ò.å. èìååì öèêë äëèíû òðè, ÷åãî íå ìîæåò
áûòü (ãäå ïîä îáîçíà÷åíèåì v1 ↔ v2 ïîäðàçóìåâàåì, ÷òî âåðøèíû v1 è v2
ñîåäèíåíû ðåáðîì). Òàêèì îáðàçîì, ïîòåíöèàë r ïîñëå êàæäîãî õîäà R
áóäåò íå ìåíüøå äâóõ, è, ñëåäîâàòåëüíî, R íèêîãäà íå áóäåò ïîéìàí.
16
Òåîðåìà 4. Ãðàáèòåëü, èñïîëüçóþùèé
àëãîðèòì 1
íå ìîæåò áûòü ïîé-
ìàí íà ãðàôå ñ min deg(v) = k, min girth(v) > 5, ïðè êîëè÷åñòâå ïîëèöåéñêèõ ðàâíîì k .
v∈V
v∈V
I Êàê ïîêàçàíî â [NS14], íà òàêîì ãðàôå ïðè ëþáîé èãðîâîé ñèòóàöèè áóäåò êàê ìèíèìóì îäíà âåðøèíà v ∈ V , â êîòîðóþ R ìîæåò
ïîõîäèòü, è C íå ñìîæåò çàõâàòèòü åãî ñëåäóþùèì õîäîì. Îòñþäà ñëåäóåò, ÷òî âåðøèíà v , ÷òî min dist(ci , v) = PC (v) > 1, îòñþäà ñëåäóåò, ÷òî
ci ∈C
ðàññòîÿíèå îò ãðàáèòåëÿ äî ïîëèöåéñêèõ âñåãäà áóäåò áîëüøå åäèíèöû.
Êàê ïîêàçûâàåò ïðàêòèêà, ïðîñòîé ïîòåíöèàëüíûé àëãîðèòì äàëåêî
íå âñåãäà áûâàåò ýôôåêòèâåí.
Ïðèìåð 1. Ïðèìåð ãðàôîâ, íà êîòîðûõ Àëãîðèòì 1 íå ðàáîòàåò
Ðèñ. 3: Ïðèìåð ãðàôîâ, íà êîòîðûõ Àëãîðèòì 1 íå ðàáîòàåò.
Âèäíî, ÷òî åñëè ôèøêà C áóäåò íàõîäèòüñÿ íà âåðøèíå 3 (çåëåíàÿ),
òî íàèáîëüøèé ïîòåíöèàë áóäåò ó âåðøèíû 1 (êðàñíàÿ) è R, ïðè âîçìîæíîñòè, å¼ çàéì¼ò. Ïîñëå òîãî, êàê C ïîäâèíåò ñâîþ ôèøêó â âåðøèíó
2 (ñèíÿÿ), ó R óæå íå áóäåò âîçìîæíîñòè èçáåæàòü ïîèìêè è îí áóäåò
çàõâà÷åí ñëåäóþùèì õîäîì.
17
4.2
Óëó÷øåíèå àëãîðèòìà äëÿ íåêîòîðûõ ÷àñòíûõ ñëó÷àåâ
Îïðåäåëåíèå 12. Àëãîðèòì 2
Ââåä¼ì îáîçíà÷åíèÿ:
∆n (v) =
X
EPn P (vi ),
vi ∈N (v)
ãäå EN è ïîñëåäîâàòåëüíîñòü EPn åñòü íåêîòîðûé íàáîð âåùåñòâåííûõ ýìïèðè÷åñêèõ êîýôôèöèåíòîâ.
Àëãîðèòìîì 2
íàçîâåì ïîòåíöèàëüíûé àëãîðèòì ñ ôóíêöèåé PC (v),
êîòîðàÿ ñ÷èòàåòñÿ ñëåäóþùèì îáðàçîì:
1. Íà ïåðâîì øàãå ïðèñâîèì êàæäîé âåðøèíå v ïîòåíöèàë p1 (v) =
min dist(v, ci )
ci ∈C
2. Ïîâòîðèì ñëåäóþùèå äåéñòâèÿ EN ðàç (îáîçíà÷èâ íîìåð ïîâòîðåíèÿ áóêâîé n):
Íàçíà÷èì íîâûé ïîòåíöèàëû Pn (v) = Pn−1 (V )−∆(v)+
P
∆(vi )
vi ∈N (v)
3.  êà÷åñòâå êîíå÷íûõ ïîòåíöèàëîâ âîçüìåì ïîëó÷åííûå çíà÷åíèÿ
Pn (v), ò.å. PC (v) := Pn (v)
Àëãîðèòì 2
åñòü ïî ñóòè ìîäèôèöèðîâàííûé àëãîðèòì 1 ñ ¾ïåðå-
òåêàíèåì ïîòåíöèàëîâ¿. Èäåÿ àëãîðèòìà 2 çàêëþ÷àåòñÿ â òîì, ÷òî åñëè
ðÿäîì ñ íåêîòîðîé âåðøèíîé ¾ìíîãî¿ âåðøèí ñ ¾áîëüøèì¿ ïîòåíöèàëîì,
òî è ó íå¼ äîëæåí áûòü ïîòåíöèàë íåñêîëüêî áîëüøå, ÷åì ó âåðøèíû,
ó êîòîðîé õîòü è òîæå ðàññòîÿíèå äî áëèæàéøåãî ïîëèöåéñêîãî, íî íå
èìåþùåé ñîñåäåé ñ ¾áîëüøèìè¿ ïîòåíöèàëàìè.
Ýòî, êàçàëîñü áû, íåáîëüøîå èçìåíåíèå äà¼ò âîçìîæíîñòü R íå çàõîäèòü â òóïèêè, â òî âðåìÿ êàê ¾àëãîðèòì 1¿ ïðèâîäèò ê òîìó, ÷òî R,
óáåãàÿ, íåïðåìåííî çàõîäèò â òóïèê, åñëè åñòü òàêàÿ âîçìîæíîñòü.
Îïðåäåëåíèå 13. Òóïèê
18
Íàçîâåì âåðøèíó v
òóïèêîì
â äâóõ ñëó÷àÿõ:
1. Åñëè deg(v) = 1
2. Åñëè äëÿ âåðøèíû v ìíîæåñòâî ñîñåäíèõ íå òóïèêîâûõ âåðøèí
ñîäåðæèò íå áîëåå îäíîãî ýëåìåíòà
Çàìå÷àíèå 3. Î÷åâèäíî, òóïèê ÿâëÿåòñÿ ÷àñòíûì ñëó÷àåì ëîâóøêè
Îáîçíà÷èì ÷åðåç G0 (V 0 , E 0 ) ãðàô, êîòîðûé ïîëó÷àåòñÿ èç G(V, E) ïîñðåäñòâîì ðåäóöèðîâàíèÿ âñåõ ëîâóøåê. Ïîêàæåì, ÷òî ïðè k = 1 è
cn(G) > 1 äëÿ R ñóùåñòâóåò ýôôåêòèâíàÿ ñòðàòåãèÿ, ïðè êîòîðîé îí
íèêîãäà íå çàõîäèò â ëîâóøêè (ìîæíî ñêàçàòü, ÷òî õîäèòü â ëîâóøêè
áåñìûñëåííî, è R ìîæåò ïåðåäâèãàòüñÿ òîëüêî ïî ðåäóöèðîâàííîìó ãðàôó G0 ).
Òåîðåìà 5. Åñëè cn(G) > 1, òî ñóùåñòâóåò âûèãðûøíàÿ ñòðàòåãèÿ äëÿ
R, ïðè êîòîðîé â êàæäûé ìîìåíò èãðû R ∈ V 0
I Ïðåäïîëîæèì, ÷òî òàêîé ñòðàòåãèè íåò. Íî òîãäà cn(G0 ) = 1, à
çíà÷èò â G0 åñòü ëîâóøêè, ÷òî ïðîòèâîðå÷èò îïðåäåëåíèþ G0 .
Îïðåäåëåíèå 14.
Àëãîðèòì 3
Àëãîðèòì 3
îïðåäåëèì êàê ìîäèôèêàöèþ Àëãîðèòìà 2, â êîòîðîé
ïîñëå ïîäñ÷¼òà ïîòåíöèàëîâ âåðøèí ïîòåíöèàë êàæäîé âåðøèíû äîìíîæàåòñÿ íà íåêîòîðûé ýìïèðè÷åñêèé ïàðàìåòð EPp , â ñëó÷àå, åñëè ýòà
âåðøèíà ÿâëÿåòñÿ òóïèêîì.
 ñëó÷àå, åñëè EPp = 0, Àëãîðèòì 3, ïî ñóòè ðåäóöèðóåò ãðàô, îòíèìàÿ îò íåãî òóïèêè. Òàêîé ïîäõîä ìîæåò îêàçàòüñÿ ýôôåêòèâíûì â
ñëó÷àå, åñëè cn(G) > 1, îäíàêî, íóæíî ó÷èòûâàòü, ÷òî, åñëè cn(G) = 1,
òî ìîæåò îêàçàòüñÿ, ÷òî âñå âåðøèíû ãðàôà îêàæóòñÿ òóïèêàìè (íàïðèìåð, åñëè G äåðåâî). Íà ïðàêòèêå, ÷òîáû íå èìåòü äåëà ñ ïóñòûìè
ãðàôàìè, áûâàåò óäîáíåå ïîëîæèòü EPp íåêîòîðîìó íåáîëüøîìó ÷èñëó.
19
4.3
Ñîïðÿæåííûé àëãîðèòì (äëÿ ïîëèöåéñêèõ)
Âåðîÿòíî, ñàìûì èíòåðåñíûì äîñòèæåíèåì ýòîé ðàáîòû ÿâëÿåòñÿ ¾äâîéñòâåííûé àëãîðèòì¿ äëÿ ïîëèöåéñêèõ, êîòîðûé ìîæíî ïîñòðîèòü êàê
òîëüêî åñòü êàêîé-òî àëãîðèòì äëÿ ãðàáèòåëÿ ñ îöåíêîé ïîçèöèè. Èäåÿ
äâîéñòâåííîãî àëãîðèòìà â òîì, ÷òî êàæäûì ñâîèì õîäîì C ìèíèìèçèðóåò îöåíêó ïîçèöèè ïîñëå ñëåäóþùåãî õîäà R.
Îïðåäåëåíèå 15.
Äâîéñòâåííûé àëãîðèòì
Ïåðâûé õîä äâîéñòâåííîãî àëãîðèòìà îïðåäåëÿåòñÿ ñëåäóùèì îáðàçîì: Îáîçíà÷èì ìàêñèìàëüíûé ïîòåíöèàë ïðè ôèêñèðîâàííîé ðàññòàíîâêå ïîëèöåéñêèõ ÷åðåç M (C):
M (C) = max PC (v).
v∈V
Äàëåå íàéäåì ìèíèìóì ýòîé ôóíêöèè ïî âñåì âîçìîæíûì C ∈ V k
è ñäåëàåì ñîîòâåòñòâóþùèé õîä. Ïîñëåäóþùèå õîäû áóäåì äåëàòü ïî
ñëåäóþùåìó ïðèíöèïó:
Ïóñòü C 0 = (c01 , ..., c0n ) îäíî èç ðàñïîëîæåíèé ïîëèöåéñêèõ òàêîå, ÷òî
(èõ ìîæåò áûòü íåñêîëüêî):
PC 0 (σR (C 0 , r)) = 00min PC 00 (σR (C 00 , r)),
C ∈N (c)
ãäå C 0 ∈ N (C), à N (C) ìíîæåñòâî âîçìîæíûõ êîíôèãóðàöèé ïîëèöåéñêèõ ïîñëå îäíîãî èõ õîäà. Òîãäà èç ïîçèöèè C äåëàåì õîä â C 0 .
Çàìå÷àíèå 4. Òàê æå êàê è ïîòåíöèàëüíûé àëãîðèòì, äâîéñòâåííûé
àëãîðèòì ñîäåðæèò íåêîòîðûé ïðîèçâîë, ñâÿçàííûé ñ òåì, ÷òî ðàçíûå
èãðîâûå ñèòóàöèè ìîãóò èìåòü îäíó è òó æå îöåíêó ïîçèöèè. Ìîæíî
ñêàçàòü, ÷òî äâîéñòâåííîìó àëãîðèòìó ñîîòâåñòâóåò íåêîòîðîå ìíîæåñòâî ñòðàòåãèé (à íå îäíà).
Òåîðåìà 6. Ïóñòü G äåðåâî, k = 1 è C èñïîëüçóåò ñîïðÿæåííûé ê
¾àëãîðèòìó 1¿ àëãîðèòì, òîãäà C ïîáåæäàåò ïðè ëþáîì ïîâåäåíèè R
I Ïóñòü èãðîêè ñäåëàëè ïåðâûå õîäû (óñòàíîâèëè íà÷àëüíûå ïîçèöèè ñâîèõ ôèøåê íà ãðàôå).  ýòîì ñëó÷àå r è c1 áóäóò ñîåäèíåíû
20
åäèíñòâåííûì ïóòåì (òàê êàê G äåðåâî). Î÷åâèäíî, ÷òî ñëåäóÿ àëãîðèòìó, ñîïðÿæåííîìó àëãîðèòìó 1 C áóäåò äâèãàòüñÿ ïî ýòîìó ïóòè.
Ó÷èòûâàÿ êîíå÷íîñòü ãðàôà G, à òàêæå, ÷òî r íå ñìîæåò ïîïàñòü â òå
âåðøèíû, â êîòîðûõ ïîáûâàë C (îïÿòü æå â ñèëó îòñóòñòâèÿ â ãðàôå öèêëîâ), ïîëó÷àåì, ÷òî R áóäåò çàõâà÷åí ÷åðåç êîíå÷íîå êîëè÷åñòâî õîäîâ.
21
5
Ìîäåëèðîâàííèå
C&R
íà JavaScript
 ýòîé ÷àñòè îïèñûâàåòñÿ ïîñòðîåííàÿ â õîäå ðàáîòû ïðîãðàììà, ìîäåëèðóþùàÿ ïîâåäåíèå ãðàáèòåëÿ è ïîëèöåéñêèõ. Äëÿ ìîäåëèðîâàíèÿ ãðàáèòåëÿ èñïîëüçóåòñÿ Àëãîðèòì 3, à äëÿ ïîëèöåéñêèõ äâîéñòâåííûé ê
íåìó àëãîðèòì.
5.1
Âèçóàëüíîå ìîäåëèðîâàíèå
Òåîðåòè÷åñêèå âûêëàäêè, òàáëèöû è ãðàôèêè îá èãðàõ íà ãðàôàõ âûãëÿäÿò äîâîëüíî áåçæèçíåííî áåç âîçìîæíîñòè èõ íàãëÿäíî ïðåäñòàâèòü.
Èìåííî ïîýòîìó, íà÷èíàÿ çàíèìàòüñÿ ýòîé äèïëîìíîé ðàáîòîé, ÿ ïåðâûì
äåëîì ñäåëàë ïðîãðàììó, íàãëÿäíî ïðåäñòàâëÿþùóþ ïðîöåññ èãðû. Èãðà
íàïèñàíà íà JavaScript è âûïîëíåííà â ôîðìàòå html âåá-ñòðàíè÷êè.
Âåðîÿòíî, òàêîé âûáîð èíñòðóìåíòîâ ðàçðàáîòêè òóò æå âûçîâåò íåêîòîðûå âîïðîñû, òàê êàê JavaScript äîâîëüíî ðåäêî èñïîëüçóåòñÿ äëÿ ìàòåìàòè÷åñêèõ ðàñ÷¼òîâ. Íà ñàìîì äåëå, ïåðåä íà÷àëîì ðàáîòû ÿ ðàññìàòðèâàë è íåñêîëüêî äðóãèõ âàðèàíòîâ, òàêèõ êàê: iPython (äëÿ êîòîðîãî
åñòü ñïåöèàëèçèðîâàííàÿ ñðåäà äëÿ ìàòåìàòè÷åñêèõ ðàñ÷¼òîâ Spyder),
C++ (íà êîòîðîì íàïèñàíû óòèëèòû èç ïàêåòà Graphviz, ïðåäîñòàâëÿþùèå óäîáíûé èíòåðôåéñ äëÿ âèçóàëèçàöèè ãðàôîâ). Áûë òàêæå âàðèàíò
ñ ðàçðàáîòêîé ïðîãðàììû íà php ñ ãåíåðàöèåé âèçóàëèçàöèè ãðàôîâ ïîñðåäñòâîì óòèëèò Graphviz íà ñòîðîíå ñåðâåðà.
Îäíàêî, ïîñëå îçíàêîìëåíèÿ ñ JavaScript-ôðýéìâîðêîì vis.js, âñå ïðî÷èå âàðèàíòû ðåçêî ïåðåñòàëè áûòü àêòóàëüíûìè. JavaScript ñ ôðåéìâîðêîì vis.js êàê íåëüçÿ ëó÷øå ïîäõîäèò ê çàäà÷å âèçóàëèçàöèè èãð íà
ãðàôàõ, òàê êàê, êðîìå ñàìîé âèçóàëèçàöèè ãðàôîâ, ïðåäîñòàâëÿåò áîãàòûå âîçìîæíîñòè â äèíàìèêå ïðîâîäèòü ñ íèìè ðàçëè÷íûå ìàíèïóëÿöèè
(èçìåíÿòü ñòðóêòóðó ãðàôà, öâåò è ðàçìåð âåðøèí, äîáàâëÿòü îáðàáîò÷èêè ðàçëè÷íûõ ñîáûòèé).
Âûáîð JavaScript-html ñâÿçêè äàë âîçìîæíîñòü ñäåëàòü êðîññïëàòôîðìåííîå áåçîïàñíîå (ñ òî÷êè çðåíèÿ ðàñïðîñòðàíåíèÿ âèðóñîâ) ïðèëîæåíèå, êîòîðîå (áëàãîäàðÿ îòñóòñòâèþ ñåðâåðíîé ÷àñòè) ìîæåò ðàáîòàòü íà âåá-ñåðâåðå ñ ñàìûì ñêðîìíûì íàáîðîì âîçìîæíîñòåé èëè äàæå
ðàáîòàòü ëîêàëüíî. Òàêæå íàäî çàìåòèòü, ÷òî ïî ñòàòèñòèêå JavaScript
22
çàìåòíî áûñòðåå, ÷åì python (ïî íåêîòîðûì îöåíêàì â 5 ðàç), õîòÿ è
óñòóïàåò ïî áûñòðîäåéñòâèþ C++.
23
5.2
Êîíñîëüíîå ïðèëîæåíèå
Äëÿ çàïóñêà êîíñîëüíîãî ïðèëîæåíèÿ ïîíàäîáèòñÿ óñòàíîâëåííàÿ ïðîãðàììà Node.js. Êðîìå òîãî, ïðèëîæåíèþ íåîáõîäèìî íàëè÷èå áèáëèîòåêè Math.js. Math.js ýòî ïîïóëÿðíàÿ áèáëèîòåêà ñ îòêðûòûì èñõîäíûì
êîäîì, ïðåäîñòàâëÿþùàÿ ïðîãðàììèñòàì JavaScript øèðîêèé ñïåêòð ìàòåìàòè÷åñêèõ âîçìîæíîñòåé. Îôèöèàëüíûé ñàéò áèáëèîòåêè http:
//mathjs.org/.
Îñíîâíîé îáúåêò èãðû èìååò ïðèìåðíî ñëåäóþùèé âèä:
1 Game ={
CopsPos : [1 ,2 ,3] ,
CopsAmount : 3 ,
Robber : 5 ,
CopToMove : 0 ,
Matrix : [....] ,
GameOver : false ,
GraphParams : { NodesAmount : 27 , Dimensions : 3} ,
2
3
4
5
6
7
8
9
AutoMoveCops : function () { .... } ,
MoveCop : function ( node ) { .... } ,
getRobberMove : function () { ... }
MoveRobber : function () { ... } ,
IsOnCop : function ( r ) { ... } ,
init : function ( N ) { ... } ,
...
10
11
12
13
14
15
16
17 }
Çäåñü óêàçàíû òîëüêî òå ÷ëåíû îáúåêòà, êîòîðûå íåîáõîäèìû ïðè ïîñòðîåíèè ñòàòèñòèê. Ïîëíûé ëèñòèíã ïðîãðàììû ÿ òóò íå ïðèâîæó, òàê
êàê ïðîãðàììà èìååò ðàçìåð áîëåå òûñÿ÷è ñòðîê êîäà. Àâòîð çàèíòåðåñîâàí â ñîâåðøåíñòâîâàíèè ïðèëîæåíèÿ, ïîýòîìó áóäåò áëàãîäàðåí çà ëþáûå êîììåíòàðèè îòïðàâëåííûå ïî àäðåñó mailto:peter.peysahovsky@
gmail.com.
Ïîÿñíèì ñìûñë ïîëåé è ìåòîäîâ:
24
Òàáëèöà 1: Ñïèñîê îñíîâíûõ ïîëåé è ìåòîäîâ
Ïîëå/ôóíêöèÿ
Ïîÿñíåíèå
CopsPos
Ìàññèâ íîìåðîâ âåðøèí, çàíèìàåìûõ C
CopsAmount
Êîëè÷åñòâî ïîëèöåéñêèõ
Robber
Íîìåð âåðøèíû, çàíèìàåìîé ãðàáèòåëåì
CopToMove
Íîìåð ïîëèöåéñêîãî, êîòîðûé äåëàåò õîä (òîëüêî äëÿ âèçóàëèçàöèè)
Matrix
Ìàòðèöà èíöèäåíòíîñòè ãðàôà
GameOver
Ôëàã çàêîí÷åííîñòè èãðû
GraphParams
Ïàðàìåòðû ãåíåðàöèè ãðàôà
AutoMoveCops()
Äåëàåò õîä çà C äâîéñòâåííûì àëãîðèòìîì
MoveCop()
Äåëàåò õîä çà C â óêàçàííóþ âåðøèíó
getRobberMove()
Âû÷èñëÿåò õîä ïîòåíöèàëüíûì àëãîðèòìîì äëÿ R
MoveRobber()
Äåëàåò õîä ïîòåíöèàëüíûì àëãîðèòìîì çà R
IsOnCop()
Ïðîâåðÿåò, îêêóïèðóåòñÿ ëè âåðøèíà ïîëèöåéñêèìè
init()
Èíèöèàëèçèðóåò èãðó
Ïðèâåäåì ïðèìåð ìèíèìàëüíîé ïðîãðàììû, ñèìóëèðóþùóþ èãðó íà
ãðàôå:
1
2
3
4
5
6
7
8
9
10
math = require ( " ./ mathjs / math . js " ) ;
require ( " ./ game . js " ) ;
Game . Generate = GraphGenerator . cube ;
Game . GraphParams = { NodesAmount : 27 , Dimensions : 3};
Game . init () ;
Game . CopsAmount = 2;
Game . CopsPos = [0 ,1];
Game . Robber = [5];
Game . MoveRobber () ;
Game . AutoMoveCops () ;
Äàííûé ïðèìåð â 10 ñòðîê êîäà ÿâëÿåòñÿ ðàáî÷åé ïðîãðàììîé, êîòîðóþ ìîæíî çàïóñòèòü â Node.js. Ïðèìåð ãåíåðèðóåò êóáè÷åñêèé ãðàô
ñåòêó 3x3x3 è äåëàåò 1 õîä ãðàáèòåëåì è äâóìÿ ïîëèöåéñêèìè.
Åñëè òðåáóåòñÿ çàïóñòèòü èãðó íà ãðàôå äðóãîãî òèïà, òî â ïîëå
Game.Generate íóæíî çàïèñàòü ññûëêó íà äðóãóþ ôóíêöèþ, ãåíåðèðóþùóþ ãðàô (à òî÷íåå ìàòðèöó èíöèäåíòíîñòè), ìîæíî èñïîëüçîâàòü îäíó
25
èç ãîòîâûõ ôóíêöèé-ïðèìåðîâ èç îáúåêòà GraphGenereator èëè íàïèñàòü
ñâîþ.
Ïðîâåðÿòü ïîáåäó C ìîæíî ñ ïîìîùüþ ôóíêöèè Game.IsOnCop() (ïðîâåðÿÿ åé âåðøèíó ãðàáèòåëÿ Game.Robber).
Ïîáåäà â èãðå äîñòà¼òñÿ R ïî îïðåäåëåíèþ, åñëè èãðà íå çàêàí÷èâàåòñÿ çà êîíå÷íîå êîëè÷åñòâî õîäîâ. Íà ïðàêòèêå ýòî ýêâèâàëåíòíî ïîâòîðåíèþ êàêîé-òî èãðîâîé ïîçèöèè 2 ðàçà. Ñ öåëüþ îòñëåæèâàíèÿ òàêîé ñèòóàöèè êàæäîé èãðîâîé ïîçèöèè ìîæíî ñîïîñòàâëÿòü óíèêàëüíûé
õýø-êîä, è ïðîâåðÿòü åãî ïîâòîðåíèå â òå÷åíèè èãðû. Òàêîé ïîäõîä ðåàëèçîâàí â êîíñîëüíîì ïðèëîæåíèè äëÿ ïîñòðîåíèÿ ñòàòèñòèê ng.js.
26
6
Îöåíêà ýôôåêòèâíîñòè ïàð àëãîðèòìîâ ñ
ïîìîùüþ ýìïèðè÷åñêîãî ïîëèöåéñêîãî ÷èñëà
Êîíå÷íî æå, ïîñëå ñîçäàíèÿ ïðîãðàììû ìîäåëèðóþùåé ïîâåäåíèå ïîëèöåéñêèõ è ãðàáèòåëåé, âñòàåò âîïðîñ îá îöåíêå ýôôåêòèâíîñòè ýòèõ
àëãîðèòìîâ. Îäíàêî, ìîäåëèðîâàíèå ïîâåäåíèÿ èãðîêîâ íå äà¼ò âîçìîæíîñòè îöåíèâàòü àëãîðèòìû ïîëèöåéñêèõ è ãðàáèòåëÿ ïî îòäåëüíîñòè.
Òåì íå ìåíåå, ìíîãèå âåëè÷èíû, êîòîðûå ìîæíî îöåíèòü ïðîãðàììîé
ìîãóò ïðåäñòàâëÿòü èíòåðåñ.
Îïðåäåëåíèå 16.
Ýìïèðè÷åñêîå ïîëèöåéñêîå ÷èñëî
(äëÿ ïàðû ñòðàòå-
ãèé)
Ïðåäïîëîæèì, ó íàñ åñòü ôèêñèðîâàííûé ãðàô G è ïàðà ôèêñèðîâàííûõ ñòðàòåãèé äëÿ îáîèõ èãðîêîâ. Îáîçíà÷èì SC ñòðàòåãèþ C , à SR
ñòðàòåãèþ R. Íàçîâ¼ì ýìïèðè÷åñêèì ïîëèöåéñêèì ÷èñëîì (cn0 (G)) äëÿ
òðîéêè (G, SC , SR ) ìèíèìàëüíîå êîëè÷åñòâî ïîëèöåéñêèõ íåîáõîäèìûõ
äëÿ ïîèìêè ãðàáèòåëÿ íà ãðàôå G ïðè èñïîëüçîâàíèè ñòðàòåãèé SC , SR .
Îïðåäåëåíèå ýìïèðè÷åñêîãî ïîëèöåéñêîãî ÷èñëà ïîçâîëÿåò îöåíèâàòü
ýôôåêòèâíîñòü ïàðû àëãîðèòìîâ äðóã îòíîñèòåëüíî äðóãà ïðè ôèêñèðîâàííîì ãðàôå.
 ñëó÷àå, åñëè ó íàñ åñòü íå ñòðàòåãèè, à àëãîðèòìû ãåíåðèðóþùèå
íåêîòîðîå ìíîæåñòâî ñòðàòåãèé, ìîæíî ïîñòðîèòü ñëåäóþùóþ õàðàêòåðèñòèêó ïàðû àëãîðèòìîâ:
Îïðåäåëåíèå 17.
Ñðåäíåå ýìïèðè÷åñêîå ïîëèöåéñêîå ÷èñëî
(äëÿ ïàðû
àëãîðèòìîâ è íåêîòîðîãî ìíîæåñòâà ãðàôîâ)
Ïóñòü åñòü íåêîòîðîå êîíå÷íîå, ìíîæåñòâî íåîðèåíòèðîâàííûõ ãðàôîâ H . Êàæäîìó G ∈ H àëãîðèòìû (AR è AC ) èãðîêîâ ñîïîñòàâëÿþò
íåêîòîðîå ìíîæåñòâî ñòðàòåãèé, îáîçíà÷èì èõ êàê AC (G) è AR (G).
Äàëåå ñîñòàâèì ìíîæåñòâî ýëåìåíòàðíûõ ñîáûòèé:
Ω = {(G, SC , SR ) | G ∈ H, SC ∈ AC (G), SR ∈ AR (G)}
27
Áóäåì ñ÷èòàòü (Ω, 2Ω , P) âåðîÿòíîñòíûì ïðîñòðàíñòâîì, ïðè ýòîì âåðîÿòíîñòíóþ ìåðó P îïðåäåëèì íà ýëåìåíòàðíûõ ñîáûòèÿõ êàê êîíñòàíòó ðàâíóþ 1/|Ω|. Î÷åâèäíî, ÷òî ýòî âîçìîæíî äëÿ êîíå÷íîãî ìíîæåñòâà
ýëåìåíòàðíûõ ñîáûòèé.
Îïðåäåëèì ñðåäíåå ýìïèðè÷åñêîå ïîëèöåéñêîå ÷èñëî êàê ìàò. îæèäàíèå ýìïèðè÷åñêîãî ïîëèöåéñêîãî ÷èñëà ïî âñåì âîçìîæíûì ãðàôàì èç
H . Èíà÷å ãîâîðÿ:
cn0 (H, AC , AR ) = E cn0 (G, SC , SR )
 ýòîé ôîðìóëå ïðîèñõîäèò îäíîâðåìåííî òðè óñðåäíåíèÿ, ïî ìíîæåñòâó ãðàôîâ è ïî ñòðàòåãèÿì ïîëèöåéñêîãî è ãðàáèòåëÿ (íàïîìíèì,
÷òî êàæäûé àëãîðèòì ìîæåò ñîïîñòàâëÿòü ãðàôó íåêîòîðîå ìíîæåñòâî
ñòðàòåãèé).
Ïðèâåä¼ì òðè ïðèìåðà ñòàòèñòèê, êîòîðûå ìíå óäàëîñü ïîñ÷èòàòü çà
èñòîðè÷åñêè êîðîòêèé ñðîê.
Ïåðâûå äâå ñòàòèñòèêè ñ÷èòàëèñü äëÿ ïîòåíöèàëüíîãî è ìîäèôèöèðîâàííîãî äâîéñòâåííîãî àëãîðèòìà. Îòëè÷èå ìîäèôèöèðîâàííîãî àëãîðèòìà ñîñòîèò â òîì, ÷òî ïåðâûé õîä äåëàåòñÿ íå ïî àëãîðèòìó, à ñëó÷àéíî. Òàêîé ïîäõîä äà¼ò äîïîëíèòåëüíî âîçìîæíîñòü ïðîñëåäèòü çàâèñèìîñòü ðåçóëüòàòà èãðû (ïîáåäà èëè ïîðàæåíèå) îò íà÷àëüíîãî ðàñïîëîæåíèÿ ïîëèöåéñêèõ.
(Èñõîäíèêè ñî âñåìè ýìïèðè÷åñêè ïîäîáðàííûìè ïàðàìåòðàìè ïðèëîæåíû ê ðàáîòå, òàê ÷òî ïðè æåëàíèè âñå ðåçóëüòàòû ìîæíî ëåãêî ïåðåïðîâåðèòü (èëè, èçìåíèâ ïàðàìåòðû, ðàñ÷èòàòü êàêèå-òî äðóãèå ñòàòèñòèêè)).
Èòàê, ïåðâàÿ ñòàòèñòèêà, êîòîðóþ ÿ ïîñ÷èòàë ýòî ïðîöåíòû ïîáåä íà n-ìåðíîì êóáå. Ïîä n-íûì êóáîì ÿ â äàííîì ñëó÷àå ïîäðàçóìåâàþ ãðàô-ñåòêó 3x3...x3. Óñðåäíåíèå ïðîâîäèëîñü ïî ñòðàòåãèÿì ïîëèöåéñêèõ.
28
Òàáëèöà 2: Ïðîöåíòû ïîáåä íà n-ìåðíîì êóáå äëÿ ðàçíîãî êîëè÷åñòâà
ïîëèöåéñêèõ (ïî ðåçóëüòàòàì äåñÿòè èñïûòàíèé)
Ðàçìåðíîñòü
Âåðøèíû
1
4
100
100
100
100
2
16
0
100
100
100
3
64
0
60
100
100
4
256
0
0
80
100
|C| = 1 |C| = 2 |C| = 3 |C| = 4
Àíàëîãè÷íàÿ ñòàòèñòèêà ïîáåä äëÿ n-ìåðíîãî òîðà âûãëÿäèò ñëåäóþùèì îáðàçîì.
Òàáëèöà 3: Ïðîöåíòû ïîáåä íà n-ìåðíîãî òîðà äëÿ ðàçíîãî êîëè÷åñòâà
ïîëèöåéñêèõ (ïî ðåçóëüòàòàì äåñÿòè èñïûòàíèé)
Ðàçìåðíîñòü
Âåðøèíû
1
4
100
100
100
100
2
16
0
100
100
100
3
64
0
0
100
100
4
256
0
0
0
100
|C| = 1 |C| = 2 |C| = 3 |C| = 4
Çäåñü âèäíî, ÷òî íà÷àëüíîå ïîëîæåíèå ïîëèöåéñêèõ íå èìååò çíà÷åíèÿ. Ïîáåäà èëè ïîðàæåíèå îïðåäåëÿåòñÿ òîëüêî êîëè÷åñòâîì ïîëèöåéñêèõ.
Äàëåå áûëî ïîñ÷èòàíî ñðåäíåå ýìïèðè÷åñêîå ïîëèöåéñêîå ÷èñëî äëÿ
ïîòåíöèàëüíîãî è äâîéñòâåííîãî ê íåìó àëãîðèòìîâ. Óñðåäíåíèå ïðîâîäèëîñü ïî ñëó÷àéíî ñãåíåðèðîâàííûì ãðàôàì.
Ñïîñîá ãåíåðàöèè ñëó÷àéíûõ ãðàôîâ ñëåäóùèé:
1. Çàïàñàåìñÿ íàáîðîì èç N âåðøèí (ò.å. îïðåäåëÿåì ìíîæåñòâî V )
2. Äëÿ êàæäîé ïàðû íåðàâíûõ âåðøèí (v1 , v2 ) äîáàâëÿåì ãðàíü â E ñ
âåðîÿòíîñòüþ p.
Äëÿ ïðåäñòàâëåííîãî ãðàôèêà p = 0.36.
29
Ðèñ. 4: Ñðåäíåå ýìïèðè÷åñêîå ïîëèöåéñêîå ÷èñëî äëÿ ñëó÷àéíûõ ãðàôîâ
(ïî ðåçóëüòàòàì èãðû íà 29 000 ãðàôàõ).
Ëîêàëüíûé ìàêñèìóì êðèâîé ñâÿçàí ñ òåì, ÷òî ïðè íåáîëüøîì êîëè÷åñòâå âåðøèí î÷åíü âåëèêà âåðîÿòíîñòü íåñêîëüêî-êîìïîíåíòíîãî ãðàôà (ò.å. ñ äâóìÿ èëè áîëåå êîìïîíåíòàìè ñâÿçíîñòè).  ñëó÷àå íåñêîëüêîêîìïîíåíòíîãî ãðàôà ñ êîëè÷åñòâîì âåðøèí ìåíüøå ÷åòûð¼õ, ïîëèöåéñêîå ÷èñëî è ýìïèðè÷åñêîå ïîëèöåéñêîå âñåãäà áóäåò ðàâíî êîëè÷åñòâó
êîìïîíåíò ñâÿçíîñòè (ò.ê. cn(G) = 1 äëÿ ëþáîãî ñâÿçíîãî ãðàôà ñ |G| <
5).
Èç ãðàôèêà âèäíî, ÷òî íà÷èíàÿ ñ íåêîòîðîãî ìîìåíòà, ñðåäíåå ýìïèðè÷åñêîå ïîëèöåéñêîå ÷èñëî ìîíîòîííî ðàñò¼ò, ïðè÷¼ì çàâèñèìîñòü
î÷åíü ïîõîæà íà ëèíåéíóþ (õîòÿ òî÷íî ñêàçàòü ïî òàêîìó íåáîëüøîìó
èíòåðâàëó ñëîæíî). Ñòîèò çàìåòèòü, ÷òî åñëè âåðèòü ãèïîòåçå Ìýéíåëà [Fra87a], òî ïîëèöåéñêîå ÷èñëî ñâÿçíîãî ãðàôà íå ìîæåò ïðåâûøàòü
êîíñòàíòó óìíîæåííóþ íà êîðåíü èç êîëè÷åñòâà âåðøèí ãðàôà.  ïðåäñòàâëåííîì íà ãðàôèêå äèàïàçîíå ãèïîòåçà Ìýéíýëà âûïîëíÿåòñÿ è äëÿ
ñðåäíåãî ýìïèðè÷åñêîãî ïîëèöåéñêîãî ÷èñëà (äàæå áåç îãðàíè÷åíèÿ íà
30
êîëè÷åñòâî êîìïîíåíò ñâÿçíîñòè), îäíàêî, ÷òîáû îíà âûïîëíÿëàñü è äàëåå â íåêîòîðûé ìîìåíò ëèíåéíûé õàðàêòåð cn0 äîëæåí îáÿçàòåëüíî èçìåíèòüñÿ, òàê êàê èíà÷å ëèíåéíàÿ ôóíêöèÿ ðàíî èëè ïîçäíî ¾îáãîíèò¿
p
d |G| (ãäå, d íåêîòîðàÿ êîíñòàíòà). Ê ñîæàëåíèþ, äëÿ ñóùåñòâóþùåãî àëãîðèòìà ïîñòðîåíèå ñòàòèñòèêè â òàêîì øèðîêîì äèàïàçîíå ïîêà
íåâîçìîæíî. Ïîñòðîåíèå òàêîãî ðîäà ñòàòèñòèê ìîæåò ñòàòü âîçìîæíî
ïîñëå ñóùåñòâåííîé îïòèìèçàöèè àëãîðèòìà èëè ñóùåñòâåííîãî óâåëè÷åíèÿ äîñòóïíûõ âû÷èñëèòåëüíûõ ìîùíîñòåé.
31
7
Çàêëþ÷åíèå
Ðåçóëüòàòîì äàííîé ðàáîòû ñòàëè ïàðà àëãîðèòìîâ äëÿ ãðàáèòåëÿ è ïîëèöåéñêèõ. Àëãîðèòìû áûëè ïðîòåñòèðîâàíû äëÿ ìíîãîìåðíûõ ãðàôîâñåòîê. Êðîìå òîãî, áûë óêàçàí ñïîñîá ¾áåñïëàòíîãî¿ ïîñòðîåíèÿ àëãîðèòìà äëÿ ïîëèöåéñêèõ, â ñëó÷àå íàëè÷èÿ ôóíêöèè îöåíêè ïîçèöèè äëÿ
ãðàáèòåëÿ (â ÷àñòíîñòè, â ñëó÷àå íàëè÷èÿ ïîòåíöèàëüíîãî àëãîðèòìà). Â
ðàáîòå ââîäèòñÿ ïîíÿòèå ¾ýìïèðè÷åñêîãî ïîëèöåéñêîãî ÷èñëà¿, ïîçâîëÿþùåå äàâàòü îöåíêó îòíîñèòåëüíîé ýôôåêòèâíîñòè ïàð àëãîðèòìîâ (èëè
ñòðàòåãèé), ÷òî ïðîäåìîíñòðèðîâàííî íà ïðèìåðå ïàð ïîòåíöèàëüíîãî è
äóàëüíîãî àëãîðèòìîâ.
Äðóãèì ðåçóëüòàòîì ðàáîòû ñòàëî ïðèëîæåíèå, ïðåäîñòàâëÿþùåå óäîáíûé ïîëüçîâàòåëüñêèé è ïðîãðàììíûé èíòåðôåéñ äëÿ ýêñïåðèìåíòîâ,
ñâÿçàííûõ ñ C&R (à òàêæå óäîáíûé ñïîñîá äåìîíñòðàöèè). Äàííîå ïðèëîæåíèå ïóáëèêóåòñÿ âìåñòå ñ ýòîé ðàáîòîé.
Ïîñòðîåííûå â äàííîé ðàáîòå ïðîãðàììíûå ñðåäñòâà è àëãîðèòìû
íåëüçÿ âîñïðèíèìàòü êàê êîíå÷íóþ öåëü. Àâòîð âèäèò øèðîêèå âîçìîæíîñòè äëÿ äàëüíåéøåé ðàáîòû. Òàê èñïîëüçîâàííûé â ïðîöåññå ïîñòðîåíèÿ ñòàòèñòèê àëãîðèòì ñîäåðæèò áîëüøîå êîëè÷åñòâî ýìïèðè÷åñêèõ
ïàðàìåòðîâ. Ýòè ýìïèðè÷åñêèå ïàðàìåòðû, âîçìîæíî, èìååò ñìûñë íàõîäèòü ãåíåòè÷åñêèì àëãîðèòìîì èëè ñ ïîìîùüþ íåéðîííûõ ñåòåé. Êðîìå
òîãî, â ðàáîòå ïîñòðîåííû òîëüêî ñàìûå ïðîñòûå ñòàòèñòèêè, â òî âðåìÿ êàê ïîòåíöèàë ïðîãðàììû ïîçâîëÿåò ñòðîèòü ìíîæåñòâî ¾òîíêèõ¿
ñòàòèñòèê.
32
Ñïèñîê ëèòåðàòóðû
[AF84] Martin Aigner and Michael Fromme.
,
A game of cops and robbers
Discrete Appl. Math. 8 (1984), no. 1, 111.
MR 739593 (85f:90124)
[BB12] William Baird, Anthony Bonato
number: a survey
Meyniel's conjecture on the cop
, Journal of Combinatorics Volume 0, Number 0 (2012),
18
[Fra87a] Peter Frankl
Cops and robbers in graphs with large girth and cayley
, Discrete Applied Mathematics, 17 (1987), 301305.
graphs
[NS14] Nicolas Nisse.
Algorithmic
Complexity
Knowledge.How Pursuit-evasion Games help
Between
Structure
and
, HDR Univ. Nice Sophia
Antipolis, CNRS, I3S, UMR 7271, Sophia Antipolis, France, (May 26th
2014), 1-43
[NW83] Richard J. Nowakowski and Peter Winkler.
Vertex-to-vertex pursuit
, 43 (1983), 235239.
in a graph. Discrete Mathematics
[Sch01] Bernd S. W. Schroder The copnumber of a graph is bounded
3
by
genus(g)
+
3
, Categorical perspectives, Trends in Mathematics
2
(2001), 243263
33
Отзывы:
Авторизуйтесь, чтобы оставить отзыв