Материал: Оптимизация и моделирование в автоматизированных системах. труд. ФГБОУ В.О., Воронежский г.т.и

Рис.2. Диаграмма компонентов

В ходе разработка системы были определены основные сущности:

ξTypeUser (Тип пользователя) – содержит информацию о типах клиента;

ξUser (Пользователь) – содержит информацию о пользователе;

ξProtection (Защита) – содержит информацию о защите ВКР;

ξGraphickPass (График сдачи зашиты) – содержит информацию времени сдачи защиты;

ξFile (Файл) – содержит информацию о файлах;

ξTemplate (Шаблон) – содержит информацию о файлах нужных для шаблона ВКР;

ξSpeciality (Специальность) – содержит информацию о специальностях;

ξDiplom (Диплом) – содержит информацию о дипломном проекте.

Рис. 3. Сущности базы данных

60

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

внедрена в Санкт-Петербургском колледже телекоммуникаций.

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

Литература

1. Лукьяненко, М. В. Проектное обучение в техническом вузе [Текст] / М. В. Лукьяненко, Г. М. Гринберг, Н. И. Пак // Проблемы повышения качества подготовки специалистов: науч.-метод. сборник / Сиб. гос. аэрокосмич. ун-т. –

Красноярск, 2006. – С. 312–320.

Санкт-Петербургский государственный университет телекоммуникаций им. проф. М. А. Бонч-Бруевича

УДК 004.9

А. Е. Обухова

РЕАЛИЗАЦИЯ АЛГОРИТМА ЛЮКА-ТРЕМО «ПОИСК ВЫХОДА ИЗ ЛАБИРИНТА»

В данной статье предложена реализация алгоритма построения лабиринта произвольного размера и нахождения пути его прохождения.

Универсальный алгоритм прохождения любых лабиринтов описан Э. Люка. При описании алгоритма, Э. Люка назвал его автором другого французского математика М. Тремо. Таким образом, алгоритм стал известен как алгоритм Люка-Тремо.

Клод Шеннон, применив вариант алгоритма Люка-Тремо, построил одного из первых самообучающихся роботов. Робот сначала обследовала весь лабиринт, а затем (во второй раз) проходил весь путь намного быстрее, избегая участков, пройденных дважды.

Алгоритм Люка-Тремо реализует 4 правила:

1.Если робот находится на перекрестке, на котором не был ни разу, то дальше он движется по коридору, следуя правилу правой руки (рис. 1), если же впереди тупик – поворачивает обратно (рис. 2).

2.Если попал на перекресток, на котором он уже был, и попал на него по такой дороге, по которой он идет в первый раз, то робот отправляется обратно

(рис. 3).

61

3.Если робот подошел к перекрестку таким путем, по которому уже дважды шел, но есть коридоры, по которым ещё ни разу не ходили, робот идет по правому из них (рис. 4).

4.Если же не пройденных коридоров на перекрестке лабиринта нет, то робот идет по правому, пройденному один раз (рис. 5).

Программа реализована на языке программирования С++. Разработанная программа, позволяет сгенерировать лабиринт заданного размера. Построение начинается с определения границ лабиринта, после того как пользователь вводит с клавиатуры требуемые значения ширины и длины. Точки входа и выхода определяются случайным образом. Далее осуществляется построение лабиринта. Построчно фиксируются случайные пути прохождения лабиринта. Потом, следуя алгоритму, в программе ещё раз построчно просматривается двумерный массив символов и все пустоты (пробелы) заменяются решетками – стенками. Таким образом, в виде элементов двумерного массива (пробелов и решеток) формируется лабиринт.

Для прохождения лабиринта сначала определяем среди элементов двумерного массива точку входа. Затем в действие приводится алгоритм ЛюкаТремо, по которому программа находит выход из лабиринта. В конце на экран выводится сам сгенерированный лабиринт и путь, по которому должен двигаться робот, чтобы его преодолеть (рис. 6, рис. 7).

62

В ходе работы разработана программа, которая строит случайным образом лабиринт заданного размера, и реализует алгоритм Люка-Тремо «Поиск выхода из лабиринта».

Не смотря на множество алгоритмов прохождения лабиринтов (волновой алгоритм, алгоритмы одной руки, алгоритм Пледжа, алгоритм Tremaux, алгоритм формирования рек, муравьиный алгоритм, алгоритмы роевого интеллекта) в работе использован алгоритм Люка-Тремо, так как он является универсальным и с его помощью можно найти выход как из односвязных, так и многосвязных лабиринтов.

Литература

1.[https://myrobot.ru/articles/logo_mazesolving.php]

2.[http://www.cyberforum.ru/cpp-beginners/thread983912.html]

3.[https://nxt33.blogspot.com/2013/04/blog-post_5912.html]

4.[https://ru.stackoverflow.com/questions]

5.[https://codelessons.ru/cplusplus/funkcii-function-v-c-peregruzki-i- prototipy-funkcij.html]

6.Мозговой, М. Занимательное программирование: Самоучитель / М. Мозговой. — Питер, 2004.

Воронежский государственный технический университет

УДК 519.173

К. Е. Ответчиков, А. Н. Миханьков

ФОРМАЛИЗАЦИЯ ЭКОНОМИЧЕСКОЙ МОДЕЛИ ЖЕЛЕЗНОДОРОЖНЫХ ПЕРЕВОЗОК

Рассмотрим задачу оптимизации железнодорожных перевозок. Среди возможных моделей к математическим наиболее близки требования минимизации экономических расходов некоторых ресурсов. К таким ресурсам относят суммарный путь, пройденный вагонами при перемещении от определённых заказчиками пунктов отправления к пунктам назначения, суммарное время в пути, амортизация инфраструктуры, включая путевое хозяйство и локомотивный парк, время работы локомотивных бригад с учётом физиологических ограничений и многие другие. Каждый из таких критериев требует анализа многих аспектов и особенностей железнодорожного транспорта. Остановимся на задаче минимизации расходов некоторого ресурса путём оптимального сбора железнодорожных составов из множества вагонов с известными пунктами отправления и назначения. Обратим внимание на постоянную корректировку объёма заказанных перевозок: по прибытии в

63

пункты назначения некоторые вагоны нужно отцепить от состава, вместо них требуется прицепить вагоны, которые должны в данных пунктах начать или продолжить движение к пунктам назначения. Будем считать, что диспетчерская служба в каждый момент времени извещена об особенностях всех перегонов транспортной сети, представленной графом ǡ. Здесь – множество станций железнодорожной сети, – множество рёбер или ориентированных дуг, связывающих станции.

В соответствии с выбранным критерием оптимизации (длина пути, нормативное время прохождения перегона средним составом, затраты энергии на проводку вагона и т.п.) дуги א получают вес . Особую разметку дуг применим в случае многопутного пути, связывающего некоторые станции. Случай неориентированных рёбер сводится к паре антипараллельных ориентированных дуг соответствующей пропускной способности в каждом направлении движения. Ряд ограничений на компоновку составов приходится учитывать в случае дополнительных условий: несущая способность полотна дороги, опасный груз, ограничения на пропускную способность узловых станций. Такие условия требуют построения специальных частных моделей перевозок между некоторыми станциями, образующими вместе с соответствующими дугами подграф ǡ графа ǡ.

Тополого-экономический граф ǡ с учётом весов всех имеющихся дуг порождает взвешенную матрицу соседства вершин . С помощью матричного алгоритма [1,2] поиска кратчайших маршрутов между всеми парами вершин получим матрицу кратчайших расстояний , а также матрицу

оптимальных маршрутов ؔ ǡ ȁǡȁ. Её элементами служат списки

найденных допустимых маршрутов, соединяющих все пары вершин ݒ ǡݒ א , упорядоченные в сторону ухудшения выбранного критерия оптимизации.

Особую сложность представляет задача многокритериальной оптимизации перевозок, когда разметка дуг орграфа ǡ несёт информацию о нескольких критериях оптимизации (например, время в пути и пропускная способность дуги). В этом случае одновременная оптимизация, как правило, не возможна, тем не менее, с помощью постановки вспомогательной задачи типа транспортной задачи линейного программирования можно найти Паретооптимальное решение. [3,4]

Продолжение однокритериальной постановки задачи сводится к нахождению непустых пересечений списков ǡ для разных пар пунктов отправления и назначения. Их наличие показывает возможность перемещения соответствующих вагонов в одном составе. Рассчитывая суммарные затраты ресурса на перемещение всего массива актуальных заказов, получаем значение заданного критерия оптимальности. Остаётся среди полученных вариантов формирования составов выбрать наилучший по заданному критерию и удовлетворяющий заданным дополнительным ограничениям. Хотя множество допустимых вариантов формирования составов растёт факториально с ростом

64