ЗАДАЧА ПОИСКА НА ГРАФАХ ПРИ НАЛИЧИИ ОГРАНИЧЕННОЙ ИНФОРМАЦИИ ОБ ИСКОМОЙ ТОЧКЕ

Аннотация

In this work, he studies the problem of searching on finite graphs with limited information about the desired point. To take into account the amount of information available to the search point, the concept of an information set is introduced. The theorems on the solvability of the search problem, which underlie the general theory, are presented. Keywords: graph, edge, vertex, invariance, awareness, similarity, existence of upper and lower bounds. Содержательно, задача поиска состоит в следующем: по графу  движутся точка P (ищущая, преследующая) и точка Q (прячущаяся, убегающая) с максимальными по модулю скоростями  и  соответственного,  0 ,  0   . Траектория точки P (соответственно Q ) определяется как абсолютно-непрерывная функция x ( ) : [ 0 ,  )   (соответственно y ( ) : [ 0 ,  )   , такая, что   u ( t )  v ( t )  п.в., где u(t)dx(t)/dt- функция управления точки P , (v(t)  dy(t)/dt- функция управления точки Q ). Целью точки P является настичь (обнаружить поймать) точку Q , которая осуществляется, если x(t) y(t) при некотором tJ , где J -либо отрезок вида [0,T], либо луч [ 0 ,  ) . Займёмся уточнением важного в задаче поиска понятия типа информированности, т.е. того объема информации, который имеет точка P в каждый текущий момент времени t , t  0 . Естественно, он должен включать всю предысторию движения самой точки P - функцию x(), 0t. Что касается информации, поступающей о местоположении точки Q, то естественно, что она должна иметь форму подмножества W графа , которого можно называть информационным множеством. Информационное множество меняется по International scientific journal ISSN: 2181-3906 «MODERN SCIENCE АND RESEARCH» 2023 VOLUME 2 / ISSUE 5 / UIF:8.2 / MODERNSCIENCE.UZ мере движения точки 1 16 7 Q и в каждый текущий момент времени t точка P получает информацию о том, что Q находится в пределах множества  . В этом работе рассматривается только понятие звёздной окрестности. Определение 1. Пусть y   . Звездной окрестностью точки y назовем подграф W графа , такой, что точка y является внутренней для W в топологии . Определение 2. Отображение W , ставящее к каждой точке y   некоторую ее звездную окрестность W(y), называется информационным отображением. В дальнейшем предлагаем, что информационное отображение постоянно на ребрах в следующем смысле: если y 1 и y 2 являются внутренними точками одного и того же ребра, то W(y )W(y ). 1 2 Под задачей поиска будем понимать четверку  , , , W     , состоящую из графа  , положительных чисел ,  и информационного отображения W . Если W(y) тождественно, то мы получим задачу поиска без текущей информации - минимаксную задачу поиска в постановке Н.Н.Петрова. [1-3]. Пусть X (соответственно, Y ) - совокупность всех траекторий x ( ) : [ 0 ,  )   точки P (траекторий y ( ) : [ 0 ,  )   точки Q ), а U (соответственно, V ) – совокупность соответствующих управлений u ( ) , u ( t )  d x ( t ) / d t п.в. (соответственно v() v(t)  dy(t)/dt п.в.) По мере движения точки Q вдоль конкретной траектории y ( t ) , меняется и    информационное множество W y t . Поскольку точка y ( t ) является внутренней для множества W y t , то на каком-то промежутке времени 0 , )  множество W y t остаётся неизменным, равным W y 0 . Пусть t - первый момент времени, когда 1 y ( t ) покидает множество W  y  0   , т.е. окажется на его границе. В этот момент времени информационное множество может измениться и тем самым точка Р получает новую порцию текущей информации, а именно, информацию о том, что точка Q находится в пределах множества W y t 1 . Поэтому каждый такой момент времени назовем моментом высвечивания. Очевидно, в момент высвечивания точка Q будет находиться на одной из вершин графа Г. По нашему определению, следующий момент высвечивания наступить только тогда, когда точка y ( t ) достигает какую-то другую вершину. Это обстоятельство обеспечивает, что W y t меняется скачками, без накопления моментов высвечивания. Обозначим Г* совокупность значений информационного отображения W. В принципе, в качестве Г* можно взять совокупность всех подмножеств Г, могущих служит звездной окрестностью. Определение 3. отображение S ставящее в соответствие к каждой паре x  : 0,t Г , WГ * функцию управления u  , называется стратегией поиска. t International scientific journal ISSN: 2181-3906 «MODERN SCIENCE АND RESEARCH» 2023 VOLUME 2 / ISSUE 5 / UIF:8.2 / MODERNSCIENCE.UZ Тройку 1 16 8 x 0 , S , y , состоящую из начальной точки x 0  Г , стратегии поиска S и траектории y  Y точки Q, назовем ситуацией. Точка Р в соответствии с выбранной ею стратегией ведет поиск следующим образом. В начальный момент времени t 0 в его распоряжении имеется информация о своим 0 положении x 0  X и о том, что точка Q находится в пределах W y 0 , помимо знания Г и чисел   , . (Было бы интересно изучить задачу поиска в случае, когда точка не имеет полную информацию о графе Г, о значении ). Стратегия поиска по этой информации диктует вести поиск по траектории