Вычислительное мышление. Метод решения сложных задач - Питер Макоуэн

Алгоритмы поиска

Наше решение для игры «20 вопросов» можно использовать, чтобы помочь пациенту с синдромом «запертого человека» разговаривать, потому что задача, в сущности, не меняется. Это задача поиска: у нас есть серия предметов и надо найти один конкретный. Решения для этой задачи называются алгоритмами поиска, и они обеспечивают беспроигрышный способ что-нибудь найти. Первый подход, проверка всех вариантов по очереди («Это A?», «Это B?..», «Это певица Адель?», «Это Джеймс Бонд?..»), — алгоритм под названием линейный поиск. Порой это лучшее, что есть в вашем распоряжении. Например, если вы были свидетелем ограбления и участвуете в опознании преступника из нескольких людей, линейный поиск будет для вас оптимальным: рассмотрите по очереди каждое лицо, пока не увидите в ряду человека, который совершил преступление. Линейный поиск хорошо работает и тогда, когда вещи, среди которых вы ведете поиск, никак не упорядочены. Если вы ищете носок, который может быть в любом ящике комода, начните сверху и последовательно проверяйте ящики один за другим.

Другой алгоритм включает вопросы, после ответа на которые остается половина вариантов: «Эта буква стоит раньше N?», «Это женщина?». Найти подобные вопросы — общая стратегия решения задач под названием «разделяй и властвуй». Если вы найдете такое решение, ответ, вероятно, будет получен очень быстро. Почему? Потому что, как мы видели, если несколько раз сократить число вероятных ответов вполовину, можно очень быстро прийти к одному варианту — гораздо быстрее, чем если бы мы проверяли последовательно пункт за пунктом. Заметим, что здесь мы снова используем обобщение. Самый простой алгоритм поиска по принципу «разделяй и властвуй» называется бинарным поиском. Представьте, что все предметы, среди которых вы ищете нужный, стоят по порядку и самый маленький — на одном конце, а самый большой — на другом. В ходе бинарного поиска вы подходите к предмету, который расположен посередине, и проверяете, лежит ли нужная вам вещь до или после него. Затем вы отбрасываете ненужную половину и повторяете ту же операцию с оставшейся. Вы делаете это до тех пор, пока не остается один предмет — тот, который вы ищете. Возможно, примерно так вы поступаете, когда нужно найти фамилию в толстом телефонном справочнике. Конечно, вы не будете начинать с первой страницы и проверять каждое имя по очереди, пока не найдете нужное!

Кроме этих двух, есть еще много алгоритмов поиска. Например, каким образом поисковая система вроде Google просматривает каждую веб-страницу на планете за доли секунды? Она использует еще более продвинутый алгоритм!

Чтобы применить алгоритм поиска, необходимо задействовать абстрагирование. Мы абстрагируемся от деталей конкретной задачи и смотрим, нельзя ли свести ее к задаче поиска, и тогда наш алгоритм поиска становится готовым решением для многих задач. Можно подойти к этому с другой стороны: как только мы придумаем стратегию выигрыша за 20 вопросов, то сумеем обобщить это решение до алгоритма «разделяй и властвуй» — у нас есть общая стратегия, которая работает и для других задач. Абстрагирование и обобщение часто неразрывно связаны.