Реализация алгоритма поиска в глубь подразумевает создание алгоритма, который перебирает дерево. Здесь мы реализуем алгоритм на языке С#. Для этого мы используем :г:ераторы, принимающие решение, и операторы цикла for, осуществляющие перебор -2-нных массива. Они невероятно популярны в программах на языке С#, и жизнь без зк была бы очень трудна. В предыдущем разделе мы реализовали проверочный код, а следующий шаг под--ззумевает реализацию версии метода DepthFirstSearch (), представляющего со-5ой оболочку, обешечивающую правильность компиляции и выполнения всего кода. Волочка — это структура, используемая для поддержки всего приложения. Она опре¬делена, как показано на рис. 4.15. Реализовав оболочку, вы могли бы запустить приложение и убедиться, все ли рабо¬тает. Если вы запустите проверочный код, то получите ошибку, поскольку вызов метода Fir.lRoute () создаст исключение, указывающее на отсутствие его реализации. (Более подробная информация об исключениях приведена в следующей главе.) Теперь, когда :солочка закончена, мы готовы реализовать внутренности алгоритма. Реализация внутренности алгоритма — возможно, один из наиболее трудных этапов ~ эграммирования, поскольку вы должны продумать логику того, что собираетесь сде-ить. Всякий раз, когда я встречаюсь с алгоритмом, который нуждается в реализации, =. не совсем уверен, как пойдет дело, я просто пишу код на основании точек входа и то-чек выхода. Проблема замочной скважины В примере точки входа и выхода алгоритма — это метод FindRoute (). В свою оче¬редь, вход метода FindRoute () — это два параметра: start, означающий начальный город, и end, означающий город назначения. Выход метода FindRoute () — массив эле¬ментов Node. Массив элементов Node следует предварительно зарезервировать с пространством, достаточным для добавления всех городов, которые могли бы быть найдены. На на¬стоящий момент мы можем сделать предположение, что предварительно резервируем количество узлов по длине переменной-члена DepthFirstSearch () ._root плюс один. Предположение основано на том, что самая длинная поездка не может превышать ко¬личество доступных городов. Известно, что корневой узел — это массив всех отправных городов; таким образом, резервирование никогда нельзя превышать. Сосредоточимся на методе FindRoute О, измененный код выглядит следующим образом: public Node [ ] FindRoute(string start, string end) { Node[] returnArray = new Node [_root. Length + 1] ; return returnArray; } Код резервирования массива — классическая проблема замочной скважины, идея. впервые представленная Скоттом Мейерсом (Scott Meyers) (http://www.aristeia.com, ТКР). Проблема замочной скважины заключается в том, что вы реализуете алгоритм на основании предположения; вот причина того, что написанный код работает лишь для определенного контекста, но терпит неудачу при выполнении в другом контексте. Код резервирует массив длиной в корень древовидной структуры, и это главное пред¬положение. Представьте, что разработчики Node решили представлять связи, которые могли бы быть доступны только через другой город, который не включен в корневые узлы. В этом случае вы могли бы превысить доступное пространство в массиве. Другое решение подразумевало бы резервирование массива произвольной длины х. Но если за¬тем появится х+1 уникальный город, то и этот массив будет нарушен. Самое простое решение подразумевало бы не резервирование массива, а выяснение количества необходимых элементов по найденному пути. Но это не сработало бы пото¬му, что вы понятия не имеете, какой город вы уже посетили. Другое решение (обсужда¬ется в главе 9, "Списки, делегаты и лямбда-выражения") заключается в использовании класса коллекции. В данном случае мы собираемся умыть руки и вынудить разработчиков узла Node изменить их класс. Разработчики класса Node добавят статический метод, который со¬общит алгоритму поиска размер необходимого массива. Далее приведен измененный код метода FindRoute (). public Node[] FindRoute(string start, string end) { Node[] returnArray = new Node[Node.GetMaxPossibleDestinationsArraySize()]; return returnArray; } Теперь код не имеет проблемы замочной скважины с точки зрения метода DepthFirstSearch () , потому что класс Node всегда будет указывать подходящий раз¬мер для массива. Если места все же не хватит, то это будет проблема класса Node. Это не идеальное решение, но иногда передача ответственности — это единственный выход. Использование цикла for Корневой узел (_root) ссылается на список городов, которые являются доступными отправными пунктами. Чтобы начать поиск, сначала необходимо сопоставить началь¬ный город параметру start при переборе списка городов. Для этого необходим цикл for. Вот модифицированный исходный код метода FindRoute (). 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; } Цикл for начинается с 0 и проходит до конца массива _root, используя свойство __root. Length. На каждой итерации цикла проверяется свойство root [cl ] . CityName на предмет начального города. Затем начальный город присваивается как первый город з массиве, который представляет найденный маршрут путешествия (returnArray [0] = root [cl] ;). И наконец, метод FindNextLeg О используется для поиска возможного маршрута до места назначения. Цикл for используется для перебора серии а на основании некой логики. Как пра-вило, для этого используется инкремент (приращение) или декремент числа, но может быть использована и другая логика. Цикл for имеет следующий формат: for ([начальное условие]; [условие окончания]; [модификация] ) [Операторы, выполняющие нечто] • [начальное условие] определяет инициализацию цикла. Считайте это конструк¬тором цикла, который устанавливает начальное состояние итерации. Как прави¬ло, это инициализация счетчика с предопределенным значением. • [условие окончания] определяет условие завершения цикла. Пример выхода из цикла — когда счетчик достигает максимальной длины массива и, таким образом, не остается элементов для обработки. • [модификация] реализует шаг перебора ряда. Считайте это перемещением от те¬кущего состояния к следующему состоянию. Если вы используете счетчик, то это означало бы приращение или уменьшение значения счетчика. Точка с запятой разделяет условия и модификацию друг от друга. В языке С# существуют и другие типы циклов, но цикл for — единственный из соз-j ающих индексы для других частей кода. В случае перебора массива он создал бы ряд : :ел (О, 1, 2, 3 и т.д.), каждое из которых можно было бы использовать для обращения элементу массива _root. На заметку. Эмпирическое правило для цикла for — он используется для создания индексного ряда, применяемого для обращения к другим элементам информации. Индексный ряд мог бы быть прямой ссылкой на элемент массива или использоваться для итерационных вычислений. Индексный ряд не должен осуществлять инкремент или декремент значений. Он также должен создать логический индексный ряд. Использование условного оператора if Когда отправной город найден, алгоритм приступает к поиску по дереву. Поиск в глубь означает, что поиск будет осуществляться по дереву вниз, насколько это возмож¬но, с возвращением назад и попыткой найти другие маршруты. Рекурсией следования по дереву и обратно занимается метод FindNextLeg (), определенный так, как показано на рис. 4.16. Основная идея заключается в том, чтобы выбрать маршрут перелета в ходе пере¬бора дерева связей в надежде, что одна из них приведет к конечной точке. Обратите внимание, что для каждого транзитного участка счет параметров увеличивается, и вы переходите по дереву на уровень глубже, а найденный город присваивается массиву маршрута. Основой этой функции является код принятия решения, представленный блоком кода if. Блок кода if говорит, "если результат проверки будет истинным, то выполнить код внутри фигурных скобок рядом с блоком if; в противном случае перейти к коду сразу после блока if". Условный оператор i f имеет следующий формат: i f( [условие] ) [Выполнить действие] } else if( [условие] ) [Выполнить действие] else [Выполнить действие] Операторы if, else if и else представляют один фрагмент логики (например, если гсловие не выполняется, то проверить следующее условие else if; если и оно не вы¬полняется, то сделать то, что указано после оператора else). Операторы после первого . f необязательны. Выражение [условие] может быть истинно (true) или ложно (false). Значение true :значает выполнение действий внутри блока if, а значение false означает переход к :ператору кода после блока if. Оператор else — эуо своего рода значение по умолчанию, или "все остальное"; его :лок выполняется, если ни один из предыдущих операторов if не оказался истинным. Вот пример логики оператора if. if(условие!) II Код1 else if(условие2) II Код2 else II КодЗ Код4 Этот код выполняет следующие шаги. • Если условие! истинно, то выполнить Код!. После выполнения Код! выполнить Код4. • Если условие! ложно, перейти к оператору else if с условием условие2. • Если условие2 истинно, то выполнить Код2. После выполнения Код2 выполнить Код4. • Если условие2 ложно, то перейти к оператору else • Выполнить КодЗ. После выполнения КодЗ выполнить Код4. Вот еще один пример. if{условие!) I Код! } else{ // Код2 ) II КодЗ Этот код выполняет следующие шаги. • Если условие! истинно, то выполнить Код!. После выполнения Код 1 вьтолнить КодЗ. • Если условие! ложно, перейти к оператору else. • Выполнить Код2. После выполнения Код2 выполнить КодЗ. Вот еще один пример. if(условие!) II Код! if(условие2) II Код2 else // КодЗ ■ II Код4 Этот код выполняет следующие шаги. • Если условие! истинно, то выполнить Код!. После выполнения Код! перейти к оператору i f с условием условие2. • Если условие! ложно, перейти к оператору if с условием условие2. • Если условие2 истинно, то выполнить Код2. После выполнения Код2 выполнить Код4. • Если условие2 ложно, перейти к оператору else. • Выполнить КодЗ. После выполнения КодЗ выполнить Код4. Следующий код недопустим: g else { // Код2 } II КодЗ Этот код также недопустим. else if(условие2) { II Код2 } else { // КодЗ } Оператор if вполне можно встроить внутрь других операторов else, if или else if, чтобы создать более сложное многоуровневое дерево принятия решений. Условие, или условием, — это логическая переменная или выражение, возвращаю-дее логическое значения true или false. Вы уже видели примеры, подобные этому. if (CanContinueSearch (returnArray, currNocle .Connections [el] ) ) Оператор if говорит, что если метод CanContinueSearch () возвращает значение : rue, то следует выполнить код внутри фигурных скобок. Вот еще один пример условия. if (returnArray[cl] != null) Этот оператор if говорит, что если элемент массива returnArray [cl] не содержит значения null, то следует выполнить код внутри фигурных скобок. В обоих примерах метод или операция сравнения, должны возвратить логическое Е : jlean) значение (true или false). Если возвращено не логическое значение, то ком¬пилятор С# выдаст сообщение об ошибке, указывающее, что код не создал значение false или true. Довольно просто увидеть, как метод может создать значение false или true. Но опе- : агор, где элемент массива содержит значение, не равное null, немного более сложен. 3 т: пример использования операторов при выполнении сравнения. При сравнении -:: зеряется, равны ли значения или нет. Иногда эти проверки просты, а иногда могут казаться очень сложны. В табл. 4.2 показаны операторы сравнения и их смысл. "=блица 4.2. Операторы сравнения Выражение Описание ?. == b Равны ли значения а и Ь? = ! = Ь Не равны ли значения а и Ь? = > b Значение а больше, чем Ь? ъ < Ъ Значение а меньше, чем Ь? :- >= b Значение а больше или равно Ь? ъ <= b Значение а меньше или равно Ь? Оператор инверсии. Если а имеет значение true, то будет false, а если false — будет true Кроме того, вы можете использовать следующие логические операторы2. • AND (&&). Если обе сравниваемые стороны имеют значение true, то возвращается urue; в остальных случаях false. • OR (II). Если обе сравниваемые стороны имеют значение false, то возвращается false; в противном случае true. Выражения не обязаны быть простыми. Они могут быть объединены, подобно ледующему: if ( (а == b) && (b == с) ) Этот пример имеет два выражения и четыре проверки3. Проверки заключены в круг-: - скобки, сначала проверяются равенства, а их результаты временно сохраняются. ггем результаты сравниваются с помощью оператора AND (&&). Если оба результата саны, то оператор AND возвратит истину. В двух словах, решающие проверки — : р авенства значений а, Ь и с. Предотвращения повторения маршрута Метод FindNextLeg () содержит ссылку на метод CanContinue (), который предназна¬чен для остановки поиска. В случае нашего алгоритма поиска в глубь задача заключа¬ется в избежании перелета в тот же город дважды. Функция FindNextLeg О содержит следующий код: private bool CanContinueSearch(Node [ ] returnArray, Node city) f for (int cl = 0; cl < returnArray.Length; cl++) t if (returnArray[cl] != null) ( if (returnArray[cl].CityName.CompareTo(city.CityName) == 0) { return false; } 1 } return true; } Логика метода CanContinueSearch () в переборе массива returnArray и выявлении совпадающих городов (переменная city) в уже найденном пути. Если город в маршруте уже есть, то мы прекращаем поиск в этой части дерева; в противном случае продолжа¬ем искать.