компьютер будет обладать вычислительной мощностью
(1.36×10>50)×10>53=1.36×10>103 бит в секунду
- Если допустить, что на проверку каждого варианта пути будет тратиться одна секунда, то на проверку всех вариантов компьютером размером со вселенную уйдет
4,666*10>155/1,36*10>103=3,43*10>52 секунд
- Это опять-таки намного порядков больше чем возраст нашей вселенной. Ждать в общем придется долго. Мораль проста. При решении с помощью перебора многих с виду простых проблем число возможных вариантов растет экспоненциально. Даже при относительно небольшом количестве составляющих частей мы очень быстро приходим к границам вычислительных возможностей110. Но что такое любая информация как не комбинация составляющих ее частей? Частей, которых может быть гораздо больше ста. Фактически любая информация — это комбинация чего-либо. Но как нужную дверь открывает далеко не любой ключ, так и не любая информация полезна. В задаче коммивояжера нас интересует не первый попавшийся путь, а именно кратчайший. Однако найти его, как мы видим, может быть очень непросто.
- Ну, мне вы можете не рассказывать про комбинаторный взрыв с его чудовищно быстрым ростом вариантов, делающим вычисления очень трудными или вообще невозможными, - улыбнулся Семченко, - Я генетик. Мы как раз имеем дело с различными комбинациями генов и тем фактом, что их возможное число огромно. Если бы матушка-природа могла перебрать все возможные варианты, то ей бы не понадобились миллиарды лет эволюции с ее мутационным блужданием наугад и беспощадным естественным отбором, убивающим те организмы, которые оказались хуже других. Она могла бы сразу выбрать самые лучшие и самые успешные образцы живого мира из всех возможных. Вот только возраста вселенной не хватит, чтобы перепробовать все возможные варианты живых существ.
- О том и речь, - согласился Поллит, - Поскольку перепробовать все возможные способы решения таких задач невозможно, то приходится действовать наугад и многое зависит от банального везения. Но не только от него. Та же задача коммивояжера приближенно неплохо решается с помощью имитации естественного отбора или строго говоря «генетического алгоритма»111. Да и эволюция живых существ вполне себе идет вперед.
- Идет, - согласился Семченко, - Только с завязанными глазами, не зная заранее каков будет результат этих попыток. Мутации и новые комбинации генов создают новые организмы. Более успешные организмы выживают, менее успешные вымирают. Выжившие передают потомкам информацию о том, как выжить.
