РЕАЛИЗАЦИЯ АЛГОРИТМА ДЕЙКСТРЫ ДЛЯ РЕШЕНИЯ ЗАДАЧИ О ЛАБИРИНТЕ В СИСТЕМЕ MAPLE THE IMPLEMENTATION OF DIJKSTRA’S ALGORITHM FOR THE SOLUTION OF TASKS OF THE LABYRINTH IN THE SYSTEM MAPLE КАДЫМОВ В.А., д-р физ.-мат. наук, проф. <...> Московский государственный гуманитарно-экономический университет КИРСАНОВ М.Н., д-р физ.-мат. наук, проф. <...> Ставится задача о нахождении кратчайшего выхода объекта из условного лабиринта, моделируемого отрезками. <...> Граф, необходимый для работы алгоритма, получается из полного графа на множестве вершин, являющихся концами отрезков преград, из которого вычитаются ребра, пересекающие преграды. <...> Алгоритм может быть использован при программировании автоматических средств передвижения лицам с ограниченными возможностями. <...> Постановка задачи Задача о выборе оптимального пути точечного объекта (мобильный робот, транспортное средство, инвалидная коляска и др.) обычно решается с применением либо различных методов искусственного интеллекта, либо методами дискретной математики. <...> В последнем случае задача сводится к задаче о кратчайшем пути во взвешенном графе. <...> Если препятствиями на пути объекта служат прямые или отрезки на плоскости, то граф является евклидовым и веса ребер совпадают с расстояниями между точками. <...> Наиболее распространенным для решения этой задачи методом является алгоритм Дейкстры [8]. <...> Этот алгоритм может быть реализован в системе компьютерной математики Maple [2,4,5]. <...> В [9] аналогичный алгоритм применялся в задаче о нахождении оптимальной траектории среди полигональных препятствий. <...> Известны также подходы к решению поставленной задачи с помощью муравьиного алгоритма [6,10]. <...> В [2] предложены алгоритмы для оптимальных маршрутов для группы объектов. <...> Задача о выходе управляемого объекта из лабиринта ставится в [7]. <...> Помимо алгоритма Дейкстры, известно еще несколько подобных алгоритмов. <...> Инклюзия 133 В.А. Кадымов, М.Н. Кирсанов маршруты между вершинами, при этом вес ребер (условные расстояния или стоимость) может быть отрицательным <...>