Различия

Здесь показаны различия между двумя версиями данной страницы.

Ссылка на это сравнение

Предыдущая версия справа и слева Предыдущая версия
pascal4beginners-algorithm [27/01/2012 12:13]
Олег Альбертович Скворцов
pascal4beginners-algorithm [27/01/2012 12:48] (текущий)
Олег Альбертович Скворцов
Строка 298: Строка 298:
  
     Рис. 4.3. Результат работы процедуры ShowMaze()     Рис. 4.3. Результат работы процедуры ShowMaze()
-    Решение лабиринта+    ​ 
 +    === Решение лабиринта ​=== 
 +    ​
     Итак, лабиринт создан и загружен в память компьютера. Теперь надо научиться его решать. Под этим термином я подразумеваю поиск пути из некоторой стартовой локации в некоторую другую (финишную). Стартовая и финишная локации в лабиринте не фиксированы:​ мы можем попытаться решить лабиринт для любой пары локаций,​ какой только захотим. Полезно рассмотреть также задачу не просто поиска какого-то пути, а пути самого короткого. Мы остановимся на двух популярных методах решения лабиринтов:​ рекурсивном обходе и алгоритме волновой трассировки.     Итак, лабиринт создан и загружен в память компьютера. Теперь надо научиться его решать. Под этим термином я подразумеваю поиск пути из некоторой стартовой локации в некоторую другую (финишную). Стартовая и финишная локации в лабиринте не фиксированы:​ мы можем попытаться решить лабиринт для любой пары локаций,​ какой только захотим. Полезно рассмотреть также задачу не просто поиска какого-то пути, а пути самого короткого. Мы остановимся на двух популярных методах решения лабиринтов:​ рекурсивном обходе и алгоритме волновой трассировки.
-    Рекурсивный обход+    ​ 
 +    === Рекурсивный обход ​=== 
 +    ​
     По правде говоря,​ у этого метода есть только одно достоинство — он простой. А еще он очень популярный (как и далеко не лучшая «пузырьковая» сортировка).     По правде говоря,​ у этого метода есть только одно достоинство — он простой. А еще он очень популярный (как и далеко не лучшая «пузырьковая» сортировка).
  
Строка 385: Строка 389:
     end; end;     end; end;
  
-    ​На первый взгляд процедура кажется довольно громоздкой,​ но если присмотреться,​ то становится ясно, что ядро у нее не такое уж большое. Для реализации процедуры мне потребовались две дополнительные функции:​ CanGo() и Solve(). Функция CanGo() определяет,​ есть или нет стены между локациями (x, y) и (x + dx, y + dy) (то есть можно ли пройти из одной в другую). При этом предполагается,​ что локации находятся по соседству — первая расположена сверху,​ слева, снизу или справа от второй. Функция Solve() более интересна и сложна. Ей передается три параметра — координаты текущей локации и номер шага. Номер нужен для того, чтобы знать, в какую строчку «бортового журнала» записывать текущее движение. Дальше все происходит по алгоритму,​ о котором мы говорили выше: ​пометить текущую локацию как посещенную+На первый взгляд процедура кажется довольно громоздкой,​ но если присмотреться,​ то становится ясно, что ядро у нее не такое уж большое. Для реализации процедуры мне потребовались две дополнительные функции:​ CanGo() и Solve(). Функция CanGo() определяет,​ есть или нет стены между локациями (x, y) и (x + dx, y + dy) (то есть можно ли пройти из одной в другую). При этом предполагается,​ что локации находятся по соседству — первая расположена сверху,​ слева, снизу или справа от второй. Функция Solve() более интересна и сложна. Ей передается три параметра — координаты текущей локации и номер шага. Номер нужен для того, чтобы знать, в какую строчку «бортового журнала» записывать текущее движение. Дальше все происходит по алгоритму,​ о котором мы говорили выше: ​
  
-    добавить ее в «бортовой журнал»...+пометить ​текущую локацию как посещенную
  
-    Обратите внимание на «признак конца». Нам как-то надо отмечать конец ​журнала. Поскольку локации с координатами (-1, -1) не существует,​ эту «псевдолокацию» вполне можно использоватьесли локация найдена — конец алгоритма+добавить ее в «бортовой журнал»...
  
-    ​исследуем каждую свободную дорожку Вот здесь я применил ​небольшую хитрость: всего из каждой локации ​может вести максимум четыре разные ​дорожки. Первая ​начинается от соседней ​сверху локации, вторая — от левой, третья — от нижней, а четвертая — от правой. Чтобы не писать четыре раза+Обратите внимание на «признак конца». Нам как-то надо отмечать конец журнала. Поскольку ​локации с координатами (-1, -1) не существует, эту «псевдолокацию» вполне можно использовать. если локация ​найдена — конец ​алгоритма
  
-    ​исследовать_дорожку(xy – 1)+исследуем каждую свободную дорожку Вот здесь я применил небольшую хитрость: ​всего из каждой локации может вести максимум четыре разные ​дорожки. Первая начинается от соседней сверху локациивторая — от левой, третья — от нижней,​ а четвертая — от правой. ​
  
-    ​исследовать_дорожку(x – 1, y)+Чтобы не писать ​четыре раза
  
-    ​исследовать_дорожку(x,​ y 1)+исследовать_дорожку(x,​ y – 1)
  
-    ​исследовать_дорожку(x ​1, y)+исследовать_дорожку(x ​– 1, y)
  
-    ​я воспользовался циклом (не забывайте,​ что исследовать_дорожку() — это не вызов процедуры,​ а фрагмент из нескольких строк кода, поэтому экономия заметная):​+исследовать_дорожку(x,​ y + 1) 
 + 
 +исследовать_дорожку(x + 1, y) 
 + 
 +я воспользовался циклом (не забывайте,​ что исследовать_дорожку() — это не вызов процедуры,​ а фрагмент из нескольких строк кода, поэтому экономия заметная):​
  
     for i := 1 to 4 do     for i := 1 to 4 do
Строка 407: Строка 415:
     enneaaiaaou_ai?​i?​eo(x + dx[i], y + dy[i])     enneaaiaaou_ai?​i?​eo(x + dx[i], y + dy[i])
  
-    ​Если решение найдено,​ то работа алгоритма заканчивается;​ в противном случае текущая локация помечается как непосещенная и происходит выход из процедуры. Обратите внимание,​ что каждый шаг в лабиринте — это рекурсивный вызов. Такое решение позволяет легко вернуться на шаг назад (помните,​ это важная часть алгоритма) — для этого надо всего лишь выйти из функции,​ сообщив при этом вызывающей функции,​ что решение не найдено. Главная процедура делает не так уж и много работы:​ она инициализирует массивы,​ затем вызывает Solve() и рисует на экране полученное решение (рис. 4.4). В примере я выбрал верхнюю левую локацию лабиринта как стартовую,​ а верхнюю правую — как финишную.+Если решение найдено,​ то работа алгоритма заканчивается;​ в противном случае текущая локация помечается как непосещенная и происходит выход из процедуры. Обратите внимание,​ что каждый шаг в лабиринте — это рекурсивный вызов. Такое решение позволяет легко вернуться на шаг назад (помните,​ это важная часть алгоритма) — для этого надо всего лишь выйти из функции,​ сообщив при этом вызывающей функции,​ что решение не найдено. Главная процедура делает не так уж и много работы:​ она инициализирует массивы,​ затем вызывает Solve() и рисует на экране полученное решение (рис. 4.4). В примере я выбрал верхнюю левую локацию лабиринта как стартовую,​ а верхнюю правую — как финишную.
  
-    ​Обратите также внимание на строку:​+Обратите также внимание на строку:​
  
     if CanGo(x, y, dx[i], dy[i]) and     if CanGo(x, y, dx[i], dy[i]) and
Строка 415: Строка 423:
     not Visited[x + dx[i], y + dy[i]] then ...     not Visited[x + dx[i], y + dy[i]] then ...
  
-    ​Если текущая локация находится на краю или в углу лабиринта,​ числа x + dx[i] и y + dy[i] могут оказаться некорректными индексами массива Visited (то есть попросту указывать на локацию,​ лежащую за границами лабиринта). Ошибки не возникает потому,​ что Delphi по умолчанию использует так называемую сокращенную схему вычисления логических выражений:​ если значение CanGo() оказалось равно false, нет нужды вычислять правую часть выражения (после and) — и так ясно, что значение всего выражения будет равно false. Если функция CanGo() определит,​ что мы пытаемся выйти за пределы лабиринта,​ она, естественно,​ вернет false, поскольку весь лабиринт ограничен стеной;​ следовательно,​ правая часть выражения в таких случаях никогда не будет вычисляться. Мы будем пользоваться этой особенностью Delphi и в дальнейшем. +Если текущая локация находится на краю или в углу лабиринта,​ числа x + dx[i] и y + dy[i] могут оказаться некорректными индексами массива Visited (то есть попросту указывать на локацию,​ лежащую за границами лабиринта). Ошибки не возникает потому,​ что Delphi по умолчанию использует так называемую сокращенную схему вычисления логических выражений:​ если значение CanGo() оказалось равно false, нет нужды вычислять правую часть выражения (после and) — и так ясно, что значение всего выражения будет равно false. Если функция CanGo() определит,​ что мы пытаемся выйти за пределы лабиринта,​ она, естественно,​ вернет false, поскольку весь лабиринт ограничен стеной;​ следовательно,​ правая часть выражения в таких случаях никогда не будет вычисляться. Мы будем пользоваться этой особенностью Delphi и в дальнейшем.
- +
  
-    Рис. 4.4. Решение,​ найденное с помощью рекурсивного обхода 
  
-    Надеюсь,​ принцип работы рекурсивного обхода более или менее ясен. Возможно,​ стоило подробнее на нем остановиться и постараться объяснить все тонкости более доходчиво (если алгоритм рекурсивен,​ он уже не слишком прост — по крайней мере, для меня), однако мне просто жаль на него времени. Сейчас я подробно распишу недостатки рекурсивного обхода,​ а потом мы рассмотрим куда более передовой алгоритм волновой трассировки. 
  
-    Итак, два ​недостатка алгоритма лежат на поверхности:+Рис. 4.4. Решение, найденное с помощью рекурсивного обхода
  
-    1)+Надеюсь,​ принцип работы рекурсивного обхода более или менее ясен. Возможно,​ стоило подробнее на нем остановиться и постараться объяснить все тонкости более доходчиво (если алгоритм рекурсивен,​ он уже не слишком прост — по крайней мере, для меня), однако мне просто жаль на него времени. Сейчас я подробно распишу недостатки рекурсивного обхода,​ а потом мы рассмотрим куда более передовой алгоритм волновой трассировки.
  
-    он обходит лабиринт нерационально: может пройти ​достаточное ​количество времени, прежде чем решение будет найдено;+Итак, два недостатка алгоритма лежат на поверхности:
  
-    ​2)+    ​1   он обходит лабиринт нерационально:​ может пройти достаточное количество времени,​ прежде чем решение будет найдено;​
  
-    полученное решение может не быть оптимальным (в примере алгоритм находит оптимальное решение,​ но в приведенном лабиринте другого решения просто нет). Третий недостаток гораздо более существенный,​ хотя и проявляется он не всегда. Посмотрите на лабиринт,​ изображенный на рис. 4.5.+    ​2)    ​полученное решение может не быть оптимальным (в примере алгоритм находит оптимальное решение,​ но в приведенном ​  
 +    ​лабиринте другого решения просто нет). ​ 
 +     
 +Третий недостаток гораздо более существенный,​ хотя и проявляется он не всегда. Посмотрите на лабиринт,​ изображенный на рис. 4.5.
  
  
CC Attribution-Noncommercial 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0