Задача на поиск пути в реальной жизни

Допустим, у вас есть такая задача: вам необходимо добраться из точки А в точку В, и вы не знаете, как туда можно попасть. Что вы сделаете в этом случае?

Ответ студента, обучающегося по программе MBA: «Я взял бы свой сотовый и ввел точки А и В в Google Maps. Если точки В на этой карте нет, я вызвал бы такси, доехал до нее, а потом отдал бы счет в бухгалтерию. Задавайте следующий вопрос».

Доктор со степенью в компьютерных науках ответил бы так: «О, я знаю. Вы спрашиваете о задаче отыскания сети…»

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

Давайте изменим формулировку вопроса. Вы находитесь в точке A и хотите отыскать точку B, но никакого руководства для этого у вас нет. Вам придется изучить дороги и тропинки, ведущие из A. Вы отыщете точку B только тогда, когда в нее попадете (если это вообще случится). Но вы можете в ней и не оказаться. Точка B может находиться вне сети дорог и поэтому быть недоступной.

Вам следует начать с ряда важных вопросов, которые надо задать интервьюеру.

1. Могу ли я спрашивать дорогу у других? Могу ли я воспользоваться GPS? Имеется ли какой-то способ оценки направления или расстояния до точки B?
2. Если в точку B нельзя попасть из точки A, есть ли какой-то способ, позволяющий это понять, чтобы прекратить бессмысленный поиск?
3. Я должен найти точку B так быстро, как это возможно, или мне нужно постараться найти самый быстрый путь из точки A в точку B, то есть максимально короткий?

Любят, любят интервьюеры такие вопросы! Несомненно, человек, который их задает, достаточно умный, чтобы уточнить детали. Но при ответе на первый ваш вопрос они сообщат, что вы не сможете получить надежные рекомендации, связанные с направлением поиска.

Второй вопрос важен потому, что умные инженеры стараются не тратить понапрасну время и усилия, если они все равно не приведут к нужному результату. Вы ведь не хотите обыскать всю планету, и, в конце концов, сделать вывод, что попасть в B из A нельзя.

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

Вы хотите получить процедуру поиска, которая отыщет точку B как можно быстрее. Однако в этом лабиринте почти всегда есть повороты, вводящие в заблуждение, и путь, который вы проделаете до выхода (от A до B), не обязательно будет самым коротким. Впрочем, в вашей ситуации это не самое главное.

А вот вам альтернативный пример: вы хотите добираться из дома (A) на работу (B) общественным транспортом. Вы подбираете для себя маршрут, чтобы потом ездить каждый рабочий день. Поэтому вы не просто ищете путь до B, но и хотите, чтобы дорога от A до B была самой короткой.

В любом поиске приходится в той или иной мере прибегать к пробам и ошибкам. Какую-то роль в этом процессе играют, конечно, ваши знания или интуиция. Может быть, вы заранее убеждены, что в B можно попасть при помощи карт, догадок, встречных местных жителей, мудрости, оставшейся у нас со времен трапперов французской Канады, или дорожных знаков, указывающих, что до точки B осталось 17 миль. Однако в любом случае процедура поиска должна быть как-то упорядочена независимо от того, какой информацией вы располагаете (и учитывая тот факт, что эта информация необязательно является надежной). Вы начнете с изучения маршрута, который, как вы считаете, является, самым коротким путем до B. По мере вашего продвижения составляйте карту, чтобы в случае чего вы могли вернуться назад и попробовать другие пути.

До сих пор все рекомендации бесспорны. Чтобы произвести впечатление на интервьюера, вам необходимо заявить что-то не столь очевидное. Скажем, попробуйте следующее: «Фундаментальный философский вопрос при поиске места назначения — когда мне следует повернуть назад?»

Бывают времена, когда вы чувствуете, что заблудились, то есть у вас появилась мысль, что вы отклонились от пути, ведущего от А к В. Вернетесь ли вы туда, где были до этого, до того, как сбились? Или вы постараетесь отыскать прямой путь до В от того места, где вы сейчас находитесь?

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

«Да ну, это бессмысленно, — возражает Бен. — Мы уже столько проехали, скорее всего мы теперь находимся ближе к В, чем были до этого. Впереди должен быть какой-то указатель».

Стратегия Бена напоминает вариант, который ученые-компьютерщики называют первым лучшим алгоритмом. Всякий раз, когда вы добираетесь до развилки на дороге, вы следуете тем путем, который вам кажется самой короткой дорогой к В, и делаете это основываясь на том, что вы знаете. Если вам повезет, это знание окажется на 100% точным, и тогда Бен доберется до пункта В кратчайшим путем.

Стратегия Эшли скорее напоминает поисковый алгоритм А* (произносится А звездочка), описанный учеными-компьютерщиками Питером Хартом, Нилсом Нилссоном и Бертраном Рафаэлем в 1968 году. Его суть (в самом первом приближении) следующая: вам следует стремиться к выбору самой близкой к самой короткой дороге из А в В. Вы, вероятно, удивитесь, а чем этот вариант, собственно говоря, отличается от стратегии Бена? Ничем, если вы на правильном пути. А вот если вы уклонились… Принимая решение, что делать дальше, Бен ориентируется на единственный аргумент — свою догадку о том, насколько далеко В лежит от того места, где Бен сейчас находится. Бен всегда пытается двигаться в сторону В. Эшли же опирается на два факта: свою оценку расстояния до В и свое знание расстояния по дороге от А до того места, где он сейчас находится. Цель Эшли минимизировать оба числа или, что будет точнее, их сумму. Эшли пытается изучить точки, которые с максимальной вероятностью лежат на кратчайшем пути между А и В.

Кто прав, Бен или Эшли? Процедура поиска Эшли лучше, когда приходится иметь дело с поворотами, заводящими не туда, куда нужно. Сущность ее подхода показана на приведенной ниже диаграмме. Начав из А, путешественник добирается до развилки дорог и должен выбрать, налево или направо ему податься. Если Бен выберет левый путь — ошибочный! — ему придется отправиться длинным кружным путем. После многих блужданий путь приведет его ближе к В.

Если Эшли также повернет неправильно, в данном случае налево, она через какое-то время поймет, что проделала уже слишком длинный путь от A, а В все еще не видать. Это для нее знак, что она, скорее всего, выбрала не самый короткий путь. Тогда Эшли вернется к развилке и попробует другой путь. И есть вероятность, она доберется до В быстрее, чем Бен.

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

Вернемся на интервью. Предпочтение стоит отдать поиску в виде А*, поскольку в формулировке вопроса утверждается, что вы не знаете, можете ли вы вообще добраться до места. Если пути, позволяющего добраться до В нет, Бен будет бродить целую вечность. Эшли исследует системно все пути, ведущие из пункта А, поскольку она минимизирует расстояние, пройденное от А. Затем она составит карту территории, которая поможет ей определить, что возможности добраться из А в В нет. Это позволит ей не тратить напрасно ресурсы.

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

Подведем итоги. Пытаясь добраться из точки А в точку В, старайтесь как можно ближе держаться дороги, которая, как вы полагаете сейчас, является самой короткой (поиск А*), и не пытайтесь просто отыскать пункт В.