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

0

Все необходимые компоненты алгоритма поиска в глубину, включая тесты, были реализованы, и теперь мы готовы приступить к его тестированию. Для первого теа попробуем найти маршрут между Монреалем и Сиэтлом. На рис. 4.7 можно веть, что существуют два варианта этого маршрута: через Лос-Анджелес и через Торонто. Но наш алгоритм выдает следующий, довольно странный, результат (мы не рассматривали, как выводить результаты на экран, но это довольно легко сдать, применив оператор цикла for для обработки массива foundRoute, который содержит города найденного маршрута):

Montreal New York Houston Miami Toronto Seattle

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

Тем не менее, несмотря на такие странные результаты, алгоритм работает должным образом. Проблема же лежит в другой плоскости — метод cancontinuesearcht) не содержит функциональности для оптимизации маршрута. На данном этапе алгитм настроен на выполнение поиска в глубину, т. е. на следование вниз по дереву, перед тем, как возвращаться обратно. Давайте-ка мы сами пройдемся по структуре в статическом конструкторе класса Node.

Наш  маршрут начинается  в Монреале,  откуда можно лететь  в следующие  города (определенные в connections):

montreal.Connections = new Node[3]; montreal.Connections[0] = newyork; montreal.Connections[1] = toronto; montreal.Connections[2] = losangeles;

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

newyork.Connections = new Node[3]; newyork.Connections[0] = montreal; newyork.Connections[1] = houston; newyork.Connections[2] = miami;

Здесь первым городом продолжения полета является Монреаль, но мы уже там би и он занесен в найденный маршрут. Поэтому выбирается второй элемент масса, которым является Хьюстон. Летим в Хьюстон.  Из Хьюстона мы можем лететь в следующие города:

houston.Connections = new Node[3]; Houston.Connections[0] = miami; houston.Connections[1] = Seattle;

houston.Connections[2] = newyork;

Здесь  первым  выбором  является  Майями,  где  мы  еще  не  были,  поэтому летим  в Майями. В Майями у нас следующий выбор городов для продолжения нашего полета: miami.Connections = new Node[3];

miami.Connections[0] = toronto; miami.Connections[1] = houston; miami.Connections[2] = newyork;

В Майями первым выбором опять является город, в котором мы еще не были — Торонто — поэтому летим в Торонто. В Торонто выбор городов для продолжения нашего полета таков:

toronto.Connections = new Node[3]; toronto.Connections[0] = miami; toronto.Connections[1] = Seattle; toronto.Connections[2] = montreal;

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

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

Советы разработчику

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

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

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

•    Структуры  данных и алгоритмы  не обязательно должны  быть  в одном  классе.

Они могут быть разных типов и часто таковыми и являются.

•    Структуры данных можно реализовать в виде обычных (struct) или ссылочных

(class) типов.

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

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

•    Конструктор представляет собой специальный тип метода, который вызывается для создания экземпляра типа. При необходимости принудительного присваания объекту правильного состояния, которое можно верифицировать, с консуктором применяются параметры.

•    При выборе ссылочного или обычного типа решение должно приниматься на основе контекста,  в котором будет применяться структура данных. Если созда-

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

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

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

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

•    При создании кода с применением циклов рассматривайте операторы в фигуых скобках как код, который генерирует индексы для последовательного оащения к настоящей информации, обрабатываемой в цикле.

•    Для принятия решений используются комбинации операторов if, else if и else.

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

По теме:

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