Теми рефератів
> Реферати > Курсові роботи > Звіти з практики > Курсові проекти > Питання та відповіді > Ессе > Доклади > Учбові матеріали > Контрольні роботи > Методички > Лекції > Твори > Підручники > Статті Контакти
Реферати, твори, дипломи, практика » Статьи » Алгоритми на графах та їх практичне! Застосування

Реферат Алгоритми на графах та їх практичне! Застосування





є технології Web-служб. Технологія Web-служб надає новий Механізм создания розподіленіх Додатків. За суті, вона є Поширеними технології создания Додатків на базі компонентів и на сферу Internet;

? Модель безпеки, что програмісті могут легко використовуват у своих програмах;

? Потужні Інструментальні засоби розробки.


2. Основні алгоритми на графах


. 1 Поиск завширшки


Поиск завширшки (breadth-first search) є одним з простих алгоритмів для обходу графа и є основою для багатьох Важлива алгоритмів для роботи з графами. Например, алгоритм Прима (Prim) поиска мінімального остовного дерева або алгоритм Дейкстри (Dijkstra) поиска найкоротшого шляху з однієї вершини Використовують Ідеї, схожі з ідеямі, вікорістовуванімі при поиска завширшки.

Поиск завширшки БУВ формально запропонованій Е. Ф. Муром в контексті поиска шляху в лабірінті. Лі Незалежності відкрів тієї ж алгоритм в контексті розводкою провідніків на друкованне платах.

Поиск завширшки может застосовуватіся для вирішенню Завдання, пов'язаних з теорією графів,:

Хвильовий алгоритм поиска шляху в лабірінті (алгоритм Лі);

Хвилевой трасування друкованне плат;

поиск компонент зв'язності в графі;

поиск найкоротшого шляху между двома Вузли незваженого графа;

поиск в пространстве станів: знаходження решение задачі з найменших числом ходів, если КОЖЕН стан системи можна представіті вершиною графа, а переходь з одного стану в інше - ребрами графа;

знаходження найкоротшого циклу в орієнтованому незваженому графові;

знаходження усіх вершин и ребер, что лежати на якому-небудь найкоротшому шляху между двома вершинами a и b;

поиск збільшуючого шляху в алгорітмі Форда-Фалкерсона (алгоритм Едмондса-Карпа).

Нехай завдань граф G=(V, Е) i віділена початкова (source) вершина s. Алгоритм поиска завширшки систематично обходити усі ребра G для Відкриття усіх вершин, досяжніх з s, обчіслюючі при цьом відстань (мінімальну Кількість ребер) від s до кожної досяжної з s вершини. Крім того, в процессе обходу будується дерево поиска завширшки з коренем s, что містіть усі досяжні вершини. Для кожної досяжної з s вершини v шлях в дереві поиска завширшки відповідає найкоротшому (тобто что містіть найменша Кількість ребер) шляху від s до v в G. Алгоритм працює як для орієнтованих, так и для неорієнтованіх графів.

Поиск завширшки має таку Назву того, что в процессе обходу ми йдемо вшир, тобто Перш чем приступити до поиска вершин на відстані k +1, віконується обхід усіх вершин на відстані k.

Для відстежування роботи алгоритму поиск завширшки розфарбовує вершини графа в білий, сірий и чорний кольори. Спочатку усі вершини білі, и пізніше смороду могут дива сірімі, а потім чорними. Колі вершина відкрівається (discovered) в процессе поиска, вон забарвлюється. Таким чином, сірі и чорні вершини - це вершини, Які Вже були відкриті, но алгоритм поиска завширшки по-різному працює з ними, ані щоб Забезпечити Оголошення порядок обходу. Если и вершина u чорного кольору, то вершина v або сіра, або чорна, тобто усі вершини, суміжні з чорною, Вже відкриті. Сірі вершини могут мати білих сусідів, будучи межею между відкрітімі и невідкрітімі вершинами.

Поиск завширшки будує дерево поиска завширшки, Пожалуйста спочатку складається з одного кореня, Яким є початкова вершина s. Если в процессе сканування списку суміжності Вже Відкритої вершини и відкрівається біла вершина v, то вершина v и ребро (u, v) додаються в дерево. Ми говоримо, что и є попередниками (predecessor), або батьком (parent), v в дереві поиска вшир. Оскількі вершина может буті Відкрита НЕ более одного разу, вона має НЕ більш одного батька. Взаєміні предків и нащадків визначаються в дереві поиска завширшки як завжди - если и находится на шляху від кореня s до вершини v, то u є предком v, av - Нащадки u.

Наведено нижчих процедура поиска завширшки BFS пріпускає, что вхідній граф G=(V, Е) уявлень помощью Списків суміжності. Крім того, підтрімуються додаткові Структури даних в Кожній вершіні графа. Колір кожної вершини u и v зберігається в змінній color [u], а попередники - в змінній? [u]. Если попередника у і немає (например, если u=s або u НЕ Відкрита), то? [u]=NIL. Відстань від s до вершини u, что обчіслюється алгоритмом, зберігається в полі d [u]. Алгоритм вікорістовує черго Q типом FIFO для роботи з множини сіріх вершин

Взагалі черга в програмуванні це дінамічна структура даних, что працює за принципом перший прийшов - перший Пішов (англ. FIFO - first in, first out). У Черги є голова (англ. Head) та хві...


Назад | сторінка 9 з 19 | Наступна сторінка





Схожі реферати:

  • Реферат на тему: Алгоритм розробки Бази даних поиска псіхологічніх тестів в мережі Internet ...
  • Реферат на тему: Пошук вершини в графі між двома заданими вершинами
  • Реферат на тему: Розробка та реалізація алгоритму Флойда і Беллмана-Форда для пошуку найкоро ...
  • Реферат на тему: Пошук найкоротшого шляху між парами вершин в орієнтованому і неориентирован ...
  • Реферат на тему: Системний аналіз предметної області та розробки вимог до создания ІТ для ав ...