VI Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Составление учебного расписания с применением теории графов
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
В наши дни люди стремятся автоматизировать как можно больше действий, которые выполняет человек. Это касается и образовательной системы. Современные образовательные учреждения, зачастую имеют большое количество классов (групп). А это значит, что составление учебного расписания является трудным процессом, требующим много времени. Но я считаю, что и его можно автоматизировать.
Целью моей исследовательской работы является написание программы, составляющей учебное расписание. В основе такой программы лежит теория графов.
Данная исследовательская работа имеет как образовательное, так и практическое значение. Во-первых, исследуя теорию графов и применяя её на практике, я расширяю свой кругозор и саморазвиваюсь. Также полученная программа будет нести практическое значение для учителей, составляющих учебное расписание.
Основы теории графов
Граф - это совокупность узлов (вершин) и соединяющих их ребер (дуг).(Рис.1)
Если дуги имеют направление ,то такой граф называется направленным или ориентированным графом (орграфом).
Цепью называется последовательность ребер, соединяющих две (возможно не соседние)вершины u и v. В направленном графе такая последовательность ребер называется «путь».
Граф называется связным, если существует цепь между любой парой вершин. Если граф несвязный, то его можно разбить на k связных компонент – он называется k-связным.
В практических задачах часто рассматриваются взвешенные графы, в которых каждому ребру приписывается вес (или длина). Такой граф называют сетью.
Циклом называется цепь из какой-нибудь вершины v в нее саму.
Деревом называется граф без циклов.
Полным называется граф, в котором проведены все возможные ребра (для графа, имеющего n вершин таких ребер будет n(n-1)/2.
Рис.1
Описание графов.
Для описания графов часто используют два типа матриц – матрицу смежности (для невзвешенных графов) и весовую матрицу (для взвешенных).
Матрица смежности графа с N вершинами – это матрица размером N на N, где каждый элемент с индексами (i,j) является логическим значением и показывает, есть ли дуга из вершины i в вершину j.
Часто вместо логических значений (истина/ложь) используют целые числа (1/0). Для неориентированных графов матрица смежности всегда симметрична относительно главной диагонали .Для ориентированных графов это не всегда так, потому что может существовать путь из вершины i в вершину j и не существовать обратного пути.
Для взвешенных графов недостаточно просто указать, есть ли связь между вершинами. Требуется еще хранить в памяти «вес» каждого ребра, например, стоимость проезда или длину пути. Для этого используется весовая матрица.
Весовая матрица графа с N вершинами – это матрица размером N на N, где каждый элемент с индексами (i,j) равен «весу» ребра из вершины i в вершину j.
Задача Прима-Краскала
Формулировка задачи
Дана плоская страна и в ней n городов с известными координатами. Нужно соединить все города телефонной сетью так, чтобы длина телефонных линий была минимальная.
Город будем изображать узлом (точкой). Телефонные линии могут разветвляться только на телефонных станциях, а не в чистом поле. Поскольку требуется линия минимальной общей длины, в ней не будет циклов, потому что иначе можно было бы убрать одно звено цикла и станции по-прежнему были бы связаны. В терминах теории графов эта задача звучит так:
Дан граф с n вершинами; длины ребер заданы матрицей {dij}, i, j=1..n. Найти набор ребер, соединяющий все вершины графа (он называется остовным деревом) и имеющий минимальную длину.
Эта задача – одна из тех немногих, для которых известно точное и несложное решение, причем алгоритм предельно прост.
Жадные алгоритмы.
Представим себе зимовщика, которому предоставили некоторый запас продуктов на всю зиму. Конечно, он может сначала съесть все самое вкусное – шоколад, мясо и т.п., но за такой подход придется жестоко расплачиваться в конце зимовки, когда останется только соль и маргарин.
Подобным образом, если оптимальное решение строится по шагам, обычно нельзя выбирать на каждом этапе «самое вкусное» – за это придется расплачиваться на последних шагах. Такие алгоритмы называют жадными.
Решение.
Удивительно, но для непростой задачи Прима-Краскала жадный алгоритм дает точное оптимальное решение. Алгоритм формулируется так:
В цикле n-1 раз выбрать из оставшихся ребер самое короткое ребро, которое не образует цикла с уже выбранными.
Как же проследить, чтобы не было циклов? Оказывается очень просто: в самом начале покрасим все вершины в разные цвета и затем, выбрав очередное ребро между вершинами i и j, где i и j имеют разные цвета, перекрасим вершину j и все соединенные с ней (то есть имеющие ее цвет) в цвет i. Таким образом, при выборе ребер, соединяющих вершины разного цвета, цикл не возникнет никогда, а после n-1 шагов все вершины будут иметь один цвет.
Для записи информации о ребрах введем структуру причем будем считать, что в паре номер первой вершины i меньше, чем номер второй j.
Приведенная ниже программа действует по следующему «жадному» алгоритму:
1. Покрасить все вершины в разные цвета.
2. Сделать n-1 раз в цикле z выбрать ребро (i,j) минимальной длины, соединяющее вершины разного цвета; z запомнить его в массиве ребер; z перекрасить все вершины, имеющие цвет j, в цвет i.
3. Вывести результат.
Пример составления расписания
Пусть необходимо составить учебное расписание для образовательного центра. При этом должна быть известна некоторая информация о группах, для которых проводятся занятия; преподавателях, которые ведут эти занятия, а также о некоторых ограничениях, накладываемых, к примеру, наличием свободных аудитории.
В учебном центре необходимо провести занятия по «Пользователь ПК», «Программирование», «Пользователь 1С», «Компьютерная графика» и «Настройка компьютера» в группах А, В, С. Занятия проводятся преподавателями K, L, M. Каждое занятие проводится в течение одного учебного часа, включая перерывы. В центре имеются три аудитории, которые вмещают лишь одну из групп. Составим расписание занятий для данного случая.
Составим граф, вершинами которого являются занятия. Вершины соединим ребром, в случае, если соответствующие занятия нельзя проводить одновременно (занятия, проводятся в одной аудитории или одним преподавателям и т.д.), тогда составление расписание сводится к нахождению правильной раскраски полученного графа минимальным количеством цветом при условии, что количество вершин, окрашенных в один цвет, не будет превосходить количества аудиторий.
Сформированный граф будет выглядеть следующим образом (рис. 2.а), а соответствующий ему раскрашенный граф будет иметь следующий вид (рис. 2.б).
Рисунок 2.
Исходя из найденной раскраски, можно сформировать расписание, которое будет соответствовать поставленной задаче.
|
K |
L |
M |
|
|
15-00 |
Программирование |
Компьютерная графика |
|
|
16-00 |
Компьютерная графика |
Программирование |
|
|
17-00 |
Настройка компьютера |
Пользователь ПК |
|
|
18-00 |
Пользователь ПК |
Пользователь 1С |
Компьютерная графика |
|
19-00 |
Настройка компьютера |
Заключение
В данной работе были исследованы основные направления, концепции, касающиеся проблемы раскраски графов. Было рассмотрено несколько алгоритмов раскраски. В результате проведенного анализа для практической части работы был выбран вышеприведенный алгоритм. Хотя данный алгоритм является приближенным, он дает относительно точный результат при довольно низких затратах ресурсов.
В данный момент идет работа над программным продуктом позволяющий решить проблему составления расписания. В качестве языка программирования для реализации поставленной задачи был выбран язык программирования Python с графической библиотекой tkinter.
Список литературы
Поляков К. Ю. Программирование. Python. C++. Часть 3: учебное пособие / К. Ю. Поляков. – М.: БИНОМ. Лаборатория знаний, 2018. – 208 с.: ил.
Джейсон Бриггс Python для детей: самоучитель по программированию. – М.: МИФ, 2016. – 320 с.: ил.
Алгоритмы на графах URL https://informatics.msk.ru/course/view.php?id=6
Алгоритмы URL http://e-maxx.ru/algo/