Автор Тема: ЛИСП алгоритм поиска выхода из лабиринта  (Прочитано 4213 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Kitty

  • Коллежский регистратор
  • *
  • Сообщений: 3
  • Репутация: 0
Может кто-то писал ?Поделитесь пожалуйста примером
« Последнее редактирование: ѕЪвпСам 31, 2008, 05:02:03 pm от Kitty »

Оффлайн aureliano

  • Надворный советник
  • *****
  • Сообщений: 400
  • Репутация: 19
Re: ЛИСП алгоритм поиска выхода из лабиринта
« Ответ #1 : ѕЪвпСам 31, 2008, 05:25:48 pm »
На Лиспе никогда не писал, а алгоритм самый тупой знаю: всегда держаться правой стороны (или левой, это не принципиально, главное одной и той же) и обязательно найдёшь выход, если он вообще есть. Но алгоритм этот далеко не самый оптимальный, т. к. при наличии нескольких путей всегда будут находиться самые обходные. :-)

Оффлайн Kitty

  • Коллежский регистратор
  • *
  • Сообщений: 3
  • Репутация: 0
Re: ЛИСП алгоритм поиска выхода из лабиринта
« Ответ #2 : ѕЪвпСам 31, 2008, 05:57:43 pm »
На Лиспе никогда не писал, а алгоритм самый тупой знаю: всегда держаться правой стороны (или левой, это не принципиально, главное одной и той же) и обязательно найдёшь выход, если он вообще есть. Но алгоритм этот далеко не самый оптимальный, т. к. при наличии нескольких путей всегда будут находиться самые обходные. :-)
дело в том что не понятно где тут правая стороа где левая)))))
дело в том что у меня лабиринт задется таким вот бразом
((1 2) (2 4) (IN 1) (IN 3) (1 3) (4 5) (5 OUT))
где числа-номера комнат
а если два числа находятся в оних скобках ,то значит они соеденины между собой

Оффлайн aureliano

  • Надворный советник
  • *****
  • Сообщений: 400
  • Репутация: 19
Re: ЛИСП алгоритм поиска выхода из лабиринта
« Ответ #3 : ЅЮпСам 01, 2008, 07:17:47 pm »
Дык я же говорю, что это не принципиально, где право, а где лево. Главное -- держаться одной стороны. В твоём случае можно условно считать меньшие номера более левыми, а большие -- более правыми (IN можно считать -бесконечностью (самым левым), а OUT -- +бесконечностью (самым правым)). После чего ищещь все элементы, начинающиеся с IN и ставишь их в начало, а далее создаёшь структуру типа B-дерева, но с возможностью зацикливания (в отличие от канонического дерева), -- для обхода это не важно, а вот при создании контейнера надо учитывать и не использовать алгоритм, который на этом может зациклиться. При чём каждый узел может иметь от 0 до 2 листьев: 1 лист -- это одна из комнат, с которой есть связь (если такая комната есть), другой -- комната с тем же номером, если она связана ещё с какой-то комнатой. Т. е. вместо ((1 2) (2 4) (IN 1) (IN 3) (1 3) (4 5) (5 OUT)) ты получишь примерно такую структуру: IN (IN (3) 1 (1 (3) 2 (4 (5 (OUT))))) (не знаю, насколько это грамотно с точки зрения лиспа, но вложенными скобками я отмечаю пути, которых на каждом шаге не больше 2, при чём 2-й всегда та же комната, если из неё более 1 выхода). А дальше идёшь вперёд, при возможности выбора выбираешь большее (ака правое) число, если зашёл в тупик -- поворачиваешь назад и при первой же развилке выбираешь уже меньшее (ака левое) число, после чего опять всё время выбираешь большее. Для приведённого примера путь будет таким: IN -> 1 -> 2 -> 4 -> 5 -> OUT (в данном случае повезло, хотя если в качестве правой стороны мы выберем меньшее число, то путь удлиннится: IN -> IN -> 3 -> IN -> 1 -> 1 -> 3 -> 1 -> 2 -> 4 -> 5 -> OUT).

PS: Только самый первый IN тебе надо пометить особо, как ROOT-IN, т. к. возврат туда будет обозначать отсутствие выхода (или отсутствие пути к выходу).
« Последнее редактирование: ЅЮпСам 01, 2008, 07:26:42 pm от aureliano »

Оффлайн Kitty

  • Коллежский регистратор
  • *
  • Сообщений: 3
  • Репутация: 0
Re: ЛИСП алгоритм поиска выхода из лабиринта
« Ответ #4 : ЅЮпСам 22, 2008, 08:21:34 pm »
(defun find_room (point labirint)                                                                             
  (cond ((null labirint) nil)                                                                                         
        ((eql (caar labirint) point) (second (car labirint)))                                                         
        (t (find_room point (cdr labirint)))))

(defun find_path_r (labyrinth path)
  (let ((room (find_room (car path) labyrinth)))
    (case room
    ((nil) nil)
    ((out) (nreverse (cons 'out path)))
    (t (find_path_r labyrinth (cons room path))))))

(defun find_path (labyrinth)
   (find_path_r labyrinth (cons 'in nil)))
вот моя программа)))))))подскажите пожалуйста как сделать так чтобы она выдавала самый короткий путь в лабиринте?)))))

Оффлайн aureliano

  • Надворный советник
  • *****
  • Сообщений: 400
  • Репутация: 19
Re: ЛИСП алгоритм поиска выхода из лабиринта
« Ответ #5 : ЅЮпСам 28, 2008, 09:57:53 pm »
К сожалению, мне не только неизвестен такой алгоритм, но я ещё и лиспа не знаю, так что данная программа для меня -- что китайская грамота. :-) Но если использовался предложенный мною алгоритм, то первое, что приходит в голову на вскидку, это попробовать вложить его в другой, рекурсивный алгоритм:

1.     прошли лабиринт по заданному алгоритму

2. нашли выход                          не нашли
           |                                                |
          \|/                                              \|/
     отсекаем                                   конец
     последнюю комнату
     на этом пути и вызываем алгоритм рекурсивно.
           |                                               |
          \|/                                             \|/
 не нашли выход                         нашли ---------+
        |                                            |                      |
       \|/                                          \|/                    \|/
     конец                                  он короче      длиннее --> передаём в рекурсивном вызове
                                                     |                                       длину кратчайшего пути,
                                                    \|/                                      флаг не устанавливаем.
                                           устанавливаем
                                           флаг, что нашли самый
                                           короткий путь и продолжаем.
                                           рекурсию, передавая длину этого
                                           пути.

Когда все пути исчерпаны (т. е. закрыто всё, откуда можно выйти), двигаемся вверх return'ами до первого фрагмента стека, где установлен флаг наикратчайшести, этот
путь и возвращаем.


Над алгоритмом особо не думал и не проверял, поэтому не исключены подводные камни. И ещё, касательно первого алгоритма (в моём сообщении от 1 ноября): он правилен только для двумерных лабиринтов, если же возможно также движение вверх и вниз, то он работать не будет.

Оффлайн gigauser

  • Статский советник
  • *****
  • Сообщений: 976
  • Репутация: 20
  • Banned
Re: ЛИСП алгоритм поиска выхода из лабиринта
« Ответ #6 : ЅЮпСам 29, 2008, 12:03:14 am »
"\|/" - пикантный значок)
по сабжу: рисуем матрицу, стенки обозначаем цифрой 1, проход - нулем, оптимальный путь будет с наименьшей суммой в конце, а алгоритм наименьшей суммы известен)
Banned