Do you know more good solution with SMath?
TSP-n Метод ближайшего соседа.sm (19,27 КиБ) скачан 46 раз(а).

А я для задачи коммивояжера использую алгоритм динамического программирование. Недавно написал программу (На маткаде)

Wrote

А я для задачи коммивояжера использую алгоритм динамического программирование. Недавно написал программу (На маткаде)

А вы можете переписать вашу программу на SMath. или просто ею поделиться с нами.

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

Wrote

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

Пришлите Mathcad расчёт, плз!

Валерий Федорович, а как здесь вставлять картинки?

Программа состоит из трех подпрограмм. Первые две основные и третья просто убирает лишние нули из вектора-ответа второй.

Получилась вставка картинки. Итак, первая подпрограмма возвращает длину оптимального пути, вторая-возвращает номера пунктов через которые проходит оптимальный путь (с лишними нулями), третья-убирает эти нули. Аргументом каждой программы является матрица, которая задает стоимость пути из пункта i в пункт j. Если эта стоимость равна нулю-значить такого пути нет.
Матрица r небольшая - можно набрать отличные от нуля элементы вручную.
При использование алгоритма динамического программирования находится оптимальный путь.
P.S.. Первая программа возвращает , конечно. не длину, а стоимость оптимального пути.

Wrote

Получилась вставка картинки. Итак, первая подпрограмма возвращает длину оптимального пути, вторая-возвращает номера пунктов через которые проходит оптимальный путь (с лишними нулями), третья-убирает эти нули. Аргументом каждой программы является матрица, которая задает стоимость пути из пункта i в пункт j. Если эта стоимость равна нулю-значить такого пути нет.
Матрица r небольшая - можно набрать отличные от нуля элементы вручную.
При использование алгоритма динамического программирования находится оптимальный путь.
P.S.. Первая программа возвращает , конечно. не длину, а стоимость оптимального пути.

Прикрепите саму программу, плз!

Вот.Дилижанс 14.mcd (16,37 КиБ) скачан 40 раз(а).

Wrote

Вот.Дилижанс 14.mcd (16,37 КиБ) скачан 40 раз(а).

Thanks!
One remark.
By solving the traveling salesman problem, we mean the following problem.
There are two vectors, X and Y, storing the coordinates of n points on a plane.
You need to create a function that returns a vector of length n+1 containing the numbers of the points — the traveling salesman path.
You don’t have this.
Спасибо!
Одно замечание.
Под решением задачи коммивояжёра понимают такую задачу.
Есть два вектора X и Y, хранящие координаты n точек на плоскости.
Нужно создать функцию, которая возвращает вектор длиной n+1, содержащий номера точек - путь коммивояжёра.
У вас этого нет.

The opposite task is to visit all the points via the longest possible route.
TSP-n Метод дальнего соседа.sm (19 КиБ) скачан 23 раз(а).

Я взял классическую постановку задачи коммивояжера для решения ее с помощью алгоритма динамического программирования (см. например Г.Вагнер Основы исследования операций т2." Имеется n городов в некотором государстве, связанных между собой некоторой сетью дорог. Нужно переехать из самого восточного города в самый западный. Задана стоимости переездов из одного города в другой в направлении с востока на запад.Найти путь из самого восточного города в самый западный минимальной стоимости.
Т.е. найти стоимость этого минимального пути и номера городов через которые он проходит. Предложенная мной программа решает эту задачу. Алгоритм ближайшего соседа в общем случае не находит этот оптимальный путь и номера городов через которые он проходит.

Wrote

Я взял классическую постановку задачи коммивояжера для решения ее с помощью алгоритма динамического программирования (см. например Г.Вагнер Основы исследования операций т2." Имеется n городов в некотором государстве, связанных между собой некоторой сетью дорог. Нужно переехать из самого восточного города в самый западный. Задана стоимости переездов из одного города в другой в направлении с востока на запад.Найти путь из самого восточного города в самый западный минимальной стоимости.
Т.е. найти стоимость этого минимального пути и номера городов через которые он проходит. Предложенная мной программа решает эту задачу. Алгоритм ближайшего соседа в общем случае не находит этот оптимальный путь и номера городов через которые он проходит.

Прошу простить, но...
Классическая постановка задачи коммивояжера
https://ru.wikipedia.org/wiki/Задача_коммивояжёра

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

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