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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #11  
Старый 12.06.2010, 23:36
гость

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

Не, не нужно. И так все ясно

Но вот что за магическое число 25? У вас 25 вершин всего? Или 25 процессоров? Для графа в 25 вершин никакое распараллеливание нах надо. Вот если 25 тыщ, или 25 лимонов, тогда другое дело
  #12  
Старый 13.06.2010, 00:29
Новичок

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

Нет, вершин всего n=5. n^2=25 процессоров содержат в себе информацию о возможности пути из пункта i в пункт j. То есть идея состоит в том, чтобы ускорить процесс поиска путей за счет использования большей памяти.
Да, я понимаю, что на матрице 5х5 использование параллельного алгоритма не нужно, но я, по сути, должен предоставить рабочую модель такого алгоритма. Да и потом, не моя это забота, нужно или нет - препод сказал сделать так, значит, должен сделать так =/
  #13  
Старый 13.06.2010, 01:18
Новичок

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

Вот что я придумал (попытаюсь сразу демонстрировать на примере):

Допустим, у нас есть граф G=(4; (1,4),(2,1),(3,1),(4,2))
(я взял граф на 4 вершинах, чтобы было проще расписывать все выкладки)

(0,0,0,1)
(1,0,0,0)
(1,0,0,0)
(0,1,0,0)

Одновременно с созданием матрицы смежности будет созданы n^2=16 матриц размером 1х2:
[1,0] [1,0] [1,0] [1,4]
[2,1] [2,0] [2,0] [2,0]
[3,1] [3,0] [3,0] [3,0]
[4,0] [4,2] [4,0] [4,0]

Каждая из матриц [i,j] содержит в себе путь из i в j. Первое значение i в матрице - это номер начального пункта, второй - j - конечного. Если путь из i в j существует, то оба значения ненулевые, иначе вторым значением идет 0. В данном случае в функцию будет передана строка (0,0,0,1) и k=1

Как будет работать программа. Существует внешний цикл for (k = 0; k <n; k++). На каждой итерации цикла будет вызываться функция f(k, &A[k][0]), в которую будет передаваться номер строки и указатель на первый элемент строки.

Далее. Из всего списка из n^2 матриц [i1, j1] будут поочередно вызываться те, у которых i1=k и j1≠0. В данном примере будет вызвана только [1,4]. Далее смотрится второе значение в матрице. Здесь j1=4. Из всего списка из матриц [i2, j2] будут снова поочередно вызываться те, у которых i2=j1 и j2≠0. В данном примере будет вызвана только [4,2]. Это как фишки в домино [1,4][4,2] => следствием такого поочередного вызова будет вывод о том, что существует путь из (1) в (2) через промежуточный пункт (4).

В список матриц вносится изменение, одна их матриц вида [1,0] будет заменена на [1,2]:
[1,0] [1,2] [1,0] [1,4]
[2,1] [2,0] [2,0] [2,0]
[3,1] [3,0] [3,0] [3,0]
[4,0] [4,2] [4,0] [4,0]
а через использование синтаксиса работы с указателями в переданную в функцию строку будет внесено изменение (0,1,0,1) . Теперь она одержит путь из (1) в (2). Выход из функции.

Аналогичным образом в функцию будут переданы строки с номерами 2, 3 и 4. После первого прохода цикла for матрица достижимости примет такой вид:

(0,1,0,1)
(1,0,0,1)
(1,0,0,1)
(1,1,0,0)

А "мини-матрицы" примут вид:
[1,0] [1,2] [1,0] [1,4]
[2,1] [2,0] [2,0] [2,4]
[3,1] [3,0] [3,0] [3,4]
[4,1] [4,2] [4,0] [4,0]

При этом обновление матрицы произойдет за n шагов.

После второго прохода цикла for:
(1,1,0,1)
(1,1,0,1)
(1,0,0,1)
(1,1,0,1)

[1,1] [1,2] [1,0] [1,4]
[2,1] [2,2] [2,0] [2,4]
[3,1] [3,2] [3,0] [3,4]
[4,1] [4,2] [4,0] [4,4]

Транзитивное замыкание завершено.

Примерно так. Как оцените?
  #14  
Старый 13.06.2010, 01:27
гость

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

какие еще там 25 или 16 матриц. вы что! всего две матрицы нужно! "текущая" и "следующая". у вас будет n итераций (внешний цикл по k), на каждой итерации у вас n^2 процессоров читают данные из "текущей" матрицы, пишет результат в следующую, потом матрицы обмениваются, начинается следующая итерация. всё.

вы что, программированием вообще не занимались?

Цитата:
Да и потом, не моя это забота, нужно или нет - препод сказал сделать так, значит, должен сделать так =/
дурак твой препод. на дворе столько всяких интересных задач, а он какой-то ерундой занимается
  #15  
Старый 13.06.2010, 02:10
Новичок

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

Ну, дурак, не дурак, а оценку он ставить будет в конечном итоге) да и ладно, фиг с ним с преподом.

Программированием специально не занимался никогда. Самоучка. Нет, нас, конечно, учат в институте, но лекции я активно гуляю) мужик, который их нам читает, программист просто отличный, но лекции читает так, что лучше повеситься. Все, что я умею - личный опыт.

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

а насчет этой задачи... Я просто все равно не до конца осознаю, что же от меня требуется. Он что-то вякал про n^2 матриц, вот я и думаю в этом направлении, бью в бубен и жду озарений.
  #16  
Старый 13.06.2010, 03:23
гость

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

я тебе уже привед код на openmp, чё не так?

вот полный исход, компилируешь g++ -fopenmp

Код:
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

#define N 5

int A[5][5], T[5][5];

void floyd() {
    #pragma omp parallel
    for (int k = 0; k < N; k++) {

        #pragma omp for collapse(2)
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                T[i][j] = A[i][j] | (A[i][k] & A[k][j]);
            }
        }
        
        #pragma omp for collapse(2)
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                A[i][j] = T[i][j];
            }
        }
    }
}

int main()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            scanf("%d", &A[i][j]);

    floyd();

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            printf("%d ", A[i][j]);
        printf("\n");
    }
}
  #17  
Старый 13.06.2010, 03:24
гость

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

и тут херня у тебя была написана:
A[i,j] = min(A[i,j], A[i,k]*A[k,j]);

извини что сразу не заметил
  #18  
Старый 13.06.2010, 12:27
Новичок

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

ну да, да, я тоже заметил ошибку, исправить уже нельзя было. Правильным должен быть такой вариант:
A[i,j] = max(A[i,j], A[i,k]*A[k,j]);
  #19  
Старый 13.06.2010, 19:45
гость

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

Сообщение от WieRuindl Посмотреть сообщение
ну да, да, я тоже заметил ошибку, исправить уже нельзя было. Правильным должен быть такой вариант:
A[i,j] = max(A[i,j], A[i,k]*A[k,j]);
зачем умножать? есть логические операции AND, OR, их и надо использовать.

A[i,j] = A[i,j] | (A[i,k] & A[k,j])
  #20  
Старый 13.06.2010, 19:53
Новичок

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

да это уже не суть принципиально, умножать или логические операции использовать.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
помогите улучшить алгоритм 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