ОИИ(Основы искусственного интелекта)
.docxМинистерство образования Республики Беларусь
Учреждение образования
«Белорусский государственный университет информатики и радиоэлектроники»
Кафедра интеллектуальных информационных технологий
Расчётная работа по дисциплине "Проектирование программ в интеллектуальных системах" на тему "Найти диаметр неориентированного графа"
Выполнил: |
студент гр. 021702 Бельский Е. А. |
Проверил: |
Лазуркин Д. А. |
Минск
2011
1.Предметная область
1)Диаметр графа – максимум расстояния между вершинами для всех пар вершин
2)Расстояние между вершинами – длина кратчайшей цепи, соединяющей заданные вершины.
Примеры:
Пример 1:
Исходный граф:{A,B},{<A,B>}
Результат:
Пример 2:
Исходный граф:{A,B,C,D,E,F,G},{<A,B>,< B,C>,<C,D>,<D,E>,<E,A>,<F,E>,< B,G>}
Результат: Диаметр = 4
Пример 3:
Исходный граф: {A,B,C,D,E,F},{<A,B>,< B,C>,<C,D>,<E,F>,<F,A>,<C,F>}
Результат: Диаметр = 3
Пример 4:
Исходный граф:{A},{}
Результат: Диаметр = 0
Пример 5:
Исходный граф:{A,B,C,D},{<A,B>,< B,C>,<C,D>,<D,A>,<A,C>,< B,D>}
Результат: Диаметр = 1
3 Описание алгоритма:
Алгоритм поиска диаметра неориентированного графа основан на алгоритме Дейкстры.
1)Загружаем матрицу смежности A графа G
2)Применяем алгоритм Дейкстры к матрице А для вычисления матрицы C, содержащей все кратчайшие пути неориентированного графа:
а.Каждой вершине сопоставим мутку-минимальное известное расстояние от этой вершины до а. Алгоритм работает пошагово- на каждом шаге он "посещает" одну вершину и пытается уменьшать метки.Работа алгоритма завершается,когда все вершины посещены.
b.Инициализация.Метка самой вершины а полагается равной 0,метки остальных вершин-бесконечности.Это отражает то,что расстояния от а до других вершин пока неизвестны.Все вершины графа помечаются как не посещённые.
с.Шаг алгоритма.Если все вершины посещены,алгоритм завершается.В противном случае go to b.
d.Находим в матрице смежности максимальный элемент-это и будет диаметр неориентированного графа.
4 Ограничения реализации алгоритма
Входной граф должен быть классическим неориентированным.
5 Список литературы
-
Кормен Д., Алгоритмы. Построение и анализ.
-
Касьянов, В. Н. Графы в программировании: обработка, визуализация и применение / В. Н. Касьянов, В. А. Евстигнеева. – СПб. : БХВ-Петербург, 2003.
-
Евстигнеев В.А., Касьянов В.Н., Толковый словарь по теории графов