(n-1)!/2
- При n равном 100 мы получим
(100-1)!/2≈4,666*10155
- Это достаточно много, - ухмыльнулся Поллит, - Намного, намного больше чем число всех существующих частиц в видимой части вселенной. Но может с помощью компьютера мы посчитаем быстрее? Есть, однако, как мне подсказывает мой искин, фундаментальные ограничения на вычислительную мощность материи, следующие из уравнения эквивалентности массы и энергии Эйнштейна и принципа неопределенности Гейзенберга. Так максимальная теоретически достижимая скорость вычислений на килограмм вещества равна108
1.36×1050 бит в секунду на килограмм
- Допустим нам удалось всю видимую нам вселенную превратить в компьютер работающий на теоретическом пределе мощности, - продолжил экономист, - Масса нашей вселенной, если брать обычную материю, а не темную, будет приблизительно равна 1053 килограмм109. Соответственно наш гигантский
компьютер будет обладать вычислительной мощностью
(1.36×1050)×1053=1.36×10103 бит в секунду
- Если допустить, что на проверку каждого варианта пути будет тратиться одна секунда, то на проверку всех вариантов компьютером размером со вселенную уйдет
4,666*10155/1,36*10103=3,43*1052 секунд
- Это опять-таки намного порядков больше чем возраст нашей вселенной. Ждать в общем придется долго. Мораль проста. При решении с помощью перебора многих с виду простых проблем число возможных вариантов растет экспоненциально. Даже при относительно небольшом количестве составляющих частей мы очень быстро приходим к границам вычислительных возможностей110. Но что такое любая информация как не комбинация составляющих ее частей? Частей, которых может быть гораздо больше ста. Фактически любая информация — это комбинация чего-либо. Но как нужную дверь открывает далеко не любой ключ, так и не любая информация полезна. В задаче коммивояжера нас интересует не первый попавшийся путь, а именно кратчайший. Однако найти его, как мы видим, может быть очень непросто.
- Ну, мне вы можете не рассказывать про комбинаторный взрыв с его чудовищно быстрым ростом вариантов, делающим вычисления очень трудными или вообще невозможными, - улыбнулся Семченко, - Я генетик. Мы как раз имеем дело с различными комбинациями генов и тем фактом, что их возможное число огромно. Если бы матушка-природа могла перебрать все возможные варианты, то ей бы не понадобились миллиарды лет эволюции с ее мутационным блужданием наугад и беспощадным естественным отбором, убивающим те организмы, которые оказались хуже других. Она могла бы сразу выбрать самые лучшие и самые успешные образцы живого мира из всех возможных. Вот только возраста вселенной не хватит, чтобы перепробовать все возможные варианты живых существ.
- О том и речь, - согласился Поллит, - Поскольку перепробовать все возможные способы решения таких задач невозможно, то приходится действовать наугад и многое зависит от банального везения. Но не только от него. Та же задача коммивояжера приближенно неплохо решается с помощью имитации естественного отбора или строго говоря «генетического алгоритма»111. Да и эволюция живых существ вполне себе идет вперед.
- Идет, - согласился Семченко, - Только с завязанными глазами, не зная заранее каков будет результат этих попыток. Мутации и новые комбинации генов создают новые организмы. Более успешные организмы выживают, менее успешные вымирают. Выжившие передают потомкам информацию о том, как выжить.
Потомки получают ее и добавляют к ней что-то свое. Так миллиардами лет в ДНК накапливаются знания.
Фактически это обучение из поколения в поколение, делающее организмы чуть более приспособленными к текущей среде. И поскольку число возможных комбинаций генов чудовищно – эволюция никогда не заканчивается112 хоть и замедляется. Собственно, так в ее процессе и создается информация – делается случайный выбор и его результаты подвергаются естественному отбору113. Если брать ваш пример с коммивояжером, то очевидно, что разные коммивояжеры будут пробовать разные способы объехать все города. И те, у которых при прочих равных суммарный путь будет короче – будут преуспевать и постепенно вытеснят с рынка остальных.
- Если только эти остальные не скопируют маршрут самого успешного коммивояжера, по которому тот объезжает населенные пункты, и не начнут использовать его сами, - вставил Граф.
108
Bremermann, H. J. (1962). Optimization through evolution and recombination. Self-organizing systems, 93-106.
109
Paul Davies (2006). The Goldilocks Enigma. First Mariner Books. p. 43–. ISBN 978-0-618-59226-5. Retrieved 1 July 2013.
110
Krippendorff, Klaus. "Combinatorial Explosion". Web Dictionary of Cybernetics and Systems. PRINCIPIA CYBERNETICA WEB. Retrieved 29 November 2010.
111
Davis, L. (Ed.). (1991). Handbook of genetic algorithms (Vol. 115). New York: Van Nostrand Reinhold.
112
Wiser, M. J., Ribeck, N., & Lenski, R. E. (2013). Long-term dynamics of adaptation in asexual populations. Science, 342(6164), 1364-1367.
113
Quastler, H. (1964). The emergence of biological organization. New Haven: Yale University Press.