Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> задачка коммивояжера, на Lisp 
:(
    Опции темы
Гость_Olga
Дата 30.11.2005, 22:51 (ссылка) | (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered
Необходимо решить задачу коммивояжера на Lisp.
Коммивояжер должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город.
Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь коммивояжера был кратчайшим?
Выдавать программа должна кротчайший путь коммивояжера (список пройденных городов) и его длину.
Для нахождения длины пути велели задавать матрицу городов в виде списка расстояний между городами. Допустим есть три города А В С , тогда надо задать список расстояний от одного города до каждого из остальных ((0 3 9) (3 0 1) (9 1 0)).
АВС
А 039
В 301
С 910
На входе у нас есть два списка: список городов и список расстояний между городами.
Надо реализовывать эвристический алгоритм поиска, с эвристикой `идти в ближайший город`. Решать задачу надо с помощью рекурсии.
Пожалуйста помогите. Заранее спасибо.
  Вверх
SET P
Дата 1.12.2005, 12:03 (ссылка) | (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered
просто, когда человек хочет решить задачу, он сначала делиться своими мыслями по реализации и рассказывает какие у него возникли трудности... в общем, активно что-то делает, а не ждёт когда за него всё сделают другие. люди, знающие LISP, здесь есть. Вам наверняка помогут.

а "на слабо" лучше брать в разделе Центр помощи
  Вверх
svg
Дата 2.12.2005, 01:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 53
Регистрация: 13.4.2005

Репутация: 2
Всего: 18
По зубам, мотивации нет работать за индивида/индивидку, который сам
никаких усилий не приложил.

Напишите Деду Морозу, найдете решение в чулке под кроватью.
PM MAIL   Вверх
Гость_Olga
Дата 2.12.2005, 18:12 (ссылка) | (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered
С чего Вы взяли, что я ничего не делаю и не приложила ни каких усилий. Просто давать какие-то рекомендации по решению я не могу, т.к не знаю как решать. А давать свои наработки (неработающие) не имеет смысла, тюкю разбираться в чужом коде зачастую весьма трудно (это я уже один раз пробовала).
То, что я прошу решить задачку еще не означает, что я "халявщица", поэтому прошу не обижать.
  Вверх
Andrey1
Дата 2.12.2005, 18:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 621
Регистрация: 27.2.2004
Где: Moscow

Репутация: нет
Всего: 5
Цитата
С чего Вы взяли, что я ничего не делаю и не приложила ни каких усилий. Просто давать какие-то рекомендации по решению я не могу, т.к не знаю как решать. А давать свои наработки (неработающие) не имеет смысла, тюкю разбираться в чужом коде зачастую весьма трудно (это я уже один раз пробовала).
То, что я прошу решить задачку еще не означает, что я "халявщица", поэтому прошу не обижать.

Не хочу, конечно, подливать масло в огонь..., но хочу заметить, что действительно, люди сюда приходят не чтобы озадачеваться. А скорее, чтобы расслабиться, пообщаться и узнать что-нибудь интересное.


--------------------
Созерцание и мудрость - едины. Соцерцание - это основа мудрости, а мудрость - это функция (т.е. умение использовать) созерцания.
из сутры помоста шестого патриарха Хуэйнена
PM MAIL WWW ICQ   Вверх
Guest
Дата 3.12.2005, 00:00 (ссылка) | (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered
Какие Вы здесь все вредные
  Вверх
DENNN
Дата 5.12.2005, 10:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник Клуба
Сообщений: 3878
Регистрация: 27.3.2002
Где: Москва

Репутация: нет
Всего: 43
Ага такие вот прямо вредные-вредные.
PM ICQ   Вверх
AntonSaburov
Дата 5.12.2005, 14:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Штурман
****


Профиль
Группа: Модератор
Сообщений: 5658
Регистрация: 2.7.2002
Где: Санкт-Петербург

Репутация: нет
Всего: 118
Видимо здесь нет людей, которые пишут на LISP (ну не популярный это язык). Можно конечно изобразить умное лицо, но если нет возможностей помочь - значит нет. Надо брать ноги в руки - и вперед. Можем пожелать удачи и терпения.


--------------------
Мои проекты для Винграда
PM MAIL WWW ICQ   Вверх
Гость_Olga
Дата 5.12.2005, 16:58 (ссылка) | (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered
Ну тогда скажите пожалуйста как удалить свою тему
  Вверх
svg
Дата 5.12.2005, 19:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 53
Регистрация: 13.4.2005

Репутация: 2
Всего: 18
Вот решение.
Код

(defparameter *towns*
  '(a b c d e f))

(defparameter *path-matrix*
  (make-array (list (length *towns*) (length *towns*))
              :initial-element 0))

(defun fill-path-matrix (&optional (max-distance 10))
  "Fill *path-matrix* randomly"
  (labels ((gen-dist ()
             (let ((d (random max-distance)))
               (if (> d 0) d (gen-dist))))
           (idx-permutations (current rest)
             (setf (aref *path-matrix* current current) 0)
             (when rest
               (dolist (idx rest)
                 (let ((dist (gen-dist)))
                   (setf (aref *path-matrix* current idx) dist
                         (aref *path-matrix* idx current) dist)))
               
               (idx-permutations (car rest) (cdr rest)))))
    (let (idxs)
      (dotimes (i (length *towns*))
        (push i idxs))
      (setf idxs (nreverse idxs))
      (idx-permutations (car idxs) (cdr idxs)))))

(defun salesman-problem (&rest towns)
  (assert (not (set-difference towns *towns*)) ()
          "don't know about these towns ~a" (set-difference towns *towns*))
  (labels (;; distance between two towns
           (dist (from to)
             (aref *path-matrix* from to))
           ;; nearest town according to heuristics
           (nearest-town (from candidates)
             (car (sort (copy-list candidates)
                        #'(lambda (a b) (< (dist from a) (dist from b))))))
           (find-path (town candidates)
             (if (not candidates)
                 nil ; last town
                 (let ((next (nearest-town town candidates)))
                   (cons next (find-path next (delete next candidates)))))))
    (let* (;; town indexes in *path-matrix*
           (idxs (mapcar #'(lambda (town) (position town *towns*)) towns))
           ;; starting here
           (from-idx (car idxs))
           ;; result path in indexes
           (idx-path (cons from-idx (find-path from-idx (cdr idxs))))
           ;; path length
           (path-len (apply #'+
                            (maplist
                             #'(lambda (path)
                                 (dist (car path) (or (cadr path) from-idx)))
                             idx-path)))
           ;; path in town's names
           (town-path (mapcar #'(lambda (idx) (elt *towns* idx))
                              idx-path)))
      (values town-path path-len))))


CL-USER> (fill-path-matrix 100)
CL-USER> *path-matrix*
#2A((0 55 16 98 9 24)
(55 0 76 47 12 7)
(16 76 0 52 22 26)
(98 47 52 0 98 25)
(9 12 22 98 0 19)
(24 7 26 25 19 0))
CL-USER> (salesman-problem 'a 'b 'c 'f)
(A C F B)
104

Это сообщение отредактировал(а) svg - 5.12.2005, 19:45
PM MAIL   Вверх
Andrey1
Дата 7.12.2005, 22:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 621
Регистрация: 27.2.2004
Где: Moscow

Репутация: нет
Всего: 5
smile
Цитата(AntonSaburov @ 5.12.2005, 14:13)
Видимо здесь нет людей, которые пишут на LISP (ну не популярный это язык)

Я пишу. Редко, мало, но пишу.
Насчет популярности... уверен, что популярная система Mathematica Вам тоже кажется непопулярной.
Цитата(Guest @ 3.12.2005, 00:00)
Какие Вы здесь все вредные

Да... рожа смайлика с табличкой - на самом деле улыбающаяся.
А вот если бы Вы, мадмуазель, спросили что-нибудь конкретное, а не литоргический вопрос "сделайте за меня мою работу, пожалуйста", то может даже мне тут не пришлось выставлять смайлики с табличками... smile
Да, и подскажите миссис, как удалить тему!.. smile

Это сообщение отредактировал(а) Andrey1 - 7.12.2005, 22:58


--------------------
Созерцание и мудрость - едины. Соцерцание - это основа мудрости, а мудрость - это функция (т.е. умение использовать) созерцания.
из сутры помоста шестого патриарха Хуэйнена
PM MAIL WWW ICQ   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0524 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.