Начало
Учебные материалы
Методы грубой силы
Идея методов грубой силы Последовательный поиск Исчерпывающий перебор Сортировки методом грубой силы
Последовательный поиск
для решения общей задачи поиска -- он называется последовательным поиском.
Этот алгоритм по очереди проверяет элементы заданного
списка до тех пор, пока не будет найден элемент с нужными свойствами
(успешный поиск) или весь список будет проверен, но
требуемый элемент не найден (неудачный поиск).
--
Алгоритм SequentialSearch (`A, K`)
// Входные данные: массив чисел `A`[0...`n-1`] и ключ поиска `K`
// Выходные данные: возвращается индекс первого элемента
// массива `A`, который равен `K`, либо `-1`
**for** `i in [0...n-1]` **do**
`quad` **if** `A_i = K`
`quad quad` **return** `i`
**return** `-1`
Последовательный поиск представляет превосходную иллюстрацию метода
грубой силы, с его характерными сильными (простота) и слабыми (низкая
эффективность) сторонами.
--
##### Поиск подстроки
Пусть дана строка `T` (текст) длиной `n` , и строка `P` (шаблон) длиной `m<=n`;
требуется найти в тексте подстроку, соответствующую шаблону. Говоря точнее, мы хотим определить `i` --
индекс крайнего слева символа первой соответствующей шаблону подстроки в тексте --
такой, что `T_i = P_0; T_{i+1}=P_1; ... ; T_{i+m-1}= P_{m-1}`.
--
Алгоритм, основанный на грубой силе, очевиден: выровняем шаблон с
началом текста и начнем сравнивать соответствующие пары символов слева направо
до тех пор, пока не убедимся, что символы во всех `m` парах равны (в этом случае
алгоритм может прекращать работу), либо не встретим пару разных символов.
В последнем случае шаблон смещается на одну позицию вправо, и сравнение
символов продолжается, начиная с первого символа шаблона и символа в
соответствующей позиции в тексте. Заметим, что последняя позиция в тексте, которая
еще может выступать в роли начала искомой подстроки -- `n-m`, так как после этой позиции в
тексте остается слишком мало символов, чтобы они могли соответствовать шаблону.
--
Алгоритм StringSearch (`T,P`)
// Входные данные: массив символов `T[0...n-1]` (текст),
// массив символов`P[0...m-1]` (шаблон)
// Выходные данные: позиция первого символа в тексте,
// с которой начинается первая искомая
// подстрока, соответствующая шаблону; если
// подстрока не найдена, возвращается `-1`
**for** `i in [0...n-m]` **do**
`quad j larr 0`
`quad` **while** `j < m` **and** `P[j] =T[i + j]` **do**
`quad quad quad j larr j+1`
`quad` **if** `j = m`
`quad quad ` **return** `i`
**return** -1
--
В примере на рисунке было выполнено 23 сравнения, что немного больше длины текста 14. В наихудшем случае алгоритм может выполнять все `m` сравнений перед сдвигом шаблона, и это происходит в каждой из `n -m + 1`
попыток. Таким образом, в наихудшем случае алгоритм имеет время работы `Theta(nm)`. Как выглядит текст и шаблон для такого случая?
Однако в случае поиска слова в тексте на естественном языке можно ожидать, что большинство сдвигов будет выполняться
после небольшого количества сравнений Таким образом, эффективность в среднем случае должна быть существенно выше эффективности в худшем случае --
можно показать, что при поиске в случайных текстах эффективность оказывается линейной, т.е. равной `Theta(n + m) = Theta(n)`.
Обратите внимание на разницу в классах для худшего и среднего случая. Поэтому для указания эффективности алгоритма часто используется `O`-обозначение,
а не `Theta`.
Существуют алгоритмы, которые имеют эффективность `Theta(n)` в худшем случае.
---
##### Задания для практики
1. Сколько сравнений символов сделает алгоритм поиска подстроки, основанный на грубой силе, для шаблона "0001" в тексте, состоящем из 1000 повторений строки "100"?
1. Популярная в Америке игра в слова состоит в том, что игрок должен найти каждое из заданного множества слов в квадратной таблице, заполненной отдельными буквами. Слова можно читать по горизонтали, вертикали или диагонали в любом направлении. Разработайте алгоритм для этой игры, основанный на использовании грубой силы.
