Версия для печати темы
Нажмите сюда для просмотра этой темы в обычном формате
Форум «Всё о Паскале» _ Задачи _ Задача про города
Автор: Алексей_Рыженко 3.07.2006 19:20
Ребят, подскажите! Вот задача. Есть пять городов А, B, C, D, E. Человек выходит
обязательно из города А и должен вернуться в А. Т.е. порядок городов за исключением
первого и последнего может менятся. Надо найти кротчайщие растояние.
Всего я подсчитал может быть 24 комбинации. Растояния между городами известно.
Я написал программу, всё вроде нормально. Но скажите так и должно быть что
иногда растояния повторяются, хотя комбинации разные? Тогда получается что
кротчайших путей может быть несколько. Может ли так быть? Если кому нужен
исходник говорите адрес пришлю.
Автор: Романтик 3.07.2006 19:23
Ребят, подскажите! Вот задача. Есть пять городов А, B, C, D, E. Человек выходит
обязательно из города А и должен вернуться в А. Т.е. порядок городов за исключением
первого и последнего может менятся. Надо найти кротчайщие растояние.
Всего я подсчитал может быть 24 комбинации. Растояния между городами известно.
Я написал программу, всё вроде нормально. Но скажите так и должно быть что
иногда растояния повторяются, хотя комбинации разные? Тогда получается что
кротчайших путей может быть несколько. Может ли так быть? Если кому нужен
исходник говорите адрес пришлю.
Может. такое часто случается. ничего удивительного.
Автор: klem4 3.07.2006 19:35
исходник говорите адрес пришлю.
Чтож за секретная разработка там у тебя ?
http://forum.pascal.net.ru/index.php?s=&showtopic=4030&view=findpost&p=40473
Автор: Алексей_Рыженко 3.07.2006 20:28
Хм ничего секретного!!!!!!!! задача из учебника. Значит говорите случается!!!!! Интересно. Ну вот у меня из 24 чисел наверно больше 5 имеют пары а то и 3 одинаковых числа подается!!!! Так говорите так и должно быть?
Автор: volvo 3.07.2006 21:11
Что значит "иногда расстояния повторяются"? При разных запусках? Тогда непонятно, почему "комбинации разные" при одних и тех же исходных данных, к примеру...
Автор: Алексей_Рыженко 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, а между СВ и ВС, т.д. - должно быть одинаково!!!!!!!!
Прикрепленные файлы
GORODA.PAS ( 2.81 килобайт )
Кол-во скачиваний: 270
Автор: WishMaster 4.07.2006 0:16
Я так понял это задача о коммивояжере.Вообщу оптимальпого алгоритма решения этой задачи НЕТ !Откуда я знаю,это тема мой курсовой работы по дискретной математике,которую я успешно сдал.Переходим к делу, всего в задаче возможно п! решений ,где п-= кол-во городов.Самое точное решение дает генетический алгоритм,или метод ветвей и границ для комбинаторных задач.Оптимальное но не точное решение даст алгоритмм ближайшего соседа (по нему я программу то и сделалл).Я рекомендую тебе использовать один из этих методов (в зависимости от степени точности решения),ну а если у тебя ничего не выйдет ,то пиши я постораюсь тебе помочь
Автор: volvo 4.07.2006 0:23
(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
Второе: о какой ТАБЛИЦЕ ты говоришь? У тебя "справа" просто распечатываются значения, они нигде не хранятся. Следовательно, для того, чтобы "найти это расстояние" (не забудь, что "этих расстояний" может быть несколько одинаковых) тебе необходимо поменять структуру программы. Так что см. пункт 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
Спасибо всем!