Задача оптимального выбора с «заминированными» объектами
Рассмотрена задача оптимального выбора при условии, что некоторые объекты, выбираемые по случайному закону, являются заминированными. Просмотр заминированного объекта приводит к принудительной остановке процесса просмотра. Установлено, что в рассматриваемом случае, оптимальная стратегия имеет порого...
Saved in:
| Published in: | Кибернетика и вычислительная техника |
|---|---|
| Date: | 2012 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/45880 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Задача оптимального выбора с «заминированными» объектами / С.И. Доценко, О.К. Закусило // Кибернетика и вычисл. техника. — 2012. — Вип. 170. — С. 51-58. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859649854323556352 |
|---|---|
| author | Доценко, С.И. Закусило, О.К. |
| author_facet | Доценко, С.И. Закусило, О.К. |
| citation_txt | Задача оптимального выбора с «заминированными» объектами / С.И. Доценко, О.К. Закусило // Кибернетика и вычисл. техника. — 2012. — Вип. 170. — С. 51-58. — Бібліогр.: 3 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и вычислительная техника |
| description | Рассмотрена задача оптимального выбора при условии, что некоторые объекты, выбираемые по случайному закону, являются заминированными. Просмотр заминированного объекта приводит к принудительной остановке процесса просмотра. Установлено, что в рассматриваемом случае, оптимальная стратегия имеет пороговый вид. Выведено уравнение, корень которого является искомой величиной порога. Найдены оптимальные стратегии при разных способах и параметрах минирования.
Розглянуто задачу оптимального вибору за умови, що деякі об’єкти, що вибираються за випадковим законом, можуть бути заміновані. Проглядання замінованого об’єкту призводить до примусової зупинки процесу проглядання. Встановлено, що у випадку, що розглядається, оптимальна стратегія має порогів вигляд. Отримано рівняння, корінь якого є шуканою величиною порогу. Знайдено оптимальні стратегії при різних способах та параметрах мінування.
For the optimal choice problem with mined objects it was shown that the support set for the stopping moment has the same structure as for the classical case. However, the threshold value is lower (i.e. stipulated by “mine threat” phenomena. For the ways of mining the threshold values are calculated and numerical results are delivered.
|
| first_indexed | 2025-12-07T13:32:28Z |
| format | Article |
| fulltext |
51
Сложные системы управления
УДК: 681.5
С.И. Доценко, О.К. Закусило
ЗАДАЧА ОПТИМАЛЬНОГО ВЫБОРА
С «ЗАМИНИРОВАННЫМИ» ОБЪЕКТАМИ
Рассмотрена задача оптимального выбора при условии, что некоторые
объекты, выбираемые по случайному закону, являются заминированными. Просмотр
заминированного объекта приводит к принудительной остановке процесса просмотра.
Установлено, что в рассматриваемом случае, оптимальная стратегия имеет пороговый вид.
Выведено уравнение, корень которого является искомой величиной порога. Найдены
оптимальные стратегии при разных способах и параметрах минирования.
Введение. В [1] была рассмотрена задача выбора наилучшего объекта,
сформулированная следующим образом. Пусть некто в случайном порядке
знакомится с n объектами и хочет выбрать среди них наилучший. При этом
после ознакомления с очередным объектом нужно либо остановить на нем
свой выбор, либо отвергнуть его; возвращаться к ранее просмотренным
объектам нельзя. Объекты являются упорядоченными определенным образом
по качеству, т.е. качества любых двух объектов сравнимы между собой.
«Ознакомление в случайном порядке» означает, что изначально все n!
перестановок, задающих порядок просмотра объектов, равновероятны.
Объект, наилучший среди всех n, в дальнейшем будем называть
наилучшим, а объект, лучший среди k просмотренных, — максимальным.
Очевидно, что в ходе просмотра следует анализировать целесообразность
остановки выбора на некотором объекте, только если он является
максимальным. При этом оказывается, что первый объект является
максимальным и индексы максимальных объектов образуют цепь Маркова с
переходными вероятностями kj
jj
kjkp >
−
= ,
)1(
),( . Независимо от того,
был ли k-й элемент максимальным или нет, вероятность того, что среди
элементов с индексами nk ...,,1+ минимальный индекс максимального
элемента будет j, равна kj
jj
k
>
−
,
)1(
и с вероятностью
n
k в
последовательности nk ...,,1+ не встретится ни одного максимального
элемента.
Доказано, что для того, чтобы выбрать наилучший объект из n, нужно
придерживаться такой стратегии: вначале пропустить все элементы с
индексами 1...,,1 * −k и затем остановить свой выбор на первом
максимальном элементе, индекс которого не меньше *k , где *k определяется
из двойного неравенства
С.И. Доценко, О.К. Закусило, 2012
ISSN 0452-9910. Кибернетика и вычисл. техника. 2012. Вып. 170
52
1
1...
1
11
1
1...1
** −
++
−
<≤
−
++
nknk
. (1)
Оказывается, что при ∞→n
en
k 1
→ , а вероятность выбора наилучшего
объекта при соблюдении описанной стратегии стремится к 1 / e. Множество
индексов, на которых возможна остановка, будем обозначать }...,*,{Г* nk= и
называть опорным множеством.
Постановка задачи оптимального выбора с заминированными
объектами
Предположим, что среди всех объектов один или несколько являются
«заминированными» (в дальнейшем будем сокращенно называть их з.о.).
Количество и положение з.о. случайно и подчинено заданому
распределению. После просмотра з.о. следует принудительное прекращение
дальнейшего просмотра и получение нулевого выигрыша (предполагается, что
подрыв на мине приводит лишь к прекращению просмотра и не несет иного
ущерба).
Далее будет рассмотрено два варианта минирования:
1. Заминирован один объект, и его положение равновероятно для всех
значений n.
2. Каждый из объектов минируется независимо от других с
вероятностью α / n. Таким образом, число з.о. имеет биномиальное, а в
пределе, при ∞→n , пуассоновское распределение.
Интуитивно ясно, что «минирование» приведет к таким последствиям:
1. Вероятность нахождения наилучшего элемента уменьшится.
2. Оптимальная стратегия просмотра станет более «осторожной», и
область просмотра сузится.
Дальнейшие выкладки подтвердят справедливость данных пред-
положений и покажут, что оптимальная стратегия по-прежнему имеет
пороговый вид, т.е. пропустить некоторое количество элементов и
остановиться после этого на первом максимальном элементе, но значение
порога (количество пропускаемых элементов) по сравнению с классическим
случаем уменьшится.
Далее найдем множества элементов, на которых следует делать
остановку при условии, что эти элементы являются максимальными.
Проведем рассуждения методом обратной индукции.
Первый случай. Пусть заминирован один объект и его положение
равновероятно для всех значений n.
Пусть просматривается (n – 1)-й элемент, он является максимальным и
при этом ни он, ни предыдущие элементы не были заминированы. Если
остановиться на данном элементе, то величина выигрыша составит
n
n 1− , а
если продолжить просмотр, то следующий элемент будет заминирован и
величина выигрыша составит 0. Таким образом, на (n – 1)-м элементе следует
остановиться.
53
Предположим, что просматривается k-й элемент, который является
максимальным и уже установлено, что на всех последующих элементах
также следует делать остановку, если они оказались максимальными. Если
сделать остановку на k-м элементе, то, как и в классическом случае, величина
выигрыша составит
n
kkf =)( . Если же продолжить просмотр, то согласно
индукции следует остановиться на следующем максимальном элементе, и
согласно формуле полной вероятности средняя величина выигрыша в
классическом случае составляет
.
1
1)(),()(
1 1
∑ ∑
+= += −
==′
n
kj
n
kj jn
kjfjkpkf (1)
В случае наличия мин каждое слагаемое в (1) следует умножить на
условную вероятность того, что среди jk ...,,1+ нет з.о. при условии, что
среди k...,,1 также нет з.о. (обозначим этот множитель через ),( jkr ), тогда
( )
( ) kn
jn
kP
jPkjkPjkr
−
−
=
−
−
=−−+=
з.о.не...,,1
з.о.не...,,1)з.о.не...,,1з.о.не...,,1(),( . (2)
Заметим, что 0),( =nkr , поэтому последнее слагаемое пропадает, и (1)
приобретает вид
∑ ∑
+=
−
+= −
−
−
==′
n
kj
n
kj j
jn
knn
kjfjkrjkpkf
1
1
1 1)(
)(),(),()( . (3)
Найдем множество индеков k, для которых справедливо неравенство
)(')( kfkf ≥ . Данное неравенство равносильно
1
1
1 1
1
≤
−
−
−
∑
−
+=
n
kj j
jn
kn
. (4)
Покажем, что левая часть (4) при любом фиксированном n монотонно
убывает по k:
+
−+−
+−
=
−−
−
= ∑
−
+=
1
1 1)1(
1)1(
1
1),(
n
kj kkn
kn
jkn
jnnkS
...
1)2(
1)2(
+
−+−
+−
+
kkn
kn
(5)
+
−++−
+−
=
−+−
−
=+ ∑
−
+=
1
2 1)2(
1
)1(
)2(
1
1
)1(
),1(
n
kj kkn
kn
jkn
jnnkS
...
1)3(
1
)1(
)3(
+
−++−
+−
+
kkn
kn
(6)
Сопоставим первое по порядку слагаемое из (5) с первым из (6), второе
54
со вторым и т.д. Заметим, что все слагаемые положительные. Каждое
слагаемое состоит из двух сомножителей, и каждый сомножитель из (5) не
меньше соответствующего сомножителя соответствующего слагаемого из (6).
Значит каждое слагаемое из (6) меньше соответствующего по порядку
слагаемого из (5). Кроме того, в (5) на одно слагаемое больше. Отсюда
),1(),( nkSnkS +> . Непосредственно легко показать, что 1),1( >nS , а
1),1( <− nnS . Значит неравенство (4) выполняется, начиная с некоторого *k
— это и есть согласно индукции множество индексов элементов, на которых
следует остановиться при условии, что элемент является максимальным. На
элементах с индексами, меньшими, чем *k , останавливаться не следует,
поскольку для них нарушается неравенство (4) и, следовательно, стратегия
остановки на таком элементе заведомо хуже, чем стратегия, состоящая в том,
чтобы сделать один шаг вперед и остановиться на следующем максимальном
элементе.
Далее, найдем предел отношения
n
k*
при ∞→n . Пусть x — некоторое
число из интервала (0; 1), тогда
[ ]
∑ ∫
−
=
∞→ −
−
−
−=
−
−
→
−−−
−1 1
1
1
)ln(1
1
1
1
1
)1(
n
nxj x
n
x
xdt
tx
t
jkn
jn и искомый предел
является корнем уравнения 11
1
)ln(
=−
−
−
x
x . Отсюда 0)ln(22 =+− xx . Данное
уравнение имеет единственный корень на интервале (0; 1), примерно равный
0,203. Значит при больших n следует придерживаться такой стратегии:
пропустить первые n203,0 элементов и остановиться на первом
максимальном элементе. При этом вероятность выбора наилучшего элемента
составит
)203,0(')миннет203,01среди(* nfnPP −=
.162,0203,0)203,01()203,0()миннет203,01среди( =⋅−=−= nfnP
Приведем строгое доказательство того, что предел отношения
n
k*
равен
меньшему корню уравнения 0)ln(22 =+− xx (поскольку данное
доказательство громоздко, оно может быть пропущено при первом чтении).
Доказательство. Пусть 3≥n , )(** nkk = — такой наименьший номер k,
начиная с которого выполняется неравенство ∑
=
≤
−
−
n
kj j
jn
kn
11 . Докажем,
что при ∞→n
n
k*
стремится к меньшему корню уравнения
0)ln(22 =+− xx (этот корень примерно равен 0,203, второй, больший корень
равен 1).
55
Обозначим 11,1
−≤≤
−
−
= ∑
=
nk
j
jn
kn
a
n
kj
nk . Как было показано ранее,
данная последовательность монотонно убывает по k при любом
фиксированном n. Кроме того, 1
1
1
1
1
1 =
−
−
>
n
n
an ,
1
1
1, −
=− n
a nn , значит
номер k существует, причем 12 * −≤≤ nk .
Таким образом, для индекса *k должно выполняться двойное
неравенство:
.1 1*,*, −<≤ knkn aa (7)
Представим последовательность kna , в виде
.1
/
11
/1
1
1:
, ∑
≤≤
−
−
=
n
j
n
kj
kn njnnk
a (8)
Учитывая (7), можно выделить подпоследовательность номеров }{ 'n , для
которой x
n
nk
→
′
′)(*
, где x — некоторое число из интервала [0; 1]. Заметим,
что тогда также x
n
nk
→
′
−′ 1)(*
.
Далее, в выражении (8) положим ∞→′= nn . Рассмотрим различные
случаи возможных значений x:
1. x = 0. Тогда ∑
≤≤
−
1*:
*, 1
/
11~
n
j
n
kj
kn njn
a . Отсюда
∫ +
∞→
→+∞→
−≥∈∀
1
*,
___
0,11lim:)1;0(
ε
εε dt
t
a kn
n
. Но, с другой стороны, из (7)
следует, что 1lim *,
___
≤
∞→
kn
n
a (это противоречит предыдущему соотношению).
Значит 0≠x .
2. x = 1. Тогда 0max)(1
*
*
1,
*
**, →
−
=
−
⋅−
−
≤
−= k
kn
j
jnkn
kn
a
nkj
kn , и
аналогично 01*, →−kna , что противоречит (7). Значит 1≠x .
3. При 0 < x < 1 имеем ∫ −
−+−
=
−
−
→
1
*, 1
1)ln(11
1
1
x
kn x
xxdt
tx
a ,
к этому же пределу сходится и 1*, −kna . С другой стороны, из (7) следует, что
1*, →kna , 11*, →−kna , 1
1
1)ln(
=
−
−+−
x
xx , 10,0)ln(22)( <<=−−= xxxxf .
56
Имеем: 012)(,)0(,0)1( =−=′+∞=+=
x
xfff при
2
1
=x . Функция f(x)
убывает на
2
1;0 , возрастает на
1;
2
1 , поэтому ( ) 01
2
1
=−<
ff , тогда на
промежутке
2
1;0 функция имеет единственный нуль 0x .
Таким образом, 0
* )( x
n
nk
→
′
′
. Предел не зависит от выбора
подпоследовательности номеров, для которой
n
nk
′
′)(*
сходится. Значит
ограниченная последовательность
≥ 3,)(*
n
n
nk имеет единственную
предельную точку 0x , отсюда ∞→→ nx
n
nk ,)(
0
*
. ■
Второй случай. Пусть каждый из объектов минируется независимо от
других с вероятностью α / n, где α — параметр, задающий среднее
количество мин. Проведем рассуждения аналогично предыдущему случаю,
методом обратной индукции. В этом случае, в отличие от предыдущего,
возможна ситуация, когда просматривается самый последний элемент и этот
элемент является максимальным. Очевидно, на таком элементе следует
остановиться.
В данном случае
kj
n
jkr
−
−=
α1),( , тогда
∑ ∑
+= +=
−
−
−
==′
n
kj
n
kj
kj
njn
kjfjkrjkpkf
1 1
.1
1
1)(),(),()( α (9)
Как и в предыдущем случае
n
kkf =)( , тогда неравенство )(')( kfkf ≥
приобретает вид
.11
1
1
1
∑
+=
−
≤
−
−
n
kj
kj
nj
α (10)
Покажем, что левая часть (10) монотонно убывает по k при
фиксированных значениях α и n. Обозначим
n
q α
−= 1 , тогда
,
1
...
1
),(
2
−
++
+
+=
−
n
q
k
q
k
qnkS
kn
(11)
.
1
...
21
),1(
12
−
++
+
+
+
=+
−−
n
q
k
q
k
qnkS
kn
(12)
57
Аналогично предыдущему случаю, все слагаемые положительны, каждое
слагаемое в (11) больше соответствующего по порядку слагаемого в (12) и
(11), содержит на одно слагаемое больше, отсюда ),1(),( nkSnkS +> . Легко
показать, что при фиксированном α и достаточно большом n 1),1( >nS , а
1),1( <− nnS . Значит неравенство (4) выполняется, начиная с некоторого *k ,
которое, естественно, будет отличаться от соответствующего значения в
предыдущем случае.
Найдем предел отношения
n
k*
при ∞→n . Пусть x — некоторое число
из интервала (0; 1), тогда
( )
[ ]
∑ ∫
−
=
∞→
−
−− →
−
−
1 1 1)(exp
1
11
n
nxj x
n
kj
dt
t
xt
jn
α
α и искомый предел
является корнем уравнения ( )∫ =−−
1
11)(exp
x
dt
t
xtα .
При этом вероятность выбора наилучшего элемента составит
=−= )(')миннет1среди( *** kfkPP
.exp)()миннет1среди(
**
**
n
k
n
kkfkP
−=−= α
В таблице приведены предельные значения
n
k*
и *P для некоторых
значений параметра α.
α 0,01 0,05 0,1 0,5 1 2 5 10
nk /* 0,367 0,363 0,358 0,319 0,271 0,192 0,087 0,043
*P 0,366 0,356 0,346 0,272 0,207 0,131 0,056 0,028
Выводы. Проделанные расчеты подтверждают следующие тенденции:
n
k*
и *P стремятся к
e
1 при малых α и к 0 при больших α. При α = 1
величины
n
k*
и *P больше, чем соответствующие величины в первом случае
(0,271 и 0,207 против соответственно 0,203 и 0,162). Это может быть
объяснено тем, что пуассоновское распределение с параметром 1 менее
регулярно, чем 1 с вероятностью 1. «Минирование» менее регулярным
образом при том же среднем количестве мин оказывается менее
эффективным.
Кроме того, были подтверждены изначальные гипотезы о том, что
интуитивно «минирование» приведет к следующему: вероятность
нахождения наилучшего элемента по сравнению с классическим случаем
58
уменьшится, а оптимальная стратегия просмотра станет более «осторожной»
и область просмотра сузится.
Интересным направлением дальнейших исследований будет
рассмотрение кооперативных и некооперативных игровых задач поиска
наилучшего элемента в «заминированной» среде.
1, Дынкин Е.Б., Юшкевич А.А. Теоремы и задачи о процессах Маркова. — М.: Наука,
1967. — С. 91–102.
2, Гусейн-Заде С.М. Задача выбора и оптимальное правило остановки
последовательности независимых испытаний. Теория вероятностей и ее приложения.
— 1966. — 11 (3). — С. 534–537.
3, Доценко С. Задача выбора наилучшего объекта как игра двух лиц // Кибернетика и
вычисл. техника. — 2011. — Вып. 164.— С. 43–53.
Киевский национальный университет
имени Тараса Шевченко Получено 01.11.2012
|
| id | nasplib_isofts_kiev_ua-123456789-45880 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0452-9910 |
| language | Russian |
| last_indexed | 2025-12-07T13:32:28Z |
| publishDate | 2012 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України |
| record_format | dspace |
| spelling | Доценко, С.И. Закусило, О.К. 2013-06-19T20:38:41Z 2013-06-19T20:38:41Z 2012 Задача оптимального выбора с «заминированными» объектами / С.И. Доценко, О.К. Закусило // Кибернетика и вычисл. техника. — 2012. — Вип. 170. — С. 51-58. — Бібліогр.: 3 назв. — рос. 0452-9910 https://nasplib.isofts.kiev.ua/handle/123456789/45880 681.5 Рассмотрена задача оптимального выбора при условии, что некоторые объекты, выбираемые по случайному закону, являются заминированными. Просмотр заминированного объекта приводит к принудительной остановке процесса просмотра. Установлено, что в рассматриваемом случае, оптимальная стратегия имеет пороговый вид. Выведено уравнение, корень которого является искомой величиной порога. Найдены оптимальные стратегии при разных способах и параметрах минирования. Розглянуто задачу оптимального вибору за умови, що деякі об’єкти, що вибираються за випадковим законом, можуть бути заміновані. Проглядання замінованого об’єкту призводить до примусової зупинки процесу проглядання. Встановлено, що у випадку, що розглядається, оптимальна стратегія має порогів вигляд. Отримано рівняння, корінь якого є шуканою величиною порогу. Знайдено оптимальні стратегії при різних способах та параметрах мінування. For the optimal choice problem with mined objects it was shown that the support set for the stopping moment has the same structure as for the classical case. However, the threshold value is lower (i.e. stipulated by “mine threat” phenomena. For the ways of mining the threshold values are calculated and numerical results are delivered. ru Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України Кибернетика и вычислительная техника Сложные системы управления Задача оптимального выбора с «заминированными» объектами Задача оптимального вибору з «замінованими» об'єктами Game situations in the modified secretary problem with «mined» objects Article published earlier |
| spellingShingle | Задача оптимального выбора с «заминированными» объектами Доценко, С.И. Закусило, О.К. Сложные системы управления |
| title | Задача оптимального выбора с «заминированными» объектами |
| title_alt | Задача оптимального вибору з «замінованими» об'єктами Game situations in the modified secretary problem with «mined» objects |
| title_full | Задача оптимального выбора с «заминированными» объектами |
| title_fullStr | Задача оптимального выбора с «заминированными» объектами |
| title_full_unstemmed | Задача оптимального выбора с «заминированными» объектами |
| title_short | Задача оптимального выбора с «заминированными» объектами |
| title_sort | задача оптимального выбора с «заминированными» объектами |
| topic | Сложные системы управления |
| topic_facet | Сложные системы управления |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45880 |
| work_keys_str_mv | AT docenkosi zadačaoptimalʹnogovyboraszaminirovannymiobʺektami AT zakusilook zadačaoptimalʹnogovyboraszaminirovannymiobʺektami AT docenkosi zadačaoptimalʹnogoviboruzzamínovanimiobêktami AT zakusilook zadačaoptimalʹnogoviboruzzamínovanimiobêktami AT docenkosi gamesituationsinthemodifiedsecretaryproblemwithminedobjects AT zakusilook gamesituationsinthemodifiedsecretaryproblemwithminedobjects |