ОИИ(Основы искусственного интелекта)

Министерство образования Республики Беларусь

Учреждение образования

«Белорусский государственный университет информатики и радиоэлектроники»

Кафедра интеллектуальных информационных технологий

Расчётная работа по дисциплине "Проектирование программ в интеллектуальных системах" на тему "Найти диаметр неориентированного графа"

Выполнил:	студент гр. 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.

• Евстигнеев В.А., Касьянов В.Н., Толковый словарь по теории графов