Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Помогите решить задачку на Lisp  (Прочитано 23902 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Catsi
Гость
« : 23-11-2005 20:31 » 

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

ru
Offline Offline
Пол: Мужской

« Ответ #1 : 24-11-2005 13:52 » 

Сначала надо уточнить задачу.

Коммивояжер должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город.
Действительно ли в задаче требуется, чтобы через каждый город маршрут проходил ровно один раз?  В такой постановке задача может оказаться неразрешимой.  Пример -- звездообразная сеть, один центральный город, города спутники связаны с центральным городом, не связаны друг с другом.  В такой сети коммивояжеру придётся постоянно проезжать через центральный город.

Расстояния между городами известны.
Что именно известно?  Заданы расстояния между соседними горадами?  Заданы минимальные расстояния между любыми двумя городами (но в таком случае не понятно, через какие города проходит минимальны маршрут)?  Если города не связаны дорогами, то какое значение для них указывается?

В каком порядке следует обходить города, чтобы замкнутый путь коммивояжера был кратчайшим?
Выдавать программа должна кротчайший путь коммивояжера (список  пройденных городов) и его длину.
 Для нахождения длины пути велели задавать матрицу городов в виде списка расстояний между городами. Допустим есть три города А В С , тогда надо задать список расстояний от одного города до каждого из остальных  ((0 3 9) (3 0 1) (9 1 0)).
    АВС
 А 039
 В 301
 С 910
В этом примере предполагается, что из города А в город В ведёт ровно одна дорога.  А если дорог несколько?  Если нет дороги?  Что указывать в таблице в этих случаях?

На входе у нас есть два списка: список городов и список расстояний между городами.
 Надо реализовывать эвристический алгоритм поиска, с эвристикой `идти в ближайший город`. Решать задачу надо с помощью рекурсии.
пожалуйста помогите. Заранее спасибо.
Пожалуйста, опишите эвристику более точно.  Наверное, надо как минимум потребовать, чтобы искать ближайший из городов, в которых ещё не бывал.

Ещё одни ворос.  На каком диалекте Lisp должно быть решение? На каком интерпретаторе решение должно работать?  Могу предположить, что язык Common Lisp.  Насчёт интерпретатора не уверен.
« Последнее редактирование: 24-11-2005 13:55 от npak » Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #2 : 24-11-2005 14:00 » 

Ещё можно попросить помощи на специализированном форуме
http://forum.vingrad.ru/index.php?showforum=119
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Catsi
Гость
« Ответ #3 : 24-11-2005 15:46 » 

npak, я надеюсь Вы мне сможете помочь!!
 Решать нужно на Common Lisp. Через каждый город надо проити и только один раз. Но из каждого города можно попасть в любой другой, поэтому мы задаем список расстояний между городами, где подсписки расстояния от одного города до всех остальных и так для каждого города. Дорога существуют между всемо городами (а если нет, то может на этом  месте в списке  расстояний писать ноль: так можно??- это мое предположение, об этом нам ничего не сказали). Что касается эвристики, то надо искать ближайший из городов, в которых ещё не бывал (т.к. каждый город надо посетить и только один раз).
Помогите пожалуйста, мне кажется Вы знаете как это сделать!!!!
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #4 : 24-11-2005 18:11 » 

Решение для эвристики "идти в ближайший город".

Код:
(defun commy-find-shortest-road (route roads)
  (let (next-hop (distance most-positive-double-float))
    (dotimes (road-num (length roads))
      (when (and (not (member road-num route))
                 (< (nth road-num roads) distance))
        (setq next-hop road-num
              distance (nth road-num roads))))
    next-hop))

(defun commy-step (route roadmap)
  (if (= (length route) (length roadmap))
      route
    (let* ((current-town (car route))
           (current-roads (nth current-town roadmap))
           (next-hop (commy-find-shortest-road route current-roads))
           )
      (push next-hop route)
      (commy-step route roadmap))))

(defun commy-route (roadmap)
  (reverse (commy-step '(0) roadmap)))

Для рассчёта маршрута нужно вызывать `commy-route', например (commy-route '((0 9 3) (9 0 1) (3 1 0))), функция вернёт список городов, (0 2 1).
Функция `commy-step' рассчитывает следующий шаг.  Текущий город находится в голове списка route; из карты дорог извлекается список дорог для текущего города, в этом списке находится дорога в незнакомый город минимальной длины (это делает функция commy-find-shortest-road). Найденный город добавляется в маршрут и функция вызывает саму себя для рассчёта следующего шага.  Функция commy-step хранит маршрут в обратном порядке, поэтому commy-route переворачивает список перед возвращением.
« Последнее редактирование: 20-12-2007 18:00 от Алексей1153++ » Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Catsi
Гость
« Ответ #5 : 24-11-2005 19:39 » 

 Почему выдается при  (commy-route '((0 3 9 8 7) (3 0 8 5 4) (9 8 0 3 7) (8 5 3 0 4) (7 4 7 4 0) )) список
(0 1 4 3 2).  В моем понимании прграмма должна была выдать (0 3 3 3 4) и его сумму как наименьшего маршрута. Где я ошибаюсь.  Я конечно восхищаюсь Вашими познаниями языка, но где эти функции можно найти, а лучше как их можно заменить, а то в нашей справки и половины из этой проги нет. Например, что это
(let (next-hop (distance most-positive-double-float))
    (dotimes (road-num (length roads))
Я очень прошу помочь мне разобраться с этой программой, а если можно упростить (для чайников). Надеюсь я не о многом прошу, просто Вы моя последняя надежда (никто не хочет браться за эту задачку).
Оплату гарантирую (если хотите).
« Последнее редактирование: 20-12-2007 18:02 от Алексей1153++ » Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #6 : 24-11-2005 19:55 » 

Можно напрячься и поискать. Например, начать с http://www.lisp.org/ .
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Catsi
Гость
« Ответ #7 : 24-11-2005 20:10 » 

RXL, извиняюсь, но я понимаю только по-русски. И мне не поверят, что по нашей справки (которую дали) можно написать такую крутую прогу. А мне ведь за нее еще и отчитаться надо, дословно рассказать, что делает каждая строчка программы.
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #8 : 25-11-2005 12:38 » 

Почему выдается при  (commy-route '((0 3 9 8 7) (3 0 8 5 4) (9 8 0 3 7) (8 5 3 0 4) (7 4 7 4 0) )) список
(0 1 4 3 2).  В моем понимании прграмма должна была выдать (0 3 3 3 4) и его сумму как наименьшего маршрута. Где я ошибаюсь.
`commy-route' возвращает список городов, через которые надо проехать коммивояжёру.  Из города 0 самая короткая дорога ведёт в город 1.  Из города 1 самая короткая дорога ведёт в город 0, но там комми уже был, среди тех, где ещё не был,  выбирает город 4.  В городе 4 кратчайшие дороги ведут в города 1 и 3.  В городе 1 уже был, поэтому выбирается город 3.  Из города 3 есть только один маршрут, в город 2, так как это последний город, в котором комми ещё не был.
Ваш список  (0 3 3 3 4) мне не понятен.  Если ему верить, то через город 3 надо будет проехать три раза.  Это нарушает постановку задачи.

Я конечно восхищаюсь Вашими познаниями языка, но где эти функции можно найти, а лучше как их можно заменить, а то в нашей справки и половины из этой проги нет.
Каких именно нет?  Напишите список, я заменю.

Например, что это
(let (next-hop (distance most-positive-double-float))
    (dotimes (road-num (length roads))
специальная форма `let' связывает имя с некоторым значением.  Имя next-hop связывается со значением nil, так как не имеет инициализатора, имя distance связывается со значением most-positive-double-float, которое равно максимально возможному числу, представимому в реализации.  Если у вас в доках нет такой константы, то замените на какое-нибудь число, которое будет точно больше расстояния между любыми двумя городами (например, 10000).  После завершения цикла `dotimes' в переменной next-hop будет номер города, в который ведёт кратчайшая дорога, в переменной distance расстояние до этого города.  Цикл `dotimes' вначале записывает в переменную `road-num' число 0, затем последовательно увеличивает значение `road-num' на 1 до тех пор, пока оно не станет равным (length roads).  Фактически, `dotimes' представляет собой цикл от 0 до некоторого макс. значения.  Если `dotimes' вы не знаете, то его можно заменить на `loop'.  Если не знаете даже `loop', то можно написать цикл `while'.

Я очень прошу помочь мне разобраться с этой программой, а если можно упростить (для чайников). Надеюсь я не о многом прошу, просто Вы моя последняя надежда (никто не хочет браться за эту задачку).
Признаться, программа очень простая.  Как мне кажется, проблема не столько в ней, сколько в вашем незнании лиспа.  Я мог бы рассказать построчно, что и как она делает, но на следущей неделе я еду в командировку, раньше пятницы, скорее всего, на форуме не появлюсь.  Напишите, что вам не понятно, попробую ответить сегодня.

Оплату гарантирую (если хотите).
Это завсегда пожалуйста Улыбаюсь  Хорошего пива много не бывает !
« Последнее редактирование: 20-12-2007 18:07 от Алексей1153++ » Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Catsi
Гость
« Ответ #9 : 25-11-2005 18:41 » 

Все понятно со  смыслом программы (выводит список городов). Я понимала, что будет выводиться список рассояний между городами и его сумма. Нельзя ли еще эту функцию добавить, а то нам сказали выводить кроме списка городов и  длину наименьшего пути (это как раз мой список (0 3 3 3 4) и его сумма).
 Насчет незнания Лиспа я согласна (просто выучить язык по  справке за 8 занятий сложновато, при условии, что надо изучать и отчитывать еще за 4 языка програмирования). Можно уточнить, что в первой функции route и roads.
Очень Выс прошу написать поподробнее, что делает функция
(defun commy-step (route roadmap)
  (if (= (length route) (length roadmap))
      route
    (let* ((current-town (car route))
           (current-roads (nth current-town roadmap))
           (next-hop (commy-find-shortest-road route current-roads))
           )
      (push next-hop route)
      (commy-step route roadmap))))
Записан
Catsi
Гость
« Ответ #10 : 01-12-2005 19:39 » 

npak , надеюсь командировка удалась и Вы полны сил, и ....
Записан
kasper
Гость
« Ответ #11 : 02-12-2005 00:09 » 

Если можно написать ее на С или С++, то я напишу ее за самое минимальное время. Написать?
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #12 : 02-12-2005 09:50 » 

Привет!

Где список непонятных функций, которые надо заменить?  И список конкретных вопросов о том, что не понятно?
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Catsi
Гость
« Ответ #13 : 02-12-2005 15:17 » 

Здравствуйте! Я уже по Вам соскучилась!
Все понятно со  смыслом программы (выводит список городов). Я понимала, что будет выводиться список рассояний между городами и его сумма. Нельзя ли еще эту функцию добавить, а то нам сказали выводить кроме списка городов и  длину наименьшего пути (это как раз мой список (0 3 3 3 4) и его сумма).
Насчет незнания Лиспа я согласна (просто выучить язык по  справке за 8 занятий сложновато, при условии, что надо изучать и отчитывать еще за 4 языка програмирования). Можно уточнить, что в первой функции route и roads. И на что можно заменить push.
Очень Выс прошу написать поподробнее, что делает функция
(defun commy-step (route roadmap)
  (if (= (length route) (length roadmap))
      route
    (let* ((current-town (car route))
           (current-roads (nth current-town roadmap))
           (next-hop (commy-find-shortest-road route current-roads))
           )
      (push next-hop route)
      (commy-step route roadmap))))
Заранее спасибо, очень надеюсь, что не сильно Вас обременяю!
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #14 : 02-12-2005 17:10 » 

Правильно ли я понял, что dotimes в списке разрешённых функций есть?  Заранее спрошу, есть ли в списке разрешённых dolist, map/mapcan/mapcar, lambda, setf и incf?

Сегодня текучка заела, отвечу на выходных.
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Catsi
Гость
« Ответ #15 : 03-12-2005 07:42 » 

dotimes - эту функцию я знаю. Также говорили про setf, mapcan.
lambda лучше не использовать, что-то у нас в универе она плохо работает.
Записан
Catsi
Гость
« Ответ #16 : 05-12-2005 14:08 » 

npak, прошу прощения за путаницу
Нельзя ли еще эту функцию добавить, а то нам сказали выводить кроме списка городов и длину наименьшего пути (это как раз мой список (0 3 3 3 4) и его сумма).


Сегодня сказали, что можно оставить решение в исходном варианте (где вывадится список пройденных городов).
А остальная просьба (про пояснения) остается неизменной.
Очень прошу ответить (не обижайтесь на меня за путаницу - "не виноватая я").
Сегодня хотела начать отчитываться, но без Вашей помощи у меня ничего не получится.
« Последнее редактирование: 05-12-2005 16:08 от Catsi » Записан
Catsi
Гость
« Ответ #17 : 08-12-2005 11:29 » 

npak, почему не выходите на связь (времени нет или  я Вам надаела)? :razz:??
« Последнее редактирование: 08-12-2005 11:32 от Catsi » Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #18 : 08-12-2005 16:47 » 

Милая Catsi,

совсем нет времени.  Может быть, у вас на потоке есть кто-то, кто разбирается в лиспе?  Если да, то покажите им, программа простая, должны суметь разобраться.  Если же нет, то назовите крайний срок, когда вам нужно получить разъяснения.
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Catsi
Гость
« Ответ #19 : 08-12-2005 17:02 » 

Все считают, что я разбираюсь.
Отчитываться я уже начала, жду ответа от преподавателя  по программе. Еще не знаю какие вопросы он мне готовит. Прошу Вас дать свой электронный адрес (попытаюсь отвечать на его вопросы сама, но если не получиться можно будет  у Вас спросить?). На форуме не хочу выкладывать его вопросы, а вдруг он сюда зайдет.
Заранее огромное спасибо.
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #20 : 08-12-2005 17:16 » 

Смотрите в личных сообщениях
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Catsi
Гость
« Ответ #21 : 17-12-2005 17:03 » 


Здравствуйте, npak. Вы не получили письмо???
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #22 : 19-12-2005 09:50 » 

У меня его спам-фильтр поел Улыбаюсь
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines