VI Международная студенческая научная конференция Студенческий научный форум - 2014

В этой статье мне хотелось бы рассказать о некоторых алгоритмах поиска. Говоря о поиске, мы имеем некий массив данных, в котором ищем определенный элемент.

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

Для двоичного поиска частым случаем является метод бисекции. Этот метод применяется для поиска корней заданной функции на определенном отрезке.

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

2. Алгоритм выбора. Этот алгоритм предназначен для нахождения n-го элемента в массиве. Алгоритм выбирает из нескольких условий, проверяя их в последовательности записи. Его используют для нахождения минимального элемента, максимального элемента или медианы.

3. Линейный ( последовательный) поиск. Этот алгоритм является простейшим, не накладывает никаких ограничений на функцию. Поиск значения происходит в ходе обычного сравнения очередного значения. И когда значения совпадают, поиск завершается.

4. Локальный поиск ( оптимизация). Представляет собой группу алгоритмов, поиск в которых ведется на основании текущего состояния. Все ранее пройденные состояния не запоминаются и не учитываются. Целью данного поиска является оптимизация целевой функции

5. Двоичное дерево поиска. Этот способ поиска наиболее эффективен. Двоичное дерево имеет коллекцию структурированных узлов. Если коллекция пуста, мы имеем пустое двоичное дерево. В случае, если коллекция не пуста, то она делится на три семейства узлов: корневой узел, левое поддерево, правое поддерево.

6. Алгоритм поиска А*. Находит маршрут с минимальной стоимостью от начальной вершины к конечной. Порядок обхода вершин определяет эвристическая функция. Алгоритм поиска А* всегда находит решение, если оно существует, поэтому является полным.

Исходя из описания данных алгоритмов поиска, можно сделать вывод. Каждый алгоритм уникален по своему. И все они достаточно эффективны при решениях конкретных задач. Но это далеко не весь перечь алгоритмов, которые принимаются в областях информатики. Здесь были рассмотрены наиболее применяемый из алгоритмов.

Таким образом, мы рассмотрели основные алгоритма поиска.