Искусство мыслить рационально. Шорткаты в математике и в жизни - [102]

Шрифт
Интервал

растет с увеличением n экспоненциально. Я уже рассказывал о том, как опасен рост этой функции, в главе 1, когда индийский царь должен был заплатить за изобретение шахмат рисовыми зернами, число которых экспоненциально увеличивалось по мере продвижения по клеткам шахматной доски. А факториал n! (произведение всех чисел от 1 до n) – это функция, рост которой на самом деле еще быстрее экспоненциального.

Таково математическое определение длинного пути: алгоритм решения задачи, время работы которого, необходимое для вычисления ответа, экспоненциально возрастает с увеличением размера задачи. Именно для таких задач хотелось бы найти шорткаты. Но что считать качественным шорткатом? Так можно назвать алгоритм, по-прежнему вычисляющий решение сравнительно быстро даже при увеличении размера задачи: так называемый алгоритм полиномиального времени.

Предположим, у меня есть случайный набор слов, которые я хочу расположить в алфавитном порядке. Сколько времени будет занимать эта работа по мере все большего удлинения списка слов? Простой алгоритм для решения этой задачи мог бы в начале просмотреть весь исходный список из N слов и выбрать из него слово, стоящее в словаре раньше всех остальных. Затем нужно повторить ту же операцию для оставшихся N – 1 слов. Таким образом, чтобы расставить по порядку все N слов, нужно будет перебрать N + (N – 1) + (N – 2) + … + 1 слово. Но благодаря шорткату Гаусса мы знаем, что для этого потребуется в общей сложности N × (N + 1)/2 = (N>2 + N)/2 просмотров.

Это пример алгоритма полиномиального времени, потому что по мере увеличения числа слов N число просмотров растет пропорционально квадрату N. В случае задачи коммивояжера нужно найти алгоритм, который сможет находить кратчайший маршрут для N городов, перебрав всего, скажем, N>2 вариантов, то есть число маршрутов, пропорциональное квадрату числа городов.

К сожалению, первые алгоритмы, приходящие в голову, не относятся к полиномиальным. По сути дела, сначала мы выбираем первый город, в который нужно заехать, затем следующий… Если на карте всего N городов, это требует перебора N! маршрутов. Как я уже говорил, эта функция растет еще быстрее, чем экспоненциальная. Следовательно, необходимо найти стратегию, более рациональную, чем перебор всех маршрутов.

Шорткат к шорткатам

Чтобы показать, что существование такого алгоритма не всегда невозможно, рассмотрим задачу, которая на первый взгляд кажется столь же непреодолимой. Выберем две точки, обозначенные на карте в числе городов, которые должен посетить коммивояжер. Какой маршрут между этими двумя городами будет самым коротким? На первый взгляд кажется, что и здесь необходимо рассмотреть множество вариантов. В конце концов, можно начать с посещения любого города, непосредственно соединенного с начальным, а затем посетить один из городов, непосредственно соединенных уже с этим. Судя по всему, с увеличением числа городов сложность такого метода снова будет расти экспоненциально.

Но в 1956 году голландский программист Эдсгер В. Дейкстра придумал гораздо более рациональную стратегию, позволяющую находить кратчайший маршрут между двумя городами за время, аналогичное тому, что занимает перестановка слов в алфавитном порядке. Он обдумывал практическую проблему прокладки самого быстрого маршрута между двумя голландскими городами, Роттердамом и Гронингеном.

Однажды утром мы с моей молодой невестой ходили по магазинам в Амстердаме, устали и сели на террасе кафе выпить по чашке кофе. Я размышлял, смогу ли я решить эту задачу, и вдруг разработал алгоритм кратчайшего пути. Его изобретение заняло минут двадцать… Одна из причин, по которым он получился таким изящным, в том, что я разработал его без карандаша и бумаги. Позднее я понял, что одно из преимуществ работы без карандаша и бумаги состоит в том, что это почти что вынуждает избегать всех осложнений, которых можно избежать. В конце концов, к моему огромному удивлению, этот алгоритм стал одним из краеугольных камней моей известности.

Рассмотрим следующую карту:


Рис. 10.3. Каков кратчайший маршрут между городами 1 и 5?


Алгоритм Дейкстры предполагает, что я начинаю путешествие из начального города, города 1. На каждом этапе я буду вычислять для каждого города промежуточную сумму расстояний, что должно помочь мне найти кратчайший маршрут. Первым делом я помечу все города, связанные с начальным, расстояниями до них. В данном случае города 2, 3 и 6 получают соответственно метки 7, 9 и 14, и первым ходом я перемещаюсь в ближайший из этих городов. Однако следует помнить, что, когда алгоритм чудесным образом решит задачу, может оказаться, что самым лучшим первым ходом был переезд совсем в другой город.

Итак, вначале я переезжаю в город 2, потому что он расположен на самом малом расстоянии от начального пункта, города 1.

Затем я присваиваю городу 1, из которого я только что уехал, метку «посещенного». Находясь в следующем пункте, городе 2, я должен изменить метки всех городов, связанных с ним. Следовательно, речь идет о городах 3 и 4. Сначала я вычисляю расстояние до них от исходного пункта, города 1, через тот пункт, в котором я нахожусь, город 2. Если новое расстояние короче, чем то, которым следующий город помечен сейчас, я присваиваю ему метку с новым расстоянием. Если новое расстояние больше, город сохраняет старую метку. В случае города 3 новое расстояние (7 + 10) больше старого; следовательно, у этого города остается старая метка с числом 9. У некоторых городов, например города 4, может не быть предыдущей метки, потому что они не связаны с городами, которые я посетил до этого. Теперь я присваиваю этим новым городам метки с только что вычисленными расстояниями до них. Таким образом, город 4 получает метку с числом 7 + 15 = 22.


Еще от автора Маркус дю Сотой
Код креативности. Как искусственный интеллект учится писать, рисовать и думать

Знаменитый оксфордский профессор и популяризатор науки Маркус дю Сотой исследует природу творчества, освещая наиболее важные аспекты работы алгоритмов и математических правил, которые лежат в их основе. Он задается вопросом, насколько наш эмоциональный отклик на произведения искусства обусловлен реакцией мозга на закономерности и структуры и что именно означает заниматься творчеством в математике, изобразительном искусстве, литературе и музыке. На основе ярких примеров того, как «поверяется алгеброй гармония» мировых шедевров, среди которых «Евгений Онегин» Пушкина, «Песнь льда и пламени» Джорджа Р.


О том, чего мы не можем знать. Путешествие к рубежам знаний

«Хотя эта книга посвящена тому, чего мы знать не можем, также очень важно понять, что мы знаем. В этом путешествии к пределам знаний мы пройдем через области, уже нанесенные учеными на карты, до самых пределов последних на сегодняшний день достижений науки. В пути мы будем задерживаться, чтобы рассмотреть те моменты, когда ученые считали, что зашли в тупик и дальнейшее продвижение вперед невозможно, но следующее поколение исследователей находило иные пути. Это позволит нам по-новому взглянуть на то, что мы сегодня можем считать непознаваемым.


Тайны чисел: Математическая одиссея

«Умение математиков заглядывать в будущее наделило тех, кто понимает язык чисел, огромным могуществом. От астрономов древних времен, способных предсказать движения планет в ночном небе, до сегодняшних управляющих хедж-фондами, прогнозирующих изменения цен на фондовом рынке, – все они использовали математику, чтобы постичь будущее. Сила математики в том, что она может гарантировать стопроцентную уверенность в свойствах мира». Маркус дю Сотой Профессор математики Оксфордского университета, заведующий кафедрой Симони, сменивший на этой должности Ричарда Докинза, Маркус дю Сотой приглашает вас в незабываемое путешествие по необычным и удивительным областям науки, лежащей в основе каждого аспекта нашей жизни. В формате pdf A4 сохранен издательский дизайн.


Рекомендуем почитать
Интеллигенция в поисках идентичности. Достоевский – Толстой

Монография посвящена проблеме самоидентификации русской интеллигенции, рассмотренной в историко-философском и историко-культурном срезах. Логически текст состоит из двух частей. В первой рассмотрено становление интеллигенции, начиная с XVIII века и по сегодняшний день, дана проблематизация важнейших тем и идей; вторая раскрывает своеобразную интеллектуальную, духовную, жизненную оппозицию Ф. М. Достоевского и Л. Н. Толстого по отношению к истории, статусу и судьбе русской интеллигенции. Оба писателя, будучи людьми диаметрально противоположных мировоззренческих взглядов, оказались “versus” интеллигентских приемов мышления, идеологии, базовых ценностей и моделей поведения.


Князь Евгений Николаевич Трубецкой – философ, богослов, христианин

Монография протоиерея Георгия Митрофанова, известного историка, доктора богословия, кандидата философских наук, заведующего кафедрой церковной истории Санкт-Петербургской духовной академии, написана на основе кандидатской диссертации автора «Творчество Е. Н. Трубецкого как опыт философского обоснования религиозного мировоззрения» (2008) и посвящена творчеству в области религиозной философии выдающегося отечественного мыслителя князя Евгения Николаевича Трубецкого (1863-1920). В монографии показано, что Е.


Технологии против Человека. Как мы будем жить, любить и думать в следующие 50 лет?

Эксперты пророчат, что следующие 50 лет будут определяться взаимоотношениями людей и технологий. Грядущие изобретения, несомненно, изменят нашу жизнь, вопрос состоит в том, до какой степени? Чего мы ждем от новых технологий и что хотим получить с их помощью? Как они изменят сферу медиа, экономику, здравоохранение, образование и нашу повседневную жизнь в целом? Ричард Уотсон призывает задуматься о современном обществе и представить, какой мир мы хотим создать в будущем. Он доступно и интересно исследует возможное влияние технологий на все сферы нашей жизни.


История инженерного дела. Важнейшие технические достижения с древних времен до ХХ столетия

Настоящая книга представляет собой интереснейший обзор развития инженерного искусства в истории западной цивилизации от истоков до двадцатого века. Авторы делают акцент на достижения, которые, по их мнению, являются наиболее важными и оказали наибольшее влияние на развитие человеческой цивилизации, приводя великолепные примеры шедевров творческой инженерной мысли. Это висячие сады Вавилона; строительство египетских пирамид и храмов; хитроумные механизмы Архимеда; сложнейшие конструкции трубопроводов и мостов; тоннелей, проложенных в горах и прорытых под водой; каналов; пароходов; локомотивов – словом, все то, что требует обширных технических знаний, опыта и смелости.


Лес. Как устроена лесная экосистема

Что такое, в сущности, лес, откуда у людей с ним такая тесная связь? Для человека это не просто источник сырья или зеленый фитнес-центр – лес может стать местом духовных исканий, служить исцелению и просвещению. Биолог, эколог и журналист Адриане Лохнер рассматривает лес с культурно-исторической и с научной точек зрения. Вы узнаете, как устроена лесная экосистема, познакомитесь с различными типами леса, характеризующимися по составу видов деревьев и по условиям окружающей среды, а также с видами лесопользования и с некоторыми аспектами охраны лесов. «Когда видишь зеленые вершины холмов, которые волнами катятся до горизонта, вдруг охватывает оптимизм.


Социальное общение и демократия. Ассоциации и гражданское общество в транснациональной перспективе, 1750-1914

Что значат для демократии добровольные общественные объединения? Этот вопрос стал предметом оживленных дискуссий после краха государственного социализма и постепенного отказа от западной модели государства всеобщего благосостояния, – дискуссий, сфокусированных вокруг понятия «гражданское общество». Ответ может дать обращение к прошлому, а именно – к «золотому веку» общественных объединений между Просвещением и Первой мировой войной. Политические теоретики от Алексиса де Токвиля до Макса Вебера, равно как и не столь известные практики от Бостона до Санкт-Петербурга, полагали, что общество без добровольных объединений неминуемо скатится к деспотизму.


Цифры не лгут. 71 факт, важный для понимания всего на свете

Канадский ученый, эколог и политолог Вацлав Смил знаменит своими работами о связи энергетики с экологией, демографией и реальной политикой, а также виртуозным умением обращаться с большими массивами статистических данных. Эта книга, которая так восхитила Билла Гейтса, обобщает самые интересные материалы, которые Смил пишет для журнала IEEE Spectrum – одного из ведущих научно-инженерных изданий мира, и представляет собой актуальное руководство для понимания истинного положения дел на нашей планете.


Как устроен мир на самом деле. Наше прошлое, настоящее и будущее глазами ученого

Наша сегодняшняя жизнь перенасыщена информацией, однако большинство людей все же не знают, как на самом деле устроен наш мир. Эта книга освещает основные темы, связанные с обеспечением нашего выживания и благополучия: энергия, производство продуктов питания, важнейшие долговечные материалы, глобализация, оценка рисков, окружающая среда и будущее человека. Поиск эффективного решения проблем требует изучения фактов — мы узнаем, например, что глобализация не была неизбежной и что наше общество все сильнее зависит от ископаемого топлива, поэтому любые обещания декарбонизации к 2050 году — не более чем сказка.


Придворный

Сочинение итальянского дипломата, писателя и поэта Бальдассаре Кастильоне (1478–1529) «Придворный», соединяющее воспоминания о придворной жизни герцогства Урбино в начале XVI века с размышлениями о морали, предназначении, стиле поведения дворянина, приближенного к государю, – одна из тех книг эпохи Возрождения, что не теряли популярности на протяжении последующих веков и восхищали блестящие умы своего и будущих столетий. Для истории культуры труд Кастильоне явился подлинной сокровищницей, и сложно представить, насколько более скудными оказались бы знания потомков об эпохе Возрождения, не будь он создан. Составленное в виде сборника занимательных и остроумных бесед, это ярко и непринужденно написанное произведение выходит за рамки источника сведений о придворных развлечениях своего времени и перечня достоинств совершенного придворного как всесторонне образованного и утонченно воспитанного человека, идеального с точки зрения гуманистических представлений.


Человеческий рой. Естественная история общества

«Эта книга посвящена захватывающей и важной для любого человека теме – осознанию себя как части общества и рассмотрению самого феномена общества под лупой эволюционных процессов в животном мире. Марк Моффетт сравнивает человеческое общество с социальными образованиями общественных насекомых, и эти сравнения вполне уместны. И его последующий интерес к устройству социальных систем у широкого круга позвоночных, от рыб до человекообразных обезьян, не случаен. Как эволюциониста, его интересы связаны с выявлением причин и факторов, влияющих на трансформации социального поведения у разных таксонов, роли экологии в усложнении общественных связей, с поиском связей между морфологическими и психологическими преобразованиями, в конечном итоге приведших к возникновению нашего вида.