Ñàíêò-Ïåòåðáóðãñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò
Ïëåõàíîâà Òàèñèÿ Ìèõàéëîâíà
Âûïóñêíàÿ êâàëèôèêàöèîííàÿ ðàáîòà àñïèðàíòà
Èñïîëüçîâàíèå òåîðåòèêè-èãðîâîãî
ïîäõîäà äëÿ ïîâûøåíèÿ
ïðîèçâîäèòåëüíîñòè ñåòè MANET
Íàïðàâëåíèå 01.06.01
Ìàòåìàòèêà è ìåõàíèêà
Îáðàçîâàòåëüíàÿ ïðîãðàììà ¾Ïðèêëàäíàÿ ìàòåìàòèêà
è ïðîöåññû óïðàâëåíèÿ¿
Íàó÷íûé ðóêîâîäèòåëü,
äîêòîð ôèçèêî-ìàòåìàòè÷åñêèõ íàóê,
äîöåíò
Ãðîìîâà Å. Â.
Ðåöåíçåíò,
êàíäèäàò ôèçèêî-ìàòåìàòè÷åñêèõ íàóê,
ßíêîâñêàÿ Ë. À.
Ñàíêò-Ïåòåðáóðã
2018
Îãëàâëåíèå
Ââåäåíèå
3
Ïîñòàíîâêà çàäà÷è
4
Îáçîð ëèòåðàòóðû
5
1
Íåêîîïåðàòèâíûé âàðèàíò
7
1.1
Îáùàÿ ñåòåâàÿ ñòðóêòóðà . . . . . . . . . . . . . . . . . . . . . . .
7
1.2
Äðîí íåôèêñèðîâàííûé àãåíò . . . . . . . . . . . . . . . . . . .
9
1.3
Ñòðàòåãèè è âûèãðûø . . . . . . . . . . . . . . . . . . . . . . . . .
10
1.4
Ôîðìóëû íàõîæäåíèÿ ñòðàòåãèé . . . . . . . . . . . . . . . . . . .
14
1.4.1
¾Ïðîñòûå¿ ñòðàòåãèè íà ãåêñàãîíàëüíîé ðåøåòêå . . . . . .
14
1.4.2
Ñòðàòåãèè ¾â ïåðñïåêòèâå¿ íà ãåêñàãîíàëüíîé ðåøåòêå . .
17
2
3
Êîîïåðàòèâíûé âàðèàíò
20
2.1
Êîîïåðàòèâíûé âàðèàíò áåç äðîíîâ . . . . . . . . . . . . . . . . .
20
2.2
Êîîïåðàòèâíûé âàðèàíò ñ äðîíàìè . . . . . . . . . . . . . . . . . .
21
Ïðèìåð èãðû
22
3.1
Íåêîîïåðàòè÷íûé âàðèàíò . . . . . . . . . . . . . . . . . . . . . . .
22
3.1.1
Ïðèìåð . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
3.1.2
Âûâîäû . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
Êîîïåðàòèâíûé âàðèàíò . . . . . . . . . . . . . . . . . . . . . . . .
24
3.2.1
Ïðèìåð èãðû . . . . . . . . . . . . . . . . . . . . . . . . . .
24
3.2.2
Âûâîäû . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
3.2
4
Ìîäåëèðîâàíèå â Network Simulator 3
26
4.1
26
Êîíôèãóðàöèÿ ñåòè . . . . . . . . . . . . . . . . . . . . . . . . . .
1
4.2
Ðåçóëüòàòû ìîäåëèðîâàíèÿ . . . . . . . . . . . . . . . . . . . . . .
26
4.3
Âûâîäû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
Çàêëþ÷åíèå
28
Ëèòåðàòóðà
29
2
Ââåäåíèå
 äàííîì èññëåäîâàíèè ðàññìàòðèâàåòñÿ ïðèìåíåíèå äèíàìè÷åñêîé òåîðèè èãð ê áåñïðîâîäíûì äåöåíòðàëèçîâàííûì ñàìîîðãàíèçóþùèìñÿ ñåòÿì
(MANET). MANET ñîñòîèò èç íàáîðà óçëîâ/àãåíòîâ ñ âîçìîæíîñòüþ èñïîëüçîâàíèÿ áåñïðîâîäíîé òåõíîëîãèè. Ñóùåñòâóåò ìíîãî ïðèëîæåíèé äëÿ MANET,
íà÷èíàÿ ñ îáìåíà ôàéëàìè â íàñòðîéêàõ ïåðñîíàëüíîé ñåòè è çàêàí÷èâàÿ ïîòîêîâîé ïåðåäà÷åé âèäåîèíôîðìàöèè ìåæäó òðàíñïîðòíûìè ñðåäñòâàìè . Ñåòü
MANET ðåàëèçóåò ìàðøðóòèçàöèþ ñ íåñêîëüêèìè ïåðåõîäàìè ýòî òèï ñâÿçè â ðàäèîñåòÿõ, â êîòîðûõ çîíà ïîêðûòèÿ ñåòè áîëüøå, ÷åì ðàäèóñ äåéñòâèÿ
îäèíî÷íûõ óçëîâ. Ïîýòîìó, ÷òîáû ïåðåäàòü èíôîðìàöèþ äî êîíå÷íîãî ïóíêòà,
óçåë ìîæåò èñïîëüçîâàòü äðóãèå óçëû â êà÷åñòâå ìàðøðóòèçàòîðîâ.  ýòîì èññëåäîâàíèè ðàññìàòðèâàåòñÿ MANET, ñïîñîáñòâóþùóþ êîîðäèíèðîâàíèþ äåéñòâèé ñïàñàòåëüíûõ îòðÿäîâ â ñèòóàöèè àâàðèéíîãî âîññòàíîâëåíèÿ ïîñëå ïðèðîäíîé êàòàñòðîôû (ò. å. ïîñëå çåìëåòðÿñåíèÿ, íàâîäíåíèé è ò. ä.), ñëåäîâàòåëüíî, îñíîâíûì óñëîâèåì ÿâëÿåòñÿ áûñòðîòà è ïðîñòîòà óñòàíîâëåíèÿ ñâÿçè
ìåæäó ó÷àñòíèêàìè ñïàñàòåëüíûõ îòðÿäîâ. Óëó÷øåíèå ïðîèçâîäèòåëüíîñòè ñåòè MANET ïðè ïðîâåäåíèè ñïàñàòåëüíûõ îïåðàöèÿõ ÿâëÿåòñÿ îäíîé èç ãëàâíûõ
çàäà÷ è â ïåðñïåêòèâå ìîæåò ñïàñòè æèçíè.
Ðàáîòà ÿâëÿåòñÿ ïðîäîëæåíèåì èññëåäîâàíèÿ, îïóáëèêîâàííîãî â [3]. Â
äàííîé ðàáîòå äëÿ óëó÷øåíèÿ ïðîèçâîäèòåëüíîñòè ñåòè, âî-ïåðâûõ, ðàññìàòðèâàåòñÿ ãåêñàãîíàëüíàÿ ñåòêà, êîòîðàÿ äàåò áîëåå ðåàëèñòè÷íîå ïðåäñòàâëåíèå
î ïåðåäà÷è â ñåòè. Âî-âòîðûõ, ââîäèòñÿ íîâûé êëàññ ñòðàòåãèé ñòðàòåãèè ¾â
ïåðñïåêòèâå¿, êîòîðûå ïðèâîäÿò ê óìåíüøåíèþ äëèíû èãðû è ÿâëÿþòñÿ óíèêàëüíûìè äëÿ ïðåäûäóùåé ïîñòàíîâêè çàäà÷è. Â-òðåòüèõ, çàäà÷à ðàñïîëîæåíèÿ àãåíòîâ íà ñåòè ôîðìèðóåòñÿ, êàê äèíàìè÷åñêàÿ êîîïåðàòèâíàÿ èãðà.
3
Ïîñòàíîâêà çàäà÷è
 äàííîé âûïóñêíîé êâàëèôèêàöèîííîé ðàáîòå äëÿ äîñòèæåíèÿ öåëè ïîâûøåíèÿ ïðîèçâîäèòåëüíîñòè ñåòè MANET ïðè ïðîâåäåíèè ñïàñàòåëüíûõ îïåðàöèÿõ íåîáõîäèìî áûëî ðåøèòü ñëåäóþùèå çàäà÷è:
1. ðàñøèðèòü îáëàñòü ïîèñêà ñòðàòåãèé, ïðåäëîæåííîé â [3], äëÿ òîãî, ÷òîáû
íàéòè ñòðàòåãèè, êîòîðûå èìåþò áîëüøèé âûèãðûø, ÷åì â [3];
2. ðàññìîòðåòü êîîïåðàòèâíûé âàðèàíò èãðû [3];
3. íàïèñàòü ïðîãðàììíîûé ïðîäóêò, ïîçâîëÿþùèé èññëåäîâàòü èãðó íà ãåêñàãîíàëüíîé ñåòêå;
4. ïðîâåñòè àíàëèç ïîëó÷åííûõ ðåçóëüòàòîâ â Network Simulator 3.
4
Îáçîð ëèòåðàòóðû
Ïðè íàïèñàíèè âûïóñêíîé êâàëèôèêàöèîííîé ðàáîòû áûëà èñïîëüçîâàíà
ñëåäóþùàÿ ëèòåðàòóðà:
1. Ïåòðîñÿí Ë. À., Çåíêåâè÷ Í. À., Øåâêîïëÿñ Å. Â. Òåîðèÿ èãð.
 äàííîé êíèãå îïèñàíû ñàìûå îñíîâíûå è àêòóàëüíûå íà äàííûé ìîìåíò íàïðàâëåíèÿ òåîðèè èãð. Ïîëíî èçëîæåíû òåîðèè êîîïåðàòèâíûõ
èãð, àíòàãîíèñòè÷åñêèõ èãð, íåàíòàãîíèñòè÷åñêèõ èãð. Âñå ãëàâû ñíàáæåíû ìíîãî÷èñëåííûìè ïðèìåðàìè, äåìîíñòðèðóþùèå îñíîâíûå ïîëîæåíèÿ
òåîðèé. Ïðè íàïèñàíèè ðàáîòû èñïîëüçîâàëàñü Ãë. 4 (Ìíîãîøàãîâûå èãðû).
2. Gromova E., Gromov D., Timonin N., Kirpichnikova A., Blackway S (2016).
A Dynamic Game of Mobile Agent Placement in a MANET
Äàííàÿ ñòàòüÿ ÿâëÿåòñÿ ôóíäàìåíòîì äëÿ ðàáîòû.  íåé îïèñàíà äèíàìè÷åñêàÿ èãðà ðàñïîëîæåíèÿ äðîíîâ íà ñåòè MANET.
3. Âèíîêóðîâ Â. Ì., Ïóãîâêèí À. Â., Ïøåííèêîâ À. À. ,Óøàðîâà Ä. Í., Ôèëàòîâ À. Ñ. Ìàðøðóòèçàöèÿ â áåñïðîâîäíûõ ìîáèëüíûõ Ad hoc-ñåòÿõ
 ýòîé ñòàòüå îïèñàíà ñåòü Ad hoc, îñîáåííîñòè ìàðøðóòèçàöèè â äàííîé ñåòè. Îïèñàíû è ïðîìîäåëèðîâàíû òàêèå ïðîòîêîëû ìàðøðóòèçàöèè:
DSR, OLSR, AODV, LANMAR, ZRP, OSPFv2.
4. Ìàõìóä À. Ø., Ïîëÿêîâ Â. Ì. Îöåíêà ïðîèçâîäèòåëüíîñòè ïðîòîêîëîâ ìîáèëüíûõ Ad-hoc ñåòåé (MANET)
 äàííîé ñòàòüå ïðèâîäèòñÿ îïèñàíèå ïðîòîêîëîâ DSR è AODV è ïðîâîäèòñÿ îöåíêà ïðîèçâîäèòåëüíîñòè óêàçàííûõ ïðîòîêîëîâ ïðè ïîìîùè
ñèìóëÿòîðà Network Simulator 2.
5. Êëèìîâ È. À., ×åðâèíñêàÿ Í. Â. Ñðàâíåíèå ïðîòîêîëîâ ìàðøðóòèçàöèè
äëÿ áåñïîâîäíûõ AD-hoc ñåòåé
 äàííîé ñòàòüå ïðîâîäèòñÿ ñðàâíåíèå ïðîòîêîëîâ ìàðøðóòèçàöèè OLSR
è AODV äëÿ ñåòè Manet. Ïðèâîäèòñÿ îïèñàíèå ðàáîòû ñåòåé Mesh.
5
6. Standart Ecma-262
Îïèñàíèå ìóëüòèïàðàäèãìåííîãî ÿçûêà JavaScript.
7. Network simulator 3 documentation
Îïèñàíèå óñòàíîâêè è èñïîëüçîâàíèÿ Network simulator 3.
6
Ãëàâà 1. Íåêîîïåðàòèâíûé âàðèàíò
1.1 Îáùàÿ ñåòåâàÿ ñòðóêòóðà
Ðàññìîòðèì ìíîæåñòâî èãðîêîâ N = 1, . . . , n. Êàæäûé èãðîê i ∈ N
èìååò Mi 6= ∅ çàôèêñèðîâàííûõ àãåíòîâ (â ïðîöåññå èãðû ïîëîæåíèå òàêèõ àãåíòîâ íà ñåòêå íå èçìåíÿåòñÿ), ðàñïîëîæåííûõ â ïîäïðîñòðàíñòâå W =
{1, . . . , Wx } × {1, ..., Wy } ⊂ R2 , ò. å. â óçëàõ ãåêñàãîíàëüíîé ñåòêè, ãäå Wx ,
Wy ∈ R. Âûáðàíà äàííàÿ îðèåíòàöèÿ ãåêñàãîíà (ñì. ðèñ. 1.1)), äëÿ óïðîùåíèÿ äàëüíåéøèõ âûêëàäîê. Ïðåäïîëàãàåì, ÷òî â îäíîé è òîé æå âåðøèíå ìîãóò
îäíîâðåìåííî íàõîäèòüñÿ àãåíòû ðàçëè÷íûõ èãðîêîâ. Ïîçèöèÿ êàæäîãî àãåíòà îïèñûâàåòñÿ ïîëîæèòåëüíûìè êîîðäèíàòàìè ãåêñàãîíàëüíîé ñåòêè. Àãåíòû
îáîçíà÷àþòñÿ òî÷êàìè â óçëàõ ãåêñàãîíàëüíîé ðåøåòêè. Áóäåì ãîâîðèòü, ÷òî
p
p
ìåæäó àãåíòàìè vi è vis , s 6= p, èãðîêà i óñòàíîâëåíà óñòîé÷èâàÿ ñâÿçü (vi ,
vis ), åñëè îíè íàõîäÿòñÿ â ñîñåäíèõ óçëàõ ñåòêè. Ïîëàãàåì, ÷òî ìåæäó àãåíòàìè
ðàçëè÷íûõ èãðîêîâ ñâÿçè îòñóòñòâóþò.
Ðèñ. 1.1. Àãåíòû è ñâÿçè ìåæäó íèìè
p
Ñëåäîâàòåëüíî, ìíîæåñòâî àãåíòîâ vi ∈ Mi , i = 1, . . . , n è ñâÿçåé e =
(vip , vis ), vip ∈ Mi , vis ∈ Mi , s 6= p, i = 1, . . . , n, ãäå V íåïóñòîå êîíå÷íîå
ìíîæåñòâî ýëåìåíòîâ, íàçûâàåìûõ âåðøèíàìè (èëè òî÷êàìè, èëè óçëàìè), E
êîíå÷íîå ìíîæåñòâî íåóïîðÿäî÷åííûõ ïàð ýëåìåíòîâ èç V , íàçûâàåìûõ ðåá7
ðàìè [10]. Ïîäãðàôîì Ri ãðàôà R, áóäåì íàçûâàòü ãðàô, âñå âåðøèíû êîòîðîãî
ïðèíàäëåæàò V , à âñå ðåáðà ïðèíàäëåæàò E .
n
Îòìåòèì, ÷òî ∪ Ri = R. Ãðàô R îïðåäåëÿåò îáùóþ ñåòåâóþ ñòðóêòóðó
i=1
èãðû, â êîòîðîé èìååòñÿ Wx × Wy âîçìîæíûõ ïîçèöèé äëÿ àãåíòîâ íà ñåòêå.
Êîëè÷åñòâî íåçàíÿòûõ ïîçèöèé àãåíòàìè |O| ìîæåò áûòü îöåíåíî:
Wx × Wy − (n1 + n2 + ... + nN ) ≤ |O| ≤ Wx × Wy − max{ni }
i∈N
Ïóñòü ïîäãðàô Ri ñâÿçíûé, ýòî óñëîâèå ãàðàíòèðóåò ñóùåñòâîâàíèå ïóòè
ìåæäó ëþáûìè äâóìÿ åãî âåðøèíàìè, ãäå ðàñïîëàãàþòñÿ àãåíòû èãðîêîâ.
Ïóòåì â ïîäãðàôå Ri áóäåì íàçûâàòü òàêóþ ïîñëåäîâàòåëüíîñòü e =
(e1 , . . . , ek , ) ðåáåð, ÷òî êîíåö êàæäîãî ïðåäûäóùåãî ðåáðà ñîâïàäàåò ñ íà÷àëîì
ñëåäóþùåãî. Äëèíà ïóòè e = (e1 , ..., ek ) ÷èñëî d(e) = k ðåáåð ïîñëåäîâàòåëüíîñòè [10]. Äëèíó êàæäîãî ðåáðà ãåêñàãîíàëüíîé ðåøåòêè, äëÿ óïðîùåíèÿ
âû÷èñëåíèé, ïîëîæèì ðàâíîé åäèíèöå, ñëåäîâàòåëüíî, äëèíà ðåáðà ei = 1.
Äèàìåòðîì ïîäãðàôà D(Ri ) áóäåì íàçûâàòü ÷èñëî ðåáåð â êðàò÷àéøåì
ïðîñòîì íåçàìêíóòîì ïóòè ìåæäó äâóìÿ íàèáîëåå óäàëåííûìè äðóã îò äðóãà
âåðøèíàìè [10] (ñì. ðèñ.1.2).
D(Ri ) =
max
(vk ,vl )∈Vi ×Vi
d(vk , vl ),
ãäå d(vk , vl ) ïóòü ìåæäó âåðøèíàìè vk è vl .
Èç ñâÿçíîñòè ïîäãðàôà Ri ñëåäóåò, ÷òî åãî äèàìåòð ìîæåò áûòü îãðàíè÷åí:
p
2( Mi − 1) ≤ D(Ri ) ≤ Mi − 1.
8
Ðèñ. 1.2. Äèàìåòð ïîäãðàôà
1.2 Äðîí íåôèêñèðîâàííûé àãåíò
Êàæäûé èãðîê èìååò îäíîãî íåôèêñèðîâàííûé àãåíòà äðîíà.
Îïðåäåëåíèå 1.2.1.
Ïîä íåôèêñèðîâàííûì àãåíòîì qi , i ∈ N áóäåì ïîäðà-
çóìåâàòü òàêîãî àãåíòà, ïîëîæåíèå êîòîðîãî íà ñåòêå â ïðîöåññå èãðû ìîæåò
èçìåíÿòüñÿ, è êîòîðûé îáëàäàåò ñëåäóþùèìè ñâîéñòâîì:
1. äðîí ìîæåò óñòàíàâëèâàòü ñâÿçü ñ ëþáûì äðîíîì qi , i ∈ N , ó÷àñòâóþùåì
â èãðå;
p
2. äðîí ìîæåò óñòàíàâëèâàòü ñâÿçü ñ ëþáûì çàôèêñèðîâàííûì àãåíòîì vi ,
vis , vis ∈ Mi , vip ∈ Mi , s 6= p, i ∈ N , ó÷àñòâóþùåì â èãðå.
Ñâÿçü äðîíà ñ çàôèêñèðîâàííûìè àãåíòàìè îïðåäåëÿåòñÿ àíàëîãè÷íî ñâÿçè ìåæäó çàôèêñèðîâàííûìè àãåíòàìè.
Ïîëàãàåì, ÷òî â íà÷àëüíîì ñîñòîÿíèè èãðû âñå äðîíû qi ðàñïîëîæåíû â
òàêîé ïîçèöèè k = (x, y), ÷òî íå ìîãóò óñòàíàâëèâàòü ñâÿçü íè ñ îäíèì àãåíòîì
íè îäíîãî èãðîêà, ò. å:
d(k, vip ) > 1,
(1.1)
d(k, vis ) > 1,
(1.2)
vis ∈ Mi , vip ∈ Mi , s 6= p, i ∈ N.
(1.3)
9
Ïîäãðàô Ri∗ ðàñøèðåííûé ïîäãðàô, ïîëó÷åííûé èç ïîäãðàôà Ri äîáàâëåíèåì äðîíîâ, ìíîæåñòâî âåðøèí ïîäãðàôà Ri∗ îïðåäåëÿåòñÿ êàê:
n
V (Ri∗ ) = Mi ∪ ∪ qi , i = 1, ..., n,
i=1
(1.4)
à ìíîæåñòâî ðåáåð îïðåäåëÿåòñÿ ñâÿçÿìè íà ìíîæåñòâå V (Ri∗ ) (ñì. ðèñ. 1.3).
Ðèñ. 1.3. Ðàñøèðåííûé ïîäãðàô
1.3 Ñòðàòåãèè è âûèãðûø
Êàæäûé èãðîê ñòàâèò ïåðåä ñîáîé çàäà÷ó ðàñïîëîæèòü äðîíà òàê, ÷òîáû
ìèíèìèçèðîâàòü äèàìåòð ðàñøèðåííîãî ïîäãðàôà.
Èãðîêè õîäÿò ïîñëåäîâàòåëüíî. Íà êàæäîì øàãå èãðîê i âûáèðàåò îäíè
ýëåìåíò èç ñâîåãî ìíîæåñòâà àëüòåðíàòèâ Wi . Ïîëàãàåì, ÷òî â íà÷àëüíîì ñîñòîÿíèè èãðû, êàæäûé èãðîê çíàåò ðàñïîëîæåíèå çàôèêñèðîâàííûõ àãåíòîâ äðóãèõ èãðîêîâ, òàêæå ïîëîæèì, ÷òî èãðîê ¾ïîìíèò¿ è ¾çíàåò¿ ñâîè ïðåäûäóùèå
õîäû è ïðåäûäóùèå õîäû äðóãèõ èãðîêîâ. Îòìåòèì, ÷òî äðîí ìîæåò ðàñïîëàãàòüñÿ íå òîëüêî â âåðøèíàõ ñåòêè, à òàêæå è â öåíòðå ñàìîãî ãåêñàãîíà. Òîãäà
íà ïåðâîì øàãå èãðû ïîä ìíîæåñòâîì ñòðàòåãèé Wi (n − 1) èãðîêîâ ïîíèìàåòñÿ
âñå âîçìîæíûå ïîëîæåíèÿ íà ãåêñàãîíàëüíîé ðåøåòêå, êîòîðûå óìåíüøàò äèàìåòð ðàñøèðåííîãî ïîäãðàôà Ri∗ èãðîêà i ïî ñðàâíåíèþ ñ íà÷àëüíûì äèàìåòðîì
(¾ïðîñòûå¿ ñòðàòåãèè), à òàêæå òàêèå ñòðàòåãèè, êîòîðûå óìåíüøàò äèàìåòð
ïîäãðàôà ¾â ïåðñïåêòèâå¿ (ñì. ðèñ. 1.4).  äàííîì ñëó÷àå ïîä ñòðàòåãèåé ¾â ïåð10
ñïåêòèâå¿ ïîäðàçóìåâàåòñÿ: âñå èãðîêè íà íà÷àëüíîì ýòàïå çíàþò êîëè÷åñòâî
äðîíîâ è ðàñïîëîæåíèå àãåíòîâ äðóãèõ èãðîêîâ, ñëåäîâàòåëüíî, (n − 1) èãðîêîâ â íà÷àëå èãðû ìîãóò ¾ïðîñ÷èòàòü¿ ñòðàòåãèè íà íåñêîëüêî øàãîâ âïåðåä,
êàê áóäòî ó èãðîêà íå îäèí äðîí â óïðàâëåíèè, à âñå. Ìàêñèìàëüíîå êîëè÷åñòâî
¾òàêèõ¿ øàãîâ ïåðâîãî èãðîêà ñîîòâåòñòâóåò êîëè÷åñòâó äðîíîâ (ò.ê. ó êàæäîãî
èãðîêà òîëüêî îäèí äðîí, ñëåäîâàòåëüíî, êîëè÷åñòâó èãðîêîâ), âòîðîãî êîëè÷åñòâî èãðîêîâ ìèíóñ 1, (n−1) èãðîêà 1 (äàëåå, ìû ââåäåì ïîíÿòèå ñòðàòåãèè
â ¾â ïåðåñïåêòèâå¿, êîòîðîå îãðàíè÷èò êîëè÷åñòâî ¾òàêèõ¿ øàãîâ äî îäíîãî).
Ýòîò ¾ïðîñ÷¼ò¿ â áîëüøèíñòâå ñëó÷àåâ ïðèâîäèò ê óìåíüøåíèþ äëèíó èãðû,
à òàêæå íàõîæäåíèþ áîëåå âûãîäíûõ ñòðàòåãèé, ò. å. ôóíêöèÿ âûèãðûøà äëÿ
ñòðàòåãèè ¾â ïåðåñïåêòèâå¿ ïî îêîí÷àíèþ èãðû áóäåò áîëüøå, ÷åì äëÿ ¾ïðîñòûõ¿ ñòðàòåãèè. Ñòîèò îòìåòèòü, ÷òî âûáîð íà ïåðâîì øàãå i èãðîêîì òàêèõ
ñòðàòåãèé ¾â ïåðñïåêòèâå¿ äàåò ¾íóëåâîé¿ âûèãðûø íà ïåðâîì øàãå (Hi1 = 0,
i = 1, . . . , n − 1).
Äàëåå äëÿ èãðîêà n íà ïåðâîì øàãå è ñëåäóþùèõ øàãàõ âñåõ èãðîêîâ ïîä
ìíîæåñòâîì ñòðàòåãèé Wi èãðîêà i áóäåì ïîíèìàòü òîëüêî ¾ïðîñòûå¿ ñòðàòåãèè. Ñòîèò îòìåòèòü, ÷òî ìíîæåñòâî ñòðàòåãèé èãðîêà i íà êàæäîì øàãå çàâèñèò
îò åãî ïðåäûäóùèõ õîäîâ, è îò ïðåäûäóùèõ õîäîâ äðóãèõ èãðîêîâ.
Ñëåäîâàòåëüíî, êàæäûé èãðîê i ïîñëå ïåðâîãî øàãà ðåøàåò çàäà÷ó ñëåäóþùåãî âèäà:
qi = argmin D(Ri )
(1.5)
i∈Wi
Òàê êàê îäíî èç ïðèìåíåíèé ñåòåé MANET ýòî ñïàñàòåëüíûå îòðÿäû,
ñëåäîâàòåëüíî, áóäåì ïîëàãàòü, ÷òî ñòðàòåãèè èãðîêîâ áóäóò ¾áëàãîæåëàòåëüíû¿ â òîì ñìûñëå, ÷òî èãðîê i ∈ N ïðè ñîâåðøåíèè ñâîåãî õîäà, áóäó÷è â
ðàâíîé ñòåïåíè çàèíòåðåñîâàí â âûáîðå ïîñëåäóþùèõ àëüòåðíàòèâ, âûáèðàåò
òó èç íèõ, êîòîðàÿ áîëåå áëàãîïðèÿòíà äëÿ äðóãîãî èãðîêà [15], ò. å. â íàøåì
ñëó÷àå êàæäûé èãðîê ïåðåìåùàåò ñâîåãî äðîíà òàê, ÷òîáû íå óâåëè÷èòü äèàìåòðû ïîäãðàôîâ äðóãèõ èãðîêîâ. Ñëåäîâàòåëüíî, äàííûé ïðîöåññ ìîæåò áûòü
ñôîðìóëèðîâàí êàê êîíå÷íîøàãîâàÿ èãðà ñ ïîëíîé èíôîðìàöèåé.
Èãðà çàêàí÷èâàåòñÿ êîãäà íè îäèí èç èãðîêîâ íå ìîæåò äàëåå óìåíüøèòü
äèàìåòðà ñâîåãî ðàñøèðåííîãî ïîäãðàôà. Ôóíêöèÿ âûèãðûøà Hi èãðîêà i çà-
11
äàåòñÿ ñëåäóþùèì îáðàçîì:
Hi = d(Ri ) − d(Ri∗ ) ≥ 0.
(1.6)
Çíàÿ îïðåäåëåíèå ôóíêöèè âûèãðûøà 1.12, ââåäåì îïðåäåëåíèÿ ¾ïðîñòîé¿ è ¾â ïåðñïåêòèâå¿ ñòðàòåãèè.
Îïðåäåëåíèå 1.3.1.
Áóäåì ãîâîðèòü, ÷òî ñòðàòåãèÿ wi ÿâëÿåòñÿ ¾ïðîñòîé¿
ñòðàòåãèåé â êîíå÷íîøàãîâîé èãðå n ëèö, åñëè ôóíêöèÿ âûèãðûøà 1.12 èìååò
ñòðîãîå íåðàâåíñòâî è îáëàäàåò ñëåäóþùèì ñâîéñòâîì:
1. ¾ïðîñòàÿ¿ ñòðàòåãèÿ wi íàõîäèòñÿ ìåæäó àãåíòàìè vi (xi , yi ), vi (xi+1 , yi+1 )
èãðîêà i òàêèìè, ÷òî ðàññòîÿíèå ìåæäó íèìè óäîâëåòâîðÿåò ñëåäóþùåìó
íåðàâåíñòâó:
(1.7)
ρ(vi , vi+1 ) ≤ 1
Äëÿ îïðåäåëåíèÿ ïîíÿòèÿ ñòðàòåãèÿ ¾â ïåðñïåêòèâå¿ ââåäåì îïðåäåëåíèÿ
îáëàñòè ¾â ïåðñïåêòèâå¿ è ìíîæåñòâà ñòðàòåãèé ¾â ïåðñïåêòèâå¿.
Îïðåäåëåíèå 1.3.2.
Îáëàñòü U1h íàçûâàåòñÿ îáëàñòüþ ¾â ïåðñïåêòèâå¿ â êî-
íå÷íîøàãîâîé èãðå 2 ëèö äëÿ èãðîêà 1 íà ïåðâîì øàãå èãðû, åñëè îíà ïðèíàä-
−−→
ëåæèò îáëàñòè, îãðàíè÷åííîé ïðÿìûìè x = x0 è x = x1 ïî îñè OX è ïðÿìûìè
−−→
y = y0 è y = y1 ïî îñè OY , ãäå (x0 , y0 ), (x1 , y2 ) êîîðäèíàòû òàêèõ àãåíòîâ
v11 (x0 , y0 ) v21 (x1 , y2 ) èãðîêà 1, êîòîðûå óäîâëåòâîðÿþò ñëåäóþùèì óñëîâèÿì:
1. äëÿ ëþáûõ àãåíòîâ v11 (x0 , y0 ) v21 (x1 , y2 ) èãðîêà 1 ñóùåñòâóþò àãåíòû
v12 (x0 , y0 ) v22 (x1 , y2 ) èãðîêà 2;
2. ðàññòîÿíèå ìåæäó àãåíòàìè (v11 , v21 ) óäîâëåòâîðÿåò íåðàâåíñòâó:
2 < ρ(v11 , v21 ) ≤ 3
(1.8)
Ðàñøèðèì ïîíÿòèå îáëàñòè ¾â ïåðñïåêòèâå¿ íà èãðó n ∈ N ëèö. Äëÿ ýòîãî
ðàññìîòðèì äâà ñëåäóþùèõ ñëó÷àÿ:
1. â âåðøèíàõ a = (x0 , y0 ) è b = (x1 , y2 ) íàõîäÿòñÿ k èãðîêîâ, k ∈ N , k ≤ n,
12
ðàññòîÿíèå ìåæäó âåðøèíàìè:
(1.9)
ρ(a, b) ≤ n + 1 − i;
2. â âåðøèíàõ a = (x0 , y0 ) è b = (x1 , y2 ) íàõîäÿòñÿ k èãðîêîâ, k ∈ N , k ≤ n,
ðàññòîÿíèå ìåæäó âåðøèíàìè:
(1.10)
n + 1 − i < ρ(a, b) < n + 2 − i.
Îáúåäèíÿÿ íåðàâåíñòâà 1.8, 1.9, 1.10, ïîëó÷àåì îïðåäåëåíèå îáëàñòè ¾â
ïåðñïåêòèâå¿.
Îïðåäåëåíèå 1.3.3.
Îáëàñòü Uikh íàçûâàåòñÿ îáëàñòüþ ¾â ïåðñïåêòèâå¿ â êî-
íå÷íîøàãîâîé èãðå n ëèö äëÿ èãðîêà i íà ïåðâîì øàãå èãðû, åñëè îíà ïðèíàä-
−−→
ëåæèò îáëàñòè, îãðàíè÷åííîé ïðÿìûìè x = x0 è x = x1 ïî îñè OX è ïðÿìûìè
−−→
y = y0 è y = y1 ïî îñè OY , ãäå (x0 , y0 ), (x1 , y2 ) êîîðäèíàòû òàêèõ àãåíòîâ
v1i (x0 , y0 ) v2i (x1 , y2 ) èãðîêà i, êîòîðûå óäîâëåòâîðÿþò ñëåäóþùèì óñëîâèÿì:
1. äëÿ ëþáûõ àãåíòîâ v1i (x0 , y0 ) v2i (x1 , y2 ) èãðîêà i ñóùåñòâóþò àãåíòû
v1j (x0 , y0 ) v2j (x1 , y2 ), v1j+1 (x0 , y0 ) v2j (x1 , y2 ), . . . , v1j+l (x0 , y0 ) v2j+l (x1 , y2 ) èãðîêîâ j , j + 1, . . . , j + l, ãäå j ∈ k ≤ n;
2. ðàññòîÿíèå ìåæäó àãåíòàìè (v1i , v2i ) óäîâëåòâîðÿåò íåðàâåíñòâó:
2 < ρ(a, b) < n + 2 − i.
(1.11)
m
Îïðåäåëåíèå 1.3.4.
Ìíîæåñòâî Wih = ∪ Uikh , ãäå m êîëè÷åñòâî îáëàñòåé
k=1
¾â ïåðñïåêòèâå¿ èãðîêà i, íàçûâàåòñÿ ìíîæåñòâîì îáëàñòåé ñòðàòåãèé ¾â ïåðñïåêòèâå¿ èãðîêà i.
Ìíîæåñòâî îáëàñòåé ¾â ïåðñïåêòèâå¿ äëÿ èãðû 2 ëèö èçîáðàæåíà íà ðèñ.
1.4.
Îïðåäåëåíèå 1.3.5.
Áóäåì ãîâîðèòü, ÷òî ñòðàòåãèÿ wi ÿâëÿåòñÿ ñòðàòåãèåé ¾â
ïåðñïåêòèâå¿ wih â êîíå÷íîøàãîâîé èãðå n äëÿ èãðîêà i íà ïåðâîì øàãå, åñëè wh
ïðèíàäëåæèò ìíîæåñòâó îáëàñòåé ñòðàòåãèé ¾â ïåðñïåêòèâå¿ Wih (wih ∈ Wih ) è
13
ôóíêöèÿ âûèãðûøà ðàâíà íóëþ, ò. å.:
Hi (wih ) = 0, äëÿ i ≤ n − 1
(1.12)
Ðèñ. 1.4. Ìíîæåñòâî îáëàñòåé ¾â ïåðñïåêòèâå¿
1.4 Ôîðìóëû íàõîæäåíèÿ ñòðàòåãèé
1.4.1
¾Ïðîñòûå¿ ñòðàòåãèè íà ãåêñàãîíàëüíîé ðåøåòêå
Íàéäåì ôîðìóëó äëÿ âû÷èñëåíèÿ êîîðäèíàò ¾ïðîñòûõ¿ ñòðàòåãèé. Äëÿ
ýòîãî èç îïðåäåëåíèÿ ¾ïðîñòîé¿ ñòðàòåãèè 1.3.1 è ïîñòàíîâêè çàäà÷è (äðîí ó
êàæäîãî èãðîêà îäèí, ðàäèóñ äåéñòâèÿ äðîíà ðàâåí ðàäèóñó äåéñòâèÿ çàôèêñèðîâàííîãî àãåíòà, ò. å. 1, âîçìîæíîñòü óñòàíàâëèâàòü äðîíà â öåíòð ãåêñàãîíà)
íàéäåì âñå ñèòóàöèè ðàñïîëîæåíèÿ àãåíòîâ íà ñåòêå, ìåæäó êîòîðûìè ìîæíî óñòàíîâèòü äðîíà. Âîçìîæíûå ñèòóàöèè ðàñïîëîæåíèÿ àãåíòîâ ìåæäó êîòîðûìè ìîæíî óñòàíîâèòü äðîíà ïðîäåìîíñòðèðîâàíû íà ðèñ. 1.5, ãäå êðàñíàÿ
îêðóæíîñòü àãåíò vl0 (vr0 ) èãðîêà, à æåëòûå îêðóæíîñòè àãåíòû vl1 ,. . . ,vl9
(vr1 ,. . . ,vr9 ) âîçìîæíûå ñèòóàöèè ðàñïîëîæåíèÿ àãåíòîâ èãðîêà îòíîñèòåëüíî àãåíòà vl0 (vr0 ). Íà ðèñóíêå òàêæå èçîáðàæåíû âñåâîçìîæíûå ñèòóàöèè äëÿ
14
óñòàíîâêè äðîíîâ (çåëåíûå îêðóæíîñòè). Â òàáë. 1.1, 1.2 ïðåäñòàâëåíà ðàñøèôðîâêà ðèñóíêà, ãäå ðàññòîÿíèå ýòî ðàññòîÿíèå ìåæäó àãåíòîì v0k è àãåíòîì
èç ñòîëáöà ¾àãåíò¿, îïðåäåëÿåìîå ñëåäóþùåé ôîðìóëîé:
ρ(v0k , vik )
q
= (xk0 − xki )2 + (y0k − yik )2 , i = 1, . . . , 9, k = l, r,
(1.13)
ãäå (xk0 , y0k ) êîîðäèíàòû àãåíòà vk0 , (xki , yik ) êîîðäèíàòû àãåíòà vki . Ìåæäó
àãåíòàìè vk0 è vki óñòàíàâëèâàåòñÿ äðîí ïîä íîìåðîì èç ñòîëáöà ¾äðîí¿.
vl3 vl2
vl4 ql3 ql2 vl1
vr3 vr2
vl5 ql4 vl0 ql1
vr4 qr3 qr2 vr1
vl6 ql5 ql6 vl9
qr4 vr0 qr1 vr9
vr5 qr5 qr6 vr8
vl7 vl8
vr6 vr7
Ðèñ. 1.5. Âñåâîçìîæíûå êîìáèíàöèè ¾ïðîñòûõ¿ ñòðàòåãèé
Àãåíò
vl1
vl2
vl3
vl4
vl5
vl6
vl7
vl8
vl9
Äðîí Ðàññòîÿíèå
√
ql1 , ql2
√3
ql2 , ql3
3
ql3
ql3 , ql4
ql4 , ql5
ql5
ql5 , ql6
ql6 , ql1
ql1
Àãåíò Äðîí Ðàññòîÿíèå
√
v1
q1 , q 2
3
v2
v3
v4
v5
v6
v7
v8
v9
√1
√3
3
√1
√3
3
1
q2
q2 , q 3
q3 , q 4
q4
q4 , q 5
q5 , q 6
q6
q6 , q 1
√1
√3
3
√1
√3
3
√1
3
Òàáëèöà 1.1. Ðàñøèôðîâêà
Òàáëèöà 1.2. Ðàñøèôðîâêà
ëåâîé ÷àñòè ðèñ. 1.5
ïðàâîé ÷àñòè ðèñ. 1.5
Êàê âèäíî èç ðèñ. 1.5 è òàáë. 1.1, 1.2 âñå äðîíû qr1 , . . . , qr6 îòíîñèòåëüíî
15
àãåíòà vr0 èìåþò èäåíòè÷íîå ðàñïîëîæåíèå, êàê äðîíû ql1 , . . . , ql6 îòíîñèòåëüíî àãåíòà vl0 , ñëåäîâàòåëüíî, äëÿ òîãî ÷òîáû íàéòè ôîðìóëó âû÷èñëåíèÿ ¾ïðîñòûõ¿ ñòðàòåãèé äîñòàòî÷íî ðàññìîòðåòü ïðàâóþ ÷àñòü ðèñ. 1.5. Äëÿ óïðîùåíèÿ
çàïèñè èíäåêñ k = r ïðè v è q â äàëüíåéøèõ âûêëàäêàõ îïóùåí.
Èç òàáë. 1.2 ìîæíî ñäåëàòü âûâîä, ÷òî ôîðìóëû âû÷èñëåíèÿ è êîëè÷åñòâî äðîíîâ áóäóò çàâèñåòü îò ðàññòîÿíèÿ. Íàéäåì ôîðìóëû äëÿ äðîíîâ, ãäå
→ −−→
−−→
ρ(v0 , vi ) = 1. Èç ðèñ. 1.5, âèäíî, ÷òî âåêòîðà −
v−
0 v3 , v0 v5 ïîëó÷åíû èç âåêòîðà v0 v9
−−→
→
ïîâîðîòîì îòíîñèòåëüíî îñè OX , ñëåäîâàòåëüíî, ðàññìîòðèì âåêòîð −
v−
0 v9 è íàéäåì ôîðìóëó äëÿ âû÷èñëåíèÿ êîîðäèíàò äðîíà q1 è âîñïîëüçóåìñÿ ôîðìóëîé
ïîâîðîòà äëÿ âû÷èñëåíèÿ îñòàëüíûõ êîîðäèíàò:
xn = (x − x0 ) cos φ − (y − y0 )sinφ + x0 ,
(1.14)
yn = (x − x0 ) sin φ + (y − y0 )cosφ + y0 .
(1.15)
Ôîðìóëû êîîðäèíàò äëÿ äðîíà q1 èìåþò âèä:
x(q1 ) = x0 + 1,
(1.16)
y(q1 ) = y0 + 0.
(1.17)
Ïîäñòàâëÿÿ ðàâåíñòâà 1.16, 1.17 â óðàâíåíèÿ 1.14, 1.15 ïîëó÷àåì ôîðìóëû
äëÿ óñòàíîâêè äðîíà, êîãäà ðàññòîÿíèå ìåæäó àãåíòàìè ρ(v0 , vi ) = 1:
x(qi ) = x0 + cos φ,
(1.18)
y(qi ) = y0 + sin φ,
(1.19)
−−→
→
ãäå φ óãîë ïîâîðîòà âåêòîðà −
v−
0 v9 îòíîñèòåëüíî îñè OX .
Ðàññìîòðèì ñëó÷àé, êîãäà ρ(v0 , vi ) =
√
3. Èç òàáë.1.1, 1.2 âèäíî, ÷òî â
ýòîì ñëó÷àå ó íàñ äâà âîçìîæíûõ âàðèàíòà äëÿ óñòàíîâêè äðîí. Èç ðèñ. 1.5,
→ −−→ −−→ −−→ −−→
−−→
âèäíî, ÷òî âåêòîðà −
v−
2 v0 , v0 v4 , v0 v5 , v0 v7 , v0 v8 ïîëó÷åíû èç âåêòîðà v0 v1 ïîâî−−→
→
ðîòîì îòíîñèòåëüíî îñè OX , ñëåäîâàòåëüíî, ðàññìîòðèì âåêòîð −
v−
0 v1 è íàéäåì
ôîðìóëû äëÿ âû÷èñëåíèÿ êîîðäèíàò äðîíà q2 . Ôîðìóëû äëÿ q1 óæå íàéäåíû.
Ôîðìóëû äëÿ q2 èìåþò âèä:
16
1
x(q2 ) = x0 + ,
√2
3
.
y(q2 ) = y0 +
2
(1.20)
(1.21)
Ïîäñòàâëÿÿ ðàâåíñòâà 1.20, 1.21 â óðàâíåíèÿ 1.14, 1.15 ïîëó÷àåì::
1
x(qi ) = x0 + cos φ,
√2
3
y(qi ) = y0 +
sin φ,
2
(1.22)
(1.23)
−−→
→
ãäå φ óãîë ïîâîðîòà âåêòîðà −
v−
1 v0 îòíîñèòåëüíî îñè OX .
Îáùèé âèä ôîðìóë äëÿ êîîðäèíàò ¾ïðîñòîé¿ ñòðàòåãèè, çíàÿ êîîðäèíàòû
àãåíòîâ v0 è v èãðîêà i, ðàññòîÿíèå ìåæäó êîòîðûìè óäîâëåòâîðÿåò íåðàâåíñòâó
1.7, èìååò âèä:
√
x1 = x0 + cos φ, y1 = y0 + sin φ, ïðè ρ(v0 , v) = 1, ρ(v0 , v) = 3
√
√
3
1
sin φ, ρ(v0 , v) = 3,
x2 = x0 + cos φ, y2 = y0 +
2
2
(1.24)
(1.25)
−−→
ãäå φ óãîë ïîâîðîòà âåêòîðà −
v→
0 v îòíîñèòåëüíî îñè OX , à ρ(v0 , v) ðàññòîÿíèå
ìåæäó àãåíòàìè v0 è v .
1.4.2
Ñòðàòåãèè ¾â ïåðñïåêòèâå¿ íà ãåêñàãîíàëüíîé ðåøåòêå
Íàéäåì ôîðìóëû âû÷èñëåíèÿ êîîðäèíàò ñòðàòåãèé ¾â ïåðñïåêòèâå¿. Äëÿ
ýòîãî èç îïðåäåëåíèÿ ñòðàòåãèè ¾â ïåðñïåêòèâå¿ 1.3.5 è ïîñòàíîâêè çàäà÷è íàéäåì âñå ñèòóàöèè ðàñïîëîæåíèÿ àãåíòîâ íà ñåòêå, ìåæäó êîòîðûìè ìîæíî óñòàíîâèòü äðîíà äëÿ êîíå÷íîøàãîâîé èãðû äâóõ ëèö. Âîçìîæíûå ñèòóàöèè ðàñïîëîæåíèÿ àãåíòîâ ìåæäó êîòîðûìè ìîæíî óñòàíîâèòü äðîíà ïðîäåìîíñòðèðîâàíû íà ðèñ. 1.6. Âñå îáîçíà÷åíèÿ íà ðèñ. 1.6 àíàëîãè÷íû îáîçíà÷åíèÿì íà ðèñ. 1.5.
 òàáë. 1.3 è 1.4 ïðèâåäåíà ðàñøèôðîâêà ðèñóíêà. Îòìåòèò òîëüêî òîò ôàêò,
÷òî âî âñåõ ïîçèöèÿõ, ãäå íàõîäÿòñÿ àãåíòû èãðîêà 1 (vl0 , . . . , vl11 , vr0 , . . . , vr11 ,),
òàêæå íàõîäÿòñÿ àãåíòû èãðîêà 2 (ï.1 îïðåäåëåíèÿ 1.3.5). Èç ðèñóíêà âèäíî, ÷òî
äðîíû ql1 , . . . , ql6 , qr1 , . . . , qr6 èìåþò àíàëîãè÷íûå ïîçèöèè, êàê äðîíû ql1 , . . . , ql6 ,
17
qr1 , . . . , qr6 èç ðèñ. 1.5, ñëåäîâàòåëüíî, äëÿ âû÷èñëåíèÿ êîîðäèíàò ýòèõ äðîíîâ
ìîæíî âîñïîëüçîâàòüñÿ ôîðìóëàìè 1.24, 1.25, ñ çàìåíîé ρ íà ñîîòâåòñòâóþùèå
çíà÷åíèÿ èç òàáë. 1.3 ïîëó÷àåì:
√
x1 = x0 + cos φ, y1 = y0 + sin φ, äëÿ ρ(v0 , v) = 3, ρ(v0 , v) = 7
√
√
1
3
sin φ, äëÿ ρ(v0 , v) = 7,
x2 = x0 + cos φ, y2 = y0 +
2
2
vl5 vl4
(1.27)
vl3
vl6 ql10 ql9 ql8
vr5
ql11 ql3 ql2 ql7 vl2
vr4 vr3
qr10 qr9 qr8 vr2
vl7 ql12 ql4 vl0 ql1 ql18 vl1
vr6 qr11 qr3 qr2 qr7
ql13 ql5 ql6 ql17 vl12
vr7 qr12 qr4 vr0 qr1 qr18 vr1
vl8 ql14 ql15 ql16
vl9 vl10
(1.26)
vr8 qr13 qr5 qr6 qr17
qr14 qr15 qr16 vr12
vl11
vr9
vr10 vr11
Ðèñ. 1.6. Âñåâîçìîæíûå êîìáèíàöèè ñòðàòåãèé ¾â ïåðñïåêòèâå¿ äëÿ êîíå÷íîøàãîâîé èãðû
äâóõ ëèö
Ðàññìîòðèì òåïåðü äðîíû ql7 , . . . , ql18 , qr7 , . . . , qr18 . Èç îïðåäåëåíèé 1.3.1,
1.3.3, 1.3.4, 1.3.5 ìîæíî ñäåëàòü ïðåäïîëîæåíèå, ÷òî äëÿ èãðîêà 1 íå íàäî èõ
âû÷èñëÿòü, ïîòîìó ÷òî èãðîê 2 ñàì èõ âû÷èñëèò, ò. ê. äëÿ èãðîêà 2 â åãî õîä
äàííûå äðîíû ïîïàäóò ïîä îïðåäåëåíèå ¾ïðîñòûõ¿ ñòðàòåãèé. Äëÿ ïîíèìàíèÿ
õîäà ðàçìûøëåíèé ðàññìàòðèì ñëåäóþùèé ïðèìåð. Ïóñòü ïðîèñõîäèò èãðà 2
ëèö. Èãðîê 1 â ñâîåì ìíîæåñòâå çàôèêñèðîâàííûõ àãåíòîâ M1 èìååò àãåíòà
v11 ∈ M1 ñ êîîðäèíàòàìè àãåíòà vl0 èç ðèñ. 1.6 è àãåíòà v21 ∈ M1 ñ êîîðäèíàòàìè
àãåíòà vl3 èç ðèñ. 1.6. Ïóñòü èãðîê 2 òàêæå èìååò àãåíòà v12 ∈ M2 ñ êîîðäèíàòàìè àãåíòà vl0 èç ðèñ. 1.6 è àãåíòà v22 ∈ M2 ñ êîîðäèíàòàìè àãåíòà vl3 èç
ðèñ. 1.6. Ïóñòü èãðîê 1 íà ñâîåì ïåðâîì øàãå ïî ôîðìóëàì 1.26, 1.27 íàõîäèò
êîîðäèíàòû äðîíà (â äàííîì ñëó÷àå êîîðäèíàòû äðîíà ql2 íà ðèñ. 1.6). Ïî ïðåäïîëîæåíèþ, ÷òî êîîðäèíàòû äðîíà ql8 íå íàäî âû÷èñëÿòü, íå âû÷èñëÿåò èõ è
18
Àãåíò
vl1
vl2
vl3
vl4
vl5
vl6
vl7
vl8
vl9
vl10
vl11
vl12
Äðîí
Ðàññòîÿíèå
ql1 , ql18
√3
ql1 , ql2 , ql18 , ql7
7
ql3 , ql8
√3
ql2 , ql3 , ql9 , ql10
7
ql3 , ql10
√3
ql3 , ql4 , ql10 , ql11
7
ql4 , ql12
√1
ql4 , ql5 , ql13 , ql14
7
ql5 , ql14
√3
ql5 , ql6 , ql14 , ql15
7
ql6 , ql16
√3
ql6 , ql1 , ql17 , ql18
7
Àãåíò
vl1
vl2
vl3
vl4
vl5
vl6
vl7
vl8
vl9
vl10
vl11
vl12
Äðîí
ql1 , ql18
ql1 , ql2 , ql7 ,
ql2 , ql8
ql2 , ql3 , ql8 ,
ql3 , ql10
ql3 , ql4 , ql11 ,
ql4 , ql12
ql4 , ql5 , ql12 ,
ql5 , ql14
ql5 , ql6 , ql15 ,
ql6 , ql16
ql6 , ql1 , ql16 ,
Ðàññòîÿíèå
ql8
ql9
ql12
ql13
ql16
ql17
√3
7
√3
7
√3
7
√1
7
√3
7
√3
7
Òàáëèöà 1.3. Ðàñøèôðîâêà
Òàáëèöà 1.4. Ðàñøèôðîâêà
ëåâîé ÷àñòè ðèñ. 1.6
ïðàâîé ÷àñòè ðèñ. 1.6
çàêàí÷èâàåò ñâîé õîä, óñòàíàâëèâàÿ ñâîåãî äðîíà q1 â ïîçèöèþ ql2 . Õîä ïåðåõîäèò ê èãðîêó 2. Ïî ñâîéñòâàì äðîíà 1.2.1 è îïðåäåëåíèþ ìíîæåñòâà âåðøèí
ðàñøèðåííîãî ïîäãðàôà 2.3, èãðîê 2 ìîæåò ðàññìàòðèâàòü äðîíà q1 , êàê ñâîåãî
äîïîëíèòåëüíîãî çàôèêñèðîâàííîãî àãåíòà, ñëåäîâàòåëüíî, ïî ôîðìóëàì 1.24,
1.25 èãðîê 2 íàõîäèò êîîðäèíàòû, êîòîðûå ñîîòâåòñòâóþò êîîðäèíàòàì ql8 èç
ðèñóíêà. Ðàñøèðèì ïðåäïîëîæåíèå íà èãðó n ëèö, ïîëó÷èì ïðàâèëî è ôîðìóëó
äëÿ âû÷èñëåíèÿ ñòðàòåãèé ¾â ïåðñïåêòèâå¿.
Ïðàâèëî âû÷èñëåíèÿ êîîðäèíàò ñòðàòåãèé ¾â ïåðñïåêòèâå¿.
Íà
ïåðâîì øàãå èãðû èãðîê i äîëæåí âû÷èñëÿòü êîîðäèíàòû ñòðàòåãèè ¾â ïåðñïåêòèâå¿ ìåæäó èãðîêàìè v0i , v i , óäîâëåòâîðÿþùèì ñâîéñòâàì 1, 2 îïðåäåëåíèÿ
1.3.3, ïî ñëåäóþùèì ôîðìóëàì:
x1 = x0 + cos φ, y1 = y0 + sin φ,
(1.28)
äëÿ 2 < ρ(v0i , v i ) < n + 2 − i è ρ(v0i , v i ) = n + 2 − i,
√
1
3
x2 = x0 + cos φ, y2 = y0 +
sin φ,
2
2
äëÿ 2 < ρ(v0i , v i ) < n + 2 − i,
19
(1.29)
Ãëàâà 2. Êîîïåðàòèâíûé âàðèàíò
2.1 Êîîïåðàòèâíûé âàðèàíò áåç äðîíîâ
Ïóñòü M ìíîæåñòâî àãåíòîâ âñåõ èãðîêîâ, îáúåäèíåííûõ âìåñòå (ìàêñèìàëüíàÿ êîàëèöèÿ), ÷òî ñîîòâåòñòâóåò èõ êîîïåðàòèâíîìó ïîâåäåíèþ. Î÷åâèäíî, ÷òî
n
|M | 6 | ∪ Mi |,
i = 1, . . . , n,
i=1
ãäå n êîëè÷åñòâî èãðîêîâ. Çàìåòèì, ÷òî â äàííîé ðàáîòå ðàññìàòðèâàåòñÿ
òîëüêî êîîïåðàöèÿ èãðîêîâ â ìàêñèìàëüíóþ êîàëèöèþ.
Ìíîæåñòâî àãåíòîâ ql ∈ M è ñâÿçåé e = (qp , qs ), qp ∈ M , qs ∈ M , s 6= p,
n
îïðåäåëÿþò ãðàô G = (T, K), ãäå T = ∪ V íåïóñòîå êîíå÷íîå ìíîæåñòâî
i=1
ýëåìåíòîâ, K êîíå÷íîå ìíîæåñòâî íåóïîðÿäî÷åííûõ ïàð ýëåìåíòîâ èç T .
Ãðàô G îïðåäåëÿåò îáùóþ ñåòåâóþ ñòðóêòóðó èãðû ïðè êîîïåðàöèè èãðîêîâ â
ìàêñèìàëüíóþ êîàëèöèþ.
Îïðåäåëèì äèàìåòð ãðàôà D(G) ïðè êîîïåðàöèè âñåõ èãðîêîâ (ðèñ. 3.1),
êàê
D(G) =
max
(gk ,gl )∈Ti ×Ti
d(gk , gl ),
(2.1)
ïðåäïîëàãàÿ, ÷òî ïîñëå îáúåäèíåíèÿ âñåõ èãðîêîâ â ìàêñèìàëüíóþ êîàëèöèþ
ãðàô G ÿâëÿåòñÿ íåçàìêíóòûì, ò. å. ñóùåñòâóåò õîòÿ áû îäèí ïîäãðàô Gi ∈
G, êîòîðûé ÿâëÿåòñÿ íåçàìêíóòûì. Ïóñòü òàêæå ãðàô G áóäåò ñâÿçíûì. Èç
ñâÿçíîñòè ãðàôà G ñëåäóåò, ÷òî åãî äèàìåòð ìîæåò áûòü îãðàíè÷åí:
√
2( M − 1) ≤ D(G) ≤ M − 1.
Îïðåäåëèì ôóíêöèþ âûèãðûøà èãðîêà i ñëåäóþùèì îáðàçîì:
Hic = D(G) − D(Ri ) > 0,
(2.2)
ãäå D(G) äèàìåòð ãðàôà ïðè êîîïåðàòèâíîì âàðèàíòå, Ri äèàìåòð ïîäãðàôà èãðîêà i ïðè íåêîîïåðàòèâíîé ïîñòàíîâêå.
20
2.2 Êîîïåðàòèâíûé âàðèàíò ñ äðîíàìè
Ïóñòü, êàê è â íåêîîïåðàòèâíîé ïîñòàíîâêå, êàæäûé èãðîê i èìååò â ñâîåì ðàñïîðÿæåíèè óïðàâëÿåìîãî àãåíòà äðîíà, êîòîðîãî îí ìîæåò óñòàíàâëèâàòü â óçëû ðåøåòêè. Âñå õàðàêòåðèñòèêè äðîíà ÿâëÿþòñÿ àíàëîãè÷íûìè èç
íåêîîïåðàòèâíîãî âàðèàíòà (îïð. 1.2.1). Î÷åâèäíî, ÷òî óñòàíîâêà äðîíà â óçëå
ðåøåòêè ïðèâîäèò ê ðàñøèðåíèþ ãðàôà G, êîòîðûé îáîçíà÷èì êàê G∗ . Ìíîæåñòâî âåðøèí ãðàôà G∗ îïðåäåëÿåòñÿ, êàê:
n
V (G∗ ) = M ∪ ∪ qi , i = 1, . . . , n.
i=1
(2.3)
Ôóíêöèþ âûèãðûøà èãðîêà i â äàííîì ñëó÷àå îïðåäåëèì, êàê:
Hic∗ = d(G∗ ) − d(Ri ) > 0,
(2.4)
ãäå d(G∗ ) äèàìåòð ðàñøèðåííîãî ãðàôà ïðè êîîïåðàòèâíîì âàðèàíòå ñ óñòàíîâëåííûìè äðîíàìè.
21
Ãëàâà 3. Ïðèìåð èãðû
3.1 Íåêîîïåðàòè÷íûé âàðèàíò
3.1.1
Ïðèìåð
 ðàìêàõ äàííîé ðàáîòû áûëî íàïèñàíî ïðîãðàììíîå îáåñïå÷åíèå, ïîçâîëÿþùåå èññëåäîâàòü îïèñàííóþ èãðó. Ïðîãðàììíîå îáåñïå÷åíèå íàïèñàíî íà
ìóëüòèïàðàäèãìåííîì ÿçûêå JavaScript. Âñå ðåçóëüòàòû äàííîé ãëàâû (3) ïîëó÷åíû ñ ïîìîùüþ íàïèñàííîãî ïðîãðàììíîãî îáåñïå÷åíèÿ.
Ðàññìîòðèì èãðó äëÿ äâóõ ó÷àñòíèêîâ. Ïóñòü èãðà Γ ïðîèñõîäèò íà ñåòåâîé ñòðóêòóðå, èçîáðàæåííîé íà ðèñ.3.1. Ìíîæåñòâî èãðîêîâ N ñîñòîèò èç äâóõ
ó÷àñòíèêîâ: N = {1, 2}. Çàôèêñèðîâàííûå àãåíòû ïåðâîãî èãðîêà èçîáðàæåíû
1
= 18), à
â âèäå çàïîëíåííûõ êðóæêîâ æåëòîãî öâåòà (êîëè÷åñòâî àãåíòîâ Nag
2
âòîðîãî èãðîêà (êîëè÷åñòâî àãåíòîâ Nag
= 18) â âèäå çàïîëíåííûõ êðóæ-
êîâ êðàñíîãî öâåòà. Äðîí ïåðâîãî èãðîêà áóäåò èçîáðàæàòüñÿ â âèäå çàïîëíåííîãî êðóæêà ÷¼ðíîãî öâåòà, à âòîðîãî èãðîêà â âèäå çàïîëíåííîãî êðóæêà
ñèíåãî öâåòà. Ïîëîæåíèå êàæäîãî àãåíòà çàäàåòñÿ äâóìÿ êîîðäèíàòàìè.  íà÷àëüíîì ñîñòîÿíèè èãðû äèàìåòðû ïîäãðàôà ïåðâîãî è âòîðîãî èãðîêîâ ðàâíû
(d(R1 ) = d(R2 ) = 17). Çàïîëíåííàÿ ñèíèì öâåòîì îáëàñòü íà ðèñóíêå èçîáðàæàåò ïðåïÿòñòâèå (íàïðèìåð, îçåðî). Íàïîìíèì, ÷òî â íà÷àëüíîì ñîñòîÿíèè
äðîíû íàõîäÿòñÿ â òàêîé ïîçèöèè íà ãåêñàãîíàëüíîé ðåøåòêè, ÷òî íå ìîãóò
óñòàíàâëèâàòü ñâÿçü íè ñ îäíèì àãåíòîì íè îäíîãî èãðîêà.
N
S1
S2
Ðèñ. 3.1. Íà÷àëüíîå ñîñòîÿíèå èãðû. Äèàìåòðû ïîäãðàôîâ
22
d(R1 ) = 17, d(R2 ) = 18
 òàáë. 3.1 ïîêàçàíû ñòðàòåãèè èãðîêà 1 íà ïåðâîì øàãå. Ñòðàòåãèè 1 è 2
ÿâëÿþòñÿ ñòðàòåãèÿìè ¾â ïåðñïåêòèâå¿ äëÿ ïåðâîãî èãðîêà, à ñòðàòåãèè 2 − 6
¾ïðîñòûå¿ ñòðàòåãèè.
ñòðàòåãèè èãðîêà 1 Êîîðäèíàòû äðîíà Ôóíêöèè âûèãðûøà
1
(5, 4.47)
(0; 0)
2
(5.5, 4.47)
(0; 0)
3
(7.5, 5.34)
(2; 2)
4
(6.5, 5.34)
(2; 2)
5
(7.5, 7.07)
(1; 1)
6
(3, 6.2)
(1; 1)
Òàáëèöà 3.1. Ñòðàòåãèè èãðîêà
1
íà ïåðâîì øàãå èãðû
 òàáë. 3.2 ïîêàçàíû ñòðàòåãèè èãðîêà 2 íà ïåðâîì øàãå. Ò. ê. 15 àãåíòîâ
èãðîêà 1 èìåþò ïîçèöèè íà ãåêñàãîíàëüíîé ñåòêå, ðàâíûå ïîçèöèÿì 15-òè àãåíòîâ èãðîêà 2, ñëåäîâàòåëüíî, ïîçèöèè äëÿ óñòàíîâêè äðîíà áóäóò äëÿ íåêîòîðûõ
ñòðàòåãèé âòîðîãî èãðîêà îäèíàêîâûìè ñ íåêîòîðûìè ñòðàòåãèÿìè ïåðâîãî èãðîêà. Ïîýòîìó, äëÿ óïðîùåíèÿ çàïèñè, â òàáë. 3.2 â ñòîëáöå ¾Êîîðäèíàòû äðîíà
2¿ â íåêîòîðûõ ÿ÷åéêàõ íîìåð ñòðàòåãèè èç òàáëèöû 3.1, êîòîðîìó ñîîòâåòñòâóþò êîîðäèíàòû äðîíà èç ñòîëáöà ¾Êîîðäèíàòû äðîíà¿. Íà âòîðîì øàãå èãðû
íè îäèí èç èãðîêîâ íå ìîæåò íàéòè ïîçèöèþ äëÿ óñòàíîâêè ñâîåãî äðîíà, ÷òîáû óìåíüøèòü äèàìåòð ñâîåãî ðàñøèðåííîãî ïîäãðàôà Ri∗ , ñëåäîâàòåëüíî, èãðà
çàêàí÷èâàåòñÿ íà ýòîì øàãå.
3.1.2
Âûâîäû
Èç òàáë. 3.1, 3.2 âèäíî, ÷òî âûèãðûø äëÿ ñòðàòåãèé ¾â ïåðñïåêòèâå¿ áîëüøå, ÷åì äëÿ ¾ïðîñòûõ¿ ñòðàòåãèé è èãðà çàêàí÷èâàåòñÿ íà 2 øàãå.
23
ñòðàòåãèè ñòðàòåãèè Êîîðäèíàòû äðîíà Ôóíêöèè
èãðîêà 1
èãðîêà 2
èãðîêà 2
âûèãðûøà
1
1
(5.5, 5.34)
(6; 6)
1
2
3
(2; 2)
1
3
4
(2; 2)
1
4
5
(1; 1)
1
5
6
(1; 1)
2
6
(5.5, 5.34)
(6; 6)
2
7
3
(2; 2)
2
8
4
(2; 2)
2
9
5
(1; 1)
2
10
6
(1; 1)
3
11
5
(3; 3)
3
12
6
(3; 3)
4
13
(5.5, 5.34)
(5; 5)
4
14
5
(3; 3)
4
15
6
(3; 3)
5
16
4
(4; 4)
5
17
3
(4; 4)
5
18
6
(2; 2)
6
19
5
(2; 2)
6
20
4
(3; 3)
6
21
3
(3; 3)
Òàáëèöà 3.2. Ñòðàòåãèè èãðîêà
2
3.2 Êîîïåðàòèâíûé âàðèàíò
3.2.1
Ïðèìåð èãðû
 äàííîì ðàçäåëå ìû ðàññìîòðèì êîîïåðàòèâíûé âàðèàíò èãðû.
Äèàìåòð ïîäãðàôà äëÿ êîîïåðàòèâíîãî âàðèàíòà èãðû, èçîáðàæåííîé íà
ðèñ. 3.1, áåç ó÷àñòèÿ äðîíîâ, ðàâåí D(G) = 17. Ôóíêöèÿ âûèãðûøà â ýòîì
ñëó÷àå èìååò âèä:
Hic = (0; 0)
(3.1)
Êàê âèäíî èç ôóíêöèè âûèãðûøà, â äàííîì ñëó÷àå êîîïåðàöèÿ èãðîêîâ
íå äàåò âûèãðûøà íè îäíîìó èç èãðîêîâ.
24
Ââåäåì â èãðó äðîíîâ. Íà ðèñ. 3.2 ïîêàçàíû ïîçèöèè äðîíîâ ñ ìàêñèìàëüíûìè ôóíêöèÿìè âûèãðûøà äëÿ îáîèõ èãðîêîâ.  ýòîì ñëó÷àå ôóíêöèè
âûèãðûøà ðàâíû:
Hic = (13; 13)
(3.2)
Ðèñ. 3.2. Ëó÷øèå ðàñïîëîæåíèå äðîíîâ ïðè êîîïåðàòèâíîé èãðå.
3.2.2
Âûâîäû
Êàê âèäíî èç 3.2 ïðè êîîïåðàòèâíîé ïîñòàíîâêå ïðè ââåäåíèè äðîíîâ â
èãðó ôóíêöèè âûèãðûøà áîëüøå, ÷åì ïðè íåêîîïåðàòèâíîé ïîñòàíîâêå. Òàêæå,
ñòîèò îòìåòèòü, ÷òî ïðè ìàêñèìàëüíîé êîîïåðàöèè ïðîöåññ ðàçâèòèÿ èãðû íå
çàâèñèò îò òîãî, êîòîðûé èç èãðîêîâ áóäåò äåëàòü ïåðâûé øàã.
25
Ãëàâà 4. Ìîäåëèðîâàíèå â Network Simulator 3
4.1 Êîíôèãóðàöèÿ ñåòè
 äàííîé ãëàâå ïðîâîäèòñÿ ìîäåëèðîâàíèå, ïîëó÷åííûõ ðåçóëüòàòîâ â ãëàâå 3.1, â Network Simulator 3. Öåëüþ áûëî ñðàâíåíèå ïðîèçâîäèòåëüíîñòè ñåòè
äëÿ âñåõ 21 ñöåíàðèåâ èç òàáë. 3.2. Â òàáë. 4.1 ïðåäñòàâëåíà êîíôèãóðàöèÿ ñåòè,
êîòîðàÿ èñïîëüçîâàëàñü ïðè ìîäåëèðîâàíèè. Âûáðàí ïðîòîêîë AODV, ïîòîìó
÷òî ýòîò ïðîòîêîë óñòàíàâëèâàåò ìàðøðóòû ïî òðåáîâàíèþ, à òàêæå AODV ÿâëÿåòñÿ áîëåå ýôôåêòèâíûì â ïëàíå ïðîïóñêíîé ñïîñîáíîñòè, â îñîáåííîñòè ïðè
óâåëè÷åíèè ðàçìåðîâ ïàêåòà èëè ñêîðîñòè óçëîâ [13].
Ïàðàìåòð
Ðàäèóñ ðàñïðîñòðàíåíèÿ
Êîëè÷åñòâî àãåíòîâ èãðîêà 1
Êîëè÷åñòâî àãåíòîâ èãðîêà 2
Âðåìÿ ñèìóëÿöèè
Èñòî÷íèê ñèãíàëà èãðîêà 1
Èñòî÷íèê ñèãíàëà èãðîêà 2
Ïóíêò íàçíà÷åíèÿ
Ôèçè÷åñêàÿ ìîäåëü
Ñêîðîñòü ïåðåäà÷è
Ðàçìåð äàííûõ
Ïðîòîêîë ìàðøðóòèçàöèè
Òðàíñïîðòíûé ïðîòîêîë
Çíà÷åíèå
105ì
18
18
2100 c
S1
S2
N
DSSS at 11Mbps
CBR at 11Mbps
64bits
AODV
UDP
Òàáëèöà 4.1. Êîíôèãóðàöèÿ ñåòè
4.2 Ðåçóëüòàòû ìîäåëèðîâàíèÿ
 äàííîé ãëàâå ïðåäñòàâëåíû ðåçóëüòàòû ìîäåëèðîâàíèÿ.  òàáë. 4.2 ñîäåðæàòñÿ, ïîëó÷åííûå â Network Simulator. Ïàðàìåòð, ïî-êîòîðîìó èäåò ñðàâíåíèå ýòî ñðåäíÿÿ ïðîïóñêíàÿ ñïîñîáíîñòü, ò. å. êîëè÷åñòâî ïàêåòîâ, ïîëó÷åííûõ â åäèíèöó âðåìåíè. Ïîñëåäíåé ñòðîêîé â òàáëèöå ðåçóëüòàòû, äëÿ ñöåíàðèÿ,
êîãäà äðîíû íå èñïîëüçóþòñÿ.
26
ñòðàòåãèè ñòðàòåãèè Ñðåäíÿÿ ïðîïóñêíàÿ Ôóíêöèè
èãðîêà 1
èãðîêà 2
ñïîñîáíîñòü
âûèãðûøà
1
1
45,125
(6; 6)
1
2
40,543
(2; 2)
1
3
39,764
(2; 2)
1
4
37,482
(1; 1)
1
5
37,320
(1; 1)
2
6
44,986
(6; 6)
2
7
39,337
(2; 2)
2
8
39,554
(2; 2)
2
9
37,521
(1; 1)
2
10
37,427
(1; 1)
3
11
41,553
(3; 3)
3
12
41,542
(3; 3)
4
13
44,723
(5; 5)
4
14
40,952
(3; 3)
4
15
41,154
(3; 3)
5
16
42,756
(4; 4)
5
17
42,958
(4; 4)
5
18
39,834
(2; 2)
6
19
39,546
(2; 2)
6
20
41,754
(3; 3)
6
21
41,359
(3; 3)
36,312
(0; 0)
Òàáëèöà 4.2. Ðåçóëüòàòû ìîäåëèðîâàíèÿ
4.3 Âûâîäû
Èç òàáëèöû 4.2 âèäíî, ÷òî ëó÷øèå ðåçóëüòàòû ïî ïðîïóñêíîé ñïîñîáíîñòè
ó ñöåíàðèåâ, êîòîðûå èìåþò ôóíêöèè âûèãðûøà áîëüøå, à ìàêñèìóìà ïðîïóñêíàÿ ñïîñîáíîñòü äîñòèãàåò ïðè óñòàíîâêå äðîíà â ïîçèöèè, ñîîòâåòñòâóþùèå
ñòðàòåãèÿì ¾â ïåðñïåêòèâå¿.
27
Çàêëþ÷åíèå
Àíàëèç óëó÷øåíèÿ ïðîèçâîäèòåëüíîñòè ñåòè MANET ïðè ïðîâåäåíèè ñïàñàòåëüíûõ îïåðàöèé â ìåñòàõ, ãäå ïðîèçîøëè ïðèðîäíûå êàòàñòðîôû, ïîêàçàë,
÷òî îäíó èç ãëàâíûõ ðîëåé èãðàåò ãðàìîòíîå ñîòðóäíè÷åñòâî ïîèñêîâûõ êîìàíä.
Ðàáîòà ÿâëÿåòñÿ ðàñøèðåíèåì ðàáîòû [3] íà ãåêñàãîíàëüíóþ ðåøåòêó. Áûë
ââåäåí íîâûé êëàññ ñòðàòåãèé ñòðàòåãèè ¾â ïåðñïåêòèâå¿. Ñ ïîìîùüþ íîâîââåäåíèÿ ïîëó÷èëîñü óìåíüøèòü äëèíó èãðû è íàéòè íîâûå ïîçèöèè äëÿ
ðàçìåùåíèÿ äðîíà, êîòîðûå äàþò ëó÷øèé ðåçóëüòàò, ÷åì ïðåäûäóùèé êëàññ
ñòðàòåãèé.
Áûëà ðàññìîòðåíà êîîïåðàòèâíàÿ ïîñòàíîâêà èãðû óïðàâëåíèÿ äðîíàìè
â ñåòè. Ïîëó÷åíî, ÷òî ïðè êîîïåðàöèè èãðîêîâ â ìàêñèìàëüíóþ êîàëèöèþ, ïðîèçâîäèòåëüíîñòü ñåòè óëó÷øàåòñÿ, â ñðàâíåíèè ñ íåêîîïåðàòèâíûì âàðèàíòîì.
Áûë íàïèñàí ïðîãðàììíûé ïðîäóêò, ïîçâîëÿþùèé ïîñòðîèòü äåðåâî ðåøåíèé äëÿ êîíå÷íîøàãîâûõ êîîïåðàòèâíîé è íåêîîïåðàòèâíîé èãð íà ãåêñàãîíàëüíîé ðåøåòêå. Ïðîãðàììíîå îáåñïå÷åíèå áûëî ïðîòåñòèðîâàíî íà èãðå äâóõ
ëèö.
Áûëà ïðîâåäåíî ìîäåëèðîâàíèå, ïîëó÷åííûõ ðåçóëüòàòîâ, â Network
Simulator 3. Áûëî óñòàíîâëåíî, ÷òî ïðèìåíåíèå òåîðåòèêî-èãðîâîãî ïîäõîäà ê
çàäà÷å óëó÷øåíèÿ ïðîèçâîäèòåëüíîñòè ñåòè äà¼ò ïîëîæèòåëüíûå ðåçóëüòàòû.
Ðàáîòà ìîæåò áûòü ðàñøèðåíà íà òðåóãîëüíóþ ðåøåòêó. Òàêæå ñëåäóåò
ïðîâåñòè ñðàâíèòåëüíûé àíàëèç äëÿ ðàññìîòðåííûõ ñåòîê (êâàäðàòíîé, ãåêñàãîíàëüíîé), ñ öåëüþ âûÿâëåíèÿ êàêîé òèï ñåòêè ÿâëÿåòñÿ ïðåäïî÷òèòåëüíåå
äëÿ îïðåäåëåííîãî òèïà ïîâåðõíîñòè, íà êîòîðîì âåäåòñÿ ïîèñêîâàÿ îïåðàöèÿ.
Òàêæå ñòîèò ðàññìîòðåòü êîîïåðàöèþ èãðîêîâ íå â ìàêñèìàëüíóþ êîàëèöèþ.
Èññëåäîâàòü äðóãèå ïðîòîêîëû ìàðøðóòèçàöèè â Network Simulator 3, íàïðèìåð, DSR, OLSR.
Íåêîòîðûå ðåçóëüòàòû èññëåäîâàíèÿ îòðàæåíû â ðàáîòàõ [4], [8], [9], [16],
[17].
28
Ëèòåðàòóðà
[1] Anjum S. S., Noor R. M., Anisi M. H. Survey on MANET based communication
scenarios for search and rescue operations, in IT Convergence and Security
(ICITCS) // 5th International Conference on. IEEE. 2015. P. 15.
[2] Standart
Ecma-262
[Ýëåêòðîííûé
ðåñóðñ]:
https://www.
ecma-international.org/publications/files/ECMA-ST/Ecma-262.pdf
(Äàòà îáðàùåíèÿ: 02.02.18).
[3] Gromova E., Gromov D., Timonin N., Kirpichnikova A., Blakeway S. A dynamic
game of mobile agents placement on MANET // Proc. of the IEEE conference
SIMS 2016. doi:10.1109/SIMS.2016.25
[4] Gromova E., Gromov D., Plekhanova T., Kirpichnikova A., Blakeway S.
Increasing network perfomance of a MANET using game-theoretic approach
to drone positioning // Ad Hoc Networks.
[5] Han Z., Niyato D., Saad W., Basar T., Hjorungnes A. Game Theory in Wireless
and Communication Networks. Theory, Models, and Applications. New York:
Cambridge University Press, 2012. 530 p.
[6] LaTeX on Wikibooks [Ýëåêòðîííûé ðåñóðñ]: URL:http://en.wikibooks.
org/wiki/LaTeX (Äàòà îáðàùåíèÿ: 02.06.18).
[7] Network simulator 3 documentation [Ýëåêòðîííûé ðåñóðñ]: https://www.
nsnam.org/documentation/ (Äàòà îáðàùåíèÿ: 09.05.18).
[8] Plekhanova T., Gromova E., Kirpichnikova A., Blakeway S. A multistage game
of mobile agents placement on a hexagonal grid - MANET // Òåçèñû XXI
ìåæäóíàðîäíîé êîíôåðåíöèè ¾Òåîðèÿ èãð è ìåíåäæìåíò¿, 2017.
[9] Plekhanova T., Gromova E., Gromov D., Kirpichnikova A., Blakeway S.
The Strategic Placement of Mobile Agents on a Hexagonal Graph
using Game Theory // Proc. of the IEEE conference ICAT 2017.
doi:10.1109/ICAT.2017.8171635
29
[10] Robin J. Introduction to Graph Theory // Edinburgh: Oliver and Boyd, 1972.
209 p.
[11] Âèíîêóðîâ Â. Ì., Ïóãîâêèí À. Â., Ïøåííèêîâ À. À., Óøàðîâà Ä. Í., Ôèëàòîâ À. Ñ. Ìàðøðóòèçàöèÿ â áåñïðîâîäíûõ ìîáèëüíûõ Ad hoc-ñåòÿõ //
Óïðàâëåíèå, âû÷èñëèòåëüíàÿ òåõíèêà è èíôîðìàòèêà, 2010, C. 288292.
[12] Êëèìîâ È. À., ×åðâèíñêàÿ Í. Â. Ñðàâíåíèå ïðîòîêîëîâ ìàðøðóòèçàöèè
äëÿ áåñïîâîäíûõ AD-hoc ñåòåé // Çáiðíèê íàóêîâèõ ïðàöü ÕIII íàóêîâîòåõíi÷íî¨ êîíôåðåíöi¨ àñïiðàíòiâ òà ñòóäåíòiâ, ÄîíÍÒÓ, 2013. Ñ. 7680.
[13] Ìàõìóä À. Ø., Ïîëÿêîâ Â. Ì. Îöåíêà ïðîèçâîäèòåëüíîñòè ïðîòîêîëîâ ìîáèëüíûõ Ad-hoc ñåòåé (MANET) // DOI:10.18413/2518-1092-2016-1-4-64-71.
[14] Íîâèêîâ Ä. À. Èãðû è ñåòè // Ìàòåìàòè÷åñêàÿ òåîðèÿ èãð è å¼ ïðèëîæåíèÿ,
2010. Ñ. 107124.
[15] Ïåòðîñÿí Ë. À., Çåíêåâè÷ Í. À., Øåâêîïëÿñ Å. Â. Òåîðèÿ èãð, 2012. Ñ. 424.
[16] Ïëåõàíîâà Ò. Ì., Ãðîìîâà Å. Â. Êîîïåðàòèâíàÿ äèíàìè÷åñêàÿ èãðà íà ñåòè
MANET // Òðóäû ¾XLIX ìåæäóíàðîäíàÿ íàó÷íàÿ êîíôåðåíöèÿ àñïèðàíòîâ è ñòóäåíòîâ ¾Ïðîöåññû óïðàâëåíèÿ è óñòîé÷èâîñòü¿, 2018.
[17] Ïëåõàíîâà Ò. Ì., Ãðîìîâà Å. Â. Ñðàâíèòåëüíûé àíàëèç ïðîèçâîäèòåëüíîñòè ñåòè MANET ïðè ïðèìåíåíèè òåîðåòèêî-èãðîâîãî ïîäõîäà äëÿ ðàçëè÷íûõ òèïîâ ðåøåòêè // Òåçèñû Âòîðîé âñåðîññèéñêîé ìåæäèñöèïëèíàðíîé
êîíôåðåíöèè ¾Ñîöèîôèçèêà è ñîöèîèíæåíåðèÿ¿, 2018.
30
Ïðèëîæåíèå
compute.js
f u n c t i o n computeGame ( game , i , j , c o l o r ) {
var c o l o r = c o l o r | |
' red ' ;
var d i s t a n c e M a t r i x = g e t D i s t a n c e M a t r i x ( game . s i t u a t i o n [ '
p l a y e r ' + i ] . X, game . s i t u a t i o n [ ' p l a y e r '+i ] . Y) ;
var markBefore = computeMark ( game . s i t u a t i o n [ ' p l a y e r ' + i
]) ;
var markBefore2 = computeMark ( game . s i t u a t i o n [ ' p l a y e r ' +
j ]) ;
var droneCoord = getDroneCoords ( d i s t a n c e M a t r i x , game .
s i t u a t i o n [ ' p l a y e r ' + i ] . X, game . s i t u a t i o n [ ' p l a y e r ' + i
] . Y) ;
var d i s t a n c e A f t e r D r o n e = [ ] ;
var d i s t a n c e A f t e r D r o n e 2 = [ ] ;
var payOff = [ ] ;
var newDroneCoord = [ ] ;
var count = 0 ;
var markAfter = 0 ;
var markAfter2 = 0 ;
for
( count ; count < droneCoord . l e n g t h − 1 ; count++) {
markAfter = computeMarkWithDrone ( game . s i t u a t i o n [ '
p l a y e r ' + i ] , droneCoord [ count ] ) ;
if
( markAfter < markBefore ) {
d i s t a n c e A f t e r D r o n e . push ( [ markAfter , markBefore −
markAfter ] ) ;
markAfter2 = computeMarkWithDrone ( game . s i t u a t i o n [ '
p l a y e r ' + j ] , droneCoord [ count ] ) ;
d i s t a n c e A f t e r D r o n e 2 . push ( [ markAfter2 , markBefore2 −
markAfter2 ] ) ;
31
payOff . push ( [ markBefore − markAfter , markBefore2 −
markAfter2 ] ) ;
newDroneCoord . push ( droneCoord [ count ] ) ;
}
}
return
newDroneCoord ;
}
draw.js
f u n c t i o n drawGame ( game ) {
game . getCtx ( ) . f i l l S t y l e = ' w h i t e ' ;
game . getCtx ( ) . f i l l R e c t ( 0 , 0 , game . getWidth ( ) , game .
getHeight () ) ;
game . drawHexGrid ( ) ;
game . drawSqureGrid ( ' h e x a g o n a l G r i d ' , game . p l a c e . SCALE) ;
game . s i t u a t i o n . p l a y e r 1 .X. f o r E a c h ( f u n c t i o n ( item , i , a r r )
{
a r r [ i ] /= 5 0 0 0 0 ;
}) ;
game . s i t u a t i o n . p l a y e r 1 .Y. f o r E a c h ( f u n c t i o n ( item , i , a r r )
{
a r r [ i ] /= 5 0 0 0 0 ;
}) ;
game . d r a w I n i t e S t a t e ( game . s i t u a t i o n . p l a y e r 1 , ' y e l l o w '
);
game . d r a w I n i t e S t a t e ( game . s i t u a t i o n . p l a y e r 2 , ' r e d ' , −4) ;
game . d r a w I n i t e S t a t e ( game . s i t u a t i o n . p l a y e r 3 , ' g r e e n ' , 4 ) ;
game . drawGuidesXY ( 1 , 1 ) ;
game . d r a w B a r r i e r ( game . b a r r i e r C o o r d s . b a r r i e r 1 ) ;
game . d r a w B a r r i e r ( game . b a r r i e r C o o r d s . b a r r i e r 2 , ' g r e e n ' ) ;
game . d r a w B a r r i e r ( game . b a r r i e r C o o r d s . b a r r i e r 3 , ' b l u e ' ) ;
game . d r a w B a r r i e r ( game . b a r r i e r C o o r d s . b a r r i e r 4 , ' b l u e ' ) ;
return
game ;
32
}
function.js
f u n c t i o n g e t P e r s p e c t i v e D r o n e (X, Y) {
// p o s s i b l e c o o r d i n a t e s
var possCoord = [ [ 'X ' , 'Y ' , ' j ' , ' i ' ] ] ;
var i = 1 ;
var x1 , x2 , y1 , y2 ;
// g e t a l l p o s s i b l e c o o r d i n a t e s
for
( var j = 0 ; j < X. l e n g t h ; j ++) {
for
( i ; i < X. l e n g t h ; i ++) {
( d i s t a n c e M a t r i x [ j ] [ i ] > 2 && d i s t a n c e M a t r i x [ j ] [ i ]
if
<= 3 ) {
if
(Y[ i ] == Y[ j ] ) {
x1 = x2 = round ( (X[ i ] + X[ j ] ) ∗ 0 . 5 , 3 ) ;
y1 = Y[ i ] + 0 . 5 ;
y2 = Y[ i ] − 0 . 5 ;
}
if
(Y[ j ] > Y[ i ] && X[ j ] < X[ i ] ) {
x1 = X[ j ] ;
x2 = X[ i ] ;
y1 = Y[ j ] − 1 ;
y2 = Y[ i ] + 1 ;
}
if
(Y[ j ] < Y[ i ] && X[ j ] > X[ i ] ) {
x1 = X[ i ] ;
x2 = X[ j ] ;
y1 = Y[ i ] − 1 ;
y2 = Y[ j ] + 1 ;
33
}
if
(Y[ j ] < Y[ i ] && X[ j ] < X[ i ] ) {
x1 = X[ j ] ;
x2 = X[ i ] ;
y1 = Y[ j ] + 1 ;
y2 = Y[ i ] − 1 ;
}
if
(Y[ j ] > Y[ i ] && X[ j ] > X[ i ] ) {
x1 = X[ i ] ;
x2 = X[ j ] ;
y1 = Y[ i ] + 1 ;
y2 = Y[ j ] − 1 ;
}
possCoord . push ( [ x1 , y1 , j , i ] , [ x2 , y2 , j , i ] ) ;
}
}
i = j + 2;
}
// g e t drone c o o r d i n a t e s
//
var a l l D r o n e C o o r d s = [ ] ; // drone c o o r d i n a t e s w i t h
hexagon c e n t e r
var notDrone =
false
;
// c o n s o l e . l o g ( ' possCoord ' , possCoord ) ;
// c h e c k i n g i f c o o r d i n a t e s have been i n a r r a y a l r e a d y
for
( j = 1 ; j < possCoord . l e n g t h ; j ++) {
notDrone = X. some ( f u n c t i o n ( Xi , index , a r r a y ) {
return
Xi == possCoord [ j ] [ 0 ] && Y[ i n d e x ] ==
possCoord [ j ] [ 1 ] ;
34
}) ;
( notDrone ==
if
false
) {
a l l D r o n e C o o r d s . push ( possCoord [ j ] ) ;
}
}
// c o n s o l e . l o g ( ' a l l D r o n e C o o r d s ' , a l l D r o n e C o o r d s ) ;
// c h e c k i n g i f c o o r d i n a t e s t h e same
a l l D r o n e C o o r d s . f o r E a c h ( f u n c t i o n ( item , i , a r r a y ) {
var a r r = a l l D r o n e C o o r d s . s l i c e ( i + 1 ) ;
var count = 0 ;
a r r . f o r E a c h ( f u n c t i o n ( i t , index , a r r ) {
if
( item [ 0 ] == i t [ 0 ] && item [ 1 ] == i t [ 1 ] ) {
a l l D r o n e C o o r d s . s p l i c e ( i + 1 + i n d e x − count , 1 ) ;
count++;
}
}) ;
}) ;
return
allDroneCoords ;
}
f u n c t i o n drawConnections ( c o o r d s , c t x ) {
var c t x = c t x | |
var SCALE =
this
var h e i g h t =
this
. getCtx ( ) ;
. p l a c e . SCALE ;
this
. getHeight () ;
// s t a r t draw
c t x . beginPath ( ) ;
ctx . s t r o k e S t y l e = ' red ' ;
ctx . lineWidth = 2 ;
35
c t x . moveTo ( c o o r d s .X [ 0 ] ∗ SCALE, h e i g h t − c o o r d s .Y [ 0 ] ∗
SCALE) ;
for
( var i = 0 ; i < c o o r d s .X. l e n g t h − 4 ; i ++) {
c t x . l i n e T o ( c o o r d s .X[ i + 1 ] ∗ SCALE, h e i g h t − c o o r d s .Y[
i + 1 ] ∗ SCALE) ;
}
// g e t l i n e
ctx . stroke () ;
ctx . closePath () ;
}
/ ∗∗
∗ drawGuidesXY
∗ @param {number} X0
∗ @param {number} Y0
∗ @param {number} SCALE
∗ @param {number} c t x
∗/
f u n c t i o n drawGuidesXY (X0 , Y0 , SCALE, c t x ) {
var t e x t = ' ' + X0 + ' , ' + Y0 ;
var c t x = c t x | |
this
var SCALE = SCALE | |
var h e i g h t =
var width =
this
this
. getCtx ( ) ;
this
. p l a c e . SCALE ;
. getHeight () ;
. getWidth ( ) ;
var X0 = (X0 ∗ SCALE) | | 0 ;
var Y0 = ( h e i g h t − Y0 ∗ SCALE) | | h e i g h t ;
// Drawing o f s q u a r e g r i d
c t x . beginPath ( ) ;
36
ctx . s t r o k e S t y l e = " black " ;
ctx . lineWidth = 2 ;
ctx . f i l l S t y l e = ' black ' ;
c t x . f o n t = " 14 px Ge o rg i a " ;
// draw v e r t i c a l
c t x . moveTo (X0 , 0 ) ;
c t x . l i n e T o (X0 , h e i g h t ) ;
// arrows x
c t x . moveTo (X0 , 0 ) ;
c t x . l i n e T o (X0 + 5 , 1 0 ) ;
c t x . moveTo (X0 , 0 ) ;
c t x . l i n e T o (X0 − 5 , 1 0 ) ;
c t x . f i l l T e x t ( ' x ' , X0 − 1 5 , 1 5 ) ;
// draw h o r i z
c t x . moveTo ( 0 , Y0) ;
c t x . l i n e T o ( width , Y0) ;
// arrows y
c t x . moveTo ( width , Y0) ;
c t x . l i n e T o ( width − 1 0 , Y0 − 5 ) ;
c t x . moveTo ( width , Y0) ;
c t x . l i n e T o ( width − 1 0 , Y0 + 5 ) ;
c t x . f i l l T e x t ( ' y ' , width − 1 5 , Y0 + 1 5 ) ;
// t e x t X0 and Y)
c t x . f i l l T e x t ( t e x t , X0 + 5 , Y0 − 5 ) ;
ctx . stroke () ;
37
ctx . closePath () ;
}
/ ∗∗
∗ add c o o r d i n a t e s o f drone t o a r r a y s X and Y
∗ @param { o b j e c t } XY
∗ @param { o b j e c t } droneCoords
∗ @returns { o b j e c t }
∗/
f u n c t i o n setDroneToXY (XY, droneCoords ) {
var X = XY.X. s l i c e ( ) ;
var Y = XY.Y. s l i c e ( ) ;
var i n d e x = X. l e n g t h − 1 ;
X. s p l i c e ( index , 0 , droneCoords [ 0 ] ) ;
Y. s p l i c e ( index , 0 , droneCoords [ 1 ] ) ;
XYwithDrone = {
X: X,
Y: Y
};
return
XYwithDrone ;
}
/ ∗∗
∗ g e t Drone C o o r d i n a t e s
∗ @param { a r r a y } d i s t a n c e M a t r i x
∗ @param { a r r a y } X
∗ @param { a r r a y } Y
∗ @param {number} q u a n t i t y D r o n e
∗ @returns { Array }
38
∗/
f u n c t i o n getDroneCoords ( d i s t a n c e M a t r i x , X, Y) {
// p o s s i b l e c o o r d i n a t e s
var possCoord = [ [ 'X ' , 'Y ' , ' j ' , ' i ' ] ] ;
var i = 1 ;
var x1 , x2 , y1 , y2 ;
// g e t a l l p o s s i b l e c o o r d i n a t e s
for
( var j = 0 ; j < X. l e n g t h ; j ++) {
for
( i ; i < X. l e n g t h ; i ++) {
( d i s t a n c e M a t r i x [ j ] [ i ] > 1 . 7 1 && d i s t a n c e M a t r i x [ j
if
] [ i ] <= 1 . 7 5 ) {
if
(Y[ i ] == Y[ j ] ) {
x1 = x2 = round ( (X[ i ] + X[ j ] ) ∗ 0 . 5 , 2 ) ;
y1 = Y[ i ] + 0 . 5 ;
y2 = Y[ i ] − 0 . 5 ;
}
if
(Y[ j ] > Y[ i ] && X[ j ] < X[ i ] ) {
x1 = X[ j ] ;
x2 = X[ i ] ;
y1 = Y[ j ] − 1 ;
y2 = Y[ i ] + 1 ;
}
if
(Y[ j ] < Y[ i ] && X[ j ] > X[ i ] ) {
x1 = X[ i ] ;
x2 = X[ j ] ;
y1 = Y[ i ] − 1 ;
y2 = Y[ j ] + 1 ;
39
}
if
(Y[ j ] < Y[ i ] && X[ j ] < X[ i ] ) {
x1 = X[ j ] ;
x2 = X[ i ] ;
y1 = Y[ j ] + 1 ;
y2 = Y[ i ] − 1 ;
}
if
(Y[ j ] > Y[ i ] && X[ j ] > X[ i ] ) {
x1 = X[ i ] ;
x2 = X[ j ] ;
y1 = Y[ i ] + 1 ;
y2 = Y[ j ] − 1 ;
}
possCoord . push ( [ x1 , y1 , j , i ] , [ x2 , y2 , j , i ] ) ;
}
}
i = j + 2;
}
// g e t drone c o o r d i n a t e s
// c o n s o l e . l o g ( ' p o s s C o o r d i n a t e s \n\ t ' , possCoord . j o i n ( ' ; \
n \ t ') ) ;
// c o n s o l e . l o g ( ' possCoord . l e n g h t \n\ t ' , possCoord . l e n g t h )
;
var a l l D r o n e C o o r d s = [ ] ; // drone c o o r d i n a t e s w i t h
hexagon c e n t e r
var notDrone =
false
;
// c o n s o l e . l o g ( ' possCoord ' , possCoord ) ;
40
// c h e c k i n g i f c o o r d i n a t e s o f drone == c o o r d i n a t e s o f
player agents
for
( j = 1 ; j < possCoord . l e n g t h ; j ++) {
notDrone = X. some ( f u n c t i o n ( Xi , i n d e x ) {
return
( Xi + 0 . 3 > possCoord [ j ] [ 0 ] ) && ( Xi − 0 . 3 <
possCoord [ j ] [ 0 ] ) && Y[ i n d e x ] == possCoord [ j ] [ 1 ] ;
}) ;
( notDrone ==
if
false
) {
a l l D r o n e C o o r d s . push ( possCoord [ j ] ) ;
}
}
// c o n s o l e . l o g ( ' a l l D r o n e C o o r d s ' , a l l D r o n e C o o r d s ) ;
// c h e c k i n g i f c o o r d i n a t e s t h e same
a l l D r o n e C o o r d s . f o r E a c h ( f u n c t i o n ( item , i ) {
var a r r = a l l D r o n e C o o r d s . s l i c e ( i + 1 ) ;
var count = 0 ;
arr . forEach ( f u n c t i o n ( it , index ) {
if
( ( item [ 0 ] + 0 . 3 > i t [ 0 ] ) && ( item [ 0 ] − 0 . 3 < i t
[ 0 ] ) && item [ 1 ] == i t [ 1 ] ) {
a l l D r o n e C o o r d s . s p l i c e ( i + 1 + i n d e x − count , 1 ) ;
count++;
}
}) ;
}) ;
return
allDroneCoords ;
}
// / ∗∗
//
∗ drawGraph d e s c r i p t i o n
//
∗ @param
{ o b j e c t } brunches
41
//
∗ @param
{ object } ctx
//
∗ @return { t y p e }
//
∗/
f u n c t i o n drawGraph ( brunches , c t x ) {
var c t x = c t x | |
this
. getCtx ( ) ;
var br u n c he s = br u n c he s | |
this
. b r u nc h e s ;
var s t r a t e g y = [ [ ] ] ;
var v e r t e x = [ {
X:
this
. getWidth ( ) / 2 ,
Y:
this
. getHeight ( ) − 10 ,
angle : 0 ,
}];
var count = 0 ;
var t e x t = b r u nc h e s . s t r a t e g y 1 . combineXY ( ) ;
var s t r a t e g i e s = br u n c he s . s t r a t e g y 1 . s t r a t e g i e s ;
var n e x t S t r a t e g i e s = [ ] ;
v e r t e x = v e r t e x . c o n c a t ( drawPluentyOfBeams ( ctx , b r u n ch e s .
s t r a t e g y 1 .X. l e n g t h , v e r t e x [ 0 ] ,
true
,
text ) ) ;
while
for
( s t r a t e g i e s . l e n g t h && count < 1 0 ) {
( var i = 0 ; i < s t r a t e g i e s . l e n g t h ; i ++) {
t e x t = br u n c he s [ ' s t r a t e g y ' + s t r a t e g i e s [ i ] ] .
combineXY ( ) ;
v e r t e x = v e r t e x . c o n c a t ( drawPluentyOfBeams ( ctx ,
b r un c h e s [ ' s t r a t e g y ' +
s t r a t e g i e s [ i ] ] . X. l e n g t h , v e r t e x [ s t r a t e g i e s [ i ] −
1] ,
b r un c h e s [ ' s t r a t e g y ' + s t r a t e g i e s [ i ] ] . p l a y e r , t e x t )
42
);
if
( b r u nc h e s [ ' s t r a t e g y ' + s t r a t e g i e s [ i ] ] . s t r a t e g i e s
!=
true )
{
n e x t S t r a t e g i e s = n e x t S t r a t e g i e s . c o n c a t ( br u n c he s [ '
strategy ' + strategies [ i ] ] . strategies ) ;
}
}
for
( var j = 0 ; j < n e x t S t r a t e g i e s . l e n g t h ; j ++) {
strategies [ j ] = nextStrategies [ j ] ;
}
nextStrategies = [ ] ;
count++;
}
return
0;
}
// / ∗∗
// ∗ drawPluentyOfBeams
//
∗ @param
{ type }
context
//
∗ @param
{ type }
quantity
//
∗ @param
{ type }
startCoord
//
∗ @param
{ Boolean } isRound
//
∗ @param
{ array } t e x t
//
∗ @param
{number} lengthBeam
//
∗ @return { t y p e }
//
∗/
f u n c t i o n drawPluentyOfBeams ( ctx , q u a n t i t y , s t a r t C o o r d ,
isRound , t e x t , lengthBeam ) {
43
var a n g l e = [ ] ;
var f i n i s h C o o r d = [ ] ;
var lengthBeam = lengthBeam | | 1 5 0 ;
var c o n s t A n g l e = ( 1 8 0 ) / ( q u a n t i t y + 1 ) ;
( quantity < 10) {
if
for
( var i = 0 ; i < q u a n t i t y ; i ++) {
angle [ i ] = constAngle ∗ ( i + 1) ;
if
( s t a r t C o o r d . a n g l e < 90 && s t a r t C o o r d . a n g l e > 0 ) {
angle [ i ] = angle [ i ] − startCoord . angle ;
}
else
if
( startCoord . angle > 90) {
angle [ i ] = angle [ i ] + ( startCoord . angle − 90) ;
}
}
}
else
{
a n g l e = 360 / ( q u a n t i t y + 1 ) ;
}
for
( var i = 0 ; i < q u a n t i t y ; i ++) {
f i n i s h C o o r d [ i ] = drawGraphBeam ( ctx , s t a r t C o o r d ,
isRound , a n g l e [ i ] , t e x t [ i ] , lengthBeam ) ;
}
return
finishCoord ;
}
//
// / ∗∗
//
∗ [ drawGraphBeam d e s c r i p t i o n ]
//
∗ @param
{[ type ]}
//
∗ @param
{ [ o b j e c t ={X: ,Y: } ] }
context
[ description ]
startCoord
[
description ]
//
∗ @param
{ Boolean } isRound
44
[ description ]
//
∗ @param
{num} a n g l e
//
∗ @param
{ [ number ] }
//
∗
//
∗ @return { [ t y p e ] }
//
∗/
[ angle in the degrees ]
lengthBeam [ d e f a u l t = 3 0 ]
[ description ]
f u n c t i o n drawGraphBeam ( ctx , s t a r t C o o r d , isRound , a n g l e ,
t e x t , lengthBeam ) {
var lengthBeam = lengthBeam | | 5 0 ;
var f i n i s h C o o r d = {
X: s t a r t C o o r d .X − lengthBeam ∗ Math . c o s ( inRad ( a n g l e ) ) ,
Y: s t a r t C o o r d .Y − lengthBeam ∗ Math . s i n ( inRad ( a n g l e ) ) ,
angle : angle
};
ctx . save ( ) ;
c t x . t r a n s l a t e ( s t a r t C o o r d . X, s t a r t C o o r d .Y) ;
c t x . beginPath ( ) ;
ctx . lineWidth = 2 ;
ctx . s t r o k e S t y l e = ' black ' ;
if
( isRound ) {
c t x . a r c ( 0 , 0 , 5 , 0 , 2 ∗ Math . PI ,
false
);
ctx . f i l l S t y l e = ' black ' ;
ctx . f i l l () ;
}
else
{
var coordRectX = − 5;
var coordRectY = − 5;
// / ∗∗
//
∗ [ c o n t e x t . f i l l ( x , y , width , h e i g h t ) The f i l l R e c t
( ) method draws a " f i l l e d " r e c t a n g l e .
//
∗ The d e f a u l t c o l o r o f t h e f i l l i s b l a c k . Use t h e
f i l l S t y l e property to set a color , gradient ,
//
∗ or p a t t e r n used t o f i l l t h e drawing . ]
//
∗ @param
{ [ number ] }
45
x
[ The x−c o o r d i n a t e o f
t h e upper − l e f t c o r n e r o f t h e r e c t a n g l e ]
//
∗ @param
{ [ number ] }
y
[ The y−c o o r d i n a t e o f t h e
upper − l e f t c o r n e r o f t h e r e c t a n g l e ]
//
∗ @param
{ [ number ] }
w i d t h [ The w i d t h o f t h e
rectangle , in p i x e l s ]
//
∗ @param
{number}
h e i g t h [ The h e i g h t o f t h e
rectangle , in p i x e l s ]
//
∗ @return { [ t y p e ] }
//
∗/
ctx . f i l l S t y l e = ' green ' ;
c t x . f i l l R e c t ( coordRectX , coordRectY , 1 0 , 1 0 ) ;
}
c t x . r o t a t e ( inRad ( a n g l e ) ) ;
c t x . moveTo ( 0 , 0 ) ;
c t x . l i n e T o (− lengthBeam , 0 ) ;
// arrows
c t x . moveTo(− lengthBeam , 0 ) ;
c t x . l i n e T o (− lengthBeam + 5 , 5 ) ;
c t x . moveTo(− lengthBeam , 0 ) ;
c t x . l i n e T o (− lengthBeam + 5 , −5) ;
// / ∗∗
//
∗ [ c o n t e x t . f i l l T e x t The f i l l T e x t ( ) method draws
f i l l e d t e x t on t h e canvas .
//
∗ The d e f a u l t c o l o r o f t h e t e x t i s b l a c k . ]
//
∗ @param
{[ type ]} t e x t
[ S p e c i f i e s the t e x t that
w i l l be w r i t t e n on t h e canvas ]
//
∗ @param
{[ type ]} x
[
The x c o o r d i n a t e
where t o s t a r t p a i n t i n g t h e t e x t ( r e l a t i v e t o t h e
canvas ) ]
//
∗ @param
{[ type ]} y
[
The y c o o r d i n a t e
where t o s t a r t p a i n t i n g t h e t e x t ( r e l a t i v e t o t h e
canvas ) ]
46
//
∗ @param
{ [ t y p e ] } maxWidth [ O p t i o n a l . The maximum
allowed width of the text , in p i x e l s ]
//
∗ @return { [ t y p e ] }
//
∗/
[ description ]
c t x . f o n t = " 14 px Ge o rg i a " ;
c t x . f i l l T e x t ( t e x t , −lengthBeam + 1 0 , −2) ;
ctx . stroke () ;
ctx . closePath () ;
ctx . r e s t o r e () ;
return
finishCoord ;
}
// h t t p : / / a l g o l i s t . manual . ru / maths / g r a p h s / s h o r t p a t h /
d i j k s t r a . php
// S a r r a y = c o n s i d e r P l a y e r
// B a r r a y = payMatrix
// C a r r a y =
// A[ i , k ] =
// Array have t o be s o r t e d
/ ∗∗
∗ Algorithm D i j k s t r a
∗ @param { Array } payMatrix
∗ @returns {{ s p a c e : [ number ] , count : number , f l a g :
boolean }|∗}
∗/
f u n c t i o n d i j k s t r a ( payMatrix ) {
var LENGTH = payMatrix [ 0 ] . l e n g t h ;
var c o n s i d e r P l a y e r = [ 0 ] ;
var s p a c e = [ 0 ] ;
47
for
( var i = 1 ; i < LENGTH; i ++) {
space [ i ] = I n f i n i t y ;
considerPlayer [ i ] = 0;
}
var maxCount = 0 ;
var u n C o n s i d e r P l a y e r = [ ] ;
var unConsiderSpace = [ ] ;
while
( c o n s i d e r P l a y e r . some ( i s C o n s i d e r ) && maxCount <
300) {
unConsiderPlayer = [ ] ;
unConsiderSpace = [ ] ;
for
( var count = 0 ; count < c o n s i d e r P l a y e r . l e n g t h ;
count++) {
if
( c o n s i d e r P l a y e r [ count ] == 0 ) {
u n C o n s i d e r P l a y e r . push ( count ) ;
}
}
for
( count = 0 ; count < u n C o n s i d e r P l a y e r . l e n g t h ; count
++) {
unConsiderSpace [ count ] = s p a c e [ u n C o n s i d e r P l a y e r [
count ] ] ;
}
var min = getMinOfArray ( unConsiderSpace , 0 ) ;
var i n d e x C o n s i d e r = u n C o n s i d e r P l a y e r [ unConsiderSpace .
indexOf ( min ) ] ;
considerPlayer [ indexConsider ] = ' consider ' ;
48
( i = 0 ; i < LENGTH; i ++) {
for
if
( payMatrix [ i n d e x C o n s i d e r ] [ i ] == 1 ) {
s p a c e [ i ] = Math . min ( s p a c e [ i ] , payMatrix [
indexConsider ] [ i ] + space [ indexConsider ] ) ;
}
}
maxCount++;
}
var spaceObj = {
s p a c e : space ,
count : maxCount ,
f l a g : c o n s i d e r P l a y e r . some ( i s C o n s i d e r ) ,
considerPlayer : considerPlayer
};
return
spaceObj ;
}
f u n c t i o n getMinOfArray ( numArray , i n d e x S e a r c h ) {
var a r r a y = numArray . s l i c e ( i n d e x S e a r c h ) ;
// c o n s o l e . l o g ( a r r a y ) ;
return
Math . min . apply ( n u l l , a r r a y ) ;
}
f u n c t i o n i s C o n s i d e r ( number ) {
return
number == 0 ;
}
// / ∗∗
//
∗ [ getPayMatrix d e s c r i p t i o n ]
//
∗ @param
//
∗ @return { [ t y p e ] }
{[ type ]} distanceMatrix [ description ]
[ description ]
49
// ∗ /
f u n c t i o n getPayMatrix ( d i s t a n c e M a t r i x ) {
var l e n g t h = d i s t a n c e M a t r i x [ 0 ] . l e n g t h ;
var payMatrix = g e t M a t r i x ( l e n g t h , l e n g t h ) ;
for
( var j = 0 ; j < l e n g t h ; j ++) {
for
if
( var i = 0 ; i < l e n g t h ; i ++) {
( d i s t a n c e M a t r i x [ j ] [ i ] > 0 . 9 5 && d i s t a n c e M a t r i x [ j
] [ i ] < 1.05) {
payMatrix [ j ] [ i ] = 1 ;
}
else
{
payMatrix [ j ] [ i ] = 0 ;
}
}
}
return
payMatrix ;
}
// / ∗∗
//
∗ [ getDistanceMatrix description ]
//
∗ @param
{[ type ]} X [ description ]
//
∗ @param
{[ type ]} Y [ description ]
//
∗ @return { [ t y p e ] }
[ description ]
// ∗ /
f u n c t i o n g e t D i s t a n c e M a t r i x (X, Y) {
var l e n g t h = X. l e n g t h ;
var d i s t M a t r i x = g e t M a t r i x ( l e n g t h , l e n g t h ) ;
for
( var j = 0 ; j < l e n g t h ; j ++) {
for
( var i = 0 ; i < l e n g t h ; i ++) {
d i s t M a t r i x [ j ] [ i ] = round ( g e t D i s t a n c e (X[ j ] , X[ i ] , Y[ j
50
] , Y[ i ] ) , 2 ) ;
}
}
return
distMatrix ;
}
f u n c t i o n g e t D i s t a n c e (X1 , X2 , Y1 , Y2) {
return
Math . s q r t ( ( X1 − X2) ∗ (X1 − X2) +
(Y1 − Y2) ∗ (Y1 − Y2) ) ;
}
// / ∗∗
//
∗ [ getMatrix description ]
//
∗ @param
{ [ t y p e ] } rowLength
//
∗ @param
{ [ t y p e ] } colomnLength [ d e s c r i p t i o n ]
//
∗ @return { [ t y p e ] }
[ description ]
[ description ]
// ∗ /
f u n c t i o n g e t M a t r i x ( rowLength , colomnLength ) {
var Matrix =
new
Array ( rowLength ) ;
( var j = 0 ; j < rowLength ; j ++) {
for
Matrix [ j ] =
new
Array ( colomnLength ) ;
}
return
Matrix ;
}
// / ∗∗
//
∗ [ round d e s c r i p t i o n ]
//
∗ @param
{ [ t y p e ] } number
//
∗ @param
{[ type ]} accuracy [ d e s c r i p t i o n ]
//
∗ @return { [ t y p e ] }
[ description ]
[ description ]
51
//
∗/
f u n c t i o n round (num , a c c u r a c y ) {
a c c u r a c y = Math . pow ( 1 0 , a c c u r a c y ) ;
return
Math . round (num ∗ a c c u r a c y ) / a c c u r a c y ;
}
// / ∗∗
//
∗ [ order d e s c r i p t i o n ]
//
∗ @param
//
∗ @return { [ t y p e ] }
//
∗/
{[ type ]} array [ d e s c r i p t i o n ]
[ description ]
function order ( array ) {
var o r d e r = [ ] ;
for
( var i = 0 ; i < a r r a y . l e n g t h ; i ++) {
order [ i ] = i ;
}
return
order ;
}
//
// / ∗∗
//
∗ [ drawCircle d e s c r i p t i o n ]
//
∗ @param
{[ type ]} x
[ description ]
//
∗ @param
{[ type ]} y
[ description ]
//
∗ @param
{[ type ]} r
[ description ]
//
∗ @param
{[ type ]} t e x t
[ description ]
//
∗ @param
{[ type ]} color [ description ]
//
∗ @param
{[ type ]} ctx
//
∗ @return { [ t y p e ] }
//
∗/
[ description ]
[ description ]
function drawCircle (x , y , r , text , color , ctx ) {
var t e x t = t e x t | | 0 ;
52
var c t x = c t x | |
this
. getCtx ( ) ;
c t x . beginPath ( ) ;
r = r | | 4;
// / ∗∗
//
∗ [ c t x . arc ( x , y , r , sAngle , eAngle , c o u n t e r c l o c k w i s e
) C r e a t e s an arc / c u r v e
//
∗ ( used t o c r e a t e c i r c l e s , or p a r t s o f c i r c l e s ) ]
//
∗ @param
{[ type ]} x
[ The x−c o o r d i n a t e o f t h e
center of the c i r c l e ]
//
∗ @param
{[ type ]} y
[ The y−c o o r d i n a t e o f t h e
center of the c i r c l e ]
//
∗ @param
{[ type ]} r
[ The r a d i u s o f t h e c i r c l e ]
//
∗ @param
{ [ t y p e ] } sAngle [ The s t a r t i n g a n g l e , i n
r a d i a n s (0 i s a t t h e 3 o ' c l o c k p o s i t i o n o f t h e arc ' s
circle ) ]
//
∗ @param
{ [ t y p e ] } eAngle
[ The e n d i n g a n g l e , i n
radians ]
//
∗ @param
{[ type ]} counterclockwise [ Optional .
S p e c i f i e s w h et h e r t h e drawing s h o u l d be
c o u n t e r c l o c k w i s e or c l o c k w i s e . F a l s e i s d e f a u l t , and
i n d i c a t e s c l o c k w i s e , w h i l e t r u e i n d i c a t e s counter −
clockwise . ]
//
∗ @return { [ t y p e ] }
//
∗/
[ description ]
c t x . a r c ( x , y , r , 0 , 2 ∗ Math . PI ,
false
ctx . globalAlpha = 1;
ctx . f i l l S t y l e = c o l o r | |
' black ' ;
ctx . f i l l () ;
ctx . lineWidth = 1 ;
ctx . s t r o k e S t y l e = c o l o r | |
if
( text ) {
53
' black ' ;
);
c t x . f o n t = " 10 px Ge o rg i a " ;
ctx . f i l l T e x t ( text , x + 5 , y + 5) ;
}
ctx . stroke () ;
ctx . closePath () ;
};
f u n c t i o n drawDrone ( x , y , r , t e x t , c o l o r , c t x ) {
drawCircle (x , y , r , text , color , ctx ) ;
ctx . s t r o k e S t y l e = c o l o r | |
' black ' ;
};
// / ∗∗
// ∗ [ combineXY d e s c r i p t i o n ]
// ∗ @param
{[ array ]} X [ d e s c r i p t i o n ]
// ∗ @param
{[ array ]} Y [ d e s c r i p t i o n ]
// ∗ @return { [ a r r a y ] }
combineArr [ d e s c r i p t i o n ]
// ∗ /
f u n c t i o n combineXY (X, Y) {
var combineArr = [ ] ;
var X = X | |
this
.X;
var Y = Y | |
this
.Y;
for
( var i = 0 ; i < X. l e n g t h ; i ++) {
combineArr [ i ] = [X[ i ] , Y[ i ] ] ;
}
return
combineArr ;
}
// / ∗∗
//
∗ [ inRad d e s c r i p t i o n ]
54
//
∗ @param
{ [num] } a n g l e [ d e s c r i p t i o n ]
//
∗ @return { [num] }
//
∗/
[ angle in the radian ]
f u n c t i o n inRad ( a n g l e ) {
a n g l e ∗ Math . PI / 1 8 0 ;
return
}
// f o r <<i n t h e p e r s p e c t i v e >> a l t e r n a t i v e
f u n c t i o n g et Dr on eC oo rds Fo rA ll ( d i s t a n c e M a t r i x , X, Y,
quantityDrone ) {
var d i a m e t e r = q u a n t i t y D r o n e | | 1 ;
// p o s s i b l e c o o r d i n a t e s
var possCoord = [ [ 'X ' , 'Y ' , ' j ' , ' i ' ] ] ;
var i = 1 ;
var x1 , x2 , y1 , y2 ;
// g e t a l l p o s s i b l e c o o r d i n a t e s
for
( var j = 0 ; j < X. l e n g t h ; j ++) {
for
( i ; i < X. l e n g t h ; i ++) {
( d i s t a n c e M a t r i x [ j ] [ i ] > 2 . 6 3 && d i s t a n c e M a t r i x [ j
if
] [ i ] <= 3 . 0 1 ) {
if
(Y[ i ] == Y[ j ] ) {
x1 = x2 = round ( (X[ i ] + X[ j ] ) ∗ 0 . 5 , 3 ) ;
y1 = Y[ i ] + 0 . 5 ;
y2 = Y[ i ] − 0 . 5 ;
}
if
(Y[ j ] > Y[ i ] && X[ j ] < X[ i ] ) {
x1 = X[ j ] ;
x2 = X[ i ] ;
y1 = Y[ j ] − 1 ;
55
y2 = Y[ i ] + 1 ;
}
if
(Y[ j ] < Y[ i ] && X[ j ] > X[ i ] ) {
x1 = X[ i ] ;
x2 = X[ j ] ;
y1 = Y[ i ] − 1 ;
y2 = Y[ j ] + 1 ;
}
if
(Y[ j ] < Y[ i ] && X[ j ] < X[ i ] ) {
x1 = X[ j ] ;
x2 = X[ i ] ;
y1 = Y[ j ] + 1 ;
y2 = Y[ i ] − 1 ;
}
if
(Y[ j ] > Y[ i ] && X[ j ] > X[ i ] ) {
x1 = X[ i ] ;
x2 = X[ j ] ;
y1 = Y[ i ] + 1 ;
y2 = Y[ j ] − 1 ;
}
possCoord . push ( [ x1 , y1 , j , i ] , [ x2 , y2 , j , i ] ) ;
}
}
i = j + 2;
}
// g e t drone c o o r d i n a t e s
//
var a l l D r o n e C o o r d s = [ ] ; // drone c o o r d i n a t e s w i t h
56
hexagon c e n t e r
var notDrone =
false
;
// c o n s o l e . l o g ( ' possCoord ' , possCoord ) ;
// c h e c k i n g i f c o o r d i n a t e s have been i n a r r a y a l r e a d y
for
( j = 1 ; j < possCoord . l e n g t h ; j ++) {
notDrone = X. some ( f u n c t i o n ( Xi , index , a r r a y ) {
return
Xi == possCoord [ j ] [ 0 ] && Y[ i n d e x ] ==
possCoord [ j ] [ 1 ] ;
}) ;
( notDrone ==
if
false
) {
a l l D r o n e C o o r d s . push ( possCoord [ j ] ) ;
}
}
// c o n s o l e . l o g ( ' a l l D r o n e C o o r d s ' , a l l D r o n e C o o r d s ) ;
// c h e c k i n g i f c o o r d i n a t e s t h e same
a l l D r o n e C o o r d s . f o r E a c h ( f u n c t i o n ( item , i , a r r a y ) {
var a r r = a l l D r o n e C o o r d s . s l i c e ( i + 1 ) ;
var count = 0 ;
a r r . f o r E a c h ( f u n c t i o n ( i t , index , a r r ) {
if
( item [ 0 ] == i t [ 0 ] && item [ 1 ] == i t [ 1 ] ) {
a l l D r o n e C o o r d s . s p l i c e ( i + 1 + i n d e x − count , 1 ) ;
count++;
}
}) ;
}) ;
return
allDroneCoords ;
}
/ ∗∗
∗ HTMLCanvasElement . p r o t o t y p e . drawFullArea
∗ @param { o b j e c t } c o o r d i n a t e s
∗ @param {number} c o l o r
57
∗/
HTMLCanvasElement . p r o t o t y p e . drawFullArea = f u n c t i o n (
coordinates , color ) {
var c t x =
this
. g e t C o n t e x t ( ' 2d ' ) ;
// s t a r t draw
c t x . beginPath ( ) ;
ctx . globalAlpha = 0 . 4 ;
ctx . f i l l S t y l e = c o l o r | |
' green ' ;
ctx . s t r o k e S t y l e = c o l o r | |
' green ' ;
ctx . lineWidth = 4 ;
c t x . moveTo ( c o o r d i n a t e s .X [ 0 ] ∗
this
. SCALE,
this
g e t A t t r i b u t e ( ' h e i g h t ' ) − c o o r d i n a t e s .Y [ 0 ] ∗
.
this
. SCALE
);
( var count = 1 ; count < c o o r d i n a t e s .X. l e n g t h ; count
for
++) {
c t x . l i n e T o ( c o o r d i n a t e s .X[ count ] ∗
this
. SCALE,
this
g e t A t t r i b u t e ( ' h e i g h t ' ) − c o o r d i n a t e s .Y[ count ] ∗
.
this
. SCALE) ;
}
c t x . l i n e T o ( c o o r d i n a t e s .X [ 0 ] ∗
this
. SCALE,
this
g e t A t t r i b u t e ( ' h e i g h t ' ) − c o o r d i n a t e s .Y [ 0 ] ∗
.
this
);
ctx . f i l l () ;
ctx . stroke () ;
ctx . closePath () ;
};
f u n c t i o n getMaxOfArray ( numArray ) {
if
( Math . max . apply ( n u l l , numArray ) !== I n f i n i t y ) {
58
. SCALE
return
}
else
Math . max . apply ( n u l l , numArray ) ;
{
numArray . s p l i c e ( numArray . indexOf ( I n f i n i t y ) , 1 ) ;
return
Math . max . apply ( n u l l , numArray ) ;
}
}
f u n c t i o n computeMarkWithDrone ( s i t u a t i o n , droneCoord ) {
var s i t u a t i o n W i t h D r o n e = setDroneToXY ( s i t u a t i o n ,
droneCoord ) ;
return
computeMark ( s i t u a t i o n W i t h D r o n e ) ;
}
f u n c t i o n computeMark ( s i t u a t i o n ) {
var d i s t a n c e M a t r i x = g e t D i s t a n c e M a t r i x ( s i t u a t i o n . X,
s i t u a t i o n .Y) ;
var payMatrix = getPayMatrix ( d i s t a n c e M a t r i x ) ;
var spaceObj = d i j k s t r a ( payMatrix ) ;
var markAfter = getMaxOfArray ( spaceObj . s p a c e ) ;
return
markAfter ;
}
f u n c t i o n c r e a t e N o d e s (X, Y, node ) {
var i ;
for
( i = 0 ; i < X. l e n g t h ; i ++) {
c r e a t e N o d e (X[ i ] , Y[ i ] , node ) ;
}
return
0;
}
59
f u n c t i o n c r e a t e B a r r i e r N o d e (X, Y) {
var i ;
var t e x t = "" ;
for
( i = 0 ; i < X. l e n g t h ; i ++) {
t e x t = t e x t + " ( "+ X[ i ] + " , " + Y[ i ] + " ) −−" ;
}
t e x t = t e x t + " ( "+ X [ 0 ] + " , " + Y [ 0 ] + " ) " ;
var d i v = document . c r e a t e E l e m e n t ( ' d i v ' ) ;
d i v . innerHTML = t e x t ;
document . body . appendChild ( d i v ) ;
return
0;
}
f u n c t i o n c r e a t e N o d e ( x , y , node ) {
var d i v = document . c r e a t e E l e m e n t ( ' d i v ' ) ;
d i v . innerHTML = " \" + " node [ " + node + " ] a t "
( "+ x + " , " + y + " ) " + " { } ; " ;
document . body . appendChild ( d i v ) ;
return
0;
}
drawGraph.js
; ( function () {
var graph = {
c v s : document . getElementById ( " graph " ) ,
getCtx : f u n c t i o n ( ) {
60
+ "
return
this
. c v s . g e t C o n t e x t ( "2d" ) ;
},
getHeight : function () {
return
this
. cvs . getAttribute ( ' height ' ) ;
},
getWidth : f u n c t i o n ( ) {
return
this
. c v s . g e t A t t r i b u t e ( ' width ' ) ;
}
};
graph . b r u n ch e s = {
strategy1 : {
X: [ 1 0 , 3 , 4 ] ,
Y: [ 1 0 , 2 , 5 ] ,
combineXY : combineXY ,
strategies : [2 , 3 , 4] ,
player :
false
},
strategy2 : {
X: [ 1 0 , 2 , 7 ] ,
Y: [ 1 0 , 2 , 7 ] ,
combineXY : combineXY ,
strategies : [6] ,
player :
false
},
strategy3 : {
X: [ 5 , 2 , 4 ] ,
Y: [ 5 , 2 , 7 ] ,
combineXY : combineXY ,
strategies : [9] ,
player :
false
61
},
strategy4 : {
X: [ 7 , 2 , 1 0 ] ,
Y: [ 7 , 2 , 1 2 ] ,
combineXY : combineXY ,
strategies : [12] ,
player :
false
},
strategy12 : {
X: [ 7 , 2 , 1 0 ] ,
Y: [ 7 , 2 , 1 2 ] ,
combineXY : combineXY ,
strategies :
player :
true
,
true
},
strategy9 : {
X: [ 1 0 , 1 4 ] ,
Y: [ 1 0 , 1 4 ] ,
combineXY : combineXY ,
strategies :
player :
true
,
true
},
strategy6 : {
X: [ 1 0 , 1 0 ] ,
Y: [ 1 0 , 1 2 ] ,
combineXY : combineXY ,
strategies :
player :
true
,
true
}
};
// drawPluentyOfBeams ( graph . g e t C t x ( ) , 5 , graph . coord ,
62
false , ' h e l l o ') ;
graph . draw = drawGraph ;
c o n s o l e . l o g ( graph . draw ( ) ) ;
}() ) ;
index.html
< !DOCTYPE
html>
<html>
<head>
<meta
c h a r s e t=" u t f
−8">
< t i t l e >C o o p e r a t i v e game on a Manet</ t i t l e >
<l i n k
h r e f="
a s s e t s / c s s / s t y l e . c s s ">
< !−− L a t e s t c o m p i l e d and m i n i f i e d CSS −−>
<l i n k
h r e f="/ b o o t s t r a p
/ 3 . 3 . 7 / c s s / b o o t s t r a p . min . c s s ">
< !−− jQuery l i b r a r y −−>
<s c r i p t
s r c=" j q u e r y
. min . j s "></ s c r i p t>
< !−− L a t e s t c o m p i l e d J a v a S c r i p t −−>
<s c r i p t
s r c=" b o o t s t r a p
. min . j s "></ s c r i p t>
</ head>
<body>
<div
c l a s s =" c o n t a i n e r
− f l u i d ">
< !−− canvas −−>
<div
c l a s s ="row
<canvas
t e x t −c e n t e r ">
i d=" h e x a g o n a l G r i d "
width=" 1400 "
canvas>
</ div>
< !−− r e s u l t s −−>
<div
c l a s s ="row">
< !−− f i r s t p l a y e r −−>
<div
i d="
f i r s t −p l a y e r ">
<div
i d="X1
drone "></ div>
<div
i d="Y1
drone "></ div>
< !−− second p l a y e r −−>
63
height=" 800 "></
< !−−<div
i d="X2
drone "></ div>−−>
< !−−<div
i d="Y2
drone "></ div>−−>
< !−−<div
c l a s s =" t e x t
< !−−<canvas
− i n f o ">Graph Tree</ div>−−>
i d=" graph "
width=" 1000 "
height=" 500 "></ canvas>
−−>
< !−−</ div>−−>
< !−− s c r i p t s −−>
<s c r i p t
s r c="
a s s e t s / j s / f u n c t i o n . j s "></ s c r i p t>
<s c r i p t
s r c="
a s s e t s / j s /draw . j s "></ s c r i p t>
<s c r i p t
s r c="
a s s e t s / j s / compute . j s "></ s c r i p t>
<s c r i p t
s r c="
a s s e t s / j s / s h o w _ r e s u l t s . j s "></ s c r i p t>
<s c r i p t
s r c="
a s s e t s / j s /drawGraph . j s "></ s c r i p t>
</ body>
</ html>
64
Отзывы:
Авторизуйтесь, чтобы оставить отзыв