Оптимальний пошук двох активних куль на множині n = 127
Розглядається задача пошуку двох активних куль на множині заданих для n = 127. Доводиться теорема, що розв’язок досягається за 13 кроків. Доведення базується на введені 2-х нових типів графів – Q-графа та N-графа....
Gespeichert in:
| Datum: | 2018 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2018
|
| Schriftenreihe: | Теорія оптимальних рішень |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/144969 |
| 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: | Оптимальний пошук двох активних куль на множині n = 127 / Г.П. Донець, В.І. Білецький, Е.І. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2018. — № 17. — С. 35-41. — Бібліогр.: 2 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-144969 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1449692019-01-13T01:23:33Z Оптимальний пошук двох активних куль на множині n = 127 Донець, Г.П. Білецький, В.І. Ненахов, Е.І. Розглядається задача пошуку двох активних куль на множині заданих для n = 127. Доводиться теорема, що розв’язок досягається за 13 кроків. Доведення базується на введені 2-х нових типів графів – Q-графа та N-графа. Рассматриваются задачи поиска двух активных шаров на множестве заданных для n = 127. Доказывается теорема, что решение достигается за 13 шагов. Доказательство базируется на введении 2-х новых типов графов – Q-графа и N-графа. The problem of search or for two active balls in the set of given ones for n=127 is considered. The theorem is proved, consisting in assertion that the task is achiked in 13 steps. The proof is based on the use of the introduced new types of graphs, namely the Q-graph and the N-graph. 2018 Article Оптимальний пошук двох активних куль на множині n = 127 / Г.П. Донець, В.І. Білецький, Е.І. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2018. — № 17. — С. 35-41. — Бібліогр.: 2 назв. — укр. 2616-5619 http://dspace.nbuv.gov.ua/handle/123456789/144969 519.8 uk Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| description |
Розглядається задача пошуку двох активних куль на множині заданих для n = 127. Доводиться теорема, що розв’язок досягається за 13 кроків. Доведення базується на введені 2-х нових типів графів – Q-графа та N-графа. |
| format |
Article |
| author |
Донець, Г.П. Білецький, В.І. Ненахов, Е.І. |
| spellingShingle |
Донець, Г.П. Білецький, В.І. Ненахов, Е.І. Оптимальний пошук двох активних куль на множині n = 127 Теорія оптимальних рішень |
| author_facet |
Донець, Г.П. Білецький, В.І. Ненахов, Е.І. |
| author_sort |
Донець, Г.П. |
| title |
Оптимальний пошук двох активних куль на множині n = 127 |
| title_short |
Оптимальний пошук двох активних куль на множині n = 127 |
| title_full |
Оптимальний пошук двох активних куль на множині n = 127 |
| title_fullStr |
Оптимальний пошук двох активних куль на множині n = 127 |
| title_full_unstemmed |
Оптимальний пошук двох активних куль на множині n = 127 |
| title_sort |
оптимальний пошук двох активних куль на множині n = 127 |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2018 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/144969 |
| citation_txt |
Оптимальний пошук двох активних куль на множині n = 127 / Г.П. Донець, В.І. Білецький, Е.І. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2018. — № 17. — С. 35-41. — Бібліогр.: 2 назв. — укр. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT donecʹgp optimalʹnijpošukdvohaktivnihkulʹnamnožinín127 AT bílecʹkijví optimalʹnijpošukdvohaktivnihkulʹnamnožinín127 AT nenahoveí optimalʹnijpošukdvohaktivnihkulʹnamnožinín127 |
| first_indexed |
2025-07-10T20:35:30Z |
| last_indexed |
2025-07-10T20:35:30Z |
| _version_ |
1837293672400420864 |
| fulltext |
ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 35
ТЕОРІЯ
ОПТИМАЛЬНИХ
РІШЕНЬ
Розглядається задача пошуку
двох активних куль на множині
заданих для n = 127. Доводиться
теорема, що розв’язок досягаєть-
ся за 13 кроків. Доведення базу-
ється на введені 2-х нових типів
графів – Q-графа та N-графа.
Г.П. Донець, В.І. Білецький,
Е.І. Ненахов, 2018
УДК 519.8
Г.П. ДОНЕЦЬ, В.І. БІЛЕЦЬКИЙ, Е.І. НЕНАХОВ
ОПТИМАЛЬНИЙ ПОШУК
ДВОХ АКТИВНИХ КУЛЬ
НА МНОЖИНІ n = 127
У роботі [1] приведений алгоритм пошуку
двох активних куль на множині заданих роз-
мірності n = 89. Тут приводиться доведення
теореми про дві активні кулі серед n = 127
заданих щонайменше можна відшукати за
13 перевірок (кроків).
При доведенні, як у [1], будемо викорис-
товувати функції: nf2 – мінімальна кіль-
кість перевірок для виявлення двох актив-
них куль із n заданих; 21, nng – мініма-
льна кількість перевірок для виявлення двох
активних куль, які перебувають по одній у
двох підмножинах, одна з яких містить 1n
куль, а друга – 2n ; ),( 21 nnh – мінімальне
число перевірок для пошуку двох активних
куль, якщо у першій множині є хоча б одна
активна куля.
Теорема. На множині куль для n = 127
мінімальна кількість перевірок для пошуку
двох активних куль 13)127(2 f .
Доведення. Крок 1. Беремо для перевірки
38 куль. Якщо результат перевірки 38 ,
тоді залишається 89 куль, дві активні кулі
серед яких можна знайти за 12)89(2 f кро-
ків [1], а всього для знаходження двох акти-
вних куль досить 13 перевірок. Якщо резуль-
тат перевірки < 38 >+, то отримаємо функцію
)89,38( h = 38∙89 2
38C = 4085< 122 . Це гово-
рить про достатність 12-и кроків для роз-
в’язання задачі. Далі будемо брати кулі з
обох множин. Результати перевірок будемо,
як правило, представляти у вигляді 2-х гра-
фів, які показані на рис. 1, 2.
Г.П. ДОНЕЦЬ, В.І. БІЛЕЦЬКИЙ, Е.І. НЕНАХОВ
36 ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17
РИС. 1. Q-граф РИС. 2. N-граф
Перший граф називається Q-графом і позначається Q (A,B,C,D), другий –
N-графом і позначається N(A,B,C,D). Частини графів будемо називати відпо-
відно A –, B –, C і D – частинами. Відмітимо, що тільки в A – частині Q-графа є
внутрішні ребра. Кількість ребер Q-графа дорівнює A(B+C+D)+ B∙C 2 ,AC де
2
AC – число комбінацій, а кількість ребер N-графа A∙B+B∙C+C∙D. Характерно,
що в Q-графі D-частина не має спільних ребер з B – і C – частинами. Якщо
в Q-графі зробити вибірку з C – частини, то в разі позитивного результату ребра
між A – і В – частинами зникають, і, таким чином, отримуємо N-граф. Те саме
можна сказати і про B – частину. Здійснюючи вибірки з N-графа, в разі позитив-
ного результату отримуємо або N-граф, або дводольні графи, які позначимо
( , ),d де , – кількість вершин у долях.
Крок 2. (+). Перевіряємо 12 куль з першої групи та 23 з другої. Якщо ре-
зультат перевірки < 121, 232 >+, то отримаємо граф Q (12, 23, 26, 66). Кількість
ребер цього графа m = 12(23 + 26 + 66) + 23∙26 2
12C = 2044< 112 .
Крок 3. (++). Беремо 8 куль з групи 121 та 10 з групи 66. В разі позитивного
результату отримаємо граф Q(8,10,4,105). Кількість ребер цього графу
m = 8(10 +4 + 105) + 10∙4 2
8C = 1020< 102 . Група із 105 вершин має спільні реб-
ра тільки з групою 8-и.
Крок 4. (+++). Беремо для перевірки 64 кулі з групи 105. В разі позитивного
результату отримаємо дводольний граф )64,8(d , який відповідає функції
9)2,2()16,8( 63 gg (див. [2]). У сумі буде 13 = 9+4 кроків (К = 13).
Крок 5. (+++−). У цьому випадку отримаємо граф Q (8, 10, 4, 41). Для нього
m = 8(10+4+41)+10∙4 2
8C = 508< 92 . Беремо 32 кулі з групи 41. В разі позитив-
ного результату отримаємо дводольний граф )32,8(d , що відповідає функції
8)2,2( 53 g . В сумі К = 8+5 = 13.
B
A
C
D
B
A D
C
ОПТИМАЛЬНИЙ ПОШУК ДВОХ АКТИВНИХ КУЛЬ …
ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 37
Крок 6. (+++−−). У цьому випадку отримаємо граф Q (8, 10, 4, 9). Для нього
m = 8(10+4+9)+10∙4 2
8C = 252< 82 . Беремо 10 куль з групи 10 та 1 кулю
з групи 9. У разі позитивного результату отримаємо граф N(4, 10, 8, 1), для якого
m = 4∙10+10∙8+ 8∙1 = 128 ≤ 72 .
Крок 7. (+++−−+). Беремо послідовно для перевірки половину куль з груп
залишених (4 і 8) і застосовуємо метод дихотомії. Незалежно від результату
отримаємо граф N(1, 10, 2, 1), для якого m ≤ 52 .
Крок 9. (+++−−+**), де * – будь-який знак (+ або −) . Беремо 1 кулю з
А – частини і 3 кулі з 10-и. В разі негативного результату перевірки отримаємо
дводольний граф (2,8),d для якого функція 4)8,2( g . При позитивному
результаті отримаємо граф N(7,1,3,2), для якого m = 16 ≤ 42 , тобто за наступні
4-и кроки легко отримуємо розв’язок. У сумі К = 9 + 4 = 13.
У разі негативного результату на 6-му кроці отримаємо функцію )12,8( h ,
яка дорівнює 7 [1, лема 10].
При негативному результаті на 3-му кроці отримаємо граф Q (4, 23, 26, 56),
для якого m = 4∙(23+26+56) +23∙26+ 2
4C = 1024 = 102 .
Крок 4. (++−). Беремо 16 куль з 23-х і 8 – з 56-и. У разі позитивного резуль-
тату отримаємо 2 дводольні графи )30,16(d і )8,4(d , які в сумі мають 512 ре-
бер. Методом дихотомії за 9 кроків знаходимо шукане ребро, тобто 2 активні
кулі. В сумі К = 9 +4 = 13.
При негативному результаті отримаємо граф Q (4, 7, 26, 48), для якого
m = 512.
Крок 5. (++−−). Беремо 6 куль з 7-и та 19 з 48-и. У разі позитивного резуль-
тату отримаємо 2 дводольних графа )30,6(d і )19,4(d , які мають в сумі 256
ребер. Методом дихотомії за 8 кроків знаходимо 2 активні кулі. Всього К = 13.
При негативному результаті отримаємо граф Q (4, 1, 26, 29), для m =
= 4∙(1+26+29) +1∙26+ 2
4C = 256 = 82 .
Крок 6. (++−−−). Беремо 24 кулі з 26 і 2 кулі з 29-и. При позитивному ре-
зультаті отримаємо 2 дводольних графа )24,5(d і )4,2(d , які в сумі мають
128 ребер. Методом дихотомії за 7 кроків знаходимо 2 активні кулі.
Всього К = 13.
У разі негативного результату отримаємо граф Q (4, 1, 2, 27), для якого
m =4∙(1+2+27) +1∙2+ 2
4C = 128 ≤ 72 .
Крок 7. (++−−−−). Беремо 16 куль з 27. При позитивному результаті отри-
маємо дводольний граф )16,4(d , який має 64 ребра. Для нього функція
6)2,2()16,4( 42 gg .
При негативному результаті отримаємо граф Q (4, 1, 2, 11), для якого m =
64.
Г.П. ДОНЕЦЬ, В.І. БІЛЕЦЬКИЙ, Е.І. НЕНАХОВ
38 ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17
Крок 8. (++−−−−−). Беремо 1 кулю з 4-х і 5 куль з 11-и. При позитивному
результаті отримаємо граф Q (1, 5, 3, 9), у якого m = 32.
Крок 9. (++−−−−−+). Беремо 4 кулі з 5-и. У разі позитивного результату
отримаємо дводольний граф )4,4(d , для якого 4)4,4( g . А при негативному
результаті отримаємо граф Q (1, 1, 3, 9), для якого m = 16, з якого розв’язок лег-
ко отримати за 4 кроки. Всього К = 9 + 4=13.
При негативному результаті на 8-у кроці отримаємо граф Q (3, 1, 2, 6), який
має 32 ребра.
Крок 9. (++−−−−−−). Беремо 1 кулю 2-х і 4 кулі з 6-и. При позитивному ре-
зультаті отримаємо два дводольні графа )4,1(d і )4,3(d , які в сумі мають
16 ребер. Розв’язок легко знаходиться за 4 кроки. Всього К = 9 + 4=13.
А при негативному результаті отримаємо граф Q (3, 1, 1, 2), для якого
m = 16 і розв’язок теж знаходиться за 4 кроки.
Тепер розглянемо негативний результат 2-го кроку. Отримаємо функцію
(26 , 66).h
Крок 3. (+−). Беремо 8 куль з 26-и та 18 куль з 66-и. Отримаємо граф
Q (8, 18, 18, 48), для якого m = 8∙(18+18+48) +18∙18+ 2
8C = 1024 = 102 . Якщо
результат позитивний, здійснюємо наступний
Крок 4. (+−+). Беремо 16 куль з В-частини та 12 куль з 48-и. При позитив-
ному результаті отримаємо 2 дводольні графи )16,26(d і )8,12(d , які в сумі
мають 512 ребер. Методом дихотомії для них розв’язок знаходиться за 9 кро-
ків. Всього К = 9 + 4=13.
У разі негативного результату отримаємо граф Q (8, 2, 18, 36), для якого
m =8∙(2+18+36) +2∙18+ 2
8C = 512 = 92 .
Крок 5. (+−+−). Беремо 16 куль з 18-и та 12 куль з 36-и. При позитивному
результаті отримаємо 2 дводольні графи )10,16(d і )8,12(d , які в сумі мають
256 ребер. Методом дихотомії для них розв’язок знаходиться за 8 кроків. Всьо-
го К = 8 + 5 = 13.
А при негативному результаті отримаємо граф Q (8, 2, 2, 24), для якого
m =8∙(2+2+24) +2∙2+ 2
8C = 256 = 82 .
Крок 6. (+−+−−). Беремо 16 куль з 24-х. При позитивному результаті отри-
маємо дводольний граф )16,8(d з 128 ребрами, для якого розв’язок методом ди-
хотомії знаходиться за 7 кроків. У сумі К = 6 + 7 = 13.
У разі негативного результату отримаємо граф Q (8, 2, 2, 8), для якого
m =8∙(2+2+8) +2∙2+ 2
8C = 128 = 72 .
Крок 7. (+−+−−−). Беремо 3 кулі з А-частини та 2 з D-частини.
При позитивному результаті отримаємо граф Q (3, 2, 5, 10), для якого
m =3∙(2 + 5 + 10) + 2∙5 +
2
3C = 64 = 62 .
ОПТИМАЛЬНИЙ ПОШУК ДВОХ АКТИВНИХ КУЛЬ …
ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 39
Крок 8. (+−+−−−+). Беремо 1 кулю з 2-х та 8 з 10-и. У разі позитивного ре-
зультату отримаємо два дводольні графи )8,1(d і )8,3(d , для яких розв’язок ме-
тодом дихотомії знаходиться за 5 кроків. У сумі К = 8+5=13.
При негативному результаті отримаємо граф Q (3, 1, 5, 2), для якого
m = 3∙(1 + 5 + 2) + 1∙5 + 2
3C = 32 = 52 .
Крок 9. (+−+−−−+−). Беремо 4 кулі з 5-и. У разі позитивного результату
отримаємо дводольний граф )4,4(d , для якого розв’язок методом дихотомії зна-
ходиться за 4 кроки. У сумі К = 9 + 4 = 13.
При негативному результаті отримаємо граф Q (3, 1, 1, 2), для якого функ-
ція )4,3( h , як доведено в [1], дорівнює 4. Тут теж К = 9 + 4 = 13.
Якщо на кроці 7 (+−+−−−) буде негативний результат, то отримаємо граф
Q (5, 2, 2, 6), для якого m = 5∙(2 + 2 + 6) + 2∙2 + 2
5C = 64 ≤ 62 .
Крок 8. (+−+−−−−). Беремо 1 кулю з 5-и, 3 кулі з 6-и та 1 кулю з В-частини.
При позитивному результаті отримаємо граф G1 (рис. 3).
Крок 9. (+−+−−−−+). Беремо 3 кулі та 1 з правої 4-и. У разі позитивного ре-
зультату отримаємо 2 дводольні графи )5,3(d і (1,1),d для яких розв’язок знахо-
диться за 4 кроки.
При негативному результаті отримаємо граф Q (1, 1, 6, 3), для якого
розв’язок легко знаходиться за 4 кроки. В обох випадках К = 9 + 4 = 13.
При негативному результаті на кроці 8 (+−+−−−−) отримуємо граф Q (4, 1,
2, 3), для якого m = 4∙(1+2+3) +1∙2+ 2
4C = 32= 52 .
Крок 9. (+−+−−−−−). Беремо 1 кулю з 4-х, 1 кулю з 2-х і 1 кулю з 3-х. У разі
позитивного результату отримаємо граф G2 (рис. 4).
РИС. 3. Граф G1 РИС. 4. Граф G2
1
1 1
1 3
3 1 4
1
3
2
4
1
Г.П. ДОНЕЦЬ, В.І. БІЛЕЦЬКИЙ, Е.І. НЕНАХОВ
40 ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17
Крок 10. (+−+−−−−−+). Беремо 1 кулю (верхню праву) та 3 кулі з правої
трійки. При позитивному результаті отримаємо 2 дводольні графи )5,1(d
і )3,1(d , які в сумі мають 8 ребер і для яких розв’язок знаходиться за 3 кроки.
А при негативному результаті отримаємо граф Q (1, 1, 3, 1), для якого
розв’язок методом дихотомії знаходиться за 3 кроки. У сумі К = 10 + 3 = 13.
У разі негативного результату на кроці 9 (+−+−−−−−), див. крок
9(+−+−−−+−), негативний результат. У цьому випадку отримаємо граф
Q (3, 1, 1, 2), для якого функція )4,3( h = 4.
При негативному результаті на кроці 3 (+−) отримуємо функцію )48,18( h ,
для якої m = 18∙48 + 2
18C = 1017< 102 .
Крок 4. (+−−). Беремо 8 куль з 18-и та 2 кулі з 48-и. А при позитивному ре-
зультаті отримаємо граф Q (8, 2, 10, 46), для якого m = 8∙(2+10+46) +2∙10+ 2
8C =
= 512 = 92 .
Крок 5. (+−−+). Беремо 8 куль з 10-и та 22 кулі з 46-и. У разі позитивного
результату отримаємо 2 дводольні графи )10,8(d і )22,8(d з 256 ребрами, для
яких методом дихотомії отримаємо розв’язок за 8 кроків. У сумі К = 5 + 8 = 13.
При негативному результаті, див. крок 5 (+−+−), негативний результат.
Якщо на кроці 4(+−−) результат негативний, то отримуємо функцію
)46,10( h , для якої m = 10∙46+ 2
10C = 505< 92 .
Крок 5. (+−−−). Беремо 4 кулі з 10-и та 7 куль з 46-и. У разі позитивного
результату отримаємо граф Q (4, 7, 6, 39), для якого m = 4∙(7+6+39) +7∙6+ 2
4C =
= 256= 82 .
Крок 6. (+−−−+). Беремо 6 куль з 7-и та 17 із 39-и. При позитивному резуль-
таті отримаємо граф N(6, 6, 4, 17), для якого m = 6∙(6+4)+4∙17 = 128= 72 ,
для якого методом дихотомії розв’язок отримуємо за 7 кроків. К = 6 + 7 = 13.
При негативному результаті отримаємо граф Q (4, 1, 6, 22), для якого
m = 4∙(1+6+22) +1∙6+ 2
4C = 128 = 72 .
Крок 7. (+−−−+−). Беремо 4 кулі з 6-и та 11 куль із 22-х. У разі позитивного
результату отримаємо 2 дводольні графи )5,4(d і )4,11(d з 64 ребрами,
для яких методом дихотомії отримуємо розв’язок за 6 кроків. К = 7 + 6 = 13.
При негативному результаті отримаємо граф Q (4, 1, 2, 11), для якого
m = 4∙(1 + 6 + 22) + 1∙6 + 2
4C = 128 = 72 . Далі див. крок 7 (++−−−−), негативний
результат.
А при негативному результаті на кроці 5(+−−−) отримаємо функцію
)39,6( h , для якої m = 6∙39+
2
6C = 249< 82 .
ОПТИМАЛЬНИЙ ПОШУК ДВОХ АКТИВНИХ КУЛЬ …
ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 41
Крок 6. (+−−−−). Беремо 2 кулі з 6-и та 10 куль з 39-и. У разі позитивного
результату отримаємо граф Q (2, 10, 4, 29), для якого m = 2∙(10 + 4 + 29) +
+10∙4 + 2
2C = 127< 72 .
Крок 7. (+−−−−+). Беремо 10 куль і 2 кулі з 29-и. При позитивному резуль-
таті отримаємо 2 дводольні графи )6,10(d і )2,2(d з 64 ребрами, для яких мето-
дом дихотомії отримуємо розв’язок за 6 кроків.
При негативному результаті отримуємо функцію )31,2( h , для якої
m = 2∙31+ 2
2C = 63< 62 . В цьому випадку розв’язок отримаємо за 6 (1 + 5) кроків,
якщо з 31 кулі послідовно (до отримання позитивного результату) брати для пе-
ревірки 16, 8, 4, 2, 1 куль. Кількість необхідних кроків буде визначатися за фо-
рмулою lkg lk )2,2( [2]. В обох випадках К = 7 + 6 = 13.
Якщо на кроці 6 (+−−−−) буде негативний результат, то отримаємо функцію
(4 ,29),h для якої m = 4∙29+ 2
4C = 122 < 72 . Розв’язок отримаємо за 7 кроків,
якщо з 31 кулі послідовно (до отримання позитивного результату) брати для
перевірки 16, 8, 4, 2, 1 куль. К = 6 + 7 = 13.
Як бачимо, в усіх випадках К = 13. Цим і завершується доведення теореми.
Г.А. Донец, В.И. Билецкий, Э.И. Ненахов
ОПТИМАЛЬНЫЙ ПОИСК ДВУХ АКТИВНЫХ ШАРОВ НА МНОЖЕСТВЕ n = 127
Рассматриваются задачи поиска двух активных шаров на множестве заданных для n = 127.
Доказывается теорема, что решение достигается за 13 шагов. Доказательство базируется на
введении 2-х новых типов графов – Q-графа и N-графа.
G.A. Donets, V.I. Biletskyi, E.I. Nenakhov
OPTIMAL SEARCH FOR TWO ACTIVE BALLS IN THE SET FOR n = 127
The Problem of search or for two active balls in the set of given ones for n=127 is considered. The
theorem is proved, consisting in assertion that the task is achiked in 13 steps. The proof is based on
the use of the introduced new types of graphs, namely the Q-graph and the N-graph.
Список літератури
1. Билецкий В.И., Ненахов Э.И. Алгоритмы поиска двух активных шаров на заданных
множествах. Теорія оптимальних рішень. К: Ин-т кибернетики имени В.М. Глушкова
НАН Украины. 2016. С. 78 – 85.
2. Донец Г.А., Билецкий В.И., Ненахов Э.И. Оптимальный поиск двух активных шаров
на множестве заданных. Теорія оптимальних рішень. К: Ин-т кибернетики имени
В.М. Глушкова НАН Украины. 2015. С. 134 – 139.
Одержано 26.03.2018
|