Книга: Вычислительное мышление: Метод решения сложных задач

Выбираем лучшее решение

Выбираем лучшее решение

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

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

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

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

Оглавление книги