> 1 <

Автор Сообщение

darkside

Members


Статус

3 сообщений

Где: Russia
Род занятий:
Возраст:

#150   2008-11-09 22:02 GMT+3 часа(ов)      
помогите плз решить эту задачку
При записи лабиринта его комнаты идентифицируются номерами, вход и выход кодируются знаками IN и OUT, а также указываются все пары комнат, соединенных проходом например -((1 2) (2 4) (IN 1) (IN 3) (1 3) (4 5) (5 OUT))

отредактировал(а) darkside: 2008-11-09 22:14 GMT+3 часа(ов)

_lee

Members


Статус

69 сообщений

Где: Russia
Род занятий:
Возраст:

#161   2008-11-12 16:23 GMT+3 часа(ов)      
Строится граф, представляющий лабиринт.
Далее стандартные алгоритмы поиска по графам (в глубину или ширину)

darkside

Members


Статус

3 сообщений

Где: Russia
Род занятий:
Возраст:

#162   2008-11-22 23:15 GMT+3 часа(ов)      
 
(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)))
 

хз вообщем как строить граф...вообщем нашел тупое решение этой задачи
Вопрос как найти оптимальный путь из лабиринта?

dmitry_vk

Members


Статус

33 сообщений
http://dmitry-vk.livejournal.com/
Где: Russia Казань
Род занятий:
Возраст: 30

#164   2008-11-23 14:49 GMT+3 часа(ов)      
Смотря что понимается под оптимальным. Если оптимальный значит, что минимальное число переходов, то можно пользоваться поиском в ширину.

darkside

Members


Статус

3 сообщений

Где: Russia
Род занятий:
Возраст:

#165   2008-11-23 15:05 GMT+3 часа(ов)      
Цитата
dmitry_vk :
Смотря что понимается под оптимальным. Если оптимальный значит, что минимальное число переходов, то можно пользоваться поиском в ширину.


что значит поиск в ширину?можно какойнить пример?

dmitry_vk

Members


Статус

33 сообщений
http://dmitry-vk.livejournal.com/
Где: Russia Казань
Род занятий:
Возраст: 30

#166   2008-11-23 17:56 GMT+3 часа(ов)      
см. http://ru.wikipedia.org/wiki/Поиск_в_ширину
А пример (не очень хороший) вот:
 
(defun search-path-breadth (graph start goal)
"Searches the path in the GRAPH from START to GOAL.
GRAPH is the connectivity list for the graph."

(let (q visited paths)
(labels ((q-put (v) (push v q)) ; puts the V into queue
(q-pop () (prog1 (car (last q))
(setf q (nbutlast q)))) ;gets the vertex from the queue
(q-empty? () (null q)) ;checks if queue is empty
(visited? (v) (not (null (find v visited)))) ;checks if we have been in V already
(adjacent-vertices (v) (cdr (find v graph :key #'car))) ;returns vertices that are immediately reachable from v
(path-to (v) (cdr (find v paths :key #'car))) ;returns recorded path to v
(visit (v)
(push v visited)
(let ((p (path-to v)))
(loop
for v2 in (adjacent-vertices v)
do (unless (visited? v2)
(push v2 visited)
(push (append (list v2) p (list v2)) paths)
(q-put v2))))))
(q-put start)
(push (list start start) paths)
(loop while (not (q-empty?)) do (visit (q-pop)))
(path-to goal))))
 
(search-path-breadth '((a b c) (b d) (c e) (d e)) 'a 'e)
=>
(A C E)
 

alice

Members


Статус

3 сообщений

Где: France
Род занятий:
Возраст:

#340   2009-04-12 16:21 GMT+3 часа(ов)      
помогите плз написать функцию,
которая проверяет, если есть дорога из комнаты ie в комнату im.И показать этот путь, если он существует. (LABIRINT L ie im)
> 1 <


Онлайн :

0 пользователь(ей), 15 гость(ей) :




Реклама на сайте: