Поиск пути на графе
1) На основе значения полей №№1-3, 9, 15, 16 отдельного студента в структуре данных, созданной в лабораторной работе №1, создать текстовую строку. 2) В соответствии с выбранным вариантом произвести шифрование полученной текстовой строки.
3) Отобразить начальные и конечные данные, а также ключ(и). 4) Оформить отчёт. 5) Подготовить ответы на контрольные вопросы. Закрепить материал.
Контрольные вопросы
1) Что такое шифрование? 2) Что такое криптография? 3) Перечислите пункты основной классификации криптографических систем. 4) Какие классы криптографических систем самые защищённые? 5) Как увеличить стойкость к дешифрации метод Цезаря? 6) В чём преимущества шифрования с открытым ключом? Теоретические сведения В процессе своей повседневной деятельности человек постоянно сталкивается с проблемой поиска пути, будь-то выбор кратчайшего пути от дома до работы, поиск искомого объекта в квартире среди старых вещей, выбор оптимального количества партнёров для производства и реализации товаров, поиск оптимальных путей решения технической задачи и т.д. Все описанные задачи можно свести к задаче поиска кратчайшего расстояния между вершинами графа. Одним из самых главных различи й в постановке указанных выше задач является наличие априорной информации, то есть известны ли заранее количество вершин графа и значения их соответствующих дуг. На примере движения мобильного робота задача формируется как поиск объекта в заранее неизвестной местности с одновременным составлением карты данной местности. Экономические задачи данного типа заключаются в выборе оптимальной стратегии при неопределённости поведения рынка. Задачи данного типа решаются эвристическими и квазиоптимальными методами, в которых из-за отсутствия запаса по времени в качестве правильного решения принимается один из возможных вариантов. Поэтому, часто решения являются не оптимальными, а выигрышными. Ввиду сложности своей реализации, данный тип задач решается метом движения с возвратом и в данной лабораторной работе рассматриваться не будет. Другим типом задач является поиск в заранее известной местности, которую можно представить виде полного графа с известными количеством вершин и значений дуг. Поиск пути на графе
Наиболее удобным способом формализации и решения указанных задач является использование теории графов. В данном случае весьма удобно воспользоваться огромным потенциалом алгоритмов и методов обработки графов. Рассмотрим наиболее интересные методы.
LIFO (образован от англ. «Last In, First Out», что означает «последним пришёл – первым ушёл») – абстрактное понятие в способах организации и манипулирования данными относительно времени и приоритетов. Термин относится к абстрактным принципам обработки списков и временного хранения данных, в частности, когда нужно иметь доступ к ограниченному набору данных в определённом порядке. Принцип LIFO применяется в тех случаях, когда последние данные, добавленные в структуру, должны быть первыми удалены или обработаны. В упорядоченных структурах данных стек используется в качестве динамического элемента памяти, в котором абстрактное понятие — аппаратно зависимый стек вызовов — используется для хранения копии данных или их части, будь то адреса памяти элементов данных или копии данных. Самой распространенной задачей обработки списков является сортировка, в которой действия машина ограничиваются сравнением всего двух элементов, тогда как список чаще всего содержит миллионы членов. Существуют различные стратегии, оптимальные для разных типов сортируемых данных, но при реализации все они прибегают к применению программ или подпрограмм, которые обычно вызывают сами себя или часть своего кода рекурсивно, и при каждом вызове добавляют в стек вызовов частично упорядоченный список элементов. Благодаря гибкости доступа к стеку вызовов с возможностью перегруппировки данных подпрограммы и стандартные функции получают требуемые данные, выполняют те свои задачи, для решения которых они оптимизированы, и передают информацию обратно в вызывающий сегмент программы. Стек вызовов в конкретных случаях включает в себя адрес следующей инструкции вызывающей программы, которая обычно выполняет какие-то действия с «откликами», полученными от подпрограмм и стандартных функций. В рекурсивных вызовах эти действия обычно включают сравнение следующего элемента списка с возвратившимся «откликом» (например, выбор из двух значений наибольшей величины), пока список не будет исчерпан. FIFO (образован от англ. First In, First Out, что означает «первым пришёл — первым ушёл») – абстрактное понятие в способах организации и манипулирования данными относительно времени и приоритетов. Это выражение описывает принцип технической обработки очереди или обслуживания конфликтных требований путём упорядочения процесса по принципу: «первым пришёл — первым обслужен». Тот, кто приходит первым, тот и обслуживается первым, пришедший следующим ждёт, пока обслуживание первого не будет закончено, и т.д. В информатике этот термин относится к способу запоминания данных, обрабатываемых в очереди. Каждый элемент очереди хранится в структуре данных очереди (без исключений). Первые данные, добавленные в очередь, будут первыми из неё удалены, т.е. обработка производится последовательно в том же порядке, что и поступление. Это типичное поведение для очереди, хотя и не единственно возможное. Принцип FIFO обычно используется в электронных схемах для буферизации и управления потоком, передаваемом от аппаратного обеспечения к программному. В аппаратной форме FIFO в основном состоит из множества указателей чтения и записи, памяти и логики управления. Устройство памяти может быть SRAM, триггер, защёлка или любого другого подходящего типа. Для FIFO больших размеров используется, как правило, двойной порт SRAM, в котором один порт используется для записи, а другой для чтения.
Поиск в ширину. Начиная со стартового узла, этот алгоритм сначала определяет все непосредственно свободные соседние узлы, затем все свободные узлы в двух шагах, затем в трех, и так далее, пока цель не достигнута. В процессе реализации типичным является то, что для каждого узла его непроверенные соседи помещаются в список Open, который обычно является FIFO очередью. Рис. 3 демонстрирует процесс поиска. Можно заметить, что он находит путь вокруг препятствий, и этот путь является кратчайшим, то есть одним из нескольких кратчайших в длину путей, если все шаги имеют одинаковую стоимость. Тут имеется множество простых проблем. Одна заключается в том, что поиск идет равномерно во всех направлениях, вместо того, чтобы быть направленным в сторону цели. Другая проблема в том, что не все шаги равны, по крайней мере, шаги по диагонали должны быть длиннее ортогональных.
Двунаправленный поиск в ширину. Это улучшает простой поиск в ширину тем, что запускаются два одновременных поиска в ширину из стартовой точки А и конечной В и останавливается, когда узел из одного фронта поиска находит соседнюю точку С из другого фронта. Как показано на рис. 4, это может улучшить простой поиск в ширину (обычно в 2 раза), но все еще является очень неэффективным, т.к. в списке Open требуется держать все ещё не пройденные точки.
Алгоритм Дейкстры. Данный алгоритм разработан для прохода по графам, грани которых имеют различный вес. На каждом шаге, он ищет необработанные узлы близкие к стартовому, затем просматривает соседей найденного узла, и устанавливает или обновляет их соответствующие расстояния от старта. Этот алгоритм имеет два преимущества по сравнению с поиском в ширину: он принимает во внимание стоимость или длину пути и обновляет узлы, если к ним найден лучший путь. Для реализации, список Open с очередью FIFO заменяется приоритетной очередью, где извлеченный узел имеет лучшее значение - здесь, это наименьшая стоимость пути от старта. Допустим V – множество всех вершин графа. Тогда каждой вершине из V сопоставляется метка — минимальное известное расстояние от этой вершины до А. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены. В начале инициализации метка самой вершины А полагается равной 0, а метки остальных вершин — бесконечности. Это отражает то, что расстояния от А до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые. Алгоритм Дейкстры работает следующим образом. Шаг алгоритма: если все вершины посещены, то алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина i, имеющая минимальную метку (расстояние до А). Далее рассматриваются все возможные маршруты, в которых i является предпоследним пунктом. Вершины, в которые ведут рёбра из i, называются соседями этой вершины. Для каждого соседа вершины i, кроме отмеченных как посещённые, рассматривается новая длина пути, равная сумме значений текущей метки i и длины ребра, соединяющего i с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину i как посещенную и повторим шаг алгоритма. Поиск в глубину. Этот поиск противоположен поиску в ширину. Вместо посещения вначале всех соседей, а потом их наследников, он сначала посещает всех наследников, а только затем переключается на соседей. Для уверенности в том, что поиск закончится, необходимо предусмотреть остановку на определенной глубине. Можно использовать тот же самый код, что и в поиске в ширину, если добавить параметр для отслеживания глубины каждого узла и заменить Open с очереди FIFO на стек LIFO. На самом деле можно полностью избавиться от списка Open и вместо этого сделать поиск рекурсивной подпрограммой, что уменьшит расход памяти использованной под Open. Необходимо, чтобы каждая ячейка маркировалась как "посещенная" при продвижении в глубь и эта пометка снималась на обратном ходу, чтобы избежать генерации путей, которые посещают дважды одну и ту же ячейку. На рис. 5 можно заметить, что этого недостаточно, алгоритм все равно может путаться вокруг себя и тратить время на бессмысленные пути. Для геометрического поиска пути можно сделать два дополнения. Первое будет заключаться в добавлении метки на каждую ячейку с длиной найденного к ней кратчайшего пути; алгоритм больше не посетит эту ячейку пока не будет иметь к ней путь с меньшей стоимостью. Другое заключается в выборе вначале соседей, которые ближе к цели. С этими двумя дополнениями, можно заметить, что поиск в глубину быстро найдет путь. Могут обрабатываться даже взвешенные пути, если сделать остановку по общей накопленной стоимости вместо общего расстояния.
Алгоритм “лучший-первый”. Это первый рассматриваемый эвристический поиск, который принимает во внимание знания о пространстве поиска для направления своих усилий. Он похож на алгоритм Дийкстры, за исключением того, что узлы в списке Open оцениваются по приблизительному оставшемуся расстоянию до цели. Эта оценка так же не требует наличия обновлений, в отличие от алгоритма Дийкстры. Рис. 6 показывает работу алгоритма. Это самый быстрый из всех планирующих алгоритмов рассмотренных ранее, который направляется по прямой к цели. Он так же имеет и свои слабости. На рис. 8 а, показано, что он не принимает во внимание накопленную стоимость пути, направляясь по прямой через зону с высокой стоимостью, а не обходя ее. И на рис. 6 б можно увидеть, что найденный путь вокруг препятствия не прямой, а изгибается вокруг препятствия на манер алгоритма трассировки, рассмотренного ранее.
Алгоритм поиска A* («А звезда» или «А стар», от англ. A star) – алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью. Данный алгоритм является наилучшим алгоритмом для поиска оптимальных путей в различных пространствах. Этот эвристический поиск сортирует все узлы по приближению наилучшего маршрута идущего через этот узел. Типичная формула эвристики выражается в виде: f(n) = g(n) + h(n) где: f(n) – значение оценки, назначенное узлу n; g(n) – наименьшая стоимость прибытия в узел n из точки старта А; h(n) – эвристическое приближение стоимости пути к цели В от узла n. Таким образом, этот алгоритм сочетает в себе учет длины предыдущего пути из алгоритма Дийкстры с эвристикой из алгоритма "лучший-первый". Так как некоторые узлы могут обрабатываться повторно (для поиска оптимальных путей к ним позднее) необходимо ввести новый список Closed для их отслеживания.A* имеет множество интересных свойств. Он гарантированно находит кратчайший путь, до тех пор пока эвристическое приближение h(n) является допустимым, то есть он никогда не превышает действительного оставшегося расстояния до цели. Этот алгоритм наилучшим образом использует эвристику: ни один другой алгоритм не раскроет меньшее число узлов, не учитывая узлов с одинаковой стоимостью. На рис. 7 а – б, можно увидеть как A* справляется с ситуациями проблемными для других алгоритмов. Описание алгоритма: 1. Начинаем со стартовой точки A и добавляем ее в "открытый список" клеток, которые нужно обработать. Открытый список это что-то наподобие списка покупок. В данный момент есть только один элемент в списке, но позже мы добавим еще. Список содержит клетки, которые может быть находятся вдоль пути, который вы выберете, а может и нет. Проще говоря, это список клеток, которые нужно проверить. 2. Ищем доступные или проходимые клетки, граничащие со стартовой точкой, игнорируя клетки со стенами, водой или другой непроходимой областью. И также добавляем их в открытый список. Для каждой из этих клеток сохраняем точку A, как "родительскую клетку". Эта родительская клетка важна, когда мы будем прослеживать наш путь. 3. Удаляем стартовую точку A с вашего открытого списка и добавляем ее в "закрытый список" клеток, которые вам больше не нужно проверять.
Волновой алгоритм является одним из самых уникальных алгоритмов трассировки. Он позволяет построить трассу (путь) между двумя элементами в любом лабиринте. На двумерной клетчатой карте (матрице), состоящей из «проходимых» и «непроходимых» клеток, обозначена клетка старта и клетка финиша. Цель алгоритма — проложить кратчайший путь от клетки старта к клетке финиша, если это, конечно, возможно. От старта во все направления распространяется волна, причем каждая пройденная волной клетка помечается как «пройденная». Волна, в свою очередь, не может проходить через клетки, помеченные как «пройденные» или «непроходимые». Волна движется, пока не достигнет точки финиша или пока не останется непройденных клеток. Если волна прошла все доступные клетки, но так и не достигла клетки финиша, значит, путь от старта до финиша проложить невозможно. После достижения волной финиша, от финиша прокладывается путь до старта и сохраняется в массиве. Алгоритм логически делится на два этапа. На первом этапе из начального элемента А распространяется в 4-х направлениях волна (рис8 а). Элемент в который пришла волна образует фронт волны. На рисунках цифрами обозначены номера фронтов волны. Каждый элемент первого фронта волны является источником вторичной волны (рис.8 б). Элементы второго фронта волны генерируют волну третьего фронта и т.д. Процесс продолжается до тех пор пока не будет достигнут конечный элемент.
На втором этапе строится сама трасса. Её построение осуществляется в соответствии со следующими правилами: - движение при построении трассы осуществляется в соответствии с выбранными приоритетами; - при движении от конечного элемента к начальному номер фронта волны (путевые координаты) должны уменьшатся. Приоритеты направления движения выбираются на стадии разработки. В зависимости от того какими задаются эти приоритеты получаются разные трассы, но длина трассы в любом случае остается одной и той же. На рис. 9 красным цветом отмечены запрещенные элементы. Серым цветом трасса после действия алгоритма; А – начальная точка, В – конечная; приоритеты движения – ВЛЕВО, ВПРАВО, ВВЕРХ, ВНИЗ. Построение трассы ведется от начальной точки к конечной. Приоритетные направления показаны зелеными стрелками.
Таким образом, наиболее известными алгоритмами, позволяющими решать задачи поиска путей являются волновой алгоритм, алгоритм А-стар и алгоритм Дейкстры, которые имеют свои достоинства и недостатки.
|
