Об одной задаче неограниченного комбинаторного распознавания

Рассматривается задача, которая относится к неограниченным комбинаторным задачам распознавания. С помощью минимального количества тестов на радиацию произвольной выборки из множества шаров необходимо обнаружить два радиоактивных. Доказывается ряд утверждений, необходимых для построения оптимально...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2013
Hauptverfasser:	Билецкий, В.И., Донец, Г.А., Ненахов, Э.И.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2013
Schriftenreihe:	Теорія оптимальних рішень
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/85047
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Об одной задаче неограниченного комбинаторного распознавания / В.И. Билецкий, Г.А. Донец, Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 88-94. — Бібліогр.: 2 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-85047
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-850472025-02-09T13:44:33Z Об одной задаче неограниченного комбинаторного распознавания Про одну задачу необмеженого комбінаторного розпізнавання One problems of unlimited combinatorial recognition Билецкий, В.И. Донец, Г.А. Ненахов, Э.И. Рассматривается задача, которая относится к неограниченным комбинаторным задачам распознавания. С помощью минимального количества тестов на радиацию произвольной выборки из множества шаров необходимо обнаружить два радиоактивных. Доказывается ряд утверждений, необходимых для построения оптимальной стратегии. Приводятся решения задачи для 15 и 22 шаров. Розглядується одна задача, що відноситься до необмежених комбінаторних задач розпізнавання. За допомогою мінімальної кількості тестів на радіацію довільної вибірки із множини кульок необхідно знайти дві радіоактивних. Доводиться ряд тверджень, які потрібні для побудови оптимальної стратегії. Приводиться розв’язок задачі для 15 і 22 кульок. The problem, concerping unlimited combinatorial problems of recognition, is analyzed. With the help of minimal amount of tests it is necessary to detect 2 radioactive balls from a set of balls. A number of assertions is proved, necessary to construct an optimal strategy. The problem solutions are provided in the cases of 15 and 22 balls. 2013 Article Об одной задаче неограниченного комбинаторного распознавания / В.И. Билецкий, Г.А. Донец, Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 88-94. — Бібліогр.: 2 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/85047 519.8 ru Теорія оптимальних рішень application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Рассматривается задача, которая относится к неограниченным комбинаторным задачам распознавания. С помощью минимального количества тестов на радиацию произвольной выборки из множества шаров необходимо обнаружить два радиоактивных. Доказывается ряд утверждений, необходимых для построения оптимальной стратегии. Приводятся решения задачи для 15 и 22 шаров.
format	Article
author	Билецкий, В.И. Донец, Г.А. Ненахов, Э.И.
spellingShingle	Билецкий, В.И. Донец, Г.А. Ненахов, Э.И. Об одной задаче неограниченного комбинаторного распознавания Теорія оптимальних рішень
author_facet	Билецкий, В.И. Донец, Г.А. Ненахов, Э.И.
author_sort	Билецкий, В.И.
title	Об одной задаче неограниченного комбинаторного распознавания
title_short	Об одной задаче неограниченного комбинаторного распознавания
title_full	Об одной задаче неограниченного комбинаторного распознавания
title_fullStr	Об одной задаче неограниченного комбинаторного распознавания
title_full_unstemmed	Об одной задаче неограниченного комбинаторного распознавания
title_sort	об одной задаче неограниченного комбинаторного распознавания
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2013
url	https://nasplib.isofts.kiev.ua/handle/123456789/85047
citation_txt	Об одной задаче неограниченного комбинаторного распознавания / В.И. Билецкий, Г.А. Донец, Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 88-94. — Бібліогр.: 2 назв. — рос.
series	Теорія оптимальних рішень
work_keys_str_mv	AT bileckijvi obodnojzadačeneograničennogokombinatornogoraspoznavaniâ AT donecga obodnojzadačeneograničennogokombinatornogoraspoznavaniâ AT nenahovéi obodnojzadačeneograničennogokombinatornogoraspoznavaniâ AT bileckijvi proodnuzadačuneobmeženogokombínatornogorozpíznavannâ AT donecga proodnuzadačuneobmeženogokombínatornogorozpíznavannâ AT nenahovéi proodnuzadačuneobmeženogokombínatornogorozpíznavannâ AT bileckijvi oneproblemsofunlimitedcombinatorialrecognition AT donecga oneproblemsofunlimitedcombinatorialrecognition AT nenahovéi oneproblemsofunlimitedcombinatorialrecognition
first_indexed	2025-11-26T11:38:59Z
last_indexed	2025-11-26T11:38:59Z
_version_	1849852838767755264
fulltext	88 Теорія оптимальних рішень. 2013 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ Рассматривается задача, ко- торая относится к неограничен- ным комбинаторным задачам распознавания. С помощью мини- мального количества тестов на радиацию произвольной выборки из множества шаров необходимо обнаружить два радиоактивных. Доказывается ряд утверджений, необходимых для построения оп- тимальной стратегии. Приво- дятся решения задачи для 15 и 22 шаров.  В.И. Билецкий, Г.А. Донец, Э.И. Ненахов, 2013 ÓÄÊ 519.8 Â.È. ÁÈËÅÖÊÈÉ, Ã.À. ÄÎÍÅÖ, Ý.È. ÍÅÍÀÕÎÂ ÎÁ ÎÄÍÎÉ ÇÀÄÀ×Å ÍÅÎÃÐÀÍÈ×ÅÍÍÎÃÎ ÊÎÌÁÈÍÀÒÎÐÍÎÃÎ ÐÀÑÏÎÇÍÀÂÀÍÈß В теории комбинаторного распознавания рас- сматриваются алгоритмы решения задач распо- знавания свойств отдельных предметов из все- го их множества с помощью тестов, или експе- риментов, которые можна трактовать доста- точно широко. Эти задачи делятся на два типа. К первому типу относятся задачи, где ос- новной операцией есть подсчет и построение конкретных комбинаторных конфигураций на множестве заданных чисел. Такие задачи возникают в разного рода лотереях, банковс- кой сфере, страховых компаниях и относятся к классу ограниченных задач комбинаторно- го распознавания. В работе [1] приводится одна из таких задач и описывается стратегия нахождения оптимального решения, которая заключается в разбиении исходного множе- ства из n элементов на группы из m (m ≤ n) элементов таким образом, чтобы потом, проделав эксперименты с помощью k-выборок (k ≤ m) в каждой из них, найти необходимое количество определенных элементов. К другому типу задач относятся задачи, где нужно из множества однородных предметов определить с помощью каких-то средств (из- мерительных приборов, химических реакти- вов и т. д.) отдельные специфические предме- ты. Такая проблема может возникнуть на та- можне, контрольно-пропускных пунктах раз- ных предприятий, в социальной сфере. В отличие от задач, рассмотренных в [1], такие задачи, которые широко встречаются на прак- тике, условно можно назвать неограничен- ными задачами комбинаторного распознава- ния. Приведем их формальную постановку. ОБ ОДНОЙ ЗАДАЧЕ НЕОГРАНИЧЕННОГО КОМБИНАТОРНОГО РАСПОЗНАВАНИЯ Теорія оптимальних рішень. 2013 89 Задача комбинаторного распознавания (неограниченная). Пусть задано множество из n чисел X = {x1, x2, …, xn}, которое состоит из m единиц и n – m нулей. Эксперимент заключается в выборе произвольного количества k (k ≤ m) чисел, после чего становится известным ихнее произведение. Необходимо за минимальное количество проб найти все числа, которые равны 0 (или, что то же самое, равны 1). Приведем пример одной такой практической задачи. Задача о радиоактивных элементах. Пусть через таможню проходит не- который груз из n элементов (предметов). Известно, что k из них (k < n) радиоа- ктивные. Для проверки на радиоактивность можно выбирать произвольное количество элементов. В результате эксперимента получаем ответ всего лишь на вопрос, есть ли в данном количестве элементов радиоактивный. Необходимо за минимальное число проверок найти все радиоактивные элементы. Очевидно, что эту задачу легко решить за n проверок, выбирая каждый раз по одному элементу (предмету). Но так как каждая проверка связана с опреде- ленными материальными расходами, то такое решение будет наихудшим. Это особенно относится к транспортным перевозкам, где проверка проводится в больших по размеру специально оборудованных помещениях. Доставка к ним всего груза по одному элементу (предмету) связана с большими расходами энергоресурсов, сложным маневрированием средств доставки (локомотивов, тягачей, буксиров) и, самое главное, потерей времени. Рассмотрим более конкретную задачу. Пусть задано n бильярдных шаров, среди которых два шара радиоактивные. Необходимо их обнаружить за мини- мальное число проверок. Очевидно, что данная задача может возникнуть в различных практических направлениях. И в тех ситуациях, где каждая проверка связана с существенными материальными потерями, такая задача является важной и актуальной. Методы решения задачи. Сформулируем общие принципы, применяемые при решении подобных задач. 1. Если из 2s шаров радиоактивный (далее активный) один, то его можно найти за s проверок (испытаний): первым шагом проверить половину шаров, затем методом дихотомии проверить то множество шаров, где находится актив- ный шар. 2. Если шаров больше, чем 2 ,s то за s шагов нельзя обеспечить отыскание одного активного шара. Предположим противное. Сделаем s испытаний, отме- чая наличие радиоактивности плюсом, а ее отсутствие – минусом. По предпо- ложению, зная возникшую последовательность знаков, мы можем указать, какой из шаров активный. Но разных последовательностей длины s из двух знаков существует всего 2 .s Указав по каждой из них активный шар, получим нелогич- ный вывод о том, что те шары, которым не соответствует никакая последова- тельность знаков, не могут быть активными. В.И. БИЛЕЦКИЙ, Г.А. ДОНЕЦ, Э.И. НЕНАХОВ 90 Теорія оптимальних рішень. 2013 3. Если из n шаров активных 2, то имеется 2 ( 1) 2 n n n C − = вариантов различ- ных активных пар. Поэтому, если ( 1) 2 2 sn n − > , то за s испытаний не удастся найти активную пару. 4. Если из n шаров мы первым шагом испытываем k шаров, то исход ис- пытания «–» соответствует 2 n kC − вариантам (оба активных шара находятся среди n k− оставшихся), а исход «+» – остальным 2 2 n n kC C −− вариантам. Если в распо- ряжении осталось только i испытаний, то обязательно должно быть 2 2i n kC − ≤ и i knn CC 2 22 ≤− − . 5. Если за s проверок удалось решить задачу для n шаров, то для меньшего количества шаров можно решить задачу также за s проверок. Это вытекает из тех соображений, что тот же результат можно достичь, если дополнить множе- ство шаров до n фиктивными (неактивными) шарами. Это означает, что для двух одинаковых значений s и разных значений n для всех промежуточных значений количества шаров задача решается за те же s проверок. При решении задачи будем строить стратегию последовательных испыта- ний. Если очередная проверка (выбор количества и индивидуальных шаров) не зависит от предыдущей проверки, назовем такую стратегию независимой. Если же определение количества шаров и их индивидуальность зависит от исхода предыдущей проверки, то назовем такую стратегию пошаговой. Для независимой стратегии является определяющим построение разбиения n шаров на m частей 1 2( , , ... , )n mR k k k= , где i k – количество шаров, испыты- ваемых на i -м шаге (1 ),i m≤ ≤ и nk m i i =∑ =1 . После m испытаний, в зависимости от знаков, задача сводится либо к получению одного множества (с меньшим количеством), содержащего оба активных шара, либо к двум множествам, со- держащим по одному активному шару. Введем обозначения трех функций, которые пригодятся для дальнейших поисков решения задачи: 2 ( )f n – минимальное число проверок для обнаружения двух активных шаров из n заданных; 1( )f n – минимальное число проверок для обнаружения одного активного шара из n заданных; ( )1 2,g n n – минимальное число проверок для обнаружения двух активных шаров, которые находятся по одному в двух подмножествах из 1n и соответственно 2n шаров. ОБ ОДНОЙ ЗАДАЧЕ НЕОГРАНИЧЕННОГО КОМБИНАТОРНОГО РАСПОЗНАВАНИЯ Теорія оптимальних рішень. 2013 91 Из принципа 2 вытекает очевидное равенство 1 2( ) logf n n=    . Однако, как будет показано далее, ( ) ( ) ( )211121 , nfnfnng +≤ , причем возможно и строгое неравенство. В работе [2] доказано ряд утверждений, которые необходимы для построения оптимальных независимых стратегий. Лемма 1. При независимой стратегии решения задачи ( )2 2( ) max , (1 ).i i f n m f k i m≤ + ≤ ≤ Это следует из того, что после m проверок знак «+» получит группа с мак- симальным значением ik , а остальные получат знак «–». Лемма 2. ( ) 1 2 1, 2 1 1 ( 3).k l g k l k l kl   + + = + + + + ≥   Составим таблицу таких пар для , 5,k l ≤ которая пригодится в дальнейшем. ТАБЛИЦА 1 2,n n 3,5 3,9 3,1 7 3,3 3 5,5 5,9 5,1 7 5,3 3 9,9 9,1 7 9,3 3 17,1 7 17,3 3 33,3 3 1 2( , )g n n 4 5 6 7 5 6 7 8 7 8 9 9 10 11 Следствие. ( ) ( ) ( )2 2 1 , 2 2 1 1 , 0; 3k l g k l k l α β + + = α + β + + + α β ≥ + ≥  . Это легко проверить, так как путем деления α раз первой группы и β раз второй группы придем к условию леммы 3. Это дает возможность свести аргу- менты функции ( )1 2,g n n к нечетным значениям. Лемма 3. ( ) ( ) 2 2 3, 2 1 1, , 2 .k l g k l k l k   + + = + + + ≥   Лемма 4. ( ) ( ) 3 2 5, 2 1 1, 3, 2 .k l g k l k l k   + + = + + + ≥ ≥   Теорема 1. ( ) ( )2 2 2 3 .s f s s= ≥ Лемма 5. ( )2 15 7.f = Там же доказано, что ( ) ( ) ( ) ( ) ( ) ( )2 2 2 2 2 29 10 6; 11 12 13 14 7.f f f f f f= = = = = = Здесь будет доказана Теорема 2. f2(22) = 8. Доказательство проводится путем пошаговой стратегии. Для первой про- верки берем 7 шаров. Если первая проверка «–», то 1+f2(11) = 8, и задача реше- на. Если первая проверка «+», то нужно доказать, что h(7, 15) = 7. Здесь и далее функция h(n1, n2) – минимальное число проверок для обнаружения двух актив- ных шаров в случае, когда один или оба располагаются в подмножестве n1. В.И. БИЛЕЦКИЙ, Г.А. ДОНЕЦ, Э.И. НЕНАХОВ 92 Теорія оптимальних рішень. 2013 Можно показать, что в сложившейся ситуации к цели приводит только один вариант второй проверки: 3 шара из 7-ми плюс один шар из 15-ти. Если вторая проверка «–», то сравнительно просто можно показать, что h(4, 14) = 6. В самом деле, теперь для 3-ей проверки берем 8 шаров из 14-ти, и если «+», то очевидно, что g(4, 8)=5, если третья проверка «–», то нужно доказать, что h(4, 6)=5. Для четвертой проверки берем 4 шара из 6-ти. Если «+», то очевидно, что g(4, 4)=4, иначе h(4, 2)=4. Последнее верно, так как для пятой проверки остается взять последние 2 шара, и, если «+», то g(4, 2)=3, а если «–», то f2(4)=3. Теперь следует вернуться ко второй проверке и предположить, что она дает, как и первая, положительный результат. Для дальнейших рассуждений перенумеруем шары числами: 1, 2, …, 22. Пусть первая проверка шаров 16, 17, 18, 19, 20, 21, 22 дает положительный результат. Точно также дает положительный результат вторая проверка шаров 20, 21, 22, 15. Теперь для третьей проверки берем шары 1, 2, 3, 4, 5, 6, 7, 8, 16, 17. В случае положительного результата для четвертой проверки берем шары 1, 2, 3, 4, 16. В случае же отрицательного результата третьей проверки для четвер- той проверки берем шары 9, 10, 11, 12, 18. В зависимости от результатов третьей и четвертой проверок возможен один из четырех вариантов, первые три из которых идентичны с точностью до нуме- рации шаров. (+, +, +, +). Пятая проверка – шары 16, 20. Если «–», то один активный среди 1, 2, 3, 4, а второй – 21 или 22. Если пятая проверка «+», то шестая проверка – шар 16. Если «+», то один шар – 16, а второй среди 15, 20, 21, 22. Если шестая проверка «–», то один шар – 20, а другой – среди 1, 2, 3, 4. (+, +, +, –). Пятая проверка – шары 17, 20. Если «–», то один активный среди 5, 6, 7, 8, а второй – 21 или 22. Если пятая проверка «+», то шестая проверка – шар 17. Если «+», то один шар – 17, а второй среди 15, 20, 21, 22. Если шестая проверка «–», то один шар – 20, а другой – среди 5, 6, 7, 8. (+, +, –, +). Пятая проверка – шары 18, 20. Если «–», то один активный среди 9, 10, 11, 12, а второй – 21 или 22. Если пятая проверка «+», то шестая проверка – шар 18. Если «+», то один шар – 18, а второй среди 15, 20, 21, 22. Если шестая проверка «–», то один шар – 20, а другой – среди 9, 10, 11, 12. В любом из этих трех случаев задача решается либо нахождением одного шара из двух на шестой проверке, либо одного шара из четырех на седьмой и восьмой проверках при условии отрицательного результата пятой проверки. Если же пятая проверка дает положительный результат, то шестая проверка определяет один из актив- ных шаров, а седьмая и восьмая уходят на поиск второго шара среди четырех. Остается рассмотреть случай, когда третья и четвертая проверки дают отрица- тельный результат (+, +, –, –). Сложившуюся ситуацию удобно изобразить с помощью графа. Вершины гра- фа – номера шаров. Ребра графа – возможные пары активных шаров (рисунок). ОБ ОДНОЙ ЗАДАЧЕ НЕОГРАНИЧЕННОГО КОМБИНАТОРНОГО РАСПОЗНАВАНИЯ Теорія оптимальних рішень. 2013 93 Далее покажем, как из 6-ти вариантов выбирается один за четыре проверки (5-я, 6-я, 7-я и 8-я). В любом случае после пятой проверки из 16-ти подозреваемых пар должно остаться 8. После 6- ой из 8-ми – 4. После 7-ой из 4-х – 2. Восьмая проверка должна определить одну из двух пар, которая и будет решением задачи. Из анализа графа видно, что для пятой проверки есть шесть вариантов выбора шаров: 13 и 20, 13 и 21, 13 и 22, 14 и 20, 14 и 21, 14 и 22. Пусть пятая проверка – шары 13 и 20. а б в РИСУНОК Как при «–», так и при «+» для дальнейшего рассмотрения остается под- граф, содержащий по 8 ребер. Теперь несложно спланировать оставшиеся три проверки для выделения одного из 16-ти вариантов. Так при получении «–» в результате первой проверки выбираем для шестой проверки шар 22 (можно было бы 21). При получении «+» в результате пятой проверки для шестой выби- раем шары 13 и 14 (можно было бы 13 и 15 или 13 и 19, или 21 и 22). Здесь возможны варианты. Рассмотрены все возможные варианты, и тем самым доказано, что f2(22)=8. Однако уместно сделать следующее замечание. После получения положитель- ного результата при первой проверке 7-ми шаров число подозреваемых пар Ch(7, 15)=C 2 7 +7·15=21+105=126. Если для второй проверки выбрать 9 шаров из 15-ти, то Сg(7, 9)=7·9=63 и Ch(7, 6)=C 2 7 +7· 6=21+42=63. 21 13 20 14 22 15 19 21 13 20 14 22 15 19 21 13 20 14 22 15 19 В.И. БИЛЕЦКИЙ, Г.А. ДОНЕЦ, Э.И. НЕНАХОВ 94 Теорія оптимальних рішень. 2013 Казалось бы, деление подозреваемых пар ровно пополам – залог успеха. Между тем, h(7, 6) > 6, так как невозможно выделить группу шаров для текущей третьей проверки, которая разобьет число подозреваемых пар на 63=31+32. Для того чтобы это стало очевидным, достаточно мысленно представить сложившуюся ситуацию с помощью графа с тринадцатью вершинами и шести- десятью ребрами. Таким образом, единственно перспективным вариантом выбора шаров для второй проверки, в случае положительного результата первой, является предло- женный здесь подход. Хотя в данном случае при отрицательном результате остается 62 варианта, а в случае положительного – 64. Этим и объясняется сложность и громоздскость доказательства теоремы. Хотя, по всей видимости, не существует более простого доказательства. В.І. Білецький, Г.П. Донець, Е.І. Ненахов ПРО ОДНУ ЗАДАЧУ НЕОБМЕЖЕНОГО КОМБІНАТОРНОГО РОЗПІЗНАВАННЯ Розглядується одна задача, що відноситься до необмежених комбінаторних задач розпізна- вання. За допомогою мінімальної кількості тестів на радіацію довільної вибірки із множини кульок необхідно знайти дві радіоактивних. Доводиться ряд тверджень, які потрібні для побудови оптимальної стратегії. Приводиться розв’язок задачі для 15 і 22 кульок. V.I. Biletsky, G.A. Donets, E.I. Nenakhov ONE PROBLEMS OF UNLIMITED COMBINATORIAL RECOGNITION The problem, concerping unlimited combinatorial problems of recognition, is analyzed. With the help of minimal amount of tests it is necessary to detect 2 radioactive balls from a set of balls. A number of assertions is proved, necessary to construct an optimal strategy. The problem solutions are provided in the cases of 15 and 22 balls. 1. Білецький В.І., Донець Г.П., Ненахов Е.І. Комбінаторне розпізнавання. Задачі та їх розв’язування // Теорія оптимальних рішень. – 2012. – С. 21–29. 2. Донец Г.А., Кузнецов С.Т. Об одной комбинаторной задаче логического типа // Там само. – 2012. – С. 101–108. Получено 02.04.2013

Об одной задаче неограниченного комбинаторного распознавания

Institution

Ähnliche Einträge