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

Реалізація алгоритму пошуку в глибину включає створення алгоритму для прохоенія вузлів дерева У цьому алгоритмі інтенсивно застосовуються оператори принісши рішення і оператори циклу для обробки даних масиву в циклі Ці оперори широко використовуються в програмах, включаючи програми на мові С

Тестовий код був реалізований в попередньому прикладі, тому наступним кроком буде реалізація варіанта методу DepthFirstsearch о, який є оболоой, щоб можна було скомпілювати весь код і виконати програму Обочка має структурну організацію і містить всі додаток Код для її оеделенія показаний на рис 415

Рис 415 Початковий варіант оболонки для алгоритму пошуку в глибину

Тепер, коли наша оболонка готова, ми можемо запустити додаток і пров, як все працює Однак виконання коду тестування на даному етапі бет невдалим, т к виклик методу 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://wwwaristeiacom/TKP/)  Дана проблема полягає в тому, що алгоритм, реалізований на ваших припущеннях, працює для даного конкретного контексту, але не працює в якомусь іншому контексті Тобто ваш алгоритм (Ключ) розроблений під конкретний контекст (замкова щілина), в той час коли нам потрібно універсальний ключ, відповідний до всіх замків

Даний код виділяє память під масив в обсязі, що дорівнює довжині маршруту від Коя деревовидної структури, що є необгрунтованим припущенням Що якщо розробник класу Node вирішить додати міста пересадки, в які можна потрапити з міста, який не включений до кореневі вузли У такому випадку сущес можливість вийти за межі доступної памяті в масиві Іншим решенм могло б бути виділення масиву довільного розміру х Але й тоді, в слае Х + 1 унікальних міст, межі цього масиву можуть бути порушені

Найпростішим рішенням було б обчислення, скільки елементів буде потрібно для знайденого маршруту Але і це не підійде, т к тоді ми б не знали, яке місто ми вже пройшли Ще одним варіантом вирішення (Яке детально рассмаівается в чолі 9) може бути використання колекції

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

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

Node [ ] retumArray =

new Nbde[NodeGetMaxPossibleDestinationsArraySize()]

return returnArray

}

Тепер з точки зору методу DepthFirstsearch () проблема замкової щілини усунена з коду, т к необхідний розмір масиву буде вказуватися класом Node Якщо і тепер розмір масиву виявиться недостатнім, то джерелом прлеми буде клас Node, а не наш алгоритм пошуку Це не зовсім ідеальне решіе, але іноді доводиться одружуватися не на королевах

Цикл for

Кореневий вузол (_root) надає список міст, які можна використовувати в якості початкової точки маршруту Для початку пошуку треба пройтися по містах у списку, щоб знайти початковий місто, зазначений у відповідному параметрі Це завдання виконується за допомогою циклу for Відповідно модифікований метод буде виглядати таким чином (код модифікації виділений жирним шрифтом):

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

new Node[NodeGetMaxPossibleDestinationsArraySize()]

for (int cl = 0 cl &lt _rootLength cl++) {

if (_root[cl]CityNameCompareTo(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 (), визначення якого показано на рис 416

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

Рис 416 Метод 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 if і волняется проверка2 \

• якщо результат проверкіг позитивний, тоді виповнюється код2 Після іолненія кода2, виповнюється код4

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

• виповнюється Кодзі Після виконання кодаЗ, виповнюється код4

Ось ще один приклад:

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

/ / Код1

}

else {

/ / Код2

}

/ / Кодзі

Потік виконання цього коду такий:

• якщо результат перевірки позитивний, тоді виповнюється код1 Після іолненія кода1, виповнюється Кодзі

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

• виповнюється код2 Після виконання кода2, виповнюється Кодзі

І ще один приклад:

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

/ / Код1

}

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

/ / Код2

&gt else {

/ / Кодзі

&gt&nbsp

/ / Код4

Потік виконання цього коду такий:

• якщо результат проверкі1 позитивний, тоді виповнюється код1 Після іолненія кода1 виконується перехід до частини if, де виконується проверка2

Проякщо результат проверкі1 негативний, виконується перехід до частини if

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

• якщо результат проверкіг позитивний, тоді виповнюється код2 Після іолненія кода2 виповнюється код4

• якщо результат проверкі2 негативний, виконується перехід до частини else

• виповнюється Кодзі Після виконання кодаЗ виповнюється код4

А ось це приклад неправильного застосування оператора if:

else {

/ / Код2

}

/ / Кодзі

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

else if (test2) {

/ / Код2

&gt&nbsp

else {

/ / Кодзі

&gt&nbsp

У оператор if можна вставляти інші оператори if, а також оператори else і else if, таким чином, створюючи більш складне багаторівневе дерево Прийнято рішенням

Булеві змінні умова або перевірок можуть приймати значення true або false

Ми вже бачили приклади застосування таких змінних, як у наступному коді:

if (CanContinueSearch(returnArray, currNodeConnections[cl]))

У даному операторі if якщо метод cancontinuesearcho повертає true, то іолняется код, укладений у фігурні дужки

Ось ще один приклад умови:

»

if (returnArray[cl] = null)

У цьому операторі if якщо елемент масиву returnArray [cl] не містить значення

null, то виповнюється код у фігурних дужках

В обох прикладах або метод, або операція порівняння мають повернути булево значення Якщо повертається небулево значення, то компілятор С # згенерує помилку, яке вказує на цю обставину

Зрозуміти, яким чином метод може повернути значення true або false, можна без проблем, але оператор порівняння елемента масиву зі значенням null трохи складніше У табл 42 наведено список операторів порівняння і їх опис

Таблиця 42Оператори порівняння

Вираз

Опис

а == 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 &lt returnArrayLength cl++) {

if (returnArray[cl] = null) {

if (returnArray[cl]CityNameCompareTo(cityCityName) == 0) { return false

&gt&nbsp

}

}

return true

&gt&nbsp

Логіка методу CanContinueSearch про полягає в тому, що він перевіряє в циклі масив returnArray (що містить знайдений шлях) на предмет вмісту в ООМ з його елементів міста, який в даний момент розглядається в якості наступної точки маршруту (змінна city) Якщо масив містить даний рік, то пошук в цієї гілки дерева припиняється в іншому випадку пошук пролжается

Джерело: Гросс К С # 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>

*

*