Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 11.06.2010, 17:24
WieRuindl

 
Сообщений: n/a

Алгоритм Уоршелла, помогите!
Дана квадратная матрица nxn, которая заполняется пользователем значениями либо 0, либо 1. Надо ее обработать следующим образом:

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

for(k= 0; k< n; k++)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
A[i,j] = min(A[i,j], A[i,k]*A[k,j]);

после выполнения алгоритма матрица получит свой конечный вид. Если кто сечет в графах, то начальная матрица - это матрица смежности в ориентированном невзвешенном графе, результат работы - матрица достижимости. Но это не суть важно. Сложность алгоритма n^3. Мне надо переписать его так, чтобы сложность была n. Преподаватель толкал что-то про распараллеливание вычислений по внутренним двум циклам for на n^2 матриц, а тогда весь проход алгоритма осуществляется только за один проход по внешнему for. Но я вообще не секу, как это сделать. ПОМОГИТЕ ПОЖ, кому не лень, мне срочно это надо написать =(
  #2  
Старый 11.06.2010, 17:41
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Даже для заполнения квадратной матрицы nxn требуется квадратичное время, так что линейное - абсурд.
  #3  
Старый 11.06.2010, 18:03
гость

 
Сообщений: n/a

там, насколько я понимаю, он хочет, чтобы сама программа завершала работу за n. При этом, полагаю, допустимо, чтобы любая другая информация, необходимая для работы, отправлялась в функции, которые будут там с ней работать. В идеале, у нас есть n^2 компьютеров, которые ведут обсчеты, а главный компьютер, на котором работает пользователь, получает результаты. В общем, не суть важно, помогите просто как можно лучше оптимизировать алгоритм
  #4  
Старый 11.06.2010, 18:24
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

ну вот тут есть наводки:
http://maths.pomorsu.ru/grid/mpi/LAB/RUS/PPT/Lab05.pdf
  #5  
Старый 11.06.2010, 18:46
WieRuindl

 
Сообщений: n/a

да видел я этот сайт. Там же ни фига не понятно =((
  #6  
Старый 12.06.2010, 02:43
гость

 
Сообщений: n/a

твой алгоритм:

for(k= 0; k< n; k++)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
A[i,j] = min(A[i,j], A[i,k]*A[k,j]);

на самом деле можно и так записать (именно в таком виде обычно и доказывается, приведенное выше - уже оптимизация по памяти):

for(k= 0; k< n; k++) {
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
T[i,j] = min(A[i,j], A[i,k]*A[k,j]);
A = T;//по элементное копирование
}

где T - временная матрица.

Итерации внутренних двух циклов можно выполнять независимо. Вот и выполняй!

На openmp что-то типа этого будет

#pragma omp parallel
{
for(k= 0; k< n; k++) {

#pragma omp for collapse(2)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
T[i,j] = min(A[i,j], A[i,k]*A[k,j]);

A = T;
}
}


for (int k

#pragma omp parallel shared(x) private(i, j)
{
#pragma omp for collapse(2)
for (i = 0; i < N; i = i + 2)
{
for (j = 0; j < N; j = j + 2)
{
#pragma omp atomic
x++;
}
}
}
  #7  
Старый 12.06.2010, 02:44
гость

 
Сообщений: n/a

это не читать
Цитата:
for (int k

#pragma omp parallel shared(x) private(i, j)
{
#pragma omp for collapse(2)
for (i = 0; i < N; i = i + 2)
{
for (j = 0; j < N; j = j + 2)
{
#pragma omp atomic
x++;
}
}
}
  #8  
Старый 12.06.2010, 02:52
гость

 
Сообщений: n/a

Но можно и ващще за O(log^2 n) параллельного времени, O(n^3 log n) работы - просто считаеш сумму A + A^2 + A^3 + ... + A^n - она равна матрице "число путей из i в j" (длины от 1 до n-1).

умножение двух матриц - O(log n) параллельной работы, вычисление A^(2^k) для всех k=0..log n - еще один фактор O(log k). Потом искомая сумма считается суммированием нужных элементов этих матриц параллельной сверткой за O(log n)
  #9  
Старый 12.06.2010, 22:46
WieRuindl

 
Сообщений: n/a

кхм... еще бы разобраться во всем этом оО
попытаюсь хотя бы) Спасибо! Если будут еще советы, буду очень рад, любые комментарии помогут!
  #10  
Старый 12.06.2010, 23:13
Новичок

Отправить личное сообщение для WieRuindl Посмотреть профиль Найти все сообщения от WieRuindl
 
Регистрация: 12.06.2010
Сообщений: 13

Вот это комментарий от преподавателя, если нужно:

...обратите внимание, что внешний цикл идет по промежуточным вершинам,
поэтому, если два внутренних цикла заменить на n2 проыессоров, каждый из
которых вычисляет возможность провести ребро (по транзитивности) между
двумя конкретными вершинами (за которые отвечает данный процессор)
через данную промежуточную вершину, то у вас и получится параллельный
алгоритм, который делает n шагов (по промежуточным вершинам) и имеет
n2 процессоров (параллельных процессов)
...за каждый такой процесс у вас должна отвечать отдельная матрица,
вот их и будет 25
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
помогите улучшить алгоритм w-x-t Реализация, исходники, языки 9 16.11.2009 01:11
Помогите найти алгоритм Бизнесмэн Математические алгоритмы 11 08.08.2009 08:58
Помогите найти алгоритм! гость Вычислительная геометрия 6 20.04.2009 17:02
Алгоритм Уоршелла для нахождения транзитивного замыкания. ioioio Реализация, исходники, языки 1 20.05.2008 23:31
Помогите найти алгоритм rom@rio Обработка изображений, звук, графика 1 16.03.2008 08:17