Составление учебного расписания с применением теории графов

VI Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке

Составление учебного расписания с применением теории графов

Нестерова  Д.М. 1
1Государственное образовательное учреждение «Коми республиканский лицей при Сыктывкарском государственном университете»
Дуркин  О.Л. 1
1Государственное образовательное учреждение «Коми республиканский лицей при Сыктывкарском государственном университете»
Автор работы награжден дипломом победителя 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/

Просмотров работы: 339