Деякі результати пошуку трьох та чотирьох активних куль на множині заданих

Розглядаються задачі пошуку трьох та чотирьох активних куль на множині заданих. Описуються деякі результати знаходження активних куль за мінімальну кількість випробовувань на основі стратегії послідовних ціленаправлених покрокових дій....

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2017
Hauptverfasser:	Донець, Г.П., Білецький, В.І., Ненахов, Е.І.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2017
Schriftenreihe:	Теорія оптимальних рішень
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/131448
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:	Деякі результати пошуку трьох та чотирьох активних куль на множині заданих / Г.П. Донець, В.І. Білецький, Е.І. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2017. — № 2017. — С. 133-138. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-131448
record_format	dspace
spelling	irk-123456789-1314482018-03-24T03:03:16Z Деякі результати пошуку трьох та чотирьох активних куль на множині заданих Донець, Г.П. Білецький, В.І. Ненахов, Е.І. Розглядаються задачі пошуку трьох та чотирьох активних куль на множині заданих. Описуються деякі результати знаходження активних куль за мінімальну кількість випробовувань на основі стратегії послідовних ціленаправлених покрокових дій. Рассматриваются задачи поиска трех и четырех активных шаров на множестве заданных. Описываются некоторые результаты нахождения активных шаров за минимальное количество испытаний на основании стратегии последовательных целенаправленых пошаговых действий. Problems of searching three or four active balls among a set of similar ones are considered. Some results of finding active balls in minimal number of trials based on the strategy of consequent purposeful steps are described. 2017 Article Деякі результати пошуку трьох та чотирьох активних куль на множині заданих / Г.П. Донець, В.І. Білецький, Е.І. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2017. — № 2017. — С. 133-138. — укр. 2616-5619 http://dspace.nbuv.gov.ua/handle/123456789/131448 519.8 uk Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
description	Розглядаються задачі пошуку трьох та чотирьох активних куль на множині заданих. Описуються деякі результати знаходження активних куль за мінімальну кількість випробовувань на основі стратегії послідовних ціленаправлених покрокових дій.
format	Article
author	Донець, Г.П. Білецький, В.І. Ненахов, Е.І.
spellingShingle	Донець, Г.П. Білецький, В.І. Ненахов, Е.І. Деякі результати пошуку трьох та чотирьох активних куль на множині заданих Теорія оптимальних рішень
author_facet	Донець, Г.П. Білецький, В.І. Ненахов, Е.І.
author_sort	Донець, Г.П.
title	Деякі результати пошуку трьох та чотирьох активних куль на множині заданих
title_short	Деякі результати пошуку трьох та чотирьох активних куль на множині заданих
title_full	Деякі результати пошуку трьох та чотирьох активних куль на множині заданих
title_fullStr	Деякі результати пошуку трьох та чотирьох активних куль на множині заданих
title_full_unstemmed	Деякі результати пошуку трьох та чотирьох активних куль на множині заданих
title_sort	деякі результати пошуку трьох та чотирьох активних куль на множині заданих
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2017
url	http://dspace.nbuv.gov.ua/handle/123456789/131448
citation_txt	Деякі результати пошуку трьох та чотирьох активних куль на множині заданих / Г.П. Донець, В.І. Білецький, Е.І. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2017. — № 2017. — С. 133-138. — укр.
series	Теорія оптимальних рішень
work_keys_str_mv	AT donecʹgp deâkírezulʹtatipošukutrʹohtačotirʹohaktivnihkulʹnamnožinízadanih AT bílecʹkijví deâkírezulʹtatipošukutrʹohtačotirʹohaktivnihkulʹnamnožinízadanih AT nenahoveí deâkírezulʹtatipošukutrʹohtačotirʹohaktivnihkulʹnamnožinízadanih
first_indexed	2025-07-09T15:27:53Z
last_indexed	2025-07-09T15:27:53Z
_version_	1837183664852566016
fulltext	Теорія оптимальних рішень. 2017 133 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Розглядаються задачі пошуку трьох та чотирьох активних куль на множині заданих. Опису- ються деякі результати знахо- дження активних куль за мініма- льну кількість випробовувань на основі стратегії послідовних ці- ленаправлених покрокових дій.  Г.П. Донець, В.І. Білецький, Е.І. Ненахов, 2017 УДК 519.8 Г.П. ДОНЕЦЬ, В.І. БІЛЕЦЬКИЙ, Е.І. НЕНАХОВ ДЕЯКІ РЕЗУЛЬТАТИ ПОШУКУ ТРЬОХ ТА ЧОТИРЬОХ АКТИВНИХ КУЛЬ НА МНОЖИНІ ЗАДАНИХ Вступ. Задача пошуку трьох та чотирьох активних куль значно складніша від задачі пошуку двох активних куль, але для свого розв’язання вона повністю використовує досягнення останньої. За аналогією з нею введемо наступні позначення: f3(n), f4(n) – мінімальна кількість спроб для виявлення від- повідно трьох і чотирьох активних куль серед n заданих; 3 4( , ), ( , )h k n k h k n k   – мініма- льна кількість спроб для виявлення відповід- но трьох і чотирьох активних куль серед n заданих після того, як перевірка k куль дала позитивний результат. Якщо з n куль активні три, то є  3 1 ( 2) 6 n n n n C    варіантів різних актив- них трійок. Тому, якщо  1 ( 2) 2 , 6 sn n n   то за s випробувань не вдасться знайти активну трійку. Якщо з n куль на першому кроці випро- бовуємо k куль, то результат випробування «–» відповідає 3 knC  варіантів (три активні кулі перебувають серед ,n k що залиши- лися), а результат «+» – іншим 33 knn CC  варіантам.  Билецкий В.И., Ненахов Э.И. Алгоритмы поиска двух активных шаров на заданных множествах. Тео- рія оптимальних рішень. 2016. С. 78 – 86. Г.П. ДОНЕЦЬ, В.І. БІЛЕЦЬКИЙ, Е.І. НЕНАХОВ 134 Теорія оптимальних рішень. 2017 Якщо в розпорядженні залишилося тільки i випробувань, то обов’язково має бути i knC 23  і i knn CC 233   . Для обчислення функцій f3(n) та f4(n) використовуються деякі результати обчислень функції   * 2f n , а кращою стратегією є індуктивний метод, коли зага- льна задача з даною кількістю активних куль зводиться до задачі з меншою кіль- кістю активних куль. 1. Обчислення функції 3( ).f n Для 4 ≤ n ≤ 9 безпосередньо переконуємося, що f3(n) = n –1. Очевидно, що 3(2 , )h k = 1 + 2( 1).f k  Приведемо деякі результати оптимальних обчислень фу- нкції 3( )f n для значень n > 9. Нехай n = 10. Покажемо, що  103f = 8. На першому кроці випробовуємо дві кулі < 2 > . Якщо отримаємо результат «–», то тоді маємо f3(8) = 7, а якщо результат випробовування буде «+», то тоді отримаємо 3(2 , 8)h  = 1 + f2(9) = 7. В обох випадках отримаємо f3(10) = 8. Для 11 куль уже недостатньо 8 випробувань, але легко довести, що f3(11) = 9. Для цього беремо одну кулю. Якщо отримаємо результат випробову- вання «–», то тоді f3(10) = 8, а якщо результат буде «+», то тоді * f2(10) = 6. Сумуючи обидва випадки, маємо f3(11) = 9. Виявляється, що також f3(12) = f3(13) = 9. Досить легко показати, що три активні кулі з 12-и можна знайти за 9 випро- бовувань, тобто довести, що f3(12) = 9. Для цього на першому кроці візьмемо дві кулі. Якщо отримаємо результат «–», то f3(10) = 8, а якщо буде «+», то спра- ведлива рівність 3(2 , 10)h  = 1 + f2(11) = 1 + 7 = 8. В підсумку отримаємо рівність f3(12) = 9. Покажемо, що три активні кулі з 13-и можна знайти за 9 випробовувань. Для цього на першому кроці для перевірки беремо три кулі. Якщо отримаємо результат «–», то тоді f3(10) = 8, і в сумі отримаємо 9 випробовувань. Якщо на першому кроці отримаємо результат «+», то приходимо до функції 3(3 , 10)h  . Доведемо, що 3(3 , 10)h  = 8. Для цього на другому кроці беремо наступні чотири кулі. Якщо результат перевірки буде «+», то за третій та четвер- тий кроки серед них знайдемо одну активну кулю, що приведе до функції 2(3 , 9).h  Це означає, що за наступні п’ять кроків ( 2(3 , 9)h  = 5 ) знайдемо ще дві активні кулі. Якщо на другому кроці отримаємо результат «–», то тоді приходимо до фун- кції 3(3 , 6).h  У цьому випадку на третьому кроці беремо для перевірки дві кулі з шести. Якщо отримаємо результат «+», то тоді на четвертому кроці знайдемо серед них одну активну і, таким чином, прийдемо до функції 2(3 , 5),h  а 2(3 , 5)h  = 5. ДЕЯКІ РЕЗУЛЬТАТИ ПОШУКУ ТРЬОХ ТА ЧОТИРЬОХ АКТИВНИХ КУЛЬ … Теорія оптимальних рішень. 2017 135 Якщо результат перевірки двох куль із шести «–», то приходимо до функції 3(3 , 4),h  яку можна прирівняти до функції f3(7), що, як відомо, f3(7) = 6. В усіх розглянутих випадках отримаємо, що f3(13) = 9. Для 14 куль 9 випробувань уже не достатньо. Доведемо, що f3(14) = 10. Для цього беремо для перевірки одну кулю. Якщо отримаємо результат перевірки «–», то тоді f3(13) = 9, а якщо результат буде «+», то тоді дві активні кулі серед 13-и легко знаходяться за f2(13) = 7 випробовувань. У обох випадках отримаємо результат f3(14) = 10. Виявляється, що також f3(15) = f3(16) = 10. Доведемо це для n = 16. Для 16 куль на першому кроці для перевірки беремо три кулі. Якщо отримаємо результат «–», то f3(13) = 9, а якщо результат буде «+», то тоді на другому кроці беремо наступні чотири кулі. Якщо результат буде «+», то за третій та четвертий кроки знаходимо серед них одну активну, що при- веде до функції 2(3 , 12),h  а, як відомо, 2(3 , 12) 6.h   Якщо результат другого кроку буде «–», то тоді приходимо до функції 3(3 , 9),h  яка покривається функцією 3(3 , 10)h  і, як було показано раніше, 3(3 , 10) 8.h   В усіх варіантах отримуємо, що f3(16) = 10. Покажемо, що f3(17) = f3(18) = f3(19) = f3(20) = 11. Для 17 куль 10 випробувань уже недостатньо. Легко довести, що для 17-и куль f3(17) = 11. Для цього беремо одну кулю. Якщо отримаємо результат «–», то тоді f3(16) = 10, а якщо результат буде «+», то тоді дві активні кулі з 16 отримаємо за f2(16) = 8 випробовувань. В обох випадках у сумі отримаємо, що f3(17) = 11. Досить легко отримати число випробовувань для знаходження трьох актив- них куль серед 18-и та показати, що f3(18) =11. Для цього на першому кроці для перевірки візьмемо дві кулі. Якщо отримаємо результат перевірки «–», то тоді три активні кулі знайдемо за f3(16) = 10 випробовувань, а якщо отримаємо ре- зультат «+», то справедливе співвідношення 3(2 , 16) 1h   + f2(17) = 9. У підсу- мку отримаємо, що f3(18) = 11. Покажемо, що і серед 19-и куль три активні можна знайти за 11 випробову- вань, тобто, що f3(19) = 11. Для цього на першому кроці беремо три кулі. Якщо отримаємо результат перевірки «–», то тоді f3(16) = 10, і в сумі отримаємо 11 перевірок. А якщо результат перевірки на першому кроці буде «+», то приходимо до функції 3(3 , 16).h  Доведемо, що 3(3 , 16)h  = 10. Для цього на другому кроці бе- ремо наступні чотири кулі. Якщо отримаємо результат перевірки «+», то за тре- тій та четвертий кроки знаходимо серед них хоча б одну активну, що приводить до функції 2(3 , 15).h  Дві інші активні кулі отримаємо за 2(3 , 15) 9h   перевірок. В сумі отримаємо 11 перевірок. Якщо на другому кроці отримаємо результат «–», то тоді приходимо до функції 3(3 , 12).h  Далі поступаємо таким чином. На третьому кроці беремо для перевірки чотири кулі з 12-ти. Якщо отрима- ємо результат «+», то на четвертому та п’ятому кроках знаходимо одну з них Г.П. ДОНЕЦЬ, В.І. БІЛЕЦЬКИЙ, Е.І. НЕНАХОВ 136 Теорія оптимальних рішень. 2017 активну. Дві інші активні кулі отримаємо за 2(3 , 11) 6h   перевірок. В сумі отримаємо 11 перевірок. Якщо на третьому кроці отримаємо результат «–», то приходимо до функції 3(3 , 8),h  яка покривається функцією 3(3 , 10)h  і, як було показано раніше, 3(3 , 10) 8.h   В усіх розглянутих випадках отримаємо, що f3(19) = 11. Покажемо, що і серед 20-и куль три активні можна знайти за 11 випробову- вань, тобто, що f3(20) = 11. Для цього на першому кроці з 20-и беремо для випробовування чотири кулі. Якщо отримаємо результат перевірки «–», то три активні кулі можна отримати за f3(16) = 10 перевірок. Якщо результат перевірки чотирьох куль буде «+», то тоді на другому кроці беремо сім наступних куль. Якщо отримаємо результат перевірки «–», то три активні кулі можна отримати за f3(13) = 9 перевірок. Якщо результат перевірки семи куль буде «+», то за третій і четвертий кроки з чоти- рьох куль отримаємо одну активну і прийдемо до функції 2(7 , 12).h  І тоді дві інші активні кулі отримаємо за 2(7 , 12) 7h   перевірок. В сумі отримаємо 11 пе- ревірок, а це означає, що f3(20) = 11. Таким же чином можна встановити, що f3(20 + к) = 12 для 1 ≤ k ≤4. Це дося- гається наступним шляхом. На першому кроці перевіряємо k куль. Якщо отрима- ємо результат перевірки «–», то тоді f3(20) = 11, а якщо результат буде «+», то за другий і третій кроки отримаємо з k куль одну активну і з решти дві активні кулі отримаємо за f2(20 + k – 1) ≤ 9 кроків, що і приводить до шуканого результату. Легко показати, що f3(25) = 12. Для цього на першому кроці беремо п’ять куль. Якщо отримаємо результат перевірки «–», то тоді f3(20) = 11. А якщо результат перевірки буде «+», то на другому кроці беремо для перевірки вісім наступних куль. Якщо результат перевірки буде «+», то за третій, четвертий і п’ятий кроки знаходимо серед них одну активну кулю. Така ситуація приводить до функції 2(5 , 19).h  А це означає, що дві інші активні кулі можна знайти за 2(5 , 19) 7h   кроків. Якщо результат перевірки восьми куль буде «–», то тоді приходимо до фун- кції 3(5 , 12).h  У цьому випадку на третьому кроці беремо для перевірки одну кулю з п’яти. Якщо отримаємо результат «+», то дві активні кулі знайдемо за вісім кроків з решти 16-и. А якщо результат перевірки однієї кулі з п’яти буде «– », то за четвертий і п’ятий кроки знаходимо серед чотирьох одну активну, а дві інші активні кулі можна знайти серед 15-и (12 + 3) останніх за f2(15) = 7 випробовувань. А всього буде 12 перевірок. 2. Обчислення функції 4( ).f n Для чотирьох куль застосовуємо ті ж самі прийоми. Безпосередньо перекону- ємося, що f4(n ) = n – 1 для 5 ≤ n ≤ 12. Очевидно, що (за аналогією п. 1) 4(2 , ) 1h k  + 3( 1).f k  ДЕЯКІ РЕЗУЛЬТАТИ ПОШУКУ ТРЬОХ ТА ЧОТИРЬОХ АКТИВНИХ КУЛЬ … Теорія оптимальних рішень. 2017 137 Переконаємось, що для 13 куль f4(13) = 11. Для цього здійснюємо перше ви- пробування, взявши для перевірки дві кулі. Якщо результат перевірки отримаємо «–», то тоді залишається 11 куль, і f4(11) = 10. А якщо результат перевірки отримаємо «+», то тоді 4(2 , 11) 1h   + f3(12) = 10. В обох випадках маємо, що f4(13) = 11. Для 14 куль не вистачає 11 випробувань, а 12 достатньо. Це легко отримати, якщо для перевірки на першому кроці взяти одну кулю. Якщо отримаємо результат перевірки «–», то тоді f4(13) = 11, а якщо буде «+», то f3(13) = 9, що і потрібно. Для 15 куль також справедливо f4(15) = 12, що доводиться наступним шляхом. На першому кроці візьмемо для перевірки три кулі. Якщо результат пе- ревірки «–», то тоді h4(12) =11. І всього отримаємо 12 перевірок. Якщо результат перевірки трьох куль «+», то приходимо до функції 4(3 , 12).h  На другому кроці беремо дві наступні кулі з 12-и та перевіряємо їх. Якщо отримаємо результат «+», то на третьому кроці знаходимо серед них одну актив- ну, що приведе до функції 3(3 , 11),h  що після визначення другої активної кулі серед трьох приведе до функції f2(13), а це означає, що дві активні кулі серед 13-и можна визначити за f2(13) = 7 кроків. В сумі буде 12 кроків. Якщо результат перевірки двох куль буде «–», то прийдемо до функції 4(3 , 10).h  Знову повторюємо прийом з двома наступними кулями (назвемо його ескалацією), що завжди приводить до двох результатів. При позитивному результаті прийдемо до функції з пошуком активних куль на одиницю менше. При негативному результаті число активних куль, які потрібно знайти у подальшому, не зменшується, зменшується тільки на дві одиниці загальна кількість куль для подальшого пошуку. У нашому випадку при позитивному результаті приходимо до функції h3(3+, 9) ≤ h3(3+, 10) = 8, як було доведено раніше. При негативному результаті прийдемо до функції h4(3+, 8). Знову застосову- ємо прийом ескалації, внаслідок якого при негативному результаті приходимо до функції h4(3+, 6), яка обчислюється безпосередньо (h4(3+, 6) = 8), та функції h3(3+, 7) – при позитивному результаті, до якої знову застосовуємо прийом еска- лації. В разі позитивного результату приходимо до функції h2(3+, 6), для якої ві- домо, що h2(3+, 6) = 5, та функції h3(3+, 5) – при позитивному результаті, до якої знову застосовуємо прийом ескалації. Внаслідок застосування прийому отримаємо функції h3(3+, 3), яка обчислю- ється безпосередньо (h3(3+, 3) = 5), або функції h2(3+, 4), для якої відомо, що h2(3+, 4) = 4, чим і завершується доведення. Для 16 куль уже необхідно 13 випробувань, хоча кількість варіантів m = 4 16 1820,C  що значно менше, ніж 213. Далі при збільшенні кількості куль цей розрив ще збільшується. Вчасно застосовуючи прийом ескалації, можна отримати наступні результа- ти: f4(16) = f4(17) = f4(18) = 13. Г.П. ДОНЕЦЬ, В.І. БІЛЕЦЬКИЙ, Е.І. НЕНАХОВ 138 Теорія оптимальних рішень. 2017 Г.А. Донец, В.И. Билецкий, Э.И. Ненахов НЕКОТОРЫЕ РЕЗУЛЬТАТЫ ПОИСКА ТРЕХ И ЧЕТЫРЕХ АКТИВНЫХ ШАРОВ НА МНОЖЕСТВЕ ЗАДАННЫХ Рассматриваются задачи поиска трех и четырех активных шаров на множестве заданных. Описываются некоторые результаты нахождения активных шаров за минимальное коли- чество испытаний на основании стратегии последовательных целенаправленых пошаговых действий. G.P. Donets, V.I. Biletsky, E.I. Nenakhov SOME RESULTS OF SEARCHING THREE OR FOUR ACTIVE BALLS ON A GIVEN SET Problems of searching three or four active balls among a set of similar ones are considered. Some results of finding active balls in minimal number of trials based on the strategy of consequent purposeful steps are described. Одержано 08.04.2017

Деякі результати пошуку трьох та чотирьох активних куль на множині заданих

Institution

Ähnliche Einträge