мета-данные страницы
Загрузка не удалась. Возможно, проблемы с правами доступа?
Различия
Показаны различия между двумя версиями страницы.
Предыдущая версия справа и слеваПредыдущая версия | |||
pascal4beginners-algorithm [27/01/2012 12:13] – oca | pascal4beginners-algorithm [27/01/2012 12:48] (текущий) – oca | ||
---|---|---|---|
Строка 298: | Строка 298: | ||
Рис. 4.3. Результат работы процедуры ShowMaze() | Рис. 4.3. Результат работы процедуры ShowMaze() | ||
- | Решение лабиринта | + | |
+ | === Решение лабиринта | ||
+ | | ||
Итак, лабиринт создан и загружен в память компьютера. Теперь надо научиться его решать. Под этим термином я подразумеваю поиск пути из некоторой стартовой локации в некоторую другую (финишную). Стартовая и финишная локации в лабиринте не фиксированы: | Итак, лабиринт создан и загружен в память компьютера. Теперь надо научиться его решать. Под этим термином я подразумеваю поиск пути из некоторой стартовой локации в некоторую другую (финишную). Стартовая и финишная локации в лабиринте не фиксированы: | ||
- | Рекурсивный обход | + | |
+ | === Рекурсивный обход | ||
+ | | ||
По правде говоря, | По правде говоря, | ||
Строка 385: | Строка 389: | ||
end; end; | end; end; | ||
- | | + | На первый взгляд процедура кажется довольно громоздкой, |
- | добавить ее в «бортовой журнал»... | + | пометить |
- | Обратите внимание на «признак конца». Нам как-то надо отмечать конец | + | добавить ее в «бортовой журнал»... |
- | | + | Обратите внимание на «признак конца». Нам как-то надо отмечать конец журнала. Поскольку |
- | | + | исследуем каждую свободную дорожку Вот здесь я применил небольшую хитрость: |
- | | + | Чтобы не писать |
- | | + | исследовать_дорожку(x, |
- | | + | исследовать_дорожку(x |
- | | + | исследовать_дорожку(x, |
+ | |||
+ | исследовать_дорожку(x + 1, y) | ||
+ | |||
+ | я воспользовался циклом (не забывайте, | ||
for i := 1 to 4 do | for i := 1 to 4 do | ||
Строка 407: | Строка 415: | ||
enneaaiaaou_ai? | enneaaiaaou_ai? | ||
- | | + | Если решение найдено, |
- | | + | Обратите также внимание на строку: |
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 ... | ||
- | | + | Если текущая локация находится на краю или в углу лабиринта, |
- | + | ||
- | Рис. 4.4. Решение, | ||
- | Надеюсь, | ||
- | Итак, два | + | Рис. 4.4. Решение, найденное с помощью рекурсивного обхода |
- | 1) | + | Надеюсь, |
- | он обходит лабиринт нерационально: может пройти | + | Итак, два недостатка алгоритма лежат на поверхности: |
- | | + | |
- | полученное решение может не быть оптимальным (в примере алгоритм находит оптимальное решение, | + | |
+ | | ||
+ | |||
+ | Третий недостаток гораздо более существенный, | ||