Так как чрезмерное употребление алкоголя вредит вашему здоровью, у нас будет задача про лекарства. Представьте, что вы работаете в лаборатории, которая ищет средство от смертельной болезни. Вам на испытание пришла партия из 1 000 пробирок с лекарством, которое нужно опробовать на людях. Проверка санкционирована Минздравом, у вас имеются все лицензии, но есть проблема. Вы узнаёте, что одну пробирку перепутали и по ошибке отправили вместо лекарства ядовитый реактив. Внешне он ничем не отличается от медикамента.
Вам нужно как можно скорее передать пробирки в больницы для запуска клинического теста, но отправлять отравленную пробирку нельзя: погибнут люди. Тесты всех пробирок займут месяцы, это очень долго. Но у вас есть лабораторные мыши. Вы знаете, что лекарство безвредно для них, а даже капля яда их убьёт за сутки. Но у вас только 10 мышей, а пробирок — 1 000.
Как определить, где яд, как можно быстрее? За какое время можно гарантированно найти пробирку с ядом?
Самопроверка
Прежде чем узнать решение, ответьте на такие вопросы:
- Рационально ли выбирать какие-то отдельные пробирки из общей массы или нужно протестировать всё?
- Есть ли в условии задачи лимит по количеству введённого лекарства?
- Обязаны ли мы тестировать одну мышь только одной пробиркой? Можно ли использовать одно животное несколько раз или дать ему лекарства из нескольких пробирок?
Сначала кажется, что решить задачу нереально — мышей в 100 раз меньше, чем пробирок. Значит, нам нужно как-то научиться быстро сокращать количество элементов, которые нужно проверить.
Мы знаем, что даже капля яда убьёт мышь за сутки. Значит, если мы смешаем эту каплю с настоящим лекарством, яд тоже сработает. Воспользуемся этим так:
Разделим все пробирки на равные группы — по 100 пробирок в каждой.
В каждой группе возьмём по капле из каждой пробирки и смешаем их. Получим 10 смесей, одна из которых отравлена, и дадим каждой мыши свою смесь. Через сутки мы увидим, какой грызун погиб, и поймём, где конкретно был яд.
Теперь у нас осталось 100 пробирок и девять мышей. Видите, мы за сутки сократили количество пробирок в 10 раз. Будем использовать этот же приём и дальше: делить сосуды на равные группы и делать смеси. На второй день разделим 100 пробирок на девять групп :
Восемь групп по 11 пробирок и одна группа из 12 пробирок.
Как видите, на совсем равные части поделить не получилось, но это не критично — задача всё равно решается. Теперь даём смеси мышам и через сутки смотрим, какое животное погибнет на этот раз.
Предположим самый сложный случай — яд был в смеси из 12 пробирок. У нас остаётся восемь мышей и 12 пробирок. Их тоже делим на восемь групп:
Четыре группы по две пробирки, и четыре группы по одной пробирке.
Снова даём вещество мышам и через сутки смотрим на результат. Если погибла особь, которая пила только из одной пробирки, — то она и была отравлена, а значит, мы нашли яд за три дня. Если эта мышь дегустировала смесь из двух сосудов, то на следующий день мы берём эти две пробирки, две мыши из тех, что остались, и обеим даём попробовать своё лекарство. Через сутки мы тоже узнаем, где был яд.
В итоге за три или за четыре дня мы точно сможем сказать, какая пробирка в партии была перепутана.
Ответ: максимум за четыре дня мы найдём сосуд с ядом.
На подумать
Чтобы решить эту задачу, нам нужен был циклический алгоритм. В первой части он делил оставшуюся пробу на порции по числу мышей, во второй снимал пробу и в третьей проверял, в какой пробе было лекарство. Кайф алгоритма в том, что его скорость исполнения нелинейна. Что это значит?
Допустим, у нас был бы бесконечный запас времени и те же 10 мышей. Мы даём каждой по одной капле из одной из пробирок в день. Если яд в районе тридцатой пробирки, мы узнаем об этом через три дня. Если в 1 000-й, то для поиска отравы потребуется 100 дней. Если бы сосудов было 10 тысяч, то понадобилось бы 1 000 дней. Время исполнения алгоритма растёт линейно: чем больше пробирок, тем больше дней.
Теперь посмотрим на наш алгоритм: чтобы проверить 1 000 пробирок, нужно четыре дня. Если бы образцов было 10 тысяч, потребовалось бы пять дней. Возрастание числа пробирок в 10 раз увеличило время исполнения только на 25%.
Это и есть нелинейная скорость выполнения. Представьте, насколько такие алгоритмы более эффективны на больших массивах данных.
