Аналіз та модифікації алгоритмів пошуку (реферат)

Реферат на тему:

Аналіз та модифікації алгоритмів пошуку

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

1. Обидва алгоритми гарантують знаходження розв’язку, якщо цей розв’язок існує.

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

2. Складність обох алгоритмів (тобто кількість кроків, які повинен здійснити кожен алгоритм, щоб знайти розв’язок або встановити, що розв’язку не існує) не перевищує величини O (n +m), де n ількість вершин, а m ількість ребер графа G.

Справді, кожне з m ребер графа аналізується не більше одного разу. А кількість кроків для визначення множини ребер R (w) (крок 5 алгоритму) має порядок числа вершин графа.

3. Якщо |VO|=1, то АПШ знаходить шлях мінімальної довжини з VO у VК. Якщо ж |VO|>1, то для пошуку найкоротшого шляху з VO у VК необхідно дещо модифікувати АПШ. А саме, необхідно знайти всі шляхи з вершин множини VO у множину вершин VК, порівняти їх за довжиною і обрати мінімальний.

4. Розв’язок, який знаходить АПГ, взагалі кажучи, не оптимальний. У найгіршому випадку АПГ може знайти шлях з VO у VК довжини n у той час як існує шлях довжини 1.

5. АПГ легше програмується:

а рахунок використання стека;

авдяки можливості запису АПГ у компактній та наочній рекурсивній формі.

6. АПГ є складовою частиною багатьох важливих алгоритмів для графів (побудова кістякового дерева, пошук зв’язних компонент, топологічне сортування вершин орграфа, пошук розділювальних вершин, перевірка планарності графа тощо [2,7,8]).

7. Пам’ять, яку використовує АПГ, взагалі кажучи, менша за обсягом ніж та пам’ять, яка необхідна АПШ.

8. Аналіз людського мислення свідчить, що людині більш притаманний АПГ при пошуках розв’язків різних задач або під час проведення досліджень (пошуки шляху в лабіринті, аналіз шахових комбінацій, розв’язування логічних задач, спелеологічні дослідження тощо).

Розглянемо деякі важливі модифікації алгоритмів пошуку.

Далі для зручності вважатимемо, що |VO|=1.

У великих графах (тобто у графах зі значною кількістю вершин і ребер) АПГ має одну суттєву ваду, яка є наслідком довільності розміщення ребер з R (w) у списку ВІДКР (крок 5). Зробивши на деякому кроці «помилковий» («неоптимальний») вибір продовження шляху, АПГ може пройти повз існуючий коротший шлях і заглибитися в граф у пошуках значно довшого і гіршого шляху.

Спробою усунути цю ваду є так званий алгоритм обмеженого пошуку вглиб (АОПГ). У цьому алгоритмі кожен шлях з VO простежується вглиб доти, поки його довжина не досягне певної наперед заданої граничної величини k. Після цього алгоритм не поповнює список ВІДКР (крок 5), а починає досліджувати інший шлях, повернувшись до останнього розгалуження і т. д.

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

Тому застосовують нижченаведену модифікацію, яка носить назву алгоритму поступового (або прогресивного) загиблення (АПЗ).

Якщо для заданого k АОПГ розв’язку не знайшов, то значення k збільшується на певну величину t (тобто k :=k +t) і АОПГ повторює свою роботу спочатку.

Очевидно, що коли k де n=|V |, тоді АПЗ збігається з АОПГ і обидва вони збігаються з класичним АПГ.

Якщо ж k =1 і t =1, то АПЗ збігається з АПШ.

Таким чином, добираючи значення k і t, можна реалізувати певний компроміс між АПГ і АПШ.

Обидва алгоритми дуже просто можна модифікувати для того, щоб здійснити систематичний обхід усіх вершин і/або всіх ребер графа. Результатом такого обходу є певна нумерація (порядок розташування) вершин і/або ребер.

Цю модифікацію одержимо, якщо вилучимо в кроці 4 перевірку w (а отже, фактично вилучимо весь крок 4), і єдиною умовою завершення алгоритму пошуку залишимо умову кроку 2 (список ВІДКР орожній).

Відповіддю (результатом дії) такого алгоритму буде або список ребер у ЗАКР і/або та послідовність, в якій аналізувалися вершини на кроці 5 (без повторень).

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

Нехай задано граф G =(V, E) і деяку дійсну функцію f: E де R+ ножина невід'ємних дійсних чисел. Такий граф, кожному ребру якого поставлене у відповідність невід'ємне дійсне число, що називаєтся вартістю (вагою, ціною) ребра, називається зваженим (позначеним) графом.

Тоді вартістю (вагою) шляху M, ребрами якого є ei1, ei2,…, eik, називають величину W = $$\underset{j=1}{\overset{k}{}}$$ f (eij).

Нехай VO і VК множини початкових і кінцевих вершин зваженого графа G =(V, E). Алгоритми, які шукають шляхи найменшої вартості з VO у VК, називаються алгоритмами пошуку найкоротших шляхів. Вони описані в [2,7,8].

Список літератури.

1. Харари Т. Теория графов.- М., 1973.

2. Лекции по теории графов / Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р.И.- М., 1990.

3. Зыков А. А. Основы теории графов.- М., 1987.

4. Оре О. Теория графов.- М., 1980.

5. Свами М., Тхуласираман К. Графы, сети, алгоритмы.- М., 1984.

6. Уилсон Р.

Введение

в теорию графов.- М., 1977.

7. Кристофидес Н. Теория графов. Алгоритмический подход.- М., 1978.

8. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы.-М., 1980.