Главная » C# » Алгоритм поиска в глубину в Visual C# (Sharp)

0

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

в глубину. Эта общая идея заключается в выполнении поиска данных, организанных в древовидную структуру.

ПРИМЕЧАНИЕ

Алгоритм— это логический набор конечных, повторяемых шагов дл я выполнения определенной задачи.  Этот  термин  обычно  применяется  по  отношени ю  к  формалым задачам, таким, как поиск, но в большинстве, если не во всех, компьютерных прраммах  используются  алгоритмы  того  или  иного  рода.

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

Представьте, что на пути на работу у входной двери вы осознали,  что  не  взяли ключи от машины. Хуже того, вы не помните, куда вы их положили, и вам теперь нужно искать их по всему дому. Конечно же, вы пытаетесь вспомнить, где вы их оставили, но рано утром память у вас работает туговато. Вы пытаетесь мысленно воссоздать картину своих вчерашний действий, а также думаете о возможных меах, в которых вы могли бы оставить их. Когда вы мысленно воссоздаете картину ваших прошлых действий, то следуете логике, по которой работает ваша память. Иными словами, ваш алгоритм поиска основан на предположениях, делаемых вей памятью о том, где могут быть ваши ключи. А комнаты вашего дома являются структурой данных, по которой вы мысленно проходите в вашем поиске. Одной из схем поиска, созданной вашим умственным алгоритмом поиска, может быть схема, показанная на рис. 4.1.

Рис.  4.1.  Возможный  порядок поиска  ключей

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

ПРИМЕЧАНИЕ

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

Как можно видеть на рис. 4.1, ваш поиск проходил против часовой стрелки. Пренив другую стратегию, вы могли бы обходить комнаты по часовой стрелке или зигзагами, или даже обыскивать одну и ту же комнату по несколько раз.

Теперь  преобразуем  рис. 4.1   в  программу,  которая  имеет  поисковый  алгоритм и структуру данных. Поисковый алгоритм будет поиском в глубину, а структура данных будет основана на  пути между соответствующими комнатами. Структура данных, представляющая планировку дома из рис. 4.1, и алгоритм поиска по ней показаны на рис. 4.2.

Рис. 4.2. Древовидная структура иллюстрирует каждое возможное действие.

Толстые стрелки представляют шаги при поиске в глубину, а каждый черный кружочек — комнату в доме 98                                                                                                                                                                                                               Глава   10

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

ПРИМЕЧАНИЕ

Древовидно е  представление  планировки дома  на  рис.  4.2  ни  в  коем  случае  не  являея полным, т. к. из каждой комнаты можно попасть в любу ю другую комнату. Полное представление  было  бы  комбинаторным  взрывом.

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

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

Логика поиска состоит в том, куда мы идем вниз по дереву, проходя комнату за комнатой. Алгоритм называется поиском в глубину,  потому что мы  проходим  вниз по дереву уровень за уровнем. Прохождение вниз по дереву прекращается при доижении комнаты, в которой мы уже побывали. Здесь мы возвращаемся на один уровень вверх и проходим комнату, находящуюся рядом с комнатой, в которой мы уже побывали. Это означает, что путь поиска, составленный компьютером, может быть подобным пути поиска, показанному на рис. 4.1. Это потому, что компьютер такой же глупый, как и мы спозаранку, хотя компьютер не говорит сам себе: "Если бы я только начал поиск с коридора".

Необходимо осознать, что волшебной  палочки, которая бы нашла ключи для нас, не  существует.  Метод  последовательного  перебора  всех  возможностей,  который применили  вы  и  компьютер  для  поиска  ключей,  называется  поиском  методом грубой силы (brute force). Этот метод требует выполнения больших объемов вычислий, и его применения обычно избегают. Но в данном случае применение перебора всех возможных решений является единственным решением, т. к. мы не знаем, где

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

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

Проблема избрания первого, или наиболее эффективного пути, является широко распространенной, которою можно наблюдать каждый день, если у вас в машине установлена система GPS (Global Positioning System, глобальная система навигации и определения положения). В устройствах GPS обычно применяется какой-либо поисковый алгоритм. Вы вводите в устройство с клавиатуры набор координат жаемой точки назначения, а оно будет пытаться найти наиболее быстрый или короткий путь к этой точке. В абстрактном смысле, поисковый алгоритм, примяемый производителями устройств GPS, идентичен алгоритму, который мы собаемся разработать в этой главе.

Источник: Гросс  К. С# 2008:  Пер. с англ. — СПб.:  БХВ-Петербург, 2009. — 576 е.:  ил. — (Самоучитель)

По теме:

  • Комментарии