Правила форума
Здравствуйте!В последнее время я все чаще задумываюсь о проблеме "בלתי סבירות"(прошу прощения,но я просто не знаю как сказать это на русском,поэтому я объясню).
Это проблема скорей всего известна всем.Допустим у нас есть город,в нем обозначем несколько мест(достопримечательности,например).Нужно найти самый короткий путь,начинающийся и заканчивающийся от ворот города, при условии,что нужно пройтись по всем достопремечательностям.
Возможное решение,это нахождение всех возможных путей,которые начинаются и заканчиваются у ворот города и проходят через каждую достопремечательность один раз.Проблема кажется легкой при условии,что число достопремечательностей не очень большое(точнее очень даже маленьекое =) )
Как известно,если у нас n точек,то есть (n-1)! вариантов возможных путей,проходящих через все точки и возращающийхся в начальную точку.Время требеющееся для нахождения самого короткого пути для шести точек - 8 милисекунд.Казалось бы пустяковое время,а теперь посмотрите на следующие данные -
Число точек,Число путей,Время
6,120,8 мс
11,362880,3.5 с
13,479001600,8 мин
21,2.43*10 в степени 18,77000 лет
Так что скажите уважаемые посетители форума?Возможно ли найти решение этой проблемы?Кстати,есть множество таких проблем,на которые решение не найдены,если конечно не считать те решения,которые приемлемы только для маленьких значений данных.]
 А есть ли решение? |
