Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Алгоритмы поиска в строке

Алгоритмы генерации комбинаторных объектов.

1.Размещения с повторениями из n символов по k – это последовательность длины k, в которых n-возможных элементов будут повторяться. A kсверху n снизу =n!/(n-k)! Напечатать все последовательности длины k из чисел 1..n. Решение: Будем печатать их в лексикографическом порядке (последовательность а предшествует последовательности b, если для некоторого i их начальные отрезки длины i равны, а (i+1)-ый член последовательности а меньше). Первой будет последовательность <1,1,...,1>, последней - <n,n,...,n>. Будем хранить последнюю напечатанную последовательность в массиве x[1],..,x[k].

last[1],..,last[k] положим равным n. Для того, чтобы перейти к следующей последовательности надо: двигаясь с конца последовательности, найти самый правый член, меньший n, увеличить его на 1, а идущие за ним члены положить равными 1. Процедура print(x:massiv) - вывод последовательности.

Функция egual(x,last:massiv):boolean - сравнивает элементы массивов,если x<>last, то egual:=false иначе egual:=true.

for i:=1 to k do x[i]:=1;

print(x);

for i:=1 to k do last[i]:=n;

while not(equal(x,last)) do

begin

p:=k;

while not (x[p]<n) do p:=p-1;

x[p]:=x[p]+1;

for i:=p+1 to k do x[i]:=1;

print(x);

end;

Перестановки из n элементов - частный случай размещения элементов из Е по k, при k=n. Иными словами, перестановками называют размещения без повторений из n элементов, в которые входят все элементы. Можно также сказать, что перестановками из n элементов называют всевозможные n-расстановки, каждая из которых содержит все эти элементы по одному разу, и которые отличаются друг от друга лишь порядком элементов. Число перестановок вычисляется по формуле: Pn=n! 1. Просматриваем а1,..., аn с конца до тех пор, пока не попадется ai<ai+1. Если таковых нет, то генерация закончена.

2. Рассматриваем ai+1, ai+2,..., an. Найдем первый с конца am больший ai и поменяем их местами.

3. ai+1, ai+2,..., an переставим в порядке возрастания (для этого достаточно её переписать с конца).

4. Печатаем найденную перестановку.

5. Возвращаемся к пункту 1.

Сочетанием элементов из Е={a1,..., an} по k называется упорядоченное подмножество из k элементов, принадлежащих Е и отличающиеся друг то друга составом, но не порядком элементов. Число сочетаний вычисляется по формуле: Ckn=n!/(n-k)!k! Алгоритм генерации сочетаний Ckn.

1. Для i:=1 до k ci:=i; печатаем ci, для i=1..k.

2. С конца находим такое i, что ci<>n-k+i. Если такого i нет, то генерация сочетаний закончена.

3. ci:=ci+1; для m=i+1, i+2,..., k выполним cm:=cm-1+1; выводим ci для i=1,..., k.

4. Возрващаемся к пункту 2.

 

3) Динамическое программирование — способ решения сложных задач путём разбиения их на более простые подзадачи. Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.

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

Этапы:

1. Разбиение задачи на подзадачи меньшего размера.

2. Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм.

3. Использование полученного решения подзадач для конструирования решения исходной задачи.

Ярким примером является вычисление последовательности Фибоначчи,Ф3=Ф2+Ф1

Динамическое программирование обычно придерживается двух подходов к решению задач:

· нисходящее динамическое программирование: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Используется запоминание для решений часто встречающихся подзадач.

· восходящее динамическое программирование: все подзадачи, которые впоследствии понадобятся для решения исходной задачи просчитываются заранее и затем используются для построения решения исходной задачи. Этот способ лучше нисходящего программирования в смысле размера необходимого стека и количества вызова функций, но иногда бывает нелегко заранее выяснить, решение каких подзадач нам потребуется в дальнейшем.

Задача о ранце: из неограниченного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при ограниченном суммарном весе.

 

Алгоритмы поиска в строке

Пусть есть некоторый текст Т и слово (или образ) W. Необходимо найти первое вхождение этого слова в указанном тексте. Это действие типично для любых систем обработки текстов. (Элементы массивов Т и W – символы некоторого конечного алфавита – например, {0, 1}, или {a, …, z}, или {а, …, я}.) Поиск строки формально определяется следующим образом. Пусть задан массив Т из N элементов и массив W из M элементов, причем 0<M≤N. Поиск строки обнаруживает первое вхождение W в Т, результатом будем считать индекс i, указывающий на первое с начала строки (с начала массива Т) совпадение с образом (словом).

Пример. Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabca.

Образец входит в текст только один раз, со сдвигом S=3, индекс i=4.

Алгоритм прямого поиска Идея алгоритма:

1. I=1,

2. сравнить I-й символ массива T с первым символом массива W,

3. совпадение → сравнить вторые символы и так далее,

4. несовпадение → I:=I+1 и переход на пункт 2,

Условие окончания алгоритма:

1. подряд М сравнений удачны,

2. I+M>N, то есть слово не найдено.

Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — алгоритм поиска образца (подстроки) в строке. Алгоритм был открыт Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом. Результаты своей работы они опубликовали совместно в 1977 году. Поставим следующую задачу: имеется образец S и строка T, и нужно определить индекс, начиная с которого строка S содержится в строке T. Если S не содержится в T — вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число). При необходимости отслеживать каждое вхождение образца в текст имеет смысл завести дополнительную функцию, вызываемую при каждом обнаружении образца.

ЛИТЕРНЫЙ ТИП У ЛИТЕРЫ

ЛИТЕРЫ

ОТ ы ЛИТЕРЫ И ДО СОВПАДЕНИЯ Литеры

После частичного совпадения начальной части образа W с соответствующими символами строки Т мы фактически знаем пройденную часть строки и может «вычислить» некоторые сведения (на основе самого образа W), с помощью которых потом быстро продвинемся по тексту.

 

Идея КМП-поиска – при каждом несовпадении двух символов текста и образа образ сдвигается на все пройденное расстояние, так как меньшие сдвиги не могут привести к полному совпадению.

 

5) Алгоритмы на графах. Поиск в глубину. Поиск в ширину.

Поиск в глубину (Depth-first search, DFS) — один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой не пройдённой вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Метод систематического прохождения (посещения) вершин графа, когда за счет продвижений от текущей вершины по ребру вперед (к еще непросмотренной вершине) всегда, когда это возможно, и возвратов от текущей вершины по пройденному ребру назад (к ранее пройденной вершине), если движение вперед от текущей вершины невозможно, осуществляется движение по всем вершинам графа, достижимым из заданной вершины s, с которой начинается поиск. Поиск в глубину всегда завершается через конечное число шагов в вершине s - начале просмотра; после его завершения все ребра связного графа оказываются разбитыми на два класса: древесные, по которым осуществлялись переходы из посещенных вершин в непосещенные, и ребра касания, замыкающие циклы.

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...