ISSN:
2181-3906
2023
International scientific journal
«MODERN SCIENCE АND RESEARCH»
VOLUME 2 / ISSUE 5 / UIF:8.2 / MODERNSCIENCE.UZ
1166
ЗАДАЧА ПОИСКА НА ГРАФАХ ПРИ НАЛИЧИИ ОГРАНИЧЕННОЙ
ИНФОРМАЦИИ ОБ ИСКОМОЙ ТОЧКЕ
Хусанбай Наржигитов
Жамуратов Кeнгаш
Хабибулла Умаров
Рустамжон Худайкулов
Гулистанский государственный университет,
г. Гулистан, Узбекистан
е-mail:
https://doi.org/10.5281/zenodo.7976774
Аннотация.
В работе изучает задаче поиска на конечных графах при ограниченной
информации об искомой точке Q . Для учета объема информации, поступающей в
распоряжение ищущей точки
P
, вводится понятие информационного множества.
Излагаются теоремы о разрешимости задачи поиска, лежащие в основе общей теории.
Ключевые слова:
граф, ребре, вершина, инвариантность, информированность,
подобие, существование верхней и нижней оценки.
SEARCH PROBLEM ON GRAPHS IN THE PRESENCE OF LIMITED
INFORMATION ABOUT THE SEARCH POINT
Abstract.
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
) определяется как абсолютно-непрерывная функция
)
,
0
[
:
)
(
x
(соответственно
)
,
0
[
:
)
(
y
, такая, что
)
(
)
(
t
v
t
u
п.в., где
dt
t
dx
t
u
/
)
(
)
(
-
функция управления точки
P
, (
dt
t
dy
t
v
/
)
(
)
(
- функция управления точки
Q
).
Целью точки
P
является настичь (обнаружить поймать) точку
Q
, которая
осуществляется, если
)
(
)
(
t
y
t
x
при некотором
J
t
, где
J
-либо отрезок вида
]
,
0
[
T
, либо
луч
)
,
0
[
.
Займёмся уточнением важного в задаче поиска понятия типа информированности,
т.е. того объема информации, который имеет точка
P
в каждый текущий момент времени
0
,
t
t
. Естественно, он должен включать всю предысторию движения самой точки
P
-
функцию
t
x
0
),
(
. Что касается информации, поступающей о местоположении точки
Q
, то естественно, что она должна иметь форму подмножества
W
графа
, которого
можно называть информационным множеством. Информационное множество меняется по
ISSN:
2181-3906
2023
International scientific journal
«MODERN SCIENCE АND RESEARCH»
VOLUME 2 / ISSUE 5 / UIF:8.2 / MODERNSCIENCE.UZ
1167
мере движения точки
Q
и в каждый текущий момент времени
t
точка
P
получает
информацию о том, что
Q
находится в пределах множества
.
В этом работе рассматривается только понятие звёздной окрестности.
Определение 1. Пусть
y
. Звездной окрестностью точки
y
назовем подграф
W
графа
, такой, что точка
y
является внутренней для
W
в топологии
.
Определение 2. Отображение
W
, ставящее к каждой точке
y
некоторую ее
звездную окрестность
)
(
y
W
, называется информационным отображением.
В дальнейшем предлагаем, что информационное отображение постоянно на ребрах
в следующем смысле: если
1
y
и 2
y
являются внутренними точками одного и того же
ребра, то
)
2
(
)
1
(
y
W
y
W
.
Под задачей поиска будем понимать четверку
W
,
,
,
, состоящую из графа
, положительных чисел
,
и информационного отображения
W
.
Если
)
(
y
W
тождественно, то мы получим задачу поиска без текущей
информации - минимаксную задачу поиска в постановке Н.Н.Петрова. [1-3].
Пусть
X
(соответственно,
Y
) - совокупность всех траекторий
)
,
0
[
:
)
(
x
точки
P
(траекторий
)
,
0
[
:
)
(
y
точки
Q
), а
U
(соответственно,
V
) – совокупность
соответствующих управлений
)
(
u
,
dt
t
dx
t
u
/
)
(
)
(
п.в. (соответственно
)
(
v
dt
t
dy
t
v
/
)
(
)
(
п.в.)
По мере движения точки Q вдоль конкретной траектории
)
(
t
y
, меняется и
информационное множество
t
y
W
. Поскольку точка
)
(
t
y
является внутренней для
множества
t
y
W
, то на каком-то промежутке времени
)
,
0
множество
t
y
W
остаётся неизменным, равным
0
y
W
.
Пусть
1
t
- первый момент времени, когда
)
(
t
y
покидает множество
0
y
W
, т.е.
окажется на его границе. В этот момент времени информационное множество может
измениться и тем самым точка Р получает новую порцию текущей информации, а именно,
информацию о том, что точка Q находится в пределах множества
1
t
y
W
. Поэтому
каждый такой момент времени назовем моментом высвечивания.
Очевидно, в момент высвечивания точка Q будет находиться на одной из вершин
графа Г. По нашему определению, следующий момент высвечивания наступить только
тогда, когда точка
)
(
t
y
достигает какую-то другую вершину. Это обстоятельство
обеспечивает, что
t
y
W
меняется скачками, без накопления моментов высвечивания.
Обозначим Г* совокупность значений информационного отображения W. В
принципе, в качестве Г* можно взять совокупность всех подмножеств Г, могущих служит
звездной окрестностью.
Определение 3. отображение S ставящее в соответствие к каждой паре
*
,
,
0
:
Г
W
Г
t
x
t
функцию управления
u
, называется стратегией поиска.
ISSN:
2181-3906
2023
International scientific journal
«MODERN SCIENCE АND RESEARCH»
VOLUME 2 / ISSUE 5 / UIF:8.2 / MODERNSCIENCE.UZ
1168
Тройку
y
S,
,
0
x
, состоящую из начальной точки
,
0
Г
x
стратегии поиска S и
траектории
Y
y
точки Q, назовем ситуацией.
Точка Р в соответствии с выбранной ею стратегией ведет поиск следующим образом.
В начальный момент времени
0
0
t
в его распоряжении имеется информация о своим
положении
X
x
0
и о том, что точка Q находится в пределах
0
y
W
, помимо знания Г
и чисел
,
. (Было бы интересно изучить задачу поиска в случае, когда точка не имеет
полную информацию о графе Г, о значении
). Стратегия поиска по этой информации
диктует
вести
поиск
по
траектории
x
,
порождаемой
управлением
.
0
y
W
,
0
x
S
u
Пусть
1
t
- первый момент высвечивания,
1
1
1
1
t
y
y
,
t
x
x
. В
этот момент времени точка Р распоряжается информацией
1
t
x
и
1
y
W
, в соответствии
с которой стратегия S порождает управление
1
t
,
x
1
y
W
S
u
. Траектория
x
продолжается по формуле
t
t
d
t
u
x
t
x
1
1
1
.
Точка Р продолжит двигаться по этой траектории до следующего момента высвечивания и
т.д.
В силу того, что граф Г конечный и скорости точек ограниченные, каждая ситуация
y
S,
,
0
x
порождает единственную траекторию
Г
x
)
,
0
:
. (Если нет
надобности, индекс
в обозначении будем опускать.)
Теорема об инвариантности.
Разрешимость задачи поиска
W
,
,
,
Г
не
зависит от точки
0
x
.
Теорема о подобии.
Если задача поиска
W
,
,
,
Г
разрешима на отрезке
Т
,
0
и
0
k
, то задача поиска
W
,
k
,
k
,
Г
разрешима на отрезке
k
Т
/
,
0
.
Теорема о существовании верхней оценки.
Существует такое, что при
задача поиска разрешима.
Теорема о существовании нижней оценки.
Если граф
Г
имеет хотя бы одну
вершину степени не меньше 3, то существует
0
,
k
k
, такое, что при
k
задача
поиска не разрешима.
Из этих утверждений вытекает, что для каждой пары графа
Г
и информационного
отображения
W
существует положительное число
0
k
, такое, что при
0
k
задача поиска
разрешима, а при
0
k
- не разрешима. К сожалению, пока не удается вычислить даже
для простейших графов. Основные результаты относятся к построению стратегии поиска,
гарантирующей разрешимость для определенных значений
/
.
REFERENCES
ISSN:
2181-3906
2023
International scientific journal
«MODERN SCIENCE АND RESEARCH»
VOLUME 2 / ISSUE 5 / UIF:8.2 / MODERNSCIENCE.UZ
1169
1.
Умаров, Х. Р., & Жамуратов, К. (2015). Решение задачи о притоке к
математическому
совершенному
горизонтальному
дренажу. Актуальные
направления научных исследований XXI века: теория и практика, 3(8-4), 303-307.
2.
Жамуратов, К., Умаров, Х., & Холбоев, С. (2016). Решение одной задачи теории
фильтрации методом квазистационарного приближения. Вестник ГулГУ, (2), 9.
3.
Умаров, Х. Г. (2012). О разрешимости одномерного уравнения Кана-Хилларда с
вязкостью в пространстве непрерывных ограниченных функций на всей
оси. Прикладная математика & Физика, 28(17 (136)), 91-101.
4.
UMAROV, H. (1986). Trudoizbytocnoe selo: problemy i resenija (Main-d'oeuvre rurale
excédentaire: problèmes et solutions). Voprosy èkonomiki, (9), 99-108.
5.
Жамуратов, К., Умаров, Х., & Сулаймонова, Н. (2021). ПРИБЛИЖЕННОЕ
РЕШЕНИЕ ОДНОЙ ЗАДАЧИ ТИПА СТЕФАНА ДЛЯ МАЛЫХ ЗНАЧЕНИЙ
ВРЕМЕНИ. Eurasian Journal of Academic Research, 1(9), 826-831.
6.
Жамуратов, К., Умаров, Х. Р., & Курбонов, Ж. Т. (2021). К приближенному
решению одной задачи теории фильтрации для малых значений времени. Научный
альманах, (1-2), 48-53.
7.
ЖАМУРАТОВ, К., УМАРОВ, Х. Р., & АЛИМБЕКОВ, А. Решениe oдной задачи
движения грунтовых вод в области с подвижной границей при наличии
испарения. НАУЧНЫЙ АЛЬМАНАХ Учредители: ООО" Консалтинговая
компания Юком", 81-84.
8.
Жамуратов, К., Гаймназаров, Х., & Худайкулов, Р. (2012). РЕШЕНИЕ ЗАДАЧИ О
ДИНАМИКЕ
ГРУНТОВЫХ
ВОД
ВБЛИЗИ
НОВЫХ
КАНАЛОВ
И
ВОДОХРАНИЛИЩ В КУСОЧНО-ОДНОРОДНОМ ПЛАСТЕ ПРИ НАЛИЧИИ
ИСПАРЕНИЯ. In Современные материалы, техника и технология (pp. 104-106).
9.
Xabibullo, U., Rustamjon, X., & Islom, O. (2022). GAMMA FUNKSIYANING
FUNKSIONAL XOSSALARI. Yosh Tadqiqotchi Jurnali, 1(3), 74-78.
10.
Gaymnazarov, G., Khudaykulov, R., Nuraliyev, A., & Khidirova, S. (2020). ON THE
APPROXIMATION OF PERIODIC FUNCTIONS OF MANY VARIABLES BY
SUMS OF MARCINKIEWICZ TYPE.
11.
Abdiev, U. B., & Khudoyqulov, R. INNOVATIVE APPROACH TO THE
DEVELOPMENT OF TECHNOLOGICAL COMPETENCE IN STUDENTS.
12.
Gaimnazarov, G., Narjigitov, H., & Gaimnazarov, O. G. (2013). On some properties of
functions associated with the derivative of fractional order in the space L p (-∞,∞). Far
East Journal of Mathematical Sciences, 76(2), 319-336.
13.
Zulunovich, M. A., Xusanboy, N., Kengash, J., Ismatulla oʻgʻLi, E. A., & Turdaliyevich,
R. J. (2021). Stability of the Galerkin Method for one Quasilinear Parabolic Type
Problem. CENTRAL ASIAN JOURNAL OF MATHEMATICAL THEORY AND
COMPUTER SCIENCES, 2(6), 6-12.
14.
Mamatov, A., Narjigitov, X., Turdibayev, D., & Rakhmanov, J. (2021). Refining the
Galerkin method error estimation for parabolic type problem with a boundary condition.
In E3S Web of Conferences (Vol. 304, p. 03019). EDP Sciences.
ISSN:
2181-3906
2023
International scientific journal
«MODERN SCIENCE АND RESEARCH»
VOLUME 2 / ISSUE 5 / UIF:8.2 / MODERNSCIENCE.UZ
1170
15.
Norjigitov, H., & Dustnazarova, I. (2021). APPLICATIONS OF THE IMPROPER
INTEGRALS TO THE PHYSICAL PROCESS. Bulletin of Gulistan State
University, 2021(1), 14-19.
16.
Норжигитов, Ҳ., & Яҳёев, Д. Т. (2022). ЧЕГИРМАЛАР НАЗАРИЯСИНИНГ
ХОСМАС ИНТЕГРАЛЛАРНИ ҲИСОБЛАШГА ТАТБИҚИ. Yosh Tadqiqotchi
Jurnali, 1(1), 120-135.
