Реферат
У даній роботі: 7 малюнків, 1 програма, 1 додаток, 35 аркушів.
Ключові слова: граф, алгоритм, пошук, ширина, програма, аргумент,елемент, масив, чергу, пам'ять, час, порівняння.
Мета роботи: Дослідити ефективність алгоритму пошуку в графі вширину.
Результат роботи програми: кількість порівнянь елемента з ключемпошуку і час, за який був знайдений елемент з даного алгоритму пошуку.
Областю застосування цього алгоритму може бути різноманітна, наприклад при побудові карт місцевості: вершини графа - міста, зв'язку --дороги.
Зміст
Введення ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 5 стор
1. Коротка теорія ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 6 стор
2. Аналіз алгоритму ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 11 стор
3. Специфікація завдання ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .14 стор
3.1 Вхідні та вихідні дані ... ... ... ... ... ... ... ... ... ... ... ... ... 14 стор
3.2 Використовувані процедури ... ... ... ... ... ... ... ... ... ... ... ... ... ... .14 стор
4. Програма на мові Turbo Pascal .. ... ... ... ... ... ... ... ... ... ... ... ... ... 15 стор
4.1 Лістинг програми ... ... ... ... .. ... ... ... .... ... ... ... ... ... ... ... ... 15 стор
4.2 Контрольний приклад для тестування № 1 .... ... ... ... ... ... .. 26 стор
4.3 Контрольний приклад для тестування № 2 .... ... ... ... ... ... .. 26 стор
4.4 Керівництво користувача ... ... ... ... ... ... ... ... ... ... ... ... ... ... .27 стор
5. Результати тестування ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 28 стор
Висновок ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 33 стор
Список використовуваної літератури ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 34 стор
Додаток А ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .35 стор
Введення.
Графи зустрічаються в сотнях різних завдань, і алгоритми обробки графівдуже важливі.
Існує безліч розроблених алгоритмів для вирішення різнихзадач з найрізноманітніших сфер людської діяльності. Формулюваннязадачі описує, яким вимогам повинна задовольняти рішення задачі, аалгоритм, який вирішує це завдання, знаходить об'єкт, цим вимогамзадовольняє. ([1])
У цій роботі, ми не будемо давати чіткого визначення алгоритму, аспробуємо проаналізувати і вивчити алгоритм пошуку в ширину в графі.
Пошуком по заданому аргументу називається алгоритм, що визначаєвідповідність ключа до заданого аргументом. Алгоритм пошуку в ширину можебути використаний для перегляду створеного графа, щоб дізнатися про складінформаційних вершин для подальшого пошуку.
В результаті роботи алгоритму пошуку задана вершина може бутизнайдена або може бути зазначена відсутність її у вихідних даних.
Якщо задана інформаційна вершина знайдена, то відбувається висновок проуспішне закінчення пошуку, висновок часу пошуку і часу пошуку ключа.
Коротка теорія.
Очевидно, що найбільш зрозумілий і корисний для людини спосібпредставлення графа - зображення графа на площині у вигляді крапок із'єднують їх ліній - буде абсолютно марним, якщо ми захочемо вирішуватиза допомогою ЕОМ завдання, пов'язані з графами. Вибір відповідної структуриданих для представлення графів має принципове вплив наефективність алгоритмів, тому ми детальніше зупинимося на цьомупроблеми. Ми покажемо кілька різних способів подання і стислорозберемо їх основні переваги і недоліки.
Ми будемо розглядати як орієнтовані, так і неорієнтованіграфи. Граф ми будемо завжди позначати G = (V, E), де V позначаєбезліч вершин, а Е - безліч ребер, причому Е (VXV дляорієнтованого графа і Е (((х, у): х, у (V? х (у) для неорієнтованогографа. Будемо також використовувати позначення | V | = n і | Е | = m.
У теорії графів класичним способом представлення графа служитьматриця інціденцій. Це матриця А з n рядками, відповідними вершин,і m стовпцями, відповідними ребрах. Для орієнтованого графа стовпець,відповідний дузі (E, містить -1 в рядку, що відповідаєвершині х, 1 у рядку, що відповідає вершині у, і нулі у всіх іншихрядках (петлю, тобто дугу вигляду, зручно представляти іншим значенняму рядку х, наприклад, 2). У разі неорієнтованого графа стовпець,відповідний ребру (х, у), містить 1 у рядках, що відповідають х і у, інулі в інших рядках. Це проілюстровано на рис. 2.1. Залгоритмічної точки зору матриця інціденцій є, ймовірно, найбільшнайгіршим способом представлення графа, який тільки можна собі уявити.
По-перше, він вимагає nm комірок пам'яті, причому більшість цих осередків взагалізайнято нулями. Незручний також доступ до інформації. Відповідь на елементарніпитання типу «чи існує дуга?», «до яких вершин ведуть ребра зх? »вимагає в гіршому випадку перебору всіх стовпців матриці, аотже, m кроків.
Кращим способом представлення графа є матриця суміжності,яка визначається як матриця В = [b • j] розміру nхm,
| |
(а) 1 -1 -1
0 0 0 0 0
2 1
0 1 0 0 0 0
3 0
1 -1 -1 0 0 0
4 0
0 0 1 1 0 0
5 0
0 0 0 -1 -1 1
6 0
0 0 0 0 1 -1
|{|{|{|{|{|{|{|{|{|< br>| 1 | 1 | 1 | 2 | 2 | 3 | 4 | 4 | 5 |
|,|,|,|,|,|,|,|,|,|< br>| 2 | 3 | 5 | 3 | 5 | 4 | 5 | 6 | 6 |
|}|}|}|}|}|}|}|}|}|
(б) 1 1
1 1 0 0 0 0 0 0
2 1
0 0 1 1 0 0 0 0
3 0
1 0 1 0 1 0 0 0
4 0
0 0 0 0 1 1 1 0
5 0
0 1 0 1 0 1 0 1
6 0
0 0 0 0 0 0 1 1
Рис. 1. а) Орієнтований граф і його матриця інціденцій; б) неорієнтовані граф і його матриця інціденцій.
де bij = 1, якщо існує ребро, що йде з вершини х у вершину у, і bij
= 0 в іншому випадку. Тут ми маємо на увазі, що ребро (х, у)неорієнтованого графа йде як від х к у, так і від у к х, так що матрицясуміжності такого графа завжди є симетричною. Це проілюстрованона рис. 2.
Основною перевагою матриці суміжності є той факт, що за одинкрок можна отримати відповідь на запитання «Чи існує ребро з х в y?».
Недоліком же є той факт, що незалежно від числа ребер об'ємвикористаної пам'яті становить n2. На практиці це незручність можна інодізменшити, зберігаючи цілий рядок (стовпчик) матриці в одному машинному слові --це можливо для малих n.
Як ще один аргумент проти використання матриці суміжностіприведемо теорему про число кроків, якеповинен виконати алгоритм, що перевіряє на основі матриці суміжностідеякий властивість графа.
Нехай Р - деяке властивість графа P (G) = 0 або P (G) = 1 в залежності відтого, має або не має G нашим властивістю. Припустимо, що властивість
Р задовольняє наступним трьом умовам:
(а) P (G) = P (G '), якщо графи G і G' ізоморфні;
(б) P (G) = 0 для довільного порожнього графа і P (G) = 1 длядовільного повного графа з досить великим числом вершин;
1 2 3 4 5 6 1 2 3 4 5 6
1 0 1 1 0 0 0 1 0 1 1 0 1 0
2 0 0 0 0 0 0 2 1 0 1 0 1 0
3 0 1 0 1 0 0 3 1 1 0 1 0 0
4 0 0 0 0 0 0 4 0 0 1 0 1 1
5 0 0 0 1 0 1 5 1 1 0 1 0 1
6 0 0 0 0 1 0 6 0 0 0 1 1 0
Рис. 2. Матриці інціденцій для графів на рис.1.
(в) додавання ребра не порушує властивості Р, тобто P (G), G '=
U>, v C V. Більш економним щодо пам'яті (особливо у випадку, нещільнеграфів, коли m набагато менше n2) є метод представлення графа здопомогою списку пар, що відповідають його ребрах. Пара відповідаєдузі, якщо граф орієнтований, і ребру (х, y) в разінеорієнтованого графа (рис. 3). Очевидно, що обсяг пам'яті в цьому випадкускладає 2т. Незручністю є велике число кроків - порядку т вгіршому випадку, - необхідна для отримання безлічі вершин, до якихведуть ребра з даної вершини.
Ситуацію можна значно поліпшити, упорядкувавши безліч парлексикографічно і застосовуючи двійковий пошук, але кращим рішенням у багатьохвипадках виявляється структура
| 1 | 2 |
| 1 | 3 |
| 1 | 5 |
| 2 | 3 |
| 2 | 5 |
| 3 | 4 |
| 4 | 5 |
| 4 | 6 |
| 5 | 6 |
| 1 | 2 |
| 1 | 3 |
| 3 | 2 |
| 3 | 4 |
| 5 | 4 |
| 5 | 6 |
| 6 | 5 |
Рис.3. Списки ребер відповідні графами на рис.1.
даних, яку ми будемо називати списками інцідентності. Вона містить длякожної вершини v CV список вершин і, таких що v -> u (або v - і в разінеорієнтованого графа). Точніше, кожен елемент такого списку єзаписом г, що містить вершину р. рядок і покажчик р. слід на наступнузапис у списку (р. слід = nil для останнього запису у списку). ПочатокКожен список зберігається в таблиці ПОЧАТОК; точніше, HAЧАЛО [v] єпокажчиком на початок списку, що містить вершини з множини (u: v + u) ((u:v - u) для неорієнтованого графа). Весь такий список зазвичай неформальнобудемо позначати 3AПІСЬ [v], а цикл, що виконує певну операцію длякожного елемента і з цього списку у довільній, але чітко визначеноїпослідовності, що відповідає черговості елементів у списку, будемозаписувати «for u C ЗАПИС [v] do ...».
Відзначимо, що для неорієнтовані графів кожне ребро (u, v)представлено двічі: через вершину v у списку ЗАПИС [u] і через вершину і всписку ЗАПИС [v]. У багатьох алгоритмах структура графа динамічномодифікується додаванням і видаленням ребер. У таких випадках думаємо, щов наших списках інцідентності елемент списку ЗАПИС [u], що містить вершинуі, забезпечений покажчиком на елемент списку 3AПІCЬ [v], що містить вершину і, іщо кожен елемент списку містить вказівник не тільки до наступногоелементу, а й до попереднього. Тоді видаляючи деякий елемент
Рис.4. Списки інцідентності ЗПІСЬ [v], v = V, відповідні графами на рис.1.
зі списку, ми можемо легко за число кроків, обмежена константою, видалитиінший елемент, який представляє той же саме ребро, не переглядаючи список,що містить цей елемент.
Аналогічним способом визначаємо для кожної вершини і неорієнтованогографа список предше [v], що містить вершини з безлічі (u: u -> v).
Число елементів пам'яті, необхідний для представлення графа за допомогоюсписків інцідентності, буде, очевидно, мати порядок m + n. На рис.4представлені списки інцідентності, відповідні графах на рис. 1.
2. Аналіз алгоритму.
Розглянемо метод пошуку в графі, званий пошуком в ширину (англ:breadth first search). Перш ніж описати його, зазначимо, що при пошуку вглибину чим пізніше буде переглянуло вершина, тим раніше вона будевикористаний - точніше, так буде з припущенням, що друга вершинавідвідується перед використанням першого. Це прямий наслідок того факту,що переглянуті, але ще не використані вершини накопичуються в стек.
Пошук в ширину, грубо кажучи, грунтується на заміні стека чергою. Післятакої модифікації, ніж раніше відвідується вершина (поміщається в чергу),тим раніше вона використовується (віддаляється з черги). Використання вершинивідбувається за допомогою перегляду відразу всіх ще не переглянуто сусідів цієївершини. Вся процедура пошуку представлена нижче (дана процедуравикористовується також і для перегляду графа, і в псевдокоді, описаному нижче,відсутні оператори, які не використовуються для пошуку).
1 procedure WS (v);
(* пошук в ширину в графі з початком у вершині v; змінні НОВИЙ, ЗАПИС - глобальні *)
2 begin
3 ЧЕРГА: =?; ЧЕРГА ver [j +1] then begin exch: = ver [j]; el: = lst [j]; em: = m [j]; ver [j]: = ver [j +1]; lst [j]: = lst [j +1]; m [j]: = m [j +1]; ver [j +1]: = exch; lst [ j +1]: = el; m [j +1]: = em; end;end;
{================================================= ====}begin while menu'4 'do begin textmode (1); textbackground (blue); clrscr; textcolor (red); gotoxy (16,3); writeln (' Г Р А Ф И '); textcolor (white); gotoxy ( 5,5); writeln ( '* Дослідження пошуку в ширину *'); textcolor (black); gotoxy (7,22); writeln ( 'Created by Andrew Spikhailo'); gotoxy (15,24); write ( 'ARMAVIR 2001 '); textcolor (white); gotoxy (7,10); write ('+----------- MENU -----------?'); gotoxy (7 , 11); write ('|'); textcolor (green); write ('1 Створення графа ');textcolor (white); write ('|'); gotoxy (7,12); write ('|'); textcolor (green); write ('2 Перегляд графа ');textcolor (white); write ('|'); gotoxy (7,13); write ('|'); textcolor (green); write ('3 Пошук елемента графа ');textcolor (white); write ('|'); gotoxy (7,14); write ('|'); textcolor (green); write ('4 Вихід ');textcolor (white); write ('|'); gotoxy (7,15); write ('|'); textcolor (white +128); write ( 'Виберіть номер пункту меню'); textcolor (white); write ( '|'); gotoxy (7,16); write ('?--------------------------+'); menu: = readkey ; case menu of
'1 ': begin
(звільнення пам'яті, якщо вона була зайнята) textmode (2); textbackground (blue); clrscr; textcolor (lightgreen); if mem then release (size); repeat clrscr; write ( 'Число вершин графа:'); writeln ( ' (1) - десять '); gotoxy (21, wherey); writeln (' (2) - сто '); gotoxy (21, wherey); writeln (' (3) - чотириста '); gotoxy (21, wherey) ; write ( '(4) - інше ...'); raz: = 0; repeat craz: = readkey; case craz of
'1': raz: = 10; < p> '2 ': raz: = 100;
'3': raz: = 400;
'4 ': begin write (' ___'); gotoxy (wherex - 3, wherey); read (raz); if (raz400) then begin raz: = 0; gotoxy (38, wherey-1); write ( 'ERROR ...'); delay (1000); end; end; end ;until (craz = '1 ') or (craz = '2') or (craz = '3 ') or (craz = '4'); clrscr; until raz> 0; writeln; write ( 'висновок списку інцідентності графа: '); writeln ('0 - заборонити'); gotoxy (35, wherey); write ('1 - дозволити '); mg: = readkey; if mg = '1' then mgsi: = true else mgsi: = false; clrscr; mark (size);
Make_Graph (mgsi); mem: = true; (тепер пам'ять можна звільняти) sor: = false; (вершини не відсортовані) readkey; end;
'2 ': begin (Перегляд графа) textmode (2); textbackground (blue); clrscr; textcolor (lightgreen); gotoxy (32,3); Writeln (' Перегляд графа: '); key: =- 1; find : = false; prosm: = true; schet: = 0;
Write_S (key, prosm, find, schet); writeln; readkey; end;
'3 ': begin (Пошук елемента графа) clrscr; textcolor (lightgreen); if not (sor) then begin writeln ( 'Відсортувати вершини по неубиванію?'); writeln ( '1-ТАК'); writeln ( '2-НІ'); sormen: = readkey; if sormen = '1 'then begin
Sort; sor: = true; end; end; prosm: = false; write (' Що будемо шукати: '); readln (key); writeln ; start (t); kols: = 0; for fil: = 1 to 10000 do begin schet: = 0; find: = false;
Write_S (key, prosm, find, schet); (пошук завширшки) kols: = kols + schet; end; stop (t);if not (find) then write ( 'На жаль такої вершини немає ...') else begin writeln (' Вершина графа ', ver [p],' знайдена! '); writeln (' Кількість порівнянь: ', kols/10000 : 5:1); report ( 'Час пошуку вершини', t); end; readkey; end; end; end;end.
4.2 Контрольний приклад для тестування № 1.
Кількість вершин графа - 5, ребра між ними формуються випадковимчином.
Список інцідентності створеного графа:
74 497-174 - §
174 §
55 497 - §
497 §
661 497 - §
КІЛЬКІСТЬ Ребер СТВОРЕНИЙ ГРАФА: 4
Зміст інформаційних вершин: 74 174 55 497 661
Примітка: символ «§» відповідає кінця списку (nil).
Отриманий граф зображений на рис.6
55 74
497
661 174
рис. 6
4.3 Контрольний приклад для тестування № 2.
Кількість вершин графа - 7, ребра між ними формуються випадковимчином.
Список інцідентності створеного графа:
704 66-373-434 - §
434 373 - §
766 706-373-434 - §
373 66 - §
66 §
706 66-704 - §
454 706-66-373 - §
КІЛЬКІСТЬ Ребер СТВОРЕНИЙ ГРАФА: 13
Зміст інформаційних вершин: 704 434 766 373 66 706 454
Примітка: символ «§» відповідає кінця списку (nil).
Отриманий граф зображений на рис.7
704
454 66
373 434
706 766 рис. 7
4.4 Керівництво користувача.
При запуску програми на екрані з'являється основне меню програми,яке складається з чотирьох пунктів:
1 Створення графа
2 Перегляд графа
3 Пошук елемента графа
4 Вихід.
Вибір потрібного пункту здійснюється за допомогою клавіш «1», «2», «3» і
«4». а) «Створення графа»
Вибравши пункт «Створення графа», на екрані з'явиться меню виборукількості вершин графа: 10, 100, 400 та інше.
Натиснувши клавішу з порядковим номером пункту меню, Ви оберетенеобхідну кількість вершин. Далі, натиснувши клавішу 1 Ви дозволитепрограмі вивести на екран список інцідентності графа, а натиснувши 0 --забороніть. б) «Перегляд графа»
При виборі пункту «Перегляд графа», на екрані з'явиться списокінформаційних вершин створеного графа. в) «Пошук елемента графа»
При виборі пункту «Пошук елемента графа» на екрані спочатку з'являєтьсязапит на сортування інформаційних вершин. Потім Вам потрібно задатиелемент пошуку в графі, після чого при вдалому пошуку на екран будевиведено час пошуку та середня кількість порівнянь. Час пошукуобчислюється за допомогою процедур Start, Stop та Report, що описані в модулі
Newtimer. Лістинг модуля Newtimer описаний в Додатку А. г) «Вихід»
При виборі пункту "Вихід" програма припиняє свою роботу.
5. Результати тестування
Досліджуємо результати роботи програми, для чого спочатку виміряємо часпошуку для трьох графів з 100, 200 і 400 елементів, відсортованих упорядку зростання і не відсортованих і порівняємо отримані результати.
Кількість інформаційних вершин - 10, вершини не відсортовані, їхзміст:
97 920 635 286 590 938 981 716 427 474
Що будемо шукати: 427
Вершина графа 427 знайдено!
Кількість порівнянь: 9.0
Момент запуску: 23:53:46.50
Момент зупинки: 23:53:46.66
Час пошуку вершини: 0.00001 cek.
Кількість інформаційних вершин - 10, вершини відсортовані, їхзміст:
32 192 234 243 297 324 775 804 982 986
Що будемо шукати: 192
Вершина графа 192 знайдено!
Кількість порівнянь: 2.0
Момент запуску: 23:55:28.33
Момент зупинки: 23:55:28.44
Час пошуку вершини: 0.00001 cek.
Кількість інформаційних вершин - 100, вершини не відсортовані, їхзміст:
575 128 905 777 923 75 716 446 477 627 70 591 250 555 111 208 315 417 309
723 963 250 561 966 790 982 965 446 228 1 344 446 237 552 912 756 142 875
665 83 863 265 369 427 0 476 253 987 537 135 768 374 117 86 12 204 149 849
694 332 219 600 738 310 532 358 882 844 394 285 899 302 940 293 276 569
607 350 478 806 95 190 153 891 774 322 876 605 798 525 310 851 399 246 876
464 91 567 308 386
Що будемо шукати: 293
Вершина графа 293 знайдено!
Кількість порівнянь: 74.0
Момент запуску: 23:58:09.98
Момент зупинки: 23:58:11.08
Час пошуку вершини: 0.00010 cek.
Кількість інформаційних вершин - 100, вершини відсортовані, їхзміст:
0 1 12 70 75 83 86 91 95 111 117 128 135 142 149 153 190 204 208 219 228
237 246 250 250 253 265 276 285 293 302 308 309 310 310 315 322 332 344 350
358 369 374 386 394 399 417 427 446 446 446 464 476 477 478 525 532 537
552 555 561 567 569 575 591 600 605 607 627 665 694 716 723 738 756 768
774 777 790 798 806 844 849 851 863 875 876 876 882 891 899 905 912 923
940 963 965 966 982 987
Що будемо шукати: 293
Вершина графа 293 знайдено!
Кількість порівнянь: 30.0
Момент запуску: 23:59:08.14
Момент зупинки: 23:59:08.80
Час пошуку вершини: 0,00006 cek.
Кількість інформаційних вершин - 400, вершини не відсортовані, їхзміст:
963 663 915 353 650 103 540 531 548 338 960 515 143 963 765 42 822 188 102
85 361 193 137 582 756 241 325 234 400 482104 416 826 611 874 500 505 805
365 134 436 606 755 278 513 684 151 42 895 633 291 621 873 249 566 877 965
925 747 359 220 126 991 823 970 79 18 524 513 127 551 851 462 403 375 88
739 754 645 357 457 82 274 23 171 523 537 131 227 148 231 657 201 88 12
620 660 273 759 359 725 191 88 517 178 361 361 527 92 412 803 656 220 967
597 889 625 740 50 219 289 519 202 120 687 957 483 263 554 353 273 769 330
825 486 546 26 566 520 501 487 96 201 682 288 677 570 647 745 329 619 594
787 100 348 70 661 523 736 286 699 434 505 345 659 558 767 930 339 559 923
246 477 449 428 262 152 551 269 552 182 421 277 286 252 408 624 157 746 782
119 302 534 581 163 506 184 622 470 239 341 330 908 326 255 318 89 294 696
884 536 687 729 849 570 903 100 412 251 359 207 930 994 3 888 816 722 499
517 955 649 619 145 328 80 633 657 752 805 761 195 920 978 963 318 152 560
634 643 533 715 982 950 369 742 156 980 111 421 401 411 194 876 797 756
449 306 387 158 3 213 719 314 861 968 122 21 570 826 242 79 648 768 660
520 702 755 610 420 391 267 114 759 683 235 77 71 46 722 136 875 526 966
306 108 858 644 729 54 46 460 71 499 85 428 356 103 737 445 289 210 538 31
371 595 466 328 342 874 924 727 757 563 981 730 734 23 18 911 181 769 228
73 43 886 626 977 359 527 483 236 196 741 382 250 731 95 291 273 51 843 342
988 453 621 228 190 296 897 399 438 703 663 466 789 656 110 504 964 289 260
154 570 413 796 709
226 583 573 611 701 244 544 10 436 759 86 333 44 364
Що будемо шукати: 228
Вершина графа 228 знайдено!
Кількість порівнянь: 342.0
Момент запуску: 00:03:13.99
Момент зупинки: 00:03:18.83
Час пошуку вершини: 0.00048 cek.
Кількість інформаційних вершин - 400, вершини відсортовані, їхзміст:
3 3 10 12 18 18 21 23 23 26 31 42 42 43 44 46 46 50 51 54 70 71 71 73 77 79
79
80 82 85 85 86 88 88 88 89 92 95 96 100 100 102 103 103 104 108 110 111 114
119 120 122 126 127 131 134 136 137 143 145 148 151 152 152 154 156 157 158
163 171 178 181 182 184 188 190 191 193 194 195 196 201 201 202 207 210 213
219 220 220 226 227 228 229 231 234 235 236 239 241 242 244 246 249 250 251
252 255 260 262 263 267 269 273 273 273 274 277 278 286 286 288 289 289 289
291 291 294 296 302 306 306 314 318 318 325 326 328 328 329 330 330 333 338
339 341 342 342 345 348 353 353 356 357 359 359 359 359 361 361 361 364 365
369 371 375 382 387 391 399 400 401 403 408 411 412 412 413 416 420 421 421
428 428 434 436 436 438 445 449 449 453 457 460 462 466 466 470 477 482 483
483 486 487 499 499 500 501 504 505 505 506 513 513 515 517 517 519 520 520
523 523 524 526 527 527 531 533 534 536 537 538 540 544 546 548 551 551 552
554 558 559 560 563 566 566 570 570 570 570 573 581 582 583 594 595 597 606
610 611 611 619 619 620 621 621 622 624 625 626 633 633 634 643 644 645 647
648 649 650 656 656 657 657 659 660 660 661 663 663 677 682 683 684 687 687
696 699 701 702 703 709 715 719 722 722 725 727 729 729 730 731 734 736 737
739 740 741 742 745 746 747 752 754 755 755 756 756 757 759 759 759 761 765
767 768 769 769 782 787 789 796 797 803 805 805 816 822 823 825 826 826 843
849 851 858 861 873 874 874 875 876 877 884 886 888 889 895 897 903 908 911
915 920 923 924 925 930 930 950 955 957 960 963 963 963 964 965 966 967 968
970 977 978 980 981 982 988 991 994
Що будемо шукати: 228
Вершина графа 228 знайдено!
Кількість порівнянь: 93.0
Момент запуску: 00:04:21.33
Момент зупинки: 00:04:23.58
Час пошуку вершини: 0.00022 cek.
Як показав експеримент, сортування інформаційних вершин графа впливаєна час пошуку елемента методом перегляду в ширину в графі. Зменшуєтьсякількість порівнянь, що також підвищує швидкодію алгоритму. Однакце істотно підвищує ефективність алгоритму тільки при набагато більшійкількості вершин, ніж у зроблених дослідах.
Час пошуку навіть за максимально можливої кількості вершин (400)настільки мало, що засікти його не представляється можливим. Тому процеспошуку повторюється 10000 разів. Точний час обчислюється в підключеномумодулі Newtimer за формулою:
T = Q/n, де
Q-загальний час пошуку;n - кількість циклів пошуку (10000).
Отримане час практично не помітно, тому що досліджувалися графиневеликий розмірності, але якщо графи будуть розмірності більш ніж 1 мільярдвершин, то час буде відчутно. І можна отримати вигоду з алгоритму пошукузавширшки, якщо використовувати його відразу для максимальної кількостіелементів, а не декілька разів, але використовуючи трохи елементів.
Таким чином, алгоритм пошуку в ширину в графі є доситьефективним і може використовуватися в програмах для швидкого пошукуелементів.
Висновок
Сучасний стан і тенденції розвитку обчислювальної техніки якосновного інструменту інформатики такі, що поряд зі збільшеннямфункціональності обчислювальна техніка набуває властивостей, що дозволяютьпрацювати на ній користувачеві, не розбирається в програмуванні. У цейперіод з'явився більш якісний інтерфейс програм. З'явилися структуриграфічних даних і більші, інтегральні інформаційні одиниці --об'єкти. Наслідком стало бурхливий розвиток об'єктно-орієнтованих системпрограмування, таких як Visual C + +, Visual BASIC і інших, в основіяких лежить обробка об'єктних структур даних. Також з'явилися новімови програмування ADA, OCCAM. ([3]) І якщо раніше великою популярністюкористувалися прості лінійні алгоритми то в даний час алгоритмитаких типів як дерева, графи, списки, черги - отримують все більшепоширення.
Даний алгоритм може знайти своє застосування в програмах длятранспортних і комунікаційних мереж, таких як: залізничноїтранспортної мережі, де вершини - станції, зв'язку - дороги, таксомоторівмережа: вершини - місця стоянки автомобілів, зв'язку - шляхи під'їзду;переміщення потоку речовини за системою труб в певний пункт призначенняі т.д. На основі алгоритму пошуку в ширину в графі можна побудуватипрограму виведення дерева найменшої вартості, що дозволить розраховуватинайкоротші шляхи до певного місця призначення (вершині).
Таким чином, розвиток інформаційних технологій, їх проникнення увсі сфери життєдіяльності людини вимагають комп'ютерного відображенняінформації у вигляді відповідних структур даних. І графи, будучи однієюз частин цих структур даних, відіграють важливу роль у сучасномупрограмуванні, графи зустрічаються в сотнях різних завдань.
Список літератури:
1. Вірт Н. Алгоритми та структури даних .- М.: Світ, 1989.
2. Кнут Д. Мистецтво програмування для ЕОМ. - У 7 т. - М.: Світ,
1876.
3. Лойко В.І. Структури та алгоритми даних ЕОМ: Курс лекцій для спец.
220400 - Краснодар: КубГТУ, 1998.
4. Марченко А.І., «Програмування в середовищі« Turbo Pascal 7.0 »,
« Століття + », Київ 1999 р.
Подпісь_________________________Дата___________________________
Додаток А
Лістинг модуля Newtimerunit newtimer;interface procedure start (var x: longint); (визначає час початку роботи) procedure stop (var x: longint); (визначає час закінчення роботи) procedure format (hour, min, sec, hund: word); procedure Report (Msg: string; x: longint);implementation uses dos; var hour_start, min_start, sec_start, hund_start, hour_stop, min_stop, sec_stop, hund_stop, hour, min, sec, hund: word; systimer: longint absolute $ 0040: $ 006c; procedure start; begin gettime (hour_start, min_start, sec_start, hund_start); x: = systimer; while x = systimer do; (ожіаніе моменту зміни таймера) x: = systimer; end; procedure stop; begin gettime (hour_stop, min_stop, sec_stop, hund_stop); x: = systimer-x ; end; procedure format; procedure print (w: word); begin if w
