Алгоритмы поиска. Линейный поиск. Двоичный поиск. Алгоритмы поиска
 Скачать 244.42 Kb.
|
|
Алгоритмы поиска. Линейный поиск. Двоичный поиск. Алгоритмы поиска Алгоритм поиска A* — особый случай поиска по первому наилучшему совпадению; используется эвристика, увеличивающая скорость работы алгоритма Алгоритм выбора (англ.) — модификация алгоритма линейного поиска; находит  -тый по величине элемент в списке;Двоичное дерево поиска — использует бинарное дерево для хранения элементов; Двоичный поиск — находит элемент в отсортированном списке Интерполирующий поиск (Предсказывающий поиск, Поиск по словарю) Линейный поиск — находит элемент в неотсортированном списке Локальный поиск (оптимизация) Метод штрафов Поиск в глубину — проходит граф ветка за веткой Поиск в ширину — проходит граф уровень за уровнем Поиск по первому наилучшему совпадению (англ. Best-first search) — проходит граф в порядке важности, используя очередь приоритетов Троичный поиск — находит максимум или минимум функции Поиск в хеш-таблице Алгоритм Ли (волновой алгоритм) — поиск пути на карте. Линейный поиск. Данный алгоритм является простейшим алгоритмом поиска и в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева направо, т.е.от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершенным. В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют только, если отрезок поиска содержит очень мало элементов, тем не менее линейный поиск не требует дополнительной памяти или обработки/анализа функции. Также, линейный поиск часто используется в виде линейных алгоритмов поиска максимума/минимума. Алгоритм последовательного поиска: Шаг1. Полагаем, что значение переменной цикла i=0. Шаг2. Если значение элемента массива x[i] равно значению ключа key, то возвращаем значение, равное номеру искомого элемента, и алгоритм завершает работу. В противном случае значение переменной цикла увеличивается на единицу i=i+1. Шаг3. Если i Двоичный поиск (также известен, как метод деления пополам и метод половинного деления) – алгоритм нахождения заданного значения монотонной (невозрастающей или неубывающей) функции. Поиск основывается на теореме о промежуточных значениях. Используется в информатике, вычислительной математике и математическом программировании. Это поиск заданного элемента на упорядоченном множестве, осуществляемый путем неоднократного деления этого множества на две части таким образом, что искомый элемент попадает в одну из этих частей. Поиск заканчивается при совпадении искомого элемента с элементом, который является границей между частями множества или при отсутствии искомого элемента. Алгоритм бинарного поиска: Шаг1. Определить номер среднего элемента массива middle=(high+low)/2. Шаг2. Если значение среднего элемента массива равно искомому, то возвращаем значение, равное номеру искомого элемента, и алгоритм завершает работу. Шаг3. Если искомое значение больше значения среднего элемента, то возьмем в качества массива все элементы справа от среднего, иначе возьмет в качестве массива все элементы слева от среднего. Перейдем к Шагу1. В массиве может встречаться несколько элементов со значениями, равными ключу. Данный алгоритм находит первый совпавший с ключом элемент, который в порядке следования в массиве может быть ни первым, ни последним среди равных ключу.
Сортировка - это процесс упорядочивания набора данных одного типа по возрастанию или убыванию значения какого-либо признака. При сортировки элементы массива меняются местами таким образом, что их значения оказываются упорядоченными или по возрастанию или по убыванию. Если в массиве есть одинаковые элементы, то говорят о сортировке по неубыванию или по невозрастанию. Сортировка Шелла— алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Сначало сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии . После этого процедура повторяется для некоторых меньших значений , а завершается сортировка Шелла упорядочиванием элементов. Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои.Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ: - отсутствие потребности в памяти под стек; - отсутствие деградации при неудачных наборах данных Пирамидальная сортировка— алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно). Количество применяемой служебной памяти не зависит от размера массива. Быстрая сортировка-один из быстрых известных универсальных алгоритмов сортировки массивов обменов при упорядочении n элементов. Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы: Сортировка слиянием— алгоритм сортировки, который упорядочивает в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи. Сортировка простыми обменами — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка. Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма. Поразрядная сортировка — алгоритм сортировки за линейное время. Алгоритм сортировки, числа сортируются по разрядам. Существует два варианта При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке все наоборот. При LSD сортировке получается следующий порядок: короткие ключи идут раньше длинных, ключи одного размера сортируются по алфавиту, это совпадает с нормальным представлением чисел: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. При MSD сортировке получается алфавитный порядок, который подходит для сортировки строк. Например "b, c, d, e, f, g, h, i, j, ba" отсортируется как "b, ba, c, d, e, f, g, h, i, j". Если MSD применить к числам разной длины, то получим последовательность 1, 10, 2, 3, 4, 5, 6, 7, 8, 9. Топологическая сортировка — упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин. Топологическая сортировка (Topological sort) — один из основных алгоритмов на графах, который применяется для решения множества более сложных задач. Задача топологической сортировки графа состоит в следующем: указать такой линейный порядок на его вершинах, чтобы любое ребро вело от вершины с меньшим номером к вершине с большим номером. Очевидно, что если в графе есть циклы, то такого порядка не существует. Ориентированной сетью (или просто сетью) называют бесконтурный ориентированный граф. В задачах подобного плана рассматриваются только конечные сети. Топологическая сортировка применяется в самых разных ситуациях, например при распараллеливании алгоритмов, когда по некоторому описанию алгоритма нужно составить граф зависимостей его операций и, отсортировав его топологически, определить, какие из операций являются независимыми и могут выполняться параллельно (одновременно). Примером использования топологической сортировки может служить создание карты сайта, где имеет место древовидная система разделов. Сортировка вставками - один из простейших способов отсортировать массив - сортировка вставками. В обычной жизни мы сталкиваемся с этим методом при игре в карты. Чтобы отсортировать имеющиеся у вас карты, вы вынимаете карту, сдвигаете оставшиеся карты, а затем вставляете карту на нужное место. Процесс повторяется до тех пор, пока хоть одна карта не на месте. Таким образом, алгоритм будет состоять из (n-1)-го прохода (n - размерность массива), каждый из которых будет включать четыре действия: - взятие очередного i-го не отсортированного элемента и сохранение его в дополнительной переменной; - поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов; - сдвиг элементов массива от i-го до j-1-го вправо, чтобы освободить найденную позицию вставки; - вставка взятого элемента в найденную i-ю позицию. Сортировка выбором— алгоритм сортировки. Может быть реализован и как устойчивый и как неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное время. Шаги алгоритма: - находим минимальное значение в текущем списке - производим обмен этого значения со значением на первой неотсортированной позиции - теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы
Процесс упорядочивания информации и называют «сортировкой». Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы. Сортировка массива данных занимает одну из самых важнейших проблем современных организаций. Ведь в каждой организации есть свои БД на сотрудников, которые нужно отсортировать, допустим, по фамилии или по зп, по возрастанию или убыванию. Чаще всего сортировка применяется для последующего поиска. Перед тем, как решать вопросы сортировки необходимо знать объем данных, которые необходимо обрабатывать. Есть методы, которые наиболее эффективны при малом количество элементов, но они становятся довольно громоздкими при большом. Постановка задачи такова: есть набор неупорядоченных данных (массив), задача – выдать те же данные, упорядоченные по некоторому полю (ключу) по возрастанию (убыванию). Обычно данные представляются в виде ключа и некоторой связанной с ним информации. Например, год рождения и фамилия. Практически каждый алгоритм сортировки можно разбить на три части: -сравнение, определяющее упорядоченность пары элементов; - перестановку, меняющую местами пару элементов; - собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены. Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти. Время – основной параметр, характеризующий быстродействие алгоритма. Память – ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Классификация алгоритмов сортировки Сортировка вставками. Создается новый массив, в который мы последовательно вставляем элементы из исходного массива так, чтобы новый массив был упорядоченным. На каждом шаге алгоритма мы выбираем один из элементов данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива. Сортировка вставками эффективна на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшей. Эффективна на наборах данных, которые уже частично отсортированы. Может сортировать список по мере его получения. Сортировка методом выбора. На первом шаге в массиве ищется самый маленький элемент и меняется местами с первым. На втором шаге ищется самый маленький, начиная со второго, и ставится на 2-е место (второй элемент, естественно, не забываем – ставим его на место, где раньше был самый маленький). И так далее, на i-ом шаге ищется самый маленький, начиная с i-го и ставится на i-е место. Метод пузырька. Метод пузырька так же называют «Пузырьковой сортировкой». Суть сортировки методом пузырька вытекает из названия. Мы находим минимальный элемент (пузырек) в массиве и выставляем его первым элементом массива (поднимает на поверхность). Далее находим следующий минимальный элемент и так же его выставляем вслед за первым элементом. И так будем действовать до самого конца. Таким образом, минимальные элементы всплывают. Этот алгоритм в исходном списке ищет пары цифр, которые следуют не по порядку и затем меняет их местами. Процесс повторяется до тех пор, пока весь список не будет отсортированным. Сортировка Шейкером. Когда данные сортируются не в оперативной памяти, а на жестком диске, особенно если ключ связан с большим объемом дополнительной информации, то количество перемещений элементов существенно влияет на время работы. Этот алгоритм уменьшает количество таких перемещений, действуя следующим образом: за один проход из всех элементов выбирается минимальный и максимальный. Потом минимальный элемент помещается в начало массива, а максимальный, соответственно, в конец. Далее алгоритм выполняется для остальных данных. Таким образом, за каждый проход два элемента помещаются на свои места, а значит, понадобится N/2 проходов, где N – количество элементов. 4. Использование списков для моделирования сложных структур данных. Часто в серьезных программах надо использовать данные, размер и структура которых должны меняться в процессе работы. Динамические массивы здесь не выручают, поскольку нельзя сказать, сколько памяти надо выделить – это выясняется только в процессе работы. В таких случаях применяют данные особой структуры, которые представляют собой отдельные элементы, связанные с помощью ссылок. Каждый элемент (узел) состоит из двух областей памяти: поля данных и ссылок. Ссылки – это адреса других узлов этого же типа, с которыми данный элемент логически связан. В языке Си для организации ссылок используются переменные-указатели. При добавлении нового узла в такую структуру выделяется новый блок памяти и с помощью ссылок устанавливаются связи этого элемент с уже существующими. Для обозначения конечного элемента в цепи используются нулевые ссылки (NULL). Линейный список – это конечная последовательность однотипных элементов (узлов), возможно, с повторениями. Количество элементов в последовательности называется длиной списка, причем длина в процессе работы программы может изменяться. При работе со списками на практике чаще всего приходится выполнять следующие операции: -найти элемент с заданным свойством; -определить первый элемент в линейном списке; -вставить дополнительный элемент до или после указанного узла; - исключить определенный элемент из списка; -упорядочить узлы линейного списка в определенном порядке. Строение списка: набор узлов, объединенных с помощью ссылок. Однонаправленный линейный список- список, который имеет указатель на начало списка, при этом каждый список имеет указатель на следующий список, а последний список принимает указатель NULL, что говорит о том, что он последний. Однонаправленный кольцевой список – список, который имеет указатель на начало списка, при этом каждый список имеет указатель на следующий список, а последний список имеет указатель на начало списка. В зависимости от количества связей между соседними элементами различают односвязные и двусвязные списки. Каждый элемент в списке с двойной связью имеет указатель на следующий элемент списка и указатель на предыдущий элемент списка. Двунаправленный список отличается двумя основными преимуществами. Во-первых, список может просматриваться в обоих направлениях. Это не только упрощает сортировку списка, но также позволяет пользователям БД просматривать данные в обоих направлениях. Во-вторых, список при нарушении одной из связей может быть восстановлен по другой связи. Это свойство имеет смысл использовать при отказах оборудования, приводящих к нарушению списка. Структура узла: struct Node{ char word[40]; //слово int count; //счетчик повторений Node *next; //ссылка на следующий элемент }; Адрес начала списка: PNode Head=NULL; Для доступа к списку достаточно знать адрес его головы. Когда нужны списки? Задача. В файле записан текст. Нужно записать в другой файл в столбик все слова, встречающиеся в тексте, в алфавитном порядке, и количество повторений для каждого слова. Проблемы: |