AI подразумевает поиск данных, а фактической основой AI является алгоритм по¬иска. (Алгоритм — это просто упорядоченный, воспроизводимый набор шагов, кото¬рые можно предпринять для решения проблемы или достижения желаемого результа¬та.) Алгоритм, который мы разработаем для этой главы, называется системой поиска в глубь (depth-first search). AI имеет и другие типы поисков, например А* или поиска в иирину (breadth-first search), но все они основаны на той же идее, что и алгоритм поис¬ка в глубь. Идея заключается в том, чтобы искать информацию, которая расположена в древовидной структуре. Давайте начнем с объяснения того, что делает алгоритм поиска в глубь и почему мы используем его. Проблема в том, как добраться из точки А в точку Б наиболее эффектив¬ным способом. Общий случай этой проблемы можно сформулировать так: "Как решить задачу А, имея X возможностей?" Вообразите, что вы собрались ехать на работу и находитесь перед дверь своего дома. Вы не знаете, где ваши ключи, и начинаете искать их. Обшаривая комнаты, вы сле¬дуете логике своей памяти. В данном случае ваш алгоритм поиска основан на предло¬жениях вашей памяти о том, где ключи могли бы быть. Структура данных, которой вы управляете, это комнаты вашего дома. Ваш мысленный алгоритм поиска мог бы создать схему, подобную представленной на рис. 4.1. На рис. 4.1 вы находите ключи в коридоре, но алгоритм поиска сбил вас с пути на некоторое время, так как вы искали в коридоре в последнюю очередь. Вы даже не знае¬те, что разработали алгоритм поиска, который на этот раз подвел. Но в следующий раз тот же самый алгоритм мог бы оказаться удачным. На заметку. Поиск с разными стратегиями очень похож на то, как вы пишете компьютерные алго¬ритмы. Не существует одного самого лучшего алгоритма; есть только хорошие алгоритмы, но с некоторыми компромиссами. Когда вы реализуете алгоритм, необходимо найти тот, который лучше всего подходит к вашим потребностям при наименьшем количестве компромиссов, ко¬торые могли бы вызвать проблемы. Как видно на рис. 4.1, вы искали против часовой стрелки. При другой стратегии поиска, по часовой стрелке или даже зигзагом, вы обыскали бы другое количество комнат. Давайте преобразуем рис. 4.1 в программу, которая имеет алгоритм поиска и струк¬туру данных. Используем алгоритм поиска в глубину, а структура данных будет основа¬на на пути между соответствующими комнатами. Структура данных, представляющая дом на рис. 4.1, приведена на рис. 4.2. В древовидной структуре, показанной на рис. 4.2, каждый узел представляет ме¬сто назначения, который можно достигнуть из определенного места в доме. Из каждой комнаты можно попасть в другую комнату. Но эта структура рекурсивна. Например, из детской вы можете попасть в гостиную, а затем снова в детскую. Даже двигаясь по дереву вниз, вы переходите из одной комнаты в другую и обратно к исходной комнате. Это прекрасно работает с точки зрения структуры данных, хотя вы, вероятно, скажете: "Но это неправильно, поскольку некоторые комнаты вовсе не рядом." На заметку. Древовидное представление на рис. 4.2 ни в коем случае неполно, поскольку из каж¬дой комнаты вы можете перейти в другую комнату. Полное древовидное представление было бы похоже на комбинаторный взрыв. В данном случае структура данных — это представление дома. Если бы вы обыски¬вали этот дом, то смогли бы переходить из одной комнаты в другую и обратно? Уверен, что да. Но делали бы вы это? Нет, поскольку здравый смысл подсказывает, что вы повто¬ряетесь и тратите время и силы впустую. Тот же трюк используется и при написании приложений. У вас есть структура данных и алгоритм, который работает со структурой данных. Я называю это построением приложения по уровням. На самом нижнем уровне находится интеллектуальная структура данных, а на самом высоком уровне — исполь¬зование функциональных возможностей интеллектуальной структуры данных. Под интеллектуальной структурой данных (intelligent data structure) я понимаю всегда однозначную структуру, не способную повредить саму себя. В этом примере ком¬ната не будет указывать на себя саму, комната будет присутствовать в структуре, только если она существует в доме, и т.д. Высокоуровневый алгоритм нес бы ответственность за выяснение того, как искать информацию по дереву. Он должен быть достаточно ин¬теллектуален, чтобы не ходить между двумя комнатами туда и обратно и не делать чего-нибудь другого, впустую тратя время. Логика поиска — это то, как вы, спускаясь по дереву, переходите из одной комнаты в другую. Это называется алгоритмом поиска в глубь, поскольку вы перебираете дерево, спускаясь по дереву уровень за уровнем. Вы прекращаете перебирать дерево, как толь¬ко попадаете в комнату, в которой уже были. Затем вы возвращаетесь на один уровень и переходите в комнату рядом с той, в которой уже были. Безусловно, путь поиска, вы¬бранный компьютером, может закончиться так же, как на рис. 4.1. Дело в том, что ком¬пьютер использует тот же подход, который использовали вы, хотя, конечно, компьютер не скажет себе, "если бы только я начал с коридора". Техника, которую использовали вы и компьютер, называется решением "в лоб", это довольно ресурсоемкий путь, его обычно стараются избегать. В данном случае решение "в лоб" — единственное реальное решение, поскольку вы не знаете, где ключи, а они могут быть в любом месте. Если не повезет, ключи окажутся в последней осматриваемой вами комнате. Выбор пути, который стоит пройти сначала, а также выбор наиболее эффективно¬го пути — это обычная проблема, свидетелем которой вы можете быть каждый день, если на вашем автомобиле имеется глобальная система позиционирования (Global Positioning System — GPS). Различие между алгоритмами поиска, используемыми GPS и нами при поиске ключей, в том, что вы даете GPS отправную точку и конечную. На основании этой информации GPS пытается найти самый быстрый или самый ко¬роткий путь между двумя пунктами. В абстрактном смысле алгоритм поиска, который применяют изготовители GPS, идентичен алгоритму^поиска, который мы собираемся разработать в этой главе.