UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 15

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваАналіз та модифікації алгоритмів пошуку (реферат)
АвторPetya
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось1289
Скачало210
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

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

 

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

пошуку між собою.

 

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 (2, у той

час як існує шлях довжини 1.

 

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

 

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

 

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

формі.

 

6. АПГ є складовою частиною багатьох важливих алгоритмів для графів

(побудова кістякового дерева, пошук зв’язних компонент, топологічне

сортування вершин орграфа, пошук розділювальних вершин, перевірка

планарності графа тощо [2,7,8]).

 

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

та пам’ять, яка необхідна АПШ.

 

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

при пошуках розв’язків різних задач або під час проведення досліджень

(пошуки шляху в лабіринті, аналіз шахових комбінацій, розв’язування

логічних задач, спелеологічні дослідження тощо).

 

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

 

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

 

У великих графах (тобто у графах зі значною кількістю вершин і ребер)

АПГ має одну суттєву ваду, яка є наслідком довільності розміщення ребер

з R(w) у списку ВІДКР (крок 5). Зробивши на деякому кроці "помилковий"

("неоптимальний") вибір продовження шляху, АПГ може пройти повз існуючий

коротший шлях і заглибитися в граф у пошуках значно довшого і гіршого

шляху.

 

Спробою усунути цю ваду є так званий алгоритм обмеженого пошуку вглиб

(АОПГ). У цьому алгоритмі кожен шлях з VO простежується вглиб доти, поки

його довжина не досягне певної наперед заданої граничної величини k.

Після цього алгоритм не поповнює список ВІДКР (крок 5), а починає

досліджувати інший шлях, повернувшись до останнього розгалуження і т. д.

 

На жаль, ще більш серйозною вадою АОПГ порівняно з АПГ є те, що він може

не знайти жодного розв’язку, в той час, як розв’язок існує. Ця ситуація

може виникнути в тому разі, коли довжина розв’язку більша від k.

-----> Page:

0 [1]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ