Графтарда қуу-құтылу ойындары және математикалық модельдері
Pursuit–evasion
Математикалық ойын: «Қуып жететін-қашатын» стратегиясы, граф іздеу, дискретті және үздіксіз нұсқаулары. Математика мен компьютер ғылымындағы зерттеулер.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математикалық ойын / есеп
Mathematical game/problem
Іздеу-құтылу (оның түрлері "полиция мен ұры" және "графты іздеу" деп аталады) – математика және компьютерлік ғылым салаларындағы проблемалар тобы, онда бір топ екінші топтың мүшелерін қоршаған ортада табуға тырысады. Осы типтегі проблемаларды зерттеудің бастапқы кезеңдерінде ортаны геометриялық түрде модельдеу жұмыстары жүргізілді. 1976 жылы Торренс Парсонс қозғалысты граф арқылы шектейтін формула енгізді. Геометриялық формула кейде үздіксіз іздеу-құтылу деп, ал графтық формула дискретті іздеу-құтылу деп аталады (осылайша графтық іздеу деп те аталады). Қазіргі зерттеулер көбінесе осы екі формуланың біріне ғана шектеледі.
Pursuit–evasion (variants of which are referred to as cops and robbers and graph searching) is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment. Early work on problems of this type modeled the environment geometrically. In 1976, Torrence Parsons introduced a formulation whereby movement is constrained by a graph. The geometric formulation is sometimes called continuous pursuit–evasion, and the graph formulation discrete pursuit–evasion (also called graph searching). Current research is typically limited to one of these two formulations.
Дискретті пішімдеу
Іздеу-құшу проблемасының дискретті тұжырымдамасында орта графиктік модельдеу арқылы бейнеленеді.
In the discrete formulation of the pursuit–evasion problem, the environment is modeled as a graph.
Мәселе анықтамасы
Қашудан қуудың сансыз нұсқалары бар, бірақ олардың көптеген элементтері ортақ. Типик, негізгі мысал келесідей (полиция мен ұрылар ойындары): Қуушылар мен қашушылар графтың түйіндерін иеленеді. Екі тарап кезекпен қимыл жасайды, мұнда әрбір мүше орнында қалады немесе қабырға бойымен көрші түйінге жылжиды. Егер қуушы қашушымен бірдей түйінде болса, қашушы ұсталып, графтан шығарылады. Көбінесе қойылатын сұрақ – барлық қашушыларды ұстау үшін қанша қуушы қажет. Егер бір қуушы жеткілікті болса, граф полиция жеңіске жететін граф деп аталады. Бұл жағдайда, графтың n түйінінің санына пропорционал уақытта бір қашушыны әрқашан ұстауға болады. k қуушымен r қашушыны ұстауға r⋅n уақыт кетеді, бірақ бірнеше қуушы үшін нақты шекара әлі белгісіз. Көбінесе қозғалыс ережелері қашушылардың жылдамдығын өзгерту арқылы өзгереді. Бұл жылдамдық – қашушы бір жүрісте қозғала алатын ең көп қабырға саны. Жоғарыдағы мысалда, қашушылардың жылдамдығы бірге тең. Екінші жағынан, шексіз жылдамдық тұжырымы бар, ол қашушыға графтың кез келген түйініне жылжуға мүмкіндік береді, егер оның бастапқы және соңғы орналасқан жерлері арасында қуушылар басып алған түйіндер жоқ жол болса. Сол сияқты, кейбір нұсқаларда қуушыларға «тікұшақтар» беріледі, бұл оларға өз кезегінде кез келген түйінге жылжуға мүмкіндік береді. Басқа нұсқаларда қуушылар мен қашушылардың әрқашан түйінде болуы керек деген шектеу ескерілмейді және олардың қабырға бойында бірде-бір жерде орналасу мүмкіндігі қарастырылады. Бұл нұсқалар көбінесе «сүріп өту» проблемалары деп аталады, ал алдыңғы нұсқалар іздеу проблемалары санатына жатады.
There are innumerable possible variants of pursuit–evasion, though they tend to share many elements. A typical, basic example is as follows (cops and robber games): Pursuers and evaders occupy nodes of a graph. The two sides take alternate turns, which consist of each member either staying put or moving along an edge to an adjacent node. If a pursuer occupies the same node as an evader the evader is captured and removed from the graph. The question usually posed is how many pursuers are necessary to ensure the eventual capture of all the evaders. If one pursuer suffices, the graph is called a cop win graph. In this case, a single evader can always be captured in time linear to the number of n nodes of the graph. Capturing r evaders with k pursuers can take in the order of r n time as well, but the exact bounds for more than one pursuer are still unknown. Often the movement rules are altered by changing the velocity of the evaders. This velocity is the maximum number of edges that an evader can move along in a single turn. In the example above, the evaders have a velocity of one. At the other extreme is the concept of infinite velocity, which allows an evader to move to any node in the graph so long as there is a path between its original and final positions that contains no nodes occupied by a pursuer. Similarly some variants arm the pursuers with "helicopters" which allow them to move to any vertex on their turn. Other variants ignore the restriction that pursuers and evaders must always occupy a node and allow for the possibility that they are positioned somewhere along an edge. These variants are often referred to as sweeping problems, whilst the previous variants would fall under the category of searching problems.
Нұсқалар
Бірнеше нұсқа маңызды граф параметрлерімен эквивалентті. Атап айтқанда, граф G-де шексіз жылдамдықпен бір қашушыны ұстау үшін қажетті қуушылардың санын табу (егер қуушылар мен қашушы кезекпен емес, бірдей уақытта қозғалса) граф G-нің ағаш енін табуға тең, ал қашушы үшін жеңіс стратегиясын граф G-дегі қауіпсіз мекен ретінде сипаттауға болады. Егер бұл қашушы қуушыларға көрінбесе, онда мәселе жол енін немесе төбелік ажыратымдылықты табуға тең. Граф G-де бір айналымда (яғни қуушылардың бастапқы орналасуынан бір қозғалыс) бір көрінбейтін қашушыны ұстау үшін қажетті қуушылардың санын табу, қуушылар бастапқыда кез келген жерге орналаса алатын жағдайда, граф G-нің ең кішкентай үстемдік жиынының өлшемін табуға тең (бұл кейінгі шарт қуушылар мен қашушы кезекпен қозғалатын болса орындалады). "Скотланд-Ярд" ойыны – қуғын-сүргін мәселесінің бір түрі.
Several variants are equivalent to important graph parameters. Specifically, finding the number of pursuers necessary to capture a single evader with infinite velocity in a graph G (when pursuers and evader are not constrained to move turn by turn, but move simultaneously) is equivalent to finding the treewidth of G, and a winning strategy for the evader may be described in terms of a haven in G. If this evader is invisible to the pursuers then the problem is equivalent to finding the pathwidth or vertex separation. Finding the number of pursuers necessary to capture a single invisible evader in a graph G in a single turn (that is, one movement by the pursuers from their initial deployment) is equivalent to finding the size of the minimum dominating set of G, assuming the pursuers can initially deploy wherever they like (this later assumption holds when pursuers and evader are assumed to move turn by turn). The board game Scotland Yard is a variant of the pursuit–evasion problem.
Күрделілігі
Бірнеше қуу-шабу нұсқаларының күрделілігі, атап айтқанда, белгілі бір графты тазалау үшін қанша қуушы қажет және берілген қуушылар саны графты олардың ең аз саяхат қашықтығымен немесе тапсырманы аяқтаудың ең аз уақытымен тазалау үшін қалай қозғалуы керек деген мәселелер Нимрод Мегиддо, С. Л. Хакими, Майкл Р. Гарей, Дэвид С. Джонсон және Христос Х. Пападимитриу (J. ACM 1988) және Р. Бори, К. Тови және С. Коениг тарапынан зерттелді.
The complexity of several pursuit–evasion variants, namely how many pursuers are needed to clear a given graph and how a given number of pursuers should move on the graph to clear it with either a minimum sum of their travel distances or minimum task completion time, has been studied by Nimrod Megiddo, S. L. Hakimi, Michael R. Garey, David S. Johnson, and Christos H. Papadimitriou (J. ACM 1988), and R. Borie, C. Tovey and S. Koenig.
Көп ойыншылы қуғын-сүргін ойындар
Көп ойыншылы қуу-құтылу ойындарын шешуге де көбірек назар аударылып келеді; R Vidal және басқалар, Chung және Furukawa, Hespanha және басқалардың еңбектерін қараңыз, сондай-ақ ондағы сілтемелерді. Маркос А. М. Виейра, Рамеш Говиндан және Гаурав С. Сухатме барлық ойыншылар толық ақпарат негізінде оңтайлы шешімдер қабылдаған жағдайда, қуушылардың барлық құтылушыларды ұстауына қажетті ең аз уақытты есептейтін алгоритм ұсынды. Бұл алгоритмді құтылушылар қуушылардан едәуір жылдам болған кезде де қолдануға болады. Алайда, бұл алгоритмдердің мүмкіндігі шағын ғана роботтар санымен шектеледі. Бұл қиындықтың шешімі ретінде Маркос А. М. Виейра, Рамеш Говиндан және Гаурав С. Сухатме қуушылардың құтылушыларды ұстауын қамтамасыз ететін, ойынды бірнеше қуушы-бір құтылушы ойындарына бөлетін бөлу алгоритмін жасап, іске қосты.
Solving multi player pursuit–evasion games has also received increased attention; see R Vidal et al., Chung and Furukawa , Hespanha et al. and the references therein. Marcos A. M. Vieira and Ramesh Govindan and Gaurav S. Sukhatme provided an algorithm that computes the minimal completion time strategy for pursuers to capture all evaders when all players make optimal decisions based on complete knowledge. This algorithm can also be applied to when evader are significantly faster than pursuers. Unfortunately, these algorithms do not scale beyond a small number of robots. To overcome this problem, Marcos A. M. Vieira and Ramesh Govindan and Gaurav S. Sukhatme design and implement a partition algorithm where pursuers capture evaders by decomposing the game into multiple multi pursuer single evader games.
Тұрақты пішімдеу
Іздеу-құшу ойындарының үздіксіз формулировкасында орта геометриялық түрде модельделеді, әдетте Евклид жазықтығы немесе басқа да көптүрлілік нысанында. Ойынның түрлері ойыншыларға жылдамдық немесе үдеудің шектеулі диапазоны сияқты маневрлеу шектеулерін қоюы мүмкін. Кедергілер де қолданылуы мүмкін. Егер арыстан адамды бірдей жылдамдықпен қуатын болса, онда адам жазықтықта немесе сферада арыстаннан әрдайым тура сызықпен алыстап жылжу арқылы қашып кетуі мүмкін екені анық. Екеуі де дөңгелек дискіге тығылған жағдайда, арыстанның адамды ұстап алуы ықтимал сияқты көрінеді. Бесикович 1952 жылы адамның кез келген стратегияға қарсы ұсталудан белгісіз мерзімге қашып құтылуға болатын стратегиясы бар екенін дәлелдеді.
In the continuous formulation of pursuit–evasion games, the environment is modeled geometrically, typically taking the form of the Euclidean plane or another manifold. Variants of the game may impose maneuverability constraints on the players, such as a limited range of speed or acceleration. Obstacles may also be used. If a lion is chasing a man with equal speed, then it is clear that the man can escape on a plane or a sphere by always moving on the straight line away from the lion. When both are confined in a circular disk, it seemed likely for the lion to catch the man. Besicovitch proved in 1952 that the man has a strategy to evade capture indefinitely against any strategy.
Қолданбалар
Руфус Айзекстің RAND корпорациясында жасаған зымыранды бағыттау жүйелері, қуу-алып кету мәселесінің бастапқы қолданылған салаларының бірі болды.
One of the initial applications of the pursuit–evasion problem was missile guidance systems formulated by Rufus Isaacs at the RAND Corporation.