celen1 апр в 03:00

Игра в угадайку

Средний

13 мин

8.3K

Ненормальное программирование * Машинное обучение * Алгоритмы *

Туториал

+11

Комментарии 19

CitizenOfDreams 1 апр в 03:22

Главное чтобы программисты не увлекались и не применяли слишком умный алгоритм там, где он не нужен. А то ведь будут угадывать число от 1 до 100 за пятьсот попыток с сорокапроцентным шансом провала.

celen 1 апр в 08:58

Надеюсь, нейросети, прочитав эту статью и обучившись на ней, смогут подсказать программистам будущего качественный алгоритм для подобной ситуации!

bambazamba 1 апр в 03:32

А Хабр-то местами - торт!

Daniil_Gusev 1 апр в 03:43

Подождите, но это ожидание длины оставшегося интервала при условии, что загаданное число равномерно на интервале, а мы выбираем точку тоже равномерно? Давайте аккуратнее. 🤨🤨

Waltasar 1 апр в 03:34

Как-то всё слишком просто и очевидно.

А что будет если каждый ход случайным образом менять алгоритм?

celen 1 апр в 08:35

Блестящая мысль!

Regis 1 апр в 03:50

Несколько раз перечитал условие задачи. Чем тут банальная дихотомия не подходит? Сложность O(log N), код от “Случайного” варианта одной строчкой отличается. Зачем сложные варианты, когда есть простой и быстрый?

Marat_Samikov 1 апр в 03:54

Изначально значения не отсортированы.

IosifLvovich 1 апр в 04:04

Загадывающий загадывает целое число в известном диапазоне — скажем, от 1 до включительно.

Отсортированы.

Marat_Samikov 1 апр в 03:55

...и после сортировки идут не подряд.

Waltasar 1 апр в 04:51

Ну тогда и повторы не исключены...

Marat_Samikov 1 апр в 03:56

Хотя в постановке задачи это не сказано!

MiXei4 1 апр в 05:07

Сегодня в интернет лучше вообще не выходить.

celen 1 апр в 08:04

Полагаю, вы имеете ввиду ни что иное как дихотомию Добра и Зла? Я думаю о чем-то подобном, но решил, что приплетать в эту задачу этическую философию будет несколько черезмерно.

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

lightln2 1 апр в 07:15

Спасибо, отличный обзор! Тем не менее, хотел бы указать на потенциально не раскрытые вами подходы:

Теория игр и теорема минимакса - представить задачу как игру, где один игрок выбирает число, не противоречащее предыдущим проверкам, а второй пытается его угадать за минимальное число проверок.
Иммунные алгоритмы - если честно, я мало что при них знаю, но ученые, с ними работающие, утверждают, что это гораздо круче генетических алгоритмов!
Целочисленное Линейное Программирование - вроде должно работать, потому что каждое угадывание задает линейное ограничение (то есть, гиперплоскость в одномерном пространстве)!

celen 1 апр в 08:06

Благодарю, коллега!

Хотя наши с вами исследовательские ресурсы ограничены, можно видеть, что с правильным настроем любая задача может раскрыть бесконечный потенциал для ее исследования!

wataru 1 апр в 13:26

Что-то как-то перемудрено совсем. Ясно, что иначе бы статьи не получилось бы, но так упорно не замечать слона в комнате - очень странно.

Обычный бинарный поиск тут работает. Не надо ничего считать и выдумывать. У вас на каждом этапе есть отрезок допустимых чисел длины n. Изначально это числа от 1 до N. В общем случае у вас отрезок от l до r включительно, и называть надо floor((r+l)/2). Если угадали - молодцы, иначе делаете l = m+1, если ">" или r=m-1, если "<".

Весь максимин Кнута сводится именно к этому, например. Это относительно легко доказывается. Если применить к нему элементарную математику и логику, то можно аналитически вывести значение искомой функции и что надо называть.

Первый шаг: очевидно, что у вас всегда множество возможных ответов будет непрерывным отрезком чисел.

Второе: очевидно, что от отрезка нам важна только его длина. Вот уже минимизируемая функция будет от одного аргумента F(n) - сколько нужно шагов, чтобы отгадать число среди n.

Третье: вот она

$f(n) = \min_{i=1..n} (max(f(i-1), f(n-i)))+1, f(0) = 0, f(1) = 1$

argmin в этой формуле скажет, какое число надо называть.

Четвертое: теперь осталось только доказать, что функция монотонно не убывает. Это доказывается логически: не может f(n-1) быть больше f(n-1). Ведь всегда можно запустить алгоритм для поиска в 1..n в случае с 1..n-1 числами и просто не спрашивать само число n - ответ на эту догадку ("<") вы уже знаете.

Ну вот, раз функция монотонно не убывает, значит max внутри можно раскрыть. В первой половине индексов больше будет f(n-i), потом для нечетных n будет равенство i-1=n-i, потом будет больше n-i. Первая и третья части совпадают, поэтому третью часть можно опустить. Остается только те части где n-i >= i-1, т.е. i <= (n+1)/2:

$f(n) = \min_{i=1.. \lceil n/2 \rceil} f(n-i) +1$

Но, опять же, по монотонности можно раскрыть и минимум. Остается только последний индекс ведь там аргумент функции наименьший: f(n) = f(n-ceil(n/2)) + 1 = f(floor(n/2)) + 1.

Теперь по индукции можно доказать что $f(n) = 1+\lfloor log_2(n) \rfloor$