IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> Задача про города, Решил, но есть один ньюанс!
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Алексей

Репутация: -  0  +


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


Бывалый
***

Группа: Пользователи
Сообщений: 159
Пол: Мужской
Реальное имя: Anton

Репутация: -  0  +


Цитата(Алексей_Рыженко @ 3.07.2006 15:20) *

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

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


--------------------
made in USSR.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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


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

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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Алексей

Репутация: -  0  +


Хм ничего секретного!!!!!!!! задача из учебника. Значит говорите случается!!!!! Интересно. Ну вот у меня из 24 чисел наверно больше 5 имеют пары а то и 3 одинаковых числа подается!!!! Так говорите так и должно быть?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Цитата(Алексей_Рыженко @ 3.07.2006 15:20)
скажите так и должно быть что иногда растояния повторяются, хотя комбинации разные?

Что значит "иногда расстояния повторяются"? При разных запусках? Тогда непонятно, почему "комбинации разные" при одних и тех же исходных данных, к примеру...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Алексей

Репутация: -  0  +


Нет!!! При одном!!!!!!!! Например:
......
Комбинация №4 ADCBEA - 312
Комбинация №5 ADCEBA - 200
....
Комбинация №15 ACDEBA - 200
.....
Комбинация №24 ABCEDA -312
Это я к примеру!!!!!!!!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






Теперь я вообще ничего не понимаю... Присоединяй исходник, вводимые данные и полное задание...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Алексей

Репутация: -  0  +


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


Прикрепленные файлы
Прикрепленный файл  GORODA.PAS ( 2.81 килобайт ) Кол-во скачиваний: 117
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 47
Пол: Мужской
Реальное имя: Юрий

Репутация: -  0  +


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


Гость






Цитата(WishMaster @ 3.07.2006 20:16)
Я так понял это задача о коммивояжере.Вообщу оптимальпого алгоритма решения этой задачи НЕТ !
Оптимального, может, и НЕТ (оптимального вообще ничего нет, то что будет оптимально для одной области, в другой - просто осмеют), а вот просто алгоритм решения у нас на форуме встречался ПО КРАЙНЕЙ МЕРЕ дважды...

(Hint: искать "комми*" - без кавычек)
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Алексей

Репутация: -  0  +


так я не понял а как моё решение??
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Новичок
*

Группа: Пользователи
Сообщений: 47
Пол: Мужской
Реальное имя: Юрий

Репутация: -  0  +


задача о комивояжере это стандартная нп-задача(она не находит за данное время решения)=>>оптимального решения НЕТ !
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Алексей

Репутация: -  0  +


А моя программа выходит не определяет кратчайший путь? Фигня?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Алексей

Репутация: -  0  +


Ответьте как моя программа? Выполняет то что требуется?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Гость






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

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


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Алексей

Репутация: -  0  +


Volvo, ты не заметил????????? там под таблицей выводится самый короткий путь!!!!!!!!!!!!!!! Посмотри!!!!!!!!!!!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Гость






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


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Алексей

Репутация: -  0  +


Так ведь можно в таблице с права найти это растояние и посмотреть какой это путь!!!!!! Разве нет?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Гость






Цитата(Алексей_Рыженко @ 5.07.2006 21:38)
Так ведь можно в таблице с права найти это растояние и посмотреть какой это путь!!!!!! Разве нет?
Ну, так ТЫ же этого не сделал!!! Сделай, присоедини новую версию, тогда и спрашивай, делает она то, что нужно по условию, или нет... Это первое.

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


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Алексей

Репутация: -  0  +


Спасибо. Так верно что может быть несколько однаковых расстояний?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 




- Текстовая версия 18.11.2017 7:59
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"