Параллельная реализация алгоритма построения всех маршрутов в графе средствами реляционной алгебры
Аннотация
В статье описывается способ оптимизации алгоритма построения всех маршрутов в графе средствами реляционной алгебры. Задача, решаемая предлагаемым методом, относится к классу NP-полных. Данный факт свидетельствует о необходимости поиска эффективного решения для снижения вычислительной сложности данной задачи. Последовательная реализация алгоритма основана на методе построения маршрутов с применением операции (1, 0)-свернутого произведения многомерных матриц и формализована в понятиях реляционной алгебры. Описываемый алгоритм, реализованный с применением технологии in memory, позволяет выполнять операции непосредственно по ключам исходных данных без предварительного приведения их к матричной форме. В следствии гомоморфизма реляционной алгебры и алгебры многомерных матриц, которая обладает естественным параллелизмом, имеется возможность увеличить эффективность алгоритма распределением данных по нескольким процессорам. В статье приводится доказательство изоморфизма обеих алгебр в рамках поставленной задачи. Подход, предложенный в статье, позволяет выполнять параллельные вычисления как на локальной машине (выделение отдельных потоков для фрагментов исходных данных), так и на масштабировать их на ПК, объединенные в локальную сеть. В качестве показателя эффективности, предлагаемого алгоритма, выбрано время, требующееся на построение всех возможных маршрутов в графе. Приведен сравнительный анализ последовательной и параллельной реализаций методов, выполняющихся на одной ЭВМ, средствами реляционной базы данных Microsoft SQL Server.
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
