close

Вход

Забыли?

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

?

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

код для вставкиСкачать
 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ТЮМЕНСКИЙ ГОСУДАРСТВЕНЫЙ УНИВЕРСИТЕТ
Институт математики и компьютерных наук
Кафедра программного обеспечения
Курсовая работа по специальности
"Математическое обеспечение и администрирование информационных систем"
Тема: Нахождение кратчайшего пути между точками с учетом препятствий посредством алгоритма поиска "А*"
Выполнил:
студент группы 304
Есболов Толгат Туребаевич
Проверила:
доцент кафедры программного обеспечения
Гаврилова Наталья Михайловна
Тюмень - 2013
Оглавление
Введение3
Глава 1. Теоретическая часть4
1.1Описание алгоритма5
Глава 2. Разработка приложения6
2.1Постановка задачи6
2.2Описание типов данных6
2.3Описание процедур и функций7
2.4Блок схема главной процедуры AStar8
2.5Примеры кода9
2.6Руководство пользователя12
Заключение14
Список литературы15
Введение
Наилучшим алгоритмом для поиска оптимальных путей в различных пространствах является A* (читается как "А-звездочка"). Этот эвристический поиск сортирует все узлы по приближению наилучшего маршрута идущего через этот узел.
Алгоритм А* - алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.
Выбор данного алгоритма обусловлен тем, что он сочетает в себе учет длины предыдущего пути из алгоритма Дейкстры и эвреристику из алгоритма "лучший-первый".
Цель моей работы - разобрать алгоритм А* и разработать приложение, реализующее алгоритм А*.
Для создания приложения была выбрана среда разработки Delphi и язык программирования Object Pascal, для визуализации был выбран компонент "Image" . Глава 1. Теоретическая часть
Этот алгоритм был впервые описан в 1968 году Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. Это по сути было расширение алгоритма Дейкстры, созданного в 1959 году. Он достигал более высокой производительности (по времени) с помощью эвристики. В их работе он упоминается как "алгоритм A". Но так как он вычисляет лучший маршрут для заданной эвристики, он был назван A*.
Поиск A*- в информатике и математике, алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной).
Порядок обхода вершин определяется эвристической функцией "расстояние + стоимость" (обычно обозначаемой как f(x)). Эта функция - сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет) и эвристической оценкой расстояния от рассматриваемой вершины к конечной (обозначается как h(x)).
Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации h(x) может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками.
* Если мы можем перемещаться в четырех направлениях, в качестве эвристики стоит выбрать манхэттенское расстояние
.
* Расстояние Чебышева применяется когда к четырем направлениям добавляются диагонали:
.
* Если передвижение не ограниченно сеткой, то можно использовать евклидово расстояние по прямой:
.
Также стоит обратить внимание на то как соотносятся f(v) и h(v). Если они измеряются в разных величинах (например, g(v) - это расстояние в километрах, а h(v) - оценка времени пути в часах) А* может выдать некорректный результат.
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;
Собственно, сам тип клетки, который является записью с одним единственным полем, которое является типом TMapCellKind
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 Примеры кода
Функция Walkable(PtA,PtB):Boolean.
function Tform1.Walkable(PtA, PtB : Tpoint) :Boolean ;
var
BigX,BigY,SmallX,SmallY : integer;
iY,iX : integer;
a,b : extended;
resultat : Boolean;
begin
If pta.X > ptb.X then
begin
BigX := pta.x ;
SmallX := Ptb.x ;
end
else
begin
BigX := Ptb.x;
SmallX := pta.x;
end ;
if pta.y>ptb.Y then
begin
BigY := pta.y ;
SmallY := Ptb.y ;
end
else
begin
BigY := Ptb.y;
SmallY := pta.y;
end;
If pta.x = ptb.X then
begin
a := 0;
end
else
begin
a := (pta.y - ptb.y)/(pta.X - ptb.X);
end;
b:= pta.Y - a*pta.X;
resultat := false;
if (ptA.y <> PtB.y)and (ptA.x <> PtB.x) then
begin
while SmallX <> BigX do
begin
IX := SmallX;
Iy := round(IX*a + b) ;
SmallX := SmallX+1 ;
if (map[IX,iy].kind <> Wall) then
resultat := true;
else
begin
resultat := false ;
break;
end;
end;
end;
If resultat then
begin
while SmallY <> BigY do
begin
Iy := SmallY;
Ix := round((Iy-b)/a) ;
SmallY := SmallY+1 ;
if (map[IX,iy].kind <> Wall) then
resultat := true;
else
begin
resultat := false ;
break;
end;
end;
end;
Walkable := resultat;
end;
Функция Smaller () : TNode.Возвращает узел, имеющий самую низкую стоимость.
Function Tlist.Smaller () : TNode ;
var
Val : integer ;
Elt,Elt_smaller : TNode ;
begin
Val := -1;
Elt_smaller := nil ;
Elt := First ;
While Elt <> nil do
begin
If (Elt.Weight < Val) or (val =-1)
then
begin
Val := elt.Weight ;
elt_smaller := elt ;
end;
Elt := Elt.Elt_next;
end;
smaller := Elt_smaller;
end;
Процедура ListFinal.Создает из списка пройденных вершин, собственно, кратчайший путь, отсеивая циклы.
procedure TForm1.ListFinal();
var
elt,parent,cur : TNode;
current,bis : TNode;
begin
bis := nil ;
list_final.clear();
current := list_Closed.last;
cur:= nil;
while current <> nil do
begin
parent := current.parent;
if current.parent <> nil then
begin
bis := TNode.Create ;
bis.Parent := cur;
bis.Position:= current.Position ;
List_final.Add(bis);
end;
cur:= bis;
current := Parent;
end;
Elt := TNode.Create ;
Elt.Position:= PointA ;
elt.Parent := list_final.Last;
list_final.Add(elt);
end;
Процедура Algostar. Основная процедура, реализующая сам алгоритм.
procedure TForm1.AlgoAstar();
var
Elt : TNode ;
NextElt : Tnode ;
Stop : Boolean ;
begin
wayfound := false;
List_Closed.Clear();
List_Open.Clear() ;
List_final.Clear() ;
Elt := TNode.Create ;
Elt.Position:= PointA ;
Elt.Calcul_coup();
List_Closed.Add(Elt);
stop := False ;
While Stop = false do
begin
Deplac_possible(Elt) ;
If not List_Open.empty then
Begin
nextelt := List_Open.Smaller();
If (nextelt.Position.X = PointB.X) and (nextelt.Position.Y = PointB.Y) then
begin
Wayfound := true ;
Stop := true ;
end ;
List_Open.Del(nextelt);
list_Closed.Add(nextelt);
elt := nextelt;
end
else Stop := true ;
if wayfound then
Caption := 'Path found'
else Caption := 'Path not found';
end;
end;
Процедура Deplac_Possible. Вычисляет вес всех возможных клеток вокруг и заносит соответствующие данные в списки.
Procedure TForm1.Deplac_Possible ( Elt : TNode) ;
Begin
CalcNewNode(Elt, Point( Elt.Position.X ,elt.Position.Y+1));
CalcNewNode(Elt, Point (Elt.Position.X ,elt.Position.Y-1));
CalcNewNode(Elt, Point(Elt.Position.X+1 ,elt.Position.Y));
CalcNewNode(Elt, Point (Elt.Position.X-1 ,elt.Position.Y));
If (map[Elt.Position.X ,elt.Position.Y+1].kind <> wall) and
(map[Elt.Position.X ,elt.Position.Y-1].kind <> wall) and
(map[Elt.Position.X+1 ,elt.Position.Y].kind <> wall) and
(map[Elt.Position.X-1 ,elt.Position.Y].kind <> wall) Then
begin
CalcNewNode(Elt, Point( Elt.Position.X+1 ,elt.Position.Y+1));
CalcNewNode(Elt, Point (Elt.Position.X+1 ,elt.Position.Y-1));
CalcNewNode(Elt, Point(Elt.Position.X-1,elt.Position.Y+1));
CalcNewNode(Elt, Point (Elt.Position.X-1 ,elt.Position.Y-1));
end;
end;
2.6 Руководство пользователя
Пользователю предоставляется возможность выбрать точки начала и конца пути(левая и правая кнопки мыши соответственно)
Расставлять препятствия нажатием ctrl и (левая кнопка - поставить препятствие, правая - убрать препятствие). Запускать расчет пути не требуется.
Заключение
Существуют ситуации, в которых A* не может работать хорошо по различным причинам. Требования работы в реальном масштабе времени для некоторых игр, плюс ограничения по памяти и процессорному времени в некоторых из них, создают проблемы для хорошей работы даже для А*. Большая карта может требовать тысячи ячеек в списках Open и Closed, для чего может оказаться недостаточно места. Даже если для них окажется достаточно памяти, алгоритмы для работы с этими списками могут оказаться неэффективными.
Качество работы алгоритма сильно зависит от качества эвристического приближения h(n). Если h близко к истинной стоимости оставшегося пути, то эффективность будет очень высокой; с другой стороны, если h будет слишком низким, то это отразится на эффективности в худшую сторону. На самом деле, алгоритм Дийкстры - это A* с h установленной в ноль для всех узлов -это конечно будет допустимым приближением и этот алгоритм найдет путь, но это будет очень медленно.
В результате написания курсовой работы были получены знания об алгоритме А*, написана программа, визуально демонстрирующая алгоритм.
Данный алгоритм остается актуальным и сегодня, и находит практическое применение во множестве прикладных задач. Список литературы
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
2
Документ
Категория
Рефераты
Просмотров
36
Размер файла
183 Кб
Теги
есболов, курсовая
1/--страниц
Пожаловаться на содержимое документа