Поиск в ширину на графах
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]) И если раньше большой популярностью пользовались простые линейные алгоритмы то в настоящее время алгоритмы таких типов как деревья, графы, списки, очереди – получают все большее распространение.
Данный алгоритм может найти своё применение в программах для транспортных и коммуникационных сетей, таких как: железнодорожной транспортной сети, где вершины - станции, связи – дороги, таксомоторная сеть: вершины – места стоянки автомобилей, связи – пути подъезда; перемещение потока вещества по системе труб в определенный пункт назначения и т.д. На основе алгоритма поиска в ширину в графе можно построить программу вывода дерева наименьшей стоимости, что позволит рассчитывать кратчайшие пути к определенному месту назначения (вершине).
Таким образом, развитие информационных технологий, их проникновение во все области жизнедеятельности человека требуют компьютерного отображения информации в виде соответствующих структур данных. И графы, являясь одной из частей этих структур данных, играют важную роль в современном программировании, графы встречаются в сотнях разных задач.
Список литературы:
Вирт Н. Алгоритмы и структуры данных.– М.: Мир, 1989.
Кнут Д. Искусство программирования для ЭВМ. – В 7 т. - М.: Мир, 1876.
Лойко В.И. Структуры и алгоритмы данных ЭВМ: Курс лекций для спец. 220400 – Краснодар: КубГТУ, 1998.
Марченко А.И., «Программирование в среде «Turbo Pascal 7.0»,
«Век+», Киев 1999 г.
Подпись_________________________Дата___________________________
Приложение А
Листинг модуля Newtimer
unit 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<10 then write('0');
write(w);
end;
begin
print(hour); write(':');
print(min); write(':');
print(sec); write('.');
print(hund);
writeln;
end;
procedure Report;
{Вывод на печать измеренного интервала в секундах и
сообщения через переменную Msg}
begin
write('Момент запуска: ');
format(hour_start, min_start, sec_start, hund_start);
write('Момент остановки: ');
format(hour_stop, min_stop, sec_stop, hund_stop);
writeln(msg,' : ',x/182000:5:5,' cek.');
end; end.