Типы алгоритмов поиска
Алгоритмы поиска составляют важную часть многих программ. Некоторые поиски включают поиск записи в базе данных, например поиск вашей записи в базе данных IRS. Другие алгоритмы поиска просматривают виртуальное пространство, например, поиск лучших шахматных ходов. Хотя программисты могут выбирать из множества типов поиска, они выбирают алгоритм, который лучше всего соответствует размеру и структуре базы данных, чтобы обеспечить удобство для пользователя.
Линейный поиск
Линейный поиск — предпочтительный алгоритм для коротких списков, потому что он прост и требует минимального кода для реализации. Алгоритм линейного поиска просматривает первый элемент списка, чтобы определить, ищете ли вы его, и если да, то вы закончили поиск. Если нет, он просматривает следующий элемент и далее по каждой записи в списке.
Бинарный поиск
Двоичный поиск — популярный алгоритм для больших баз данных с записями, упорядоченными по числовому ключу. Примеры кандидатов включают базу данных IRS с ключом по номеру социального страхования и записи DMV с ключом по номеру водительского удостоверения. Алгоритм начинается с середины базы данных — если ваше целевое число больше среднего числа, поиск продолжится в верхней половине базы данных. Если ваше целевое число меньше среднего числа, поиск продолжится с нижней половиной базы данных. Он продолжает повторять этот процесс, каждый раз разрезая базу данных пополам, пока не найдет запись. Этот поиск более сложен, чем линейный поиск, но для больших баз данных он намного быстрее, чем линейный поиск.
Поиск по дереву
Поиск по дереву работает, только если данные укладываются в древовидную структуру. База данных начинается с корня, который переходит к нескольким элементам, каждый из которых переходит к еще нескольким элементам и так далее, пока не получится дерево. Одним из примеров является игра в шахматы. Текущая позиция на доске — корень. Разрешенные ходы из этой позиции представляют собой один шаг вниз по дереву, и так далее, пока игрок не найдет позицию на доске, которая оставит его в лучшей позиции.
Генетический алгоритм
Генетический алгоритм поиска — один из методов искусственного интеллекта. Он ищет «оптимальное решение», выраженное в виде строки данных — например, списка внутренних размеров реактивного двигателя, обеспечивающего максимальную тягу. Поиск начинается со случайной совокупности строк и проверяет каждую из них, сохраняя лучшие и размножая их для получения следующего поколения. Программа продолжает повторять этот процесс, пока не придет к строке оптимального решения.