Бозиҳо дар графҳои даврӣ

Бозиҳо дар графҳои даврӣ

Бигзор бозие аз ҷониби ду бозингар дар графи ихтиёрии $G$ бозӣ карда шавад. Яъне ҳолати ҷории бозӣ як қуллаи муайян аст. Бозингарон навбат ба навбат ҳаракат мекунанд ва аз қуллаи ҷорӣ ба қуллаи ҳамсоя тавассути канори пайвасткунанда мегузаранд. Вобаста ба бозӣ, шахсе, ки наметавонад ҳаракат кунад, ё мебозад ё мебарад.

Мо ҳолати умумитаринро баррасӣ мекунем, ҳолати графи ихтиёрии самтдор бо давраҳо. Вазифаи мо муайян кардан аст, бо додани ҳолати ибтидоӣ, ки кӣ бозиро мебарад, агар ҳар ду бозингар бо стратегияҳои оптималӣ бозӣ кунанд, ё муайян кардан, ки натиҷаи бозӣ мусовӣ хоҳад буд.

Мо ин масъаларо хеле самаранок ҳал мекунем. Мо ҳалли онро барои ҳамаи қуллаҳои имконпазири оғозии граф дар вақти хаттӣ нисбат ба шумораи канорҳо меёбем: $O(M)$.

Тавсифи алгоритм

Мо қулларо қуллаи бурднок меномем, агар бозингаре, ки аз ин ҳолат оғоз мекунад, бозиро бибарад, агар оптималӣ бозӣ кунад (новобаста аз он ки бозингари дигар чӣ гуна навбатҳо мекунад). Ба ҳамин монанд, мо қулларо қуллаи бохтнок меномем, агар бозингаре, ки аз ин қулла оғоз мекунад, бозиро бибозад, агар рақиб оптималӣ бозӣ кунад.

Барои баъзе қуллаҳои граф, мо аллакай пешакӣ медонем, ки онҳо қуллаҳои бурднок ё бохтнок ҳастанд: маҳз ҳамаи қуллаҳое, ки канори баромадкунанда надоранд.

Инчунин мо қоидаҳои зеринро дорем:

• агар қулла канори баромадкунандае дошта бошад, ки ба қуллаи бохтнок мебарад, пас худи қулла қуллаи бурднок аст.
• агар ҳамаи канорҳои баромадкунандаи қуллаи муайян ба қуллаҳои бурднок баранд, пас худи қулла қуллаи бохтнок аст.
• агар дар ягон лаҳза ҳанӯз қуллаҳои номуайян боқӣ монанд, ва ҳеҷ кадом ба қоидаи якум ё дуюм мувофиқ нашавад, пас ҳар яке аз ин қуллаҳо, ҳангоми истифода шудан ҳамчун қуллаи оғозӣ, ба мусовӣ меорад, агар ҳар ду бозингар оптималӣ бозӣ кунанд.

Ҳамин тавр, мо метавонем алгоритмеро муайян кунем, ки фавран дар вақти $$ кор мекунад. Мо аз ҳамаи қуллаҳо мегузарем ва кӯшиш мекунем қоидаи якум ё дуюмро татбиқ кунем, ва такрор мекунем.