Виконання алгоритму пошуку в глибину в Visual C # (Sharp)

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

Montreal New York Houston Miami Toronto Seattle

Перше, що можна подумати, побачивши цей результат, що алгоритм не працює, т к за винятком Лос-Анджелеса, даний маршрут містить всі можливі міста

Проте, незважаючи на такі дивні результати, алгоритм працює належним чином Проблема ж лежить в іншій площині – метод cancontinuesearcht) не містить функціональності для оптимізації маршруту На даному етапі алгітм налаштований на виконання пошуку в глибину, тобто на проходження вниз по дереву, перед тим, як повертатися назад Давайте-но ми самі пройдемося по структурі в статичному конструкторі класу Node

Наш маршрут починається в Монреалі, звідки можна летіти в наступні міста (визначені в connections):

montrealConnections = new Node[3] montrealConnections[0] = newyork montrealConnections[1] = toronto montrealConnections[2] = losangeles

Згідно з принципом роботи нашого алгоритму перший елемент дерева вважається наступним містом у маршруті, та з Монреаля ми летимо у Нью-Йорк Прилетівши в Нью-Йорк, ми отримуємо наступний вибір міст для продовження нашого польоту:

newyorkConnections = new Node[3] newyorkConnections[0] = montreal newyorkConnections[1] = houston newyorkConnections[2] = miami

Тут першим містом продовження польоту є Монреаль, але ми вже там бі і він занесений в знайдений маршрут Тому вибирається другий елемент маса, яким є Хюстон Летимо в Хюстон З Хюстона ми можемо летіти в наступні міста:

houstonConnections = new Node[3] HoustonConnections[0] = miami houstonConnections[1] = Seattle

houstonConnections[2] = newyork

Тут першим вибором є Майямі, де ми ще не були, тому летимо в Майямі У Майямі у нас наступний вибір міст для продовження нашої польоту: miamiConnections = new Node [3]

miamiConnections[0] = toronto miamiConnections[1] = houston miamiConnections[2] = newyork

У Майямі першим вибором знову є місто, в якому ми ще не були – Торонто – тому летимо в Торонто У Торонто вибір міст для продовження нашої польоту такий:

torontoConnections = new Node[3] torontoConnections[0] = miami torontoConnections[1] = Seattle torontoConnections[2] = montreal

У Торонто першим вибором наступного міста маршруту є Майямі, але ми вже там були Другим вибором є Сіетл, який і є кінцевий місто нашого маршруту

Так що, з точки зору алгоритму, до нього не може бути жодних претензій – він спрацював точно так, як був запрограмований Але у пасажира, якому був би запропонований цей маршрут, претензії, швидше за все, були б Це ще раз демотрірует важливість тестування вашого коду, т к він може бути технічно правильним, але видавати зовсім не ті результати, які ви очікували від нього Виконати оптимізацію алгоритму надається вам в якості одного з уажненій, заданих в кінці розділу

У цьому розділі ми розглянули структури даних і алгоритми З цього матеріалу рекомендується запамятати такі аспекти

• При розробці програми першим ділом необхідно продумати структури даних і алгоритми, які можна застосувати в ній

• Для більшості завдань не існує однієї кращої структури даних і одне кращого алгоритму Будь-яка можлива структура даних і будь-який алгоритм містить компроміси З усіх можливих структур даних і алгоритмів нбходімо вибрати такі, які підходять найкраще для вирішення даної задачі і містять найменше число критичних компромісів

Структури даних і алгоритми не обовязково повинні бути в одному класі

Вони можуть бути різних типів і часто такими і є

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

(Class) типів

• Структури даних звичайних типів мають три обмеження, про які ви доли бути інформовані Ці обмеження повязані з тим, що при присвоєнні змінних іншим змінним їх дані копіюються, з тим, що відбувається при впровадженні посилального типу в звичайний тип, і з тим, що відбувається, коли звичайні типи застосовуються в якості параметрів методів

• На практиці в більшості випадків застосовуються посилальні типи, але звичайні типи також мають своє застосування При використанні звичайних типів неоодімо розуміти, яким чином ведуть себе відповідні значення в привносячи випадку можна отримати небажані взаємодії

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

• При виборі посилального або звичайного типу рішення має прийматися на основі контексту, в якому буде застосовуватися структура даних Якщо ство-

ється складна структура даних, скажімо, дерево для пошуку, тоді потрібно іользовать контрольний тип для простих же структур буде цілком прийнятним звичайний тип

• При створенні примірників типів кожен обєкт має власний примірник набору методів та членів даних Методи і члени даних типу, оголошені з використанням ключового слова static, існують в одиничному екземплярі і не асоціюються з примірником типу

Про Практика створення тестів, перш ніж реалізовувати тип, дозволяє разрабоіку відчути, як повинен виглядати і вести себе тип, а також предостаяет певні орієнтири для подальшої реалізації типу

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

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

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

Джерело: Гросс К С # 2008: Пер з англ – СПб: БХВ-Петербург, 2009 – 576 е: ил – (Самовчитель)

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*