Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Make things as simple as possible but not simpler. A. Einstein Глава 7. СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ С ПОМОЩЬЮ АЛГОРИТМОВ В предыдущей главе рассматривались проблемы принципиальной возмож­ ности вычислений и были исследованы различные подходы к понятию вычис­ лимости. При этом не обращалось внимания на ресурсы времени и памяти. Од­ нако оказывается, что существуют задачи, которые теоретически разрешимы, но их решение практически неосуществимо. Рассмотрим следующий простой пример такой задачи, именно задачу коммивояжера. Эта задача, как известно, состоит в следующем. Дано п городов, которые должен посетить коммивояжер, причем каждый город посетить один и только один раз и вернуться в исходный город, из которого он начал движение. При выборе маршрута необходимо ми­ нимизировать, например, длину маршрута. Эта задача алгоритмически разрешима, ибо достаточно перебрать все ва­ рианты построения маршрутов и выбрать среди них кратчайший маршрут. Не­ трудно убедиться, что число возможных вариантов обхода для п городов будет равно: 5- ={п - 1)!/2. При п = А получим, что 5- = ( 4 - 1 ) ! / 2 =Ъ \ 1 1 = (1x2x3 )/2 = 3 и варианты обхода представлены на Рис. 7.1. Рис. 7.1. При п = Ъ число вариантов равно s = А\ 11 = (1х2хЗх4)/2 = 12, для и = 8 получим S = 1\ 11 = 2520 и последовательно: n = \\,s = 1 814 400, п = 2\, s > 18 1.2x10 . Пусть п = 51, тогда число вариантов обхода будет 5- = 50 ! / 2. По формуле Стирлинга: f 50^^^ 50 ! = Л/27ГХ50Х — = 17.72х(18.38)^® =1.772х10х(1.83)^^x10^®= = 1.772x10x^1.65х10^^;х10^® =2.924x10^"^. В результате s = 1.462x10^^. Теперь сосчитаем наличное время: 1 минута = 60 секунд, 1 час = 3 600 се­ кунд, 1 сутки = 3 600 X 24 = 86 400 секунд, 1 год = 86 400 х 365 = 31 536 ОО = 3.154 X 10^ секунд. 217