Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Национальный Исследовательский Университет

МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ

Институт автоматики и вычислительной техники

Кафедра прикладной математики

Лабораторная работа № 2

Решение задачи поиска кратчайшего пути

в обыкновенном графе с учетом веса рёбер

Курс «Параллельные системы и параллельные вычисления»

Выполнил

студент 5 курса группы А-13-08

Захаров Антон

Преподаватель

Панков Николай Александрович

Постановка задачи

Пусть дана матрица смежности графа :

Требуется найти путь минимальной длины из начальной вершины в конечную .

Для нахождения кратчайшего пути необходимо составить последовательно-параллельную программу на языке C/C++ с применением интерфейса передачи сообщений (MPI, Message Passing Interface), а также исследовать характеристики разработанной программы в зависимости от числа исполнителей.

Последовательный алгоритм решения

Алгоритм Флойда-Уоршелла

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

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

Существует два варианта значения :

1. Кратчайший путь между , не проходит через вершину , тогда

2. Существует более короткий путь между i,\;j, проходящий через k, тогда он сначала идёт от до , а потом от до . В этом случае, очевидно,

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

Алгоритм Флойда-Уоршелла последовательно вычисляет все значения , . Полученные значения являются длинами кратчайших путей между вершинами . Алгоритм можно легко дополнить для получения интересующего пути, добавив вычисление матрицы предшествования .

1. for (k = 0; k < n; k++) {

2. for (i = 0; i < n; i++) {

3. for (j = 0; j < n; j++) {

4. if(M[i][j] > M[i][k] + M[k][j]) {

5. P[i][j] = P[k][j];

6. M[i][j] = M[i][k] + M[k][j];

7. } } } }

Параллельный алгоритм решения

В данной работе предложена параллельная реализация алгоритма Флойда-Уоршелла: матрица смежности и исходная матрица предшествования рассылаются на все узлы, каждый узел вычисляет по одной полосе фиксированного размера двух искомых матриц (матрицы весок кратчайших путей и матрицы предшествования). На каждой k-ой итерации происходит объединение результатов и повторная рассылка матриц узлам.

Результаты вычислительного эксперимента

Число вершин 100

Время

(сек)

Зависимость времени решения задачи от числа исполнителей

Число

исполнителей

Ускорение

Зависимость ускорения параллельного решения от числа исполнителей

Число

исполнителей

Число вершин 1000

Время

(сек)

Зависимость времени решения задачи от числа исполнителей

Число

исполнителей

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лабораторной работы