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

У системах ШІ потрібно виконувати пошук даних, тому базовим алгоритмом для системи ШІ є алгоритм пошуку У цьому розділі ми розробимо алгоритм пошуку в глибину У ІІ також застосовуються інші пошуки, наприклад А * або пск в ширину, але всі вони засновані на тій же самій ідеї, що і алгоритм пошуку

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

ПРИМІТКА

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

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

Уявіть, що на шляху на роботу біля вхідних дверей ви усвідомили, що не взяли ключі від машини Гірше того, ви не памятаєте, куди ви їх поклали, і вам тепер потрібно шукати їх по всьому будинку Звичайно ж, ви намагаєтеся згадати, де ви їх залишили, але рано вранці память у вас працює туговато Ви намагаєтеся подумки відтворити картину своїх вчорашній дій, а також думаєте про можливі меах, в яких ви могли б залишити їх Коли ви подумки відтворює картину ваших минулих дій, то прямуєте логікою, за якою працює ваша память Іншими словами, ваш алгоритм пошуку заснований на припущеннях, зроблених вей памяттю про те, де можуть бути ваші ключі А кімнати вашого будинку є структурою даних, по якій ви подумки проходите у вашому пошуку Однією зі схем пошуку, створеної вашим розумовим алгоритмом пошуку, може бути схема, показана на рис 41

Рис 41 Можливий порядок пошуку ключів

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

ПРИМІТКА

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

Як можна бачити на рис 41, ваш пошук проходив проти годинникової стрілки Дебатах іншу стратегію, ви могли б обходити кімнати за годинниковою стрілкою або зигзагами, або навіть обшукувати одну і ту ж кімнату по кілька разів

Тепер перетворимо рис 41 в програму, яка має пошуковий алгоритм і структуру даних Пошуковий алгоритм буде пошуком в глибину, а структура даних буде заснована на шляху між відповідними кімнатами Структура даних, що представляє планування будинку з рис 41, і алгоритм пошуку по ній показані на рис 42

Рис 42 Деревоподібна структура ілюструє кожне можливе дію

Товсті стрілки представляють кроки при пошуку в глибину, а кожен чорний кружечок – кімнату в будинку 98 Глава  10

У структурі дерева на рис 42 кожен вузол, позначений чорним кружоом, являє пункт, в який можна потрапити з певного місця в будинку З кожної кімнати ми можемо потрапити в будь-яку іншу кімнату Але ця структура рекурсивна Наприклад, з дитячої можна потрапити у вітальню, а звідти назад у дитячу Хоча ми пройшлися вниз по дереву, ми перейшли з однієї кімнати в іншу і назад в першу кімнату Це цілком прийнятно з точки зору структури даних, хоча ви, можливо, думаєте: Але ж це неправильно, т к кімнати будуть пройдені по кілька разів.

ПРИМІТКА

Древовидно е уявлення планування будинку на рис 42 ні в якому разі не являея повним, т к з кожної кімнати можна потрапити в любу ю іншу кімнату Повне уявлення було б комбінаторним вибухом

Дана структура показана таким чином, яким вона є, тому що це реальне уявлення речей Могли б ви в пошуку своїх ключів повертатися по нколько раз в одну й ту ж кімнату Звичайно ж, могли б Але поверталися б Ні, т к ваш розумовий алгоритм пошуку сказав би вам: Слухай, хлопець, ми вже тут були. Ось в цьому і полягає трюк при написанні додатків: ми застосовуємо розумну структуру даних і алгоритм, який, оперує на цій структурі даних Я називаю цей процес створенням додатка пошарово Ніій рівень – це розумна структура даних, а вищий рівень використовує функціональність цієї розумної структури даних

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

Логіка пошуку полягає в тому, куди ми йдемо вниз по дереву, проходячи кімнату за кімнатою Алгоритм називається пошуком в глибину, Тому що ми проходимо вниз по дереву рівень за рівнем Проходження вниз по дереву припиняється при доіженіі кімнати, в якій ми вже побували Тут ми повертаємося на один рівень вгору і проходимо кімнату, що знаходиться поруч з кімнатою, в якій ми вже побували Це означає, що шлях пошуку, складений компютером, може бути подібним шляху пошуку, показаному на рис 41 Це тому, що компютер такий же дурний, як і ми спозаранку, хоча компютер не говорить сам собі: Якби я тільки почав пошук з коридору.

Необхідно усвідомити, що чарівної палички, яка б знайшла ключі для нас, не існує Метод послідовного перебору всіх можливостей, який застосували ви і компютер для пошуку ключів, називається пошуком методом грубої сили (Brute force) Цей метод вимагає виконання великих обсягів обчислив, і його застосування зазвичай уникають Але в даному випадку застосування перебору всіх можливих рішень є єдиним рішенням, т к ми не знаємо, де

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

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

Проблема обрання першого, або найбільш ефективного шляху, є широко поширеною, которою можна спостерігати кожен день, якщо у вас в машині встановлена ​​система GPS (Global Positioning System, глобальна система навігації та визначення положення) У пристроях GPS зазвичай застосовується який-небудь пошуковий алгоритм Ви вводите в пристрій з клавіатури набір координат жаем ​​точки призначення, а воно намагатиметься знайти найбільш швидкий або короткий шлях до цієї точки В абстрактному сенсі, пошуковий алгоритм, примяти виробниками пристроїв GPS, ідентичний алгоритму, який ми соба розробити в цьому розділі

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

*

*