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

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

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

> А есть ли решение?
сообщение
Сообщение #1


Гость






Здравствуйте!В последнее время я все чаще задумываюсь о проблеме "בלתי סבירות"(прошу прощения,но я просто не знаю как сказать это на русском,поэтому я объясню).
Это проблема скорей всего известна всем.Допустим у нас есть город,в нем обозначем несколько мест(достопримечательности,например).Нужно найти самый короткий путь,начинающийся и заканчивающийся от ворот города, при условии,что нужно пройтись по всем достопремечательностям.
Возможное решение,это нахождение всех возможных путей,которые начинаются и заканчиваются у ворот города и проходят через каждую достопремечательность один раз.Проблема кажется легкой при условии,что число достопремечательностей не очень большое(точнее очень даже маленьекое =) )
Как известно,если у нас  n точек,то есть (n-1)! вариантов возможных путей,проходящих через все точки и возращающийхся в начальную точку.Время требеющееся для нахождения самого короткого пути для шести точек - 8 милисекунд.Казалось бы пустяковое время,а теперь посмотрите на следующие данные -



Число точек,Число путей,Время

6,120,8 мс
11,362880,3.5 с
13,479001600,8 мин
21,2.43*10 в степени 18,77000 лет



Так что скажите уважаемые посетители форума?Возможно ли найти решение этой проблемы?Кстати,есть множество таких проблем,на которые решение не найдены,если конечно не считать те решения,которые приемлемы только для маленьких значений данных.]
 К началу страницы 
+ Ответить 

Сообщений в этой теме
I love Prolog =)   А есть ли решение?   27.06.2003 20:43
Andrey   Re: А есть ли решение?   27.06.2003 23:32
Morpheus   Re: А есть ли решение?   29.06.2003 9:09


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

 





- Текстовая версия 29.03.2024 12:21
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name