Подразделы

Другие разделы

Дата и время

09/04/2025 22:03:38

Авторизация

Зарегистрироваться
Восстановить пароль

Методы грубой силы

Идея методов грубой силы Последовательный поиск Исчерпывающий перебор Сортировки методом грубой силы

Последовательный поиск

Мы уже рассматривали алгоритм, основанный на методе грубой силы, для решения общей задачи поиска – он называется последовательным поиском. Этот алгоритм по очереди проверяет элементы заданного списка до тех пор, пока не будет найден элемент с нужными свойствами (успешный поиск) или весь список будет проверен, но требуемый элемент не найден (неудачный поиск).

Алгоритм 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}$ .

width:400px;float:right|поиск подстроки Алгоритм, основанный на грубой силе, очевиден: выровняем шаблон с началом текста и начнем сравнивать соответствующие пары символов слева направо до тех пор, пока не убедимся, что символы во всех $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)$ в худшем случае.

Задания для практики

Сколько сравнений символов сделает алгоритм поиска подстроки, основанный на грубой силе, для шаблона "0001" в тексте, состоящем из 1000 повторений строки "100"?
Популярная в Америке игра в слова состоит в том, что игрок должен найти каждое из заданного множества слов в квадратной таблице, заполненной отдельными буквами. Слова можно читать по горизонтали, вертикали или диагонали в любом направлении. Разработайте алгоритм для этой игры, основанный на использовании грубой силы.

Назад