Хаос. Как беспорядок меняет нашу жизнь к лучшему

Рассмотрим следующую задачу: наложить контур на кремниевую микросхему. Описание назначения контура[10] говорит нам о том, как именно сочетаются части компонентов. Но существуют миллионы миллионов возможных способов проложить разводку и интегральные схемы, составляющие контур, — и одни из них будут эффективнее других, что влияет на производительность чипа. Этот пример того, что математики называют задачей недетерминированной полиномиальной сложности (НП-проблемой). НП-проблемы похожи на огромные кодовые замки: если у вас есть комбинация, вы легко проверите, работает ли она, но потребуется бесконечно долгий период, чтобы отыскать решение самостоятельно, методично пробуя каждый вариант.

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

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

Оптимальный вариант — последовать примеру Брайана Ино и внести в свои действия разумную долю случайности. К примеру, алгоритм под названием «имитация отжига» запускается с практически случайного поиска, с целью опробовать любое изменение — хорошее или плохое. Постепенно изменения вносятся с большей придирчивостью, до тех пор, пока алгоритм не превратится в пошаговый избирательный поиск небольших улучшений. Этот подход не гарантирует, что вы получите лучшую раскладку, но он обычно приводит к хорошему результату. Комбинация постепенных улучшений и случайных изменений — эффективное решение сложных задач. Например, когда нужно оценить возможности медицинского использования новой молекулы, сравнив ее структуру со структурой других молекул, лечебные свойства которых уже известны. Другие примеры таких проблем: планирование расписания (график экзаменов, удобный для каждого студента) и логистика (прокладка оптимального маршрута для доставки посылок).

Вот аналогия: представьте, что вы участвуете в странном конкурсе по поиску самой высокой точки планеты, и при этом картой пользоваться нельзя. Вы можете назвать любые координаты, и вам скажут высоту над уровнем моря в этом месте. Допустим, «50,945980, 6,973465» с ответом: «Эта точка находится в 65 метрах над уровнем моря». Затем вы можете назвать следующие координаты, затем другие — сколько угодно раз, пока не выйдет время.

Какой стратегией вы воспользуетесь? Как и в случае с прошлыми задачами, можно прибегнуть к методичному поиску: начать с «0,000001, 0,000001» и продолжить в том же духе, увеличивая значения. В таком случае вы вряд ли найдете нужную высоту к тому моменту, как закончится время.

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

Принципиальная альтернатива представляет собой метод поиска экстремума, аналогичный пошаговым улучшениями в контуре кремниевого чипа. Начните в случайной точке и затем просмотрите все близлежащие координаты, скажем, на метр в каждом направлении. Выберите самый высокий пункт и повторяйте весь процесс снова и снова. Алгоритм поиска экстремума гарантированно приведет вас к самой высокой точке на местности, из которой каждый шаг будет спуском. Данная стратегия поможет, если с первой же догадкой вы попадете к подножию высоченной горы. Но с тем же успехом можно указать и на песчаную дюну или питчерскую горку^{5}. Метод поиска экстремума заведет вас в тупик, если вы окажетесь на местности с ровным ландшафтом.