мета-данные страницы
  •  
Загрузка не удалась. Возможно, проблемы с правами доступа?

Различия

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

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

Предыдущая версия справа и слеваПредыдущая версия
Следующая версия		Предыдущая версия
pascal4beginners-algorithm [27/01/2012 12:10] – ocapascal4beginners-algorithm [27/01/2012 12:48] (текущий) – oca
Строка 99: Строка 99:
  
 ==== Создание лабиринта ==== ==== Создание лабиринта ====
 +{{:mozgovoj.jpg|}}
  
 [[http://www.piter-press.ru/attachment.php?barcode=978594723853&at=exc&n=0| [[http://www.piter-press.ru/attachment.php?barcode=978594723853&at=exc&n=0|
Строка 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) не существует, эту «псевдолокацию» вполне можно использовать. если локация найдена — конец алгоритма
  
-    исследовать_дорожку(x, y – 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.