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

0

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

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

Рис. 4.15. Первоначальный вариант оболочки для алгоритма поиска в глубину

Теперь, когда наша оболочка готова, мы можем запустить  приложение  и  провить, как все работает. Однако выполнение кода тестирования на данном этапе бет неудачным, т. к. вызов метода FindRoute () генерирует исключение. Это указает,  что  метод еще  не был  реализован.  (Исключения  подробно  рассматриваются в следующей главе.) Тем не менее, оболочка полностью готова, и мы можем пртупить к реализации алгоритма.

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

Проблема замочной скважины

Точкой входа в нашем алгоритме является метод FindRouteO. В свою очередь, входом метода FindRouteO являются два параметра: start, указывающий началый город маршрута, и end, указывающий город назначения. Выходом метода FindRoute () является массив элементов типа Node.

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

Модифицированный метод FindFout () будет выглядеть таким образом (код модикации выделен жирным шрифтом):

public Node[] FindRoute(string start, string end) { Node[] retumArray = new Node [_root. Length + 1]; return retumArray;

}

Код, в котором выделяется массив, представляет собой классическую проблему замочной скважины  (эта концепция была впервые выдвинута Скоттом Мэйерсом (Scott  Meyers),  см.  http://www.aristeia.com/TKP/).  Данная  проблема  заключается в том, что алгоритм, реализованный на ваших предположениях, работает для данного конкретного контекста,  но  не  работает  в  каком-либо  другом  контексте. То есть ваш алгоритм (ключ) разработан под конкретный контекст (замочная скважина), в то время когда нам требуется универсальный ключ, подходящий ко всем замкам.

Данный код выделяет память под массив в объеме, равном длине маршрута от коя древовидной структуры, что является необоснованным предположением.  Что если разработчик класса Node решит добавить города пересадки, в которые можно попасть из города, который не включен в корневые узлы? В таком случае сущесует возможность выйти за пределы доступной памяти в массиве. Другим решенм могло бы быть выделение массива произвольного размера х Но и тогда, в слае Х+ 1 уникальных городов, пределы этого массива могут быть нарушены.

Самым простым решением было бы вычисление,  сколько элементов  потребуется для найденного маршрута. Но и это не подойдет, т. к. тогда мы бы не знали, какой город мы уже прошли. Еще одним вариантом решения (которое подробно рассмаивается в главе 9) может быть использование коллекции.   .

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

public Node[] FindRoute(string start, string end) {

Node [ ] retumArray =

new Nbde[Node.GetMaxPossibleDestinationsArraySize()];

return returnArray;

}

Теперь с точки зрения метода DepthFirstsearch () проблема замочной скважины устранена из кода, т. к. необходимый размер массива будет указываться классом Node. Если и теперь размер массива окажется недостаточным, то источником прлемы будет класс Node, а не наш алгоритм поиска. Это не совсем идеальное решие, но иногда приходится жениться не на королевах.

Цикл for

Корневой узел (_root) предоставляет список городов, которые можно использовать в качестве начальной точки маршрута. Для начала поиска надо пройтись по городам в списке, чтобы найти начальный город, указанный в соответствующем параметре. Эта задача выполняется с помощью цикла for. Соответственно модифицированный метод будет выглядеть таким образом (код модификации выделен жирным шрифтом):

public Node[] FindRoute(string start, string end) { Node[] returnArray =

new Node[Node.GetMaxPossibleDestinationsArraySize()];

for (int cl = 0; cl < _root.Length; cl++) {

if (_root[cl].CityName.CompareTo(start) == 0) { returnArray[0] = _root[cl]; FindNextLeg(returnArray, 1, end, _root[cl]);

}

}

return returnArray;

}

Поиск начинается с нулевого индекса массива (т. е. первого элемента); конечный элемент поиска (т. е. конечный элемент массива) указывается свойством _root. Length. В каждом проходе цикла проверяется, не является ли элемент _root [cl ] .CityName начальным городом маршрута. При обнаружении начального города он присваивтся первому элементу массива, который представляет найденный маршрут (returnArray[о] = _root[ci];). После этого в действие подключается метод FindNextLeg (), который и находит возможный маршрут к городу назначения.

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

for ([начальное условие];  [конечное условие];    [модификация])    { [выполнение      действий]

}

Элементы оператора имеют следующее назначение:

•  [начальное  условие]  —  определяет  начальную  инициализацию   цикла.   Его можно рассматривать как конструктор цикла, который устанавливает состояние для итерирования. По большому счету, здесь происходит инициализация счеика предопределенным значением;

•  [конечное условие] — определяет условия для завершения цикла. В качестве примера завершения цикла можно привести достижение счетчиком максималого индекса массива, таким образом, прекращая его дальнейшую обработку;

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

Оба условия и модификация отделяются друг от друга точкой с запятой.

В С# имеются и другие операторы цикла, но оператор цикла for является единсенным, который явно предназначен для генерирования индексов. В случае примения его для обработки нашего массива _root он сгенерировал последователость значений (О, I, 2, 3 и т.д.), каждое из которых было использовано для последовательного обращения к отдельному элементу данного массива.

ПРИМЕЧАНИЕ

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

Оператор if

Когда начальный город маршрута определен, алгоритм начинает поиск промежочных городов маршрута вниз по дереву вплоть до конечного города маршрута. Поиск в глубину означает, что алгоритм будет идти вниз по дереву до тех пор, пока это возможно, после чего возвратится назад и попытается найти другие маршруты. Рекурсивное обхождение дерева управляется методом для нахождения следующего города маршрута FindNextLeg(), определение которого показано на рис. 4.16.

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

Рис. 4.16. Метод FindNextLeg () ищет следующий отрезок маршрута

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

Оператор if имеет такой синтаксис:

if( [условие]   )   { [действие]

}

else if ([условие]) {

[действие]

}

else {

[действие]

}

Операторы if, else if и else совместно представляют один логический блок (т. е. если условие в  if неверно, тогда следует проверить условие в else if; если и это

условие неверно, тогда выполняются действия, указанные в части else). Операты после первого if  являются необязательными.

Проверка условия [условие] должна возвратить значение true (истина) или false (ложь). Значение true позволяет выполнить действия, указанные в блоке; значение false вызывает переход к следующему оператору кода.

Часть els e обеспечивает обработку случаев, которые не попадают ни в одну из if-частей.

В качестве примера логики оператора  if  можно привести следующий код:

i f    (проверка1 }   {

/ /   код1

}

else if (проверка2) {

//   код2

}

else {

// кодЗ

}

// код4

Исполнение данного кода происходит таким образом:

•    если  результат проверки! положительный, тогда исполняется  код1. После  иолнения кода1 исполняется код4;

•    если  результат проверкиг  отрицательный,  выполняется  переход к els e   i f  и  волняется     проверка2\

•    если  результат  проверкиг  положительный,  тогда  исполняется  код2. После  иолнения кода2, исполняется код4;

•    если результат проверкиг отрицательный,  выполняется  переход к части  else ;

•    исполняется кодЗ. После исполнения кодаЗ, исполняется код4.

Вот еще один пример:

if     (проверка 1)    {

// код1

}

else {

//   код2

}

// кодЗ

Поток исполнения этого кода таков:

•    если  результат проверки! положительный, тогда исполняется  код1. После  иолнения кода1, исполняется кодЗ;

•    если  результат проверки!  отрицательный,  выполняется  переход к части  else;

•    исполняется код2. После исполнения кода2, исполняется кодЗ.

И еще один пример:

i f    ( проверк а 1 )   {

// код1

}

i f    ( проверка2 )   {

// код2

> else {

// кодЗ

// код4

Поток исполнения этого кода таков:

•    если  результат  проверки1  положительный,  тогда  исполняется  код1. После  иолнения кода1 выполняется  переход к части  if , где выполняется проверка2;

О   если   результат   проверки1   отрицательный,   выполняется   переход   к   части   i f

С      проверкой2\

•    если  результат  проверкиг  положительный,  тогда  исполняется  код2. После  иолнения кода2 исполняется код4;

•    если результат проверки2 отрицательный,  выполняется переход к части  else;

•    исполняется кодЗ. После исполнения кодаЗ исполняется код4.

А вот это пример неправильного применения оператора if :

else {

//   код2

}

// кодЗ

Этот код тоже неправильный:

else if (test2) {

// код2

else {

// кодЗ

В  оператор  if   можно  вставлять  другие  операторы  if ,  а  также  операторы  else и else if , таким образом, создавая более сложное многоуровневое дерево приния решений.

Булевы переменные условие или проверкам могут принимать значение true или false.

Мы уже видели примеры применения таких переменных, как в следующем коде:

if (CanContinueSearch(returnArray, currNode.Connections[cl]))

В данном операторе if если метод cancontinuesearcho возвращает true, то иолняется код, заключенный в фигурные скобки.

Вот еще один пример условия:

»

if (returnArray[cl] != null)

В этом операторе if если элемент массива returnArray [cl] не содержит значение

null, то исполняется код в фигурных скобках.

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

Понять, каким образом метод может возвратить значение true или  false, можно без проблем, но оператор сравнения элемента массива со значением null немного посложнее. В табл. 4.2 приведен список операторов сравнения и их описание.

Таблица      4.2.       Операторы       сравнения

Выражение

Описание

а   ==   b

Проверка на равенство значения  а значению b

а   ! =  b

Проверка на  неравенство значения  а значению b

а   >  b

Проверка, является ли значение а больше, чем значение b

а  <   b

Проверка, является ли значение а меньше, чем значение b

а   >=   b

Проверка, является пи значение а больше или равным значению b

а   <=   b

Проверка,  является ли значение а меньше или равным значению b

! а

Оператор инверсии,  преобразующий true в  false и наоборот

Кроме этого, совместно с операторами принятия решения можно использовать слующие логические операторы:

AND (&&) —  возвращает  true, если  оба  операнда  сравнения  возвращают  true, и false в противном случае;

OR (| |) —  возвращает  false, если  оба операнда сравнения  возвращают  false, и true в противном случае.

Логические операторы применяются для составления сложных выражений сравния из простых, например, как это:

if ((а == Ь) && (Ь == с))

Данное составное выражение состоит из двух простых выражений проверки значий на равенство. Сначала выполняются операции сравнения во внутренних скоах, их результаты временно сохраняются, а потом с помощью логического оперора AND (&&) сравниваются между собой. Если оба первые сравнения возвратили true, то оператор AND также возвратит true. В данном случае оператор проверяет: а равно ь и равно с?

Предотвращение повторений в маршруте

Метод для нахождения следующего города FindNextLeg () вызывает метод CanContinue (), назначением которого является прекращение поиска. Другими слами,  мы  не  хотим,  чтобы  по  маршруту,  найденному  нашим  алгоритмом  поиска в глубину, мы посещали один и тот же город дважды. Код этого метода подобный коду самого метода FindNextLeg () :

private bool CanContinueSearch(Node[] returnArray, Node city) { for (int cl = 0; cl < returnArray.Length; cl++) {

if (returnArray[cl] != null) {

if (returnArray[cl].CityName.CompareTo(city.CityName) == 0) { return false;

}

}

return true;

Логика метода CanContinueSearch о заключается  в том, что он проверяет в цикле массив returnArray (содержащий найденный путь) на предмет содержания в оом из его элементов города, который в данный момент рассматривается в качестве следующей точки маршрута (переменная city). Если массив содержит данный год, то поиск в этой ветви дерева прекращается; в  противном случае поиск  пролжается.

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

По теме:

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