Помогите решить задачку на Lisp

[Catsi]

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

[npak]

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

Коммивояжер должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город.

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

Расстояния между городами известны.

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

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

В этом примере предполагается, что из города А в город В ведёт ровно одна дорога.  А если дорог несколько?  Если нет дороги?  Что указывать в таблице в этих случаях?

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

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

Ещё одни ворос.  На каком диалекте Lisp должно быть решение? На каком интерпретаторе решение должно работать?  Могу предположить, что язык Common Lisp.  Насчёт интерпретатора не уверен.

[npak]

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

[Catsi]

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

[npak]

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

Код:

(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 переворачивает список перед возвращением.

[Catsi]

 Почему выдается при  (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))
Я очень прошу помочь мне разобраться с этой программой, а если можно упростить (для чайников). Надеюсь я не о многом прошу, просто Вы моя последняя надежда (никто не хочет браться за эту задачку).
Оплату гарантирую (если хотите).

[RXL]

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

[Catsi]

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

[npak]

Почему выдается при  (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'.

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

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

Оплату гарантирую (если хотите).

Это завсегда пожалуйста   Хорошего пива много не бывает !

[Catsi]

Все понятно со  смыслом программы (выводит список городов). Я понимала, что будет выводиться список рассояний между городами и его сумма. Нельзя ли еще эту функцию добавить, а то нам сказали выводить кроме списка городов и  длину наименьшего пути (это как раз мой список (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]

npak , надеюсь командировка удалась и Вы полны сил, и ....

[kasper]

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

[npak]

Привет!

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

[Catsi]

Здравствуйте! Я уже по Вам соскучилась!
Все понятно со  смыслом программы (выводит список городов). Я понимала, что будет выводиться список рассояний между городами и его сумма. Нельзя ли еще эту функцию добавить, а то нам сказали выводить кроме списка городов и  длину наименьшего пути (это как раз мой список (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]

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

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

[Catsi]

dotimes - эту функцию я знаю. Также говорили про setf, mapcan.
lambda лучше не использовать, что-то у нас в универе она плохо работает.

[Catsi]

npak, прошу прощения за путаницу

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

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

[Catsi]

npak, почему не выходите на связь (времени нет или  я Вам надаела)? :razz:??

[npak]

Милая Catsi,

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

[Catsi]

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

[npak]

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

[Catsi]

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

[npak]

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