close

Вход

Забыли?

вход по аккаунту

?

Курсовая Есболов Т.

код для вставкиСкачать
 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ТЮМЕНСКИЙ ГОСУДАРСТВЕНЫЙ УНИВЕРСИТЕТ
Институт математики и компьютерных наук
Кафедра программного обеспечения
Курсовая работа по специальности
"Математическое обеспечение и администрирование информационных систем"
Тема: Алгоритм А*
Выполнил:
студент группы 304
Есболов Толгат
Проверила:
кафедра программного обеспечения
Тюмень - 2013
Оглавление
Введение3
Глава 1. Теоретическая часть4
1.1Описание алгоритма4
Глава 2. Разработка приложения6
2.1Постановка задачи6
2.2Описание типов данных6
2.3Описание процедур и функций6
2.4Блок схема главной процедуры AStar6
2.5Руководство пользователя6
Заключение6
Список литературы6
Введение
Алгоритм А* - алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
Цель моей работы - разобрать алгоритм А* и разработать приложение, реализующее алгоритм А*.
Для создания приложения была выбрана среда разработки Delphi и язык программирования Object Pascal.
Глава 1. Теоретическая часть
Этот алгоритм был впервые описан в 1968 году Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. Это по сути было расширение алгоритма Дейкстры, созданного в 1959 году. Он достигал более высокой производительности (по времени) с помощью эвристики. В их работе он упоминается как "алгоритм A". Но так как он вычисляет лучший маршрут для заданной эвристики, он был назван A*.
Поиск A*- в информатике и математике, алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной).
Порядок обхода вершин определяется эвристической функцией "расстояние + стоимость" (обычно обозначаемой как f(x)). Эта функция - сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет) и эвристической оценкой расстояния от рассматриваемой вершины к конечной (обозначается как h(x)).
Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации h(x) может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками.
* Если мы можем перемещаться в четырех направлениях, в качестве эвристики стоит выбрать манхэттенское расстояние
.
* Расстояние Чебышева применяется когда к четырем направлениям добавляются диагонали:
.
* Если передвижение не ограниченно сеткой, то можно использовать евклидово расстояние по прямой:
.
Также стоит обратить внимание на то как соотносятся и . Если они измеряются в разных величинах (например, - это расстояние в километрах, а - оценка времени пути в часах) А* может выдать некорректный результат.
1.1 Описание алгоритма
A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Как и все информированные алгоритмы поиска, он просматривает сначала те маршруты, которые "кажутся" ведущими к цели. От жадного алгоритма (который тоже является алгоритмом поиска по первому лучшему совпадению) его отличает то, что при выборе вершины он учитывает, помимо прочего, весьпройденный до неё путь (составляющая g(x) - это стоимость пути от начальной вершины, а не от предыдущей, как в жадном алгоритме). В начале работы просматриваются узлы, смежные с начальным; выбирается тот из них, который имеет минимальное значение f(x), после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых (листовых) вершин графа ("множеством частных решений"), которое размещается в очереди с приоритетом. Приоритет пути определяется по значению f(x) = g(x) + h(x). Алгоритм продолжает свою работу до тех пор, пока значение f(x) целевой вершины не окажется меньшим, чем любое значение в очереди (либо пока всё дерево не будет просмотрено). Из множественных решений выбирается решение с наименьшей стоимостью.
Чем меньше эвристика h(x), тем больше приоритет (поэтому для реализации очереди можно использовать сортирующие деревья).
Глава 2. Разработка приложения
1. 2.1 Постановка задачи
Разработать приложение, наглядно демонстрирующее работу алгоритма. 2 2.1 2.2 Описание типов данных
1. TMapCellKind = (floor, wall);
Перечислимый тип, показывающий, является ли клетка препятствием или она свободна для перемещения.
2. TMapCell = record
kind: TMapCellKind;
end;
Собственно, сам тип клетки, который является записью с 1 единственным полем, которое является типом 1
3. TNode = class
Weight : integer ;
Coup_eval: integer ; Coup_move : integer ;
Elt_next : TNode ; Elt_pred : TNode ; Parent : TNode ;
Position : TPoint ;
Тип узла, в котором имеется вес, функции g,h, из которых вычисляется вес, ссылки на предыдущий и следующий узлы, ссылка на родительский узел, координаты в сетке.
4. TList = class
First : Tnode ;
Last : Tnode ;
Список из пункта 3.
2.3 Описание процедур и функций
1 function Walkable(PtA, PtB : Tpoint) :Boolean ;
Функция проверяет наличие препятствий между клетками. 2 procedure drawMap();
Отрисовка карты.
3 procedure drawStart();
Отрисовка начала пути.
4 procedure drawEnd();
Отрисовка конца пути.
5 procedure drawClear;
Очистка экрана.
6 procedure drawCells();
Отрисовка сетки.
7 procedure drawCell(x, y: Integer);
Отрисовка 1 клетки.
8 procedure drawWay();
Отрисовка пути.
9 procedure grid();
Отрисовка решетки.
10 procedure initLists();
Инициализация списков открытых, закрытых вершин, а также списка, содержащего итоговый кратчайший путь.
11 procedure ListFinal();
Отсеивание циклов в списке закрытых вершин и занесение их в список итогового кратчайшего пути.
12 function CalcNewNode(parent: TNode; position: TPoint): integer;
Рассчёт веса данной клетки от начальной.
13 Procedure Deplac_Possible ( Elt : TNode) ;
Рассчитать вес всех клеток вокруг.
14 Procedure AlgoAStar ( ) ;
2.4 Блок схема главной процедуры AStar
2.5 Руководство пользователя
Пользователю предоставляется возможность выбрать точки начала и конца пути(левая и правая кнопки мыши), а также расставить препятствия при нажатии ctrl или shift(левая кнопка - поставить препятствие, правая - убрать препятствие). Запускать расчет пути не требуется.
Заключение
В результате написания курсовой работы были получены знания об алгоритме А*, написана программа, демонстрирующая алгоритм.
Данный алгоритм остается актуальным и сегодня, и находит практическое применение во множестве прикладных задач. Список литературы
1. Лорьер Ж.-Л. Системы искусственного интеллекта / Пер. с фр. и ред. В. Л. Стефанюка. - М.: Мир, 1991. - С. 238-244. - 20 000 экз, экз. - ISBN 5-03-001408-X
2. Рассел С. Дж., Норвиг, П. Искусственный интеллект: современный подход = Artificial Intelligence: A Modern Approach / Пер. с англ. и ред. К. А. Птицына. - 2-е изд.. - М.: Вильямс, 2006. - С. 157-162. - 3 000 экз, экз. - ISBN 5-8459-0887-6
3. Нильсон Н. Искусственный интеллект: методы поиска решений = Problem-solving Methods in Artificial Intelligence / Пер. с англ. В. Л. Стефанюка; под ред. С. В. Фомина. - М.: Мир, 1973. - С. 70 - 80.
4. Dechter, R., Pearl, J. Generalized best-first search strategies and the optimality of A* // Journal of the ACM. - 1985. - Т. 32. - № 3. - С. 505 - 536.
5. Hart P. E., Nilsson, N. J., Raphael, B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths // IEEE Transactions on Systems Science and Cybernetics SSC4. - 1968. - № 2. - С. 100 - 107.
6. Hart P. E., Nilsson, N. J., Raphael, B. Correction to "A Formal Basis for the Heuristic Determination of Minimum Cost Paths" // SIGART Newsletter. - 1972. - Т. 37. - С. 28 - 29.
7. Pearl J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. - Addison-Wesley, 1984. - ISBN 0-201-05594-5
Документ
Категория
Рефераты
Просмотров
71
Размер файла
50 Кб
Теги
есболов, курсовая
1/--страниц
Пожаловаться на содержимое документа