Ребят, подскажите! Вот задача. Есть пять городов А, B, C, D, E. Человек выходит обязательно из города А и должен вернуться в А. Т.е. порядок городов за исключением первого и последнего может менятся. Надо найти кротчайщие растояние. Всего я подсчитал может быть 24 комбинации. Растояния между городами известно. Я написал программу, всё вроде нормально. Но скажите так и должно быть что иногда растояния повторяются, хотя комбинации разные? Тогда получается что кротчайших путей может быть несколько. Может ли так быть? Если кому нужен исходник говорите адрес пришлю.
Романтик
3.07.2006 19:23
Цитата(Алексей_Рыженко @ 3.07.2006 15:20)
Ребят, подскажите! Вот задача. Есть пять городов А, B, C, D, E. Человек выходит обязательно из города А и должен вернуться в А. Т.е. порядок городов за исключением первого и последнего может менятся. Надо найти кротчайщие растояние. Всего я подсчитал может быть 24 комбинации. Растояния между городами известно. Я написал программу, всё вроде нормально. Но скажите так и должно быть что иногда растояния повторяются, хотя комбинации разные? Тогда получается что кротчайших путей может быть несколько. Может ли так быть? Если кому нужен исходник говорите адрес пришлю.
Может. такое часто случается. ничего удивительного.
Хм ничего секретного!!!!!!!! задача из учебника. Значит говорите случается!!!!! Интересно. Ну вот у меня из 24 чисел наверно больше 5 имеют пары а то и 3 одинаковых числа подается!!!! Так говорите так и должно быть?
volvo
3.07.2006 21:11
Цитата(Алексей_Рыженко @ 3.07.2006 15:20)
скажите так и должно быть что иногда растояния повторяются, хотя комбинации разные?
Что значит "иногда расстояния повторяются"? При разных запусках? Тогда непонятно, почему "комбинации разные" при одних и тех же исходных данных, к примеру...
Алексей_Рыженко
3.07.2006 21:49
Нет!!! При одном!!!!!!!! Например: ...... Комбинация №4 ADCBEA - 312 Комбинация №5 ADCEBA - 200 .... Комбинация №15 ACDEBA - 200 ..... Комбинация №24 ABCEDA -312 Это я к примеру!!!!!!!!
volvo
3.07.2006 21:56
Теперь я вообще ничего не понимаю... Присоединяй исходник, вводимые данные и полное задание...
Алексей_Рыженко
3.07.2006 22:34
Есть пять городов , А , Б , С , Д и Е. Известно что человек всегда выходит из города А , и обязательно должен пройти все оставшиеся города и попасть обратно в А. К примеру , Из А -> Б -> C->Д->E->A. То есть за исключением А , порядок посещения оставшихся четырех городов может меняться. То есть существует (5-1)! комбинаций. Как мне задать чтобы программа сама смогла их посчитать, а потом выдать наикратчайщий путь ??? Вот файл. Вначале надо заполнить таблицу расстояний Может это очевидно но я поясню!!!!!!! Растояние между А и А, В и В, и т.д. - до лжно быть равно 0, а между СВ и ВС, т.д. - должно быть одинаково!!!!!!!!
WishMaster
4.07.2006 0:16
Я так понял это задача о коммивояжере.Вообщу оптимальпого алгоритма решения этой задачи НЕТ !Откуда я знаю,это тема мой курсовой работы по дискретной математике,которую я успешно сдал.Переходим к делу, всего в задаче возможно п! решений ,где п-= кол-во городов.Самое точное решение дает генетический алгоритм,или метод ветвей и границ для комбинаторных задач.Оптимальное но не точное решение даст алгоритмм ближайшего соседа (по нему я программу то и сделалл).Я рекомендую тебе использовать один из этих методов (в зависимости от степени точности решения),ну а если у тебя ничего не выйдет ,то пиши я постораюсь тебе помочь
volvo
4.07.2006 0:23
Цитата(WishMaster @ 3.07.2006 20:16)
Я так понял это задача о коммивояжере.Вообщу оптимальпого алгоритма решения этой задачи НЕТ !
Оптимального, может, и НЕТ (оптимального вообще ничего нет, то что будет оптимально для одной области, в другой - просто осмеют), а вот просто алгоритм решения у нас на форуме встречался ПО КРАЙНЕЙ МЕРЕ дважды...
(Hint: искать "комми*" - без кавычек)
Алексей_Рыженко
4.07.2006 0:30
так я не понял а как моё решение??
WishMaster
4.07.2006 0:58
задача о комивояжере это стандартная нп-задача(она не находит за данное время решения)=>>оптимального решения НЕТ !
Алексей_Рыженко
4.07.2006 1:15
А моя программа выходит не определяет кратчайший путь? Фигня?
Алексей_Рыженко
4.07.2006 17:53
Ответьте как моя программа? Выполняет то что требуется?
volvo
5.07.2006 15:28
Нет... Что требуется? Найти минимальный путь, так? А у тебя что выводится? ВСЕ ВОЗМОЖНЫЕ пути? А зачем? Дейкстра или Флойд тебе в помощь - у нас в FAQ-е есть реализации...
А тебе WishMaster, я еще раз повторяю (если тебя читать и понимать прочитанное не научили): я и не говорил об оптимальном решении, еще раз тебе говорю - нет НИЧЕГО оптимального!!! Есть только решения, устраивающие заказчика. ВСЁ. Даже вычисление квадратного корня через Sqrt какого-то заказчика может не устроить!
Алексей_Рыженко
5.07.2006 16:19
Volvo, ты не заметил????????? там под таблицей выводится самый короткий путь!!!!!!!!!!!!!!! Посмотри!!!!!!!!!!!
volvo
5.07.2006 22:33
Да это я видел... Только... Понимаешь, "Наикратчайший путь" и "Наименьшее расстояние" - не одно и то же... Пути-то нет... Есть длина его, а где сам маршрут? Кстати, твою программу можно малость оптимизировать, чтобы при вводе она сама заполняла уже введенные расстояния между городами (а не ты должен был бы вспоминать, чему равно расстояние AC, чтобы его же ввести в CA)
Алексей_Рыженко
6.07.2006 1:38
Так ведь можно в таблице с права найти это растояние и посмотреть какой это путь!!!!!! Разве нет?
volvo
8.07.2006 18:58
Цитата(Алексей_Рыженко @ 5.07.2006 21:38)
Так ведь можно в таблице с права найти это растояние и посмотреть какой это путь!!!!!! Разве нет?
Ну, так ТЫ же этого не сделал!!! Сделай, присоедини новую версию, тогда и спрашивай, делает она то, что нужно по условию, или нет... Это первое.
Второе: о какой ТАБЛИЦЕ ты говоришь? У тебя "справа" просто распечатываются значения, они нигде не хранятся. Следовательно, для того, чтобы "найти это расстояние" (не забудь, что "этих расстояний" может быть несколько одинаковых) тебе необходимо поменять структуру программы. Так что см. пункт 1...
Алексей_Рыженко
9.07.2006 1:06
Спасибо. Так верно что может быть несколько однаковых расстояний?
virt
10.07.2006 23:28
пусть у тебя 4 вершины, пусть у тебя следующая матрица расстояний :
A B C D A 0 1 1 0 B 1 0 0 1 C 1 0 0 1 D 0 1 1 0
Тут всего два маршрута ,и их длины равны. Ответ: может.
Алексей_Рыженко
14.07.2006 14:45
Спасибо всем!
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.