Разработка системы задач (алгоритмы-программы) по дискретной математике (стр. 2 из 6)
Способы описания. Выбор соответствующей структуры данных для представления графа имеет принципиальное значение при разработке эффективных алгоритмов. При решении задач используются следующие четыре основных способа описания графа: матрица инциденций; матрица смежности; списки связи и перечни ребер. Мы будем использовать только два: матрицу смежности и перечень ребер.
Матрица смежности - это двумерный массив размерности N*N. 1, вершина с номером i смежна с вершиной с номером j, 0, вершина с номером i не смежна с вершиной с номером j
Для хранения перечня ребер необходим двумерный массив R размерности М*2. Строка массива описывает ребро.
Достижимость
Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Простой путь - это путь, в котором каждая дуга используется не более одного раза.
Элементарный путь - это путь, в котором каждая вершина используется не более одного раза.
Если существует путь из вершины графа v в вершину i, то говорят, что i достижима из v.
Матрицу достижимости определим следующим образом:
1, если вершина i достижима из v иR[v,u]=0, при недостижимости
Множество R(v) - это множество таких вершин графа G, каждая из которых может быть достигнута из вершины v. Обозначим через F(v) множество таких вершин графа G, которые достижимы из v с использованием путей длины 1. T2(v) - это Г(Г(у)), то есть с использованием путей длины 2 и так далее. В этом случае:
R(v)={v}UГ(v)UГ2(v)U...UГp(v).
При этом р - некоторое конечное значение, возможно, достаточно большое.
Пример (для рисунка). R(1)={1}U{2,5}U{1,6}U{2,5,4}U{1,6,7}={1,2,4,5,6,7}
Выполняя эти действия для каждой вершины графа, мы получаем матрицу достижимостей R.
Алгоритм Дейкстры
Дано. Ориентированный граф G=<V,E>, s - вершина источник; матрица смежности A (A:array[1..n,1..n] of integer); для любых u, v€V вес дуги неотрицательный (А[u,v]>=0). Результат. Массив кратчайших расстояний - D.
В данном алгоритме формируется множество вершин Т, для которых еще не вычислена оценка расстояние и, это главное, минимальное значение в D по множеству вершин, принадлежащих Т, считается окончательной оценкой для вершины, на которой достигается этот минимум. С точки зрения здравого смысла этот факт достаточно очевиден. Другой "заход" в эту вершину возможен по пути, содержащему большее количество дуг, а так как веса неотрицательны, то и оценка пути будет больше.
Пример
Его матрица смежности: | ∞ 3 7 ∞ ∞ ∞ 1 ∞ 2 ∞ ∞ 1 А= ∞ 1 ∞ 4 4 ∞ ∞ ∞ ∞ ∞ 1 5 ∞ ∞ 1 ∞ ∞ 3 ∞ ∞ ∞ 2 ∞ ∞ |
В таблице приведена последовательность шагов (итераций) работы алгоритма. На первом шаге минимальное значение D достигается на второй вершине. Она исключается из множества Т, и улучшение оценки до оставшихся вершин (3,4,5,6) ищется не по всем вершинам, а только от второй.
| № итерации | D[1] | D[2] | D[31 | D[4] | D[5] | D[6] | T |
| 1 | 0 | 3 | 7 | ∞ | ∞ | ∞ | [2,3,4,5,6] |
| 2 | 0 | 3 | 5 | ∞ | 11 | 4 | [3,4,5,6] |
| 3 | 0 | 3 | 5 | 6 | ∞ | 4 | [3,4,5] |
| 4 | 0 | 3 | 5 | 6 | 9 | 4 | [4,5] |
| 5 | 0 | 3 | 5 | 6 | 7 | 4 | [5] |
Время работы алгоритма пропорционально N2.
Алгоритм Флойда (кратчайшие пути между всеми парами вершин).
Дано. Ориентированный граф G=<V,E>, s - вершина источник; матрица смежности A (A:array[1..n,1..n] of integer); для любых u, v€V вес дуги неотрицательный (А[u,v]>=0). Результат. Матрица D кратчайших расстояний между всеми парами вершин графа и кратчайшие пути.
Идея алгоритма. Обозначим через Dm[i,j] оценку кратчайшего пути из i в j с промежуточными вершинами из множества [1..m]. Тогда имеем: D0[i,j]:=A[i,j] и D(m+1)[i,j]=min{Dm[i,j],Dm[i,m+1]+Dm[m+1,j]}. Второе равенство требует пояснения. Пусть мы находим кратчайший путь из i в j с промежуточными вершинами из множества [1..(m+1)]. Если этот путь не содержит вершину (m+1), то D(m+1)[i,j]=Dm[i,j]. Если же он содержит эту вершину, то его можно разделить на две части от i до (m+1) до j. Время работы алгоритма пропорционально N3.
Глава 2 Система задач и упражнений.
Набор задач, разработанный нами и изложенный ниже можно систематизировать по следующим критериям:
По тематике.  |
По уровню сложности задачи. Задачи высокого уровня сложности: это задачи олимпиадного уровня, требующие глубокого знания предмета, а также комплексного подхода к решению задачи (Пример для нашего набора задач, задача о роботах, задача о комнатах музея).
Задачи среднего уровня сложности: это задачи, требующие хороших знаний предмета и навыков применения знаний на практике, т.е в процессе решения задач (Пример: задача о семьях, задача о футболистах, задача про милицию и диспетчера).
Задачи низкого уровня сложности: это задачи, для решения которых необходимы общие знания предмета и не требующие особых навыков применения знаний на практике, т.к. данные задачи направлены на формирование данных навыков.
 |
Ситуативные задачи: это задачи, формулировка которых представляет собой ситуацию из жизни. Это необходимо для более наглядного представления задачи, а также для того, чтобы сделать задачу более интересной для решения.
Задачи со строгой формулировкой: это задачи, в формулировке которой строго изложена суть задачи. Данные задачи являются задачами более низкого уровня, так как в них не требуется определения тематики задачи, а следовательно, и выбора способа решения, требуется лишь реализация алгоритма на языке программирования.
Задачи с единственным способом решения: это задачи, решить которые можно лишь одним способом, т.е. задачу нельзя рассмотреть с точки зрения различных тематик, таким образом, отсутствует выбор способа решения задачи (Пример: задача о футболистах и т.д.).
Задачи с несколькими способами решения: это задачи, которые могут быть рассмотрены с точки зрения различных тематик и, таким образом, имеют более широкий спектр решений (Пример: задача о метрополитене и т.д.).
 |
Задачи, имеющие решение применимое только к конкретным задачам: это задачи, которые в своей формулировке имеют достаточно много деталей, чтобы их решение было применимо только к конкретным задачам (Пример: задача о роботах).
Задачи, имеющие решение применимое к целому классу подобных задач: это задачи, в формулировке которых не содержится особых деталей, чтобы их решение было применимо к целому классу подобных задач (Пример: задача о метрополитене и т.д.).
Задачи.
Комнаты музея. Составьте алгоритм-программу определения числа комнат в музее и площади каждой комнаты в клетках. План музея показан ниже на рисунке.
11 6 11 6 3 10 6
7 9 6 13 5 7 5
1 10 12 7 13 13 5
13 11 10 8 10 14 13
Цифровая карта
Площадь музея состоит из клеток: m рядов и p столбцов. В каждой клетке такой матрицы (цифровая карта) проставляется число, в котором кодируется наличие стен у данной клетки. Значение числа в каждой клетке является суммой чисел: 1 (клетка имеет стену на западе), 2 (клетка имеет стену на севере), 4 (клетка имеет стену на востоке), 8 (клетка имеет стену на юге). Например, если в клетке стоит число 11 (11=8 + 2 + 1), то клетка имеет стену с южной стороны, с северной и с западной.
Исходные данные представляются в текстовом файле со следующей структурой. Первая строка: m, p – размерность сетки. Вторая строка, третья и следующие строки содержат описание матрицы цифровой карты по строкам. Расчетные данные вывести на экран в следующем порядке: первая строка – площадь каждой комнаты музея, вторая строка – количество комнат в музее.
Пример файла исходных данных:
4 7
11 6 11 6 3 10 6
7 9 6 13 5 7 5
1 10 12 7 13 13 5
13 11 10 8 10 14 13
Пример выходных данных:
9 3 8 2 6
5
Идея решения:
Данную задачу можно решить используя метод перебора с возвратом. Используя массив координат перемещения, смотрим, где отсутствуют стены, для каждой клетки, и последовательно двигаемся в ту клетку, в которую возможно, предварительно помечая клетку, в которой уже были. Если мы зашли в тупик, то возвращаемся в клетку, из которой вышли. Одновременно считаем количество клеток в каждой комнате. Когда происходит возврат в начальную точку движения, делаем всю комнату просмотренной (при помощи массива логического типа). Затем ищем клетку, в которой ещё не были и делаем её начальной точкой движения.