Материал: Интеллектуальные информационные системы. труды международной научно-практической конференции. И73

7. Коротченко А.Г. О сравнении различных методов решения задачи Коши для системы обыкновенных дифференциальных уравнений [Текст] / Коротченко А.Г., Сморякова В.М. // Интеллектуальные информационные системы Труды Международной научно-практической конференции. В 2-х частях. - 2019. - С. 133-137.

Национальный исследовательский Нижегородский государственный университет им. Н.И. Лобачевского

УДК 004.9

А. Е. Обухова

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

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

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

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

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

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

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

(рис. 3).

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

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

96

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

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

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

97

Несмотря на множество алгоритмов прохождения лабиринтов (волновой алгоритм, алгоритмы одной руки, алгоритм Пледжа, алгоритм 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.

ФГБОУ ВО «Воронежский государственный технический университет»

УДК 005

Е. С. Оськина, Н. Н. Барышева

РАЗРАБОТКА СИСТЕМЫ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ ДЛЯ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ДЕЯТЕЛЬНОСТИ ПЕРСОНАЛА В АЛТАЙСКОМ ИНСТИТУТЕ РАЗВИТИЯ ОБРАЗОВАНИЯ ИМЕНИ А.М. ТОПОРОВА

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

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

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

98

ровать, что другие смогут понять, почему эти решения были приняты тем или иным способом.

Как дополнительное средство для помощи в принятии решений в управлении используются системы поддержки принятия решений [1].

Система поддержки принятия решений выполняет две основные задачи:

−поиск наилучшего варианта из множества предложенных (оптимизация);

−установление возможных вариантов от наиболее к наименее предпочтительному (ранжирование).

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

Зачастую имеется много различных критериев, которые необходимо учитывать при принятии решения. Важно определить критерии и принять решение по этим критериям как можно точнее. Максимизировать каждый критерий просто невозможно, и максимизация одного критерия, скорее всего, не позволит учесть другие важные критерии [4].

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

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

–это метод взвешенной суммы критериев (МВСК) [5]. Этот метод является простым инструментом, который может быть очень полезным при принятии сложных решений, особенно тогда, когда есть много вариантов и много критериев различной важности, подлежащие рассмотрению.

Рассмотрим метод взвешенной суммы критериев с научной точки зрения.

Предварительно введем начальные данные. Пусть Zi – множество значений критерия fi. Каждый вариант x характеризуется значениями критериев y1 = f1(x), …, ym = fm(x), образующими векторную, или критериальную оценку данного варианта y = (y1, …, ym). Обозначим через X множество всех вариантов.

Сравнение вариантов по предпочтительности выполняется по принципу сопоставления их векторных оценок [3].

Данный метод можно представить в виде следующей матрицы (таблица).

99