Построение логической и физической информационной модели (компьютерной). Физический уровень информационной модели

Практическая работа №4

Тема: «Применение методов «Перебора в ширину», «Перебора в глубину»

Метод поиска в глубину на графе.

Рекурсивная и не рекурсивная реализации алгоритма DFS

Цель: Сформировать представление о методе и алгоритме поиска в глубину на графе и его применении при решении задач (задачи класса сложности Р).

Результаты. После выполнения лабораторной работы должны сформироваться умения:

· находить соответствие между объектом исследования (системой) и его концептуальной информационной моделью, логическим и физическим уровнями информационной модели;

· применять рекурсивный метод поиска (перебора) вершин в глубину на графе;

· формулировать и строить абстрактный алгоритм решения задачи поиска (перебора) вершин в глубину;

· применять программирование для реализации алгоритма поиска в глубину;

· выполнять оценку трудности программы для выбранного способа представления графа;

· обосновывать принадлежность алгоритма к категории сложности Р;

· уметь применять поиск в глубину на графе при решении практических задач.

Теоретические сведения

Постановка задачи. Концептуальный уровень информационной модели

Неформальная постановка задачи

На схеме метрополитена отмечены станции и ветки метро - линии их соединяющие, ряд станций отмечены как строящиеся и не имеют действующих линий. Требуется проложить произвольный маршрут через промежуточные станции, чтобы соединить между собой станцию – пункт отправления и конечный пункт следования. Определить все станции метрополитена, связанные между собой линиями метро.

Построение предметной модели и ее качественное описание совпадает со схемой метро с нанесенными на нее системой линий и станций или табличным описанием в виде перечисления станций и связей между ними (линии), представляющим бинарную матрицу, столбцы и строки которой соответствуют названиям станций.

Построение концептуальной информационной модели, отражающей идеологию структуризации данных, приводит к возможному представлению предметной модели в виде неориентированного графа, в котором вершинам соответствуют станции метрополитена, а ребрам графа – линии метро, соединяющие соответствующие станции. Граф при этом оказывается несвязным, т.к. часть вершин, соответствующих нанесенным на карту метро строящимся станциям, не имеет исходящих ребер и соответственно смежных вершин. При этом в информационную модель не включается информация несущественная для поставленной цели решения задачи: расстояние между станциями, время движения между станциями, интервал между движениями поездов и т.д.

Построение математической модели в виде формальной системы (исчисления). Логический уровень информационной модели

Формальная постановка задачи (в виде формальной системы)

Связаны ли какие-либо две вершины графа или нет? Найти простой путь между двумя вершинами v и w графа (path). Путь – последовательность вершин v, …vi, vi+1, …w , между каждой парой вершин vi, vi+1 такого пути должно существовать ребро. Перечислить все вершины, связанные с заданной вершиной графа.
Граф представлен конечными множествами вершин V={v1, v2, v3, … vi,…vn} и ребер E={e1, e2, e3, …ek, …, em}. Каждое ребро задается парой смежных вершин ek=(vi,vj).

Построение алгоритма решения математической задачи (построение абстрактного вычислительного алгоритма)

Идея метода

Для отыскания такого простого пути найдем и проверим любую смежную вершину i с вершиной v – началом пути, а затем, в случае если искомая вершина конца пути w не найдена, продолжим поиск следующей смежной и не просмотренной вершины для ранее просмотренной вершины i. Переход в следующую смежную и ранее не просмотренную вершину происходит до тех пор, пока не будет найдена искомая вершина w, либо, в случае отрицательного результата поиска, не будут просмотрены все вершины графа. Если на очередном шаге у текущей вершины i не оказывается смежных и не посещенных вершин, то осуществляется возврат к предыдущей смежной вершине. Данный способ (порядок) обхода вершин носит название поиск или обход в глубину. Для запоминания порядка посещения и обеспечения возврата используем структуру стек или механизм рекурсии. Для обозначения просмотренных вершин можно использовать метки.

Построение полиномиального алгоритма (задача класса Р)
Алгоритм поиска в глубину (DFS – Depth-first search):

· Поиск начинается с произвольной фиксированной вершины v, отмечаем ее как просмотренную и помещаем в Стек.

· Извлекается вершина, находящаяся на вершине Стека, становится текущей вершиной поиска.

· Производится поиск вершины, смежной и не просмотренной с текущей вершиной. Если такая вершина находится, то ее номер также заносятся в Стек, и вершина отмечается меткой посещенная.

· Процесс поиска продолжается для каждой новой вершины поиска п.3), если смежных и не пройденных вершин нет, то извлекается и обрабатывается вершина, записанная в Стек, п. 2)

· Поиск заканчивается, если искомая вершина w найдена или стек становится пустой (последнее условие обязательно для полного обхода всех вершин графа или для случая неуспешного поиска вершины w).

Построение логической и физической информационной модели (компьютерной). Физический уровень информационной модели