Задача про города, Решил, но есть один ньюанс! Опции

[Алексей_Рыженко]

Ребят, подскажите! Вот задача. Есть пять городов А, B, C, D, E. Человек выходит
обязательно из города А и должен вернуться в А. Т.е. порядок городов за исключением
первого и последнего может менятся. Надо найти кротчайщие растояние.
Всего я подсчитал может быть 24 комбинации. Растояния между городами известно.
Я написал программу, всё вроде нормально. Но скажите так и должно быть что
иногда растояния повторяются, хотя комбинации разные? Тогда получается что
кротчайших путей может быть несколько. Может ли так быть? Если кому нужен
исходник говорите адрес пришлю.

[Романтик]

Ребят, подскажите! Вот задача. Есть пять городов А, B, C, D, E. Человек выходит
обязательно из города А и должен вернуться в А. Т.е. порядок городов за исключением
первого и последнего может менятся. Надо найти кротчайщие растояние.
Всего я подсчитал может быть 24 комбинации. Растояния между городами известно.
Я написал программу, всё вроде нормально. Но скажите так и должно быть что
иногда растояния повторяются, хотя комбинации разные? Тогда получается что
кротчайших путей может быть несколько. Может ли так быть? Если кому нужен
исходник говорите адрес пришлю.

Может. такое часто случается. ничего удивительного.

[klem4]

Если кому нужен
исходник говорите адрес пришлю.

Чтож за секретная разработка там у тебя ?

Поиск кратчайших путей

[Алексей_Рыженко]

Хм ничего секретного!!!!!!!! задача из учебника. Значит говорите случается!!!!! Интересно. Ну вот у меня из 24 чисел наверно больше 5 имеют пары а то и 3 одинаковых числа подается!!!! Так говорите так и должно быть?

[volvo]

скажите так и должно быть что иногда растояния повторяются, хотя комбинации разные?

Что значит "иногда расстояния повторяются"? При разных запусках? Тогда непонятно, почему "комбинации разные" при одних и тех же исходных данных, к примеру...

[Алексей_Рыженко]

Нет!!! При одном!!!!!!!! Например:
......
Комбинация №4 ADCBEA - 312
Комбинация №5 ADCEBA - 200
....
Комбинация №15 ACDEBA - 200
.....
Комбинация №24 ABCEDA -312
Это я к примеру!!!!!!!!

[volvo]

Теперь я вообще ничего не понимаю... Присоединяй исходник, вводимые данные и полное задание...

[Алексей_Рыженко]

Есть пять городов , А , Б , С , Д и Е. Известно что человек всегда выходит из города А , и обязательно должен пройти все оставшиеся города и попасть обратно в А. К примеру , Из А -> Б -> C->Д->E->A. То есть за исключением А , порядок посещения оставшихся четырех городов может меняться. То есть существует (5-1)! комбинаций. Как мне задать чтобы программа сама смогла их посчитать, а потом выдать наикратчайщий путь ???
Вот файл. Вначале надо заполнить таблицу расстояний Может это очевидно но я поясню!!!!!!! Растояние между А и А, В и В, и т.д. - до лжно быть равно 0, а между СВ и ВС, т.д. - должно быть одинаково!!!!!!!!

[WishMaster]

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

[volvo]

Я так понял это задача о коммивояжере.Вообщу оптимальпого алгоритма решения этой задачи НЕТ !

Оптимального, может, и НЕТ (оптимального вообще ничего нет, то что будет оптимально для одной области, в другой - просто осмеют), а вот просто алгоритм решения у нас на форуме встречался ПО КРАЙНЕЙ МЕРЕ дважды...

(Hint: искать "комми*" - без кавычек)

[Алексей_Рыженко]

так я не понял а как моё решение??

[WishMaster]

задача о комивояжере это стандартная нп-задача(она не находит за данное время решения)=>>оптимального решения НЕТ !

[Алексей_Рыженко]

А моя программа выходит не определяет кратчайший путь? Фигня?

[Алексей_Рыженко]

Ответьте как моя программа? Выполняет то что требуется?

[volvo]

Нет... Что требуется? Найти минимальный путь, так? А у тебя что выводится? ВСЕ ВОЗМОЖНЫЕ пути? А зачем? Дейкстра или Флойд тебе в помощь - у нас в FAQ-е есть реализации...

А тебе WishMaster, я еще раз повторяю (если тебя читать и понимать прочитанное не научили): я и не говорил об оптимальном решении, еще раз тебе говорю - нет НИЧЕГО оптимального!!! Есть только решения, устраивающие заказчика. ВСЁ. Даже вычисление квадратного корня через Sqrt какого-то заказчика может не устроить!

[Алексей_Рыженко]

Volvo, ты не заметил????????? там под таблицей выводится самый короткий путь!!!!!!!!!!!!!!! Посмотри!!!!!!!!!!!

[volvo]

Да это я видел... Только... Понимаешь, "Наикратчайший путь" и "Наименьшее расстояние" - не одно и то же... Пути-то нет... Есть длина его, а где сам маршрут? Кстати, твою программу можно малость оптимизировать, чтобы при вводе она сама заполняла уже введенные расстояния между городами (а не ты должен был бы вспоминать, чему равно расстояние AC, чтобы его же ввести в CA)

[Алексей_Рыженко]

Так ведь можно в таблице с права найти это растояние и посмотреть какой это путь!!!!!! Разве нет?

[volvo]

Так ведь можно в таблице с права найти это растояние и посмотреть какой это путь!!!!!! Разве нет?

Ну, так ТЫ же этого не сделал!!! Сделай, присоедини новую версию, тогда и спрашивай, делает она то, что нужно по условию, или нет... Это первое.

Второе: о какой ТАБЛИЦЕ ты говоришь? У тебя "справа" просто распечатываются значения, они нигде не хранятся. Следовательно, для того, чтобы "найти это расстояние" (не забудь, что "этих расстояний" может быть несколько одинаковых) тебе необходимо поменять структуру программы. Так что см. пункт 1...

[Алексей_Рыженко]

Спасибо. Так верно что может быть несколько однаковых расстояний?