Міністерство освіти та науки України
Національний університет „Львівська Політехніка”
Кафедра ЕОМ
ЗВІТ
Про виконання лабораторної роботи № 3
з предмету „Паралельні та розподілені обчислення”
на тему:
„ МОЖЛИВОСТІ ВИКОРИСТАННЯ ПАРАЛЕЛЬНИХ АЛГОРИТМІВ.”
м Львів – 2005
Мета: Дослідити можливості розв’язання різноманітних задач за допомогою паралельних алгоритмів. Навчитися виділяти незалежні гілки обчислень та виконувати їх паралельно.
Завдання:
11. Лабіринт задається матрицею з’єднань в якій для кожної пари кімнат вказано чи з’єднані вони коридором. Задати (ввести з клавіатури, або генерувати випадковим чином): кількість кімнат лабіринту (n); матрицю з’єднань для них; Побудувати шлях з кімнати з номером i в кімнату з номером j.
Припустимо, що нам необхідно знайти шлях з кімнати М у кімнату Н:
Оскільки нам невідомий початковий напрям руху при пошуку шляху з кімнати М у кімнату Н, то задача вирішується перебором всіх можливих шляхів з кімнати М. Задача вирішується тоді, коли при переборі шляхів ми натрапляємо на шукану кімнату Н. На прикладі, що зображений ліворуч, помічаємо, що починаючи пошук з кімнати М наступною може бути будь-яка з кімнат 1, 2, 3. Пошук в цих напрямках не залежить один від іншого, тому можна розпаралелити задачу – одночасно вести пошук в трьох напрямках (виділили 3 підзадачі). Після того як, наприклад, ми дійшли до кімнати 1 у нас теж можливе те, що наступною може бути одна з декількох кімнат, які безпосередньо зв’язані з кімнатою 1. Звичайно, що і на цьому етапі можна виконати розпаралелення пошуку шляху. Кількість одночасно перебираємих шляхів безпосередньо залежить (а вірніше рівна) від кількості процесорних елементів. Після того, як ми задали початкову кімнату М – пошук шляхів почнеться одночасно в напрямках М-1-…, М-2-…, М-3-… на трьох процесорних елементах. Якщо ще є вільні процесорні елементи, то, наприклад продовження пошуку шляху по напрямку М-1-… можна знову розпаралелити (якщо з кімнати 1 виходить більше одного шляху). Звичайно, що шляхи пошуку можуть відрізнятись за глибиною (довжиною) – це трапляється, коли ми приходимо в "глухий кут", або перебрали всі можливі шляхи у з певної вершини (а отже на певному процесорному елементі). В такому разі процесорний елемент починає пошук шляху в певному напрямку при розпаралеленні іншої гілки (іншого шляху).
Часові (обчислювальні) затрати вирішення задачі залежать насамперед від матриці зв’язків, а не від кількості кімнат (оскільки кількість кімнат може бути великою, а будь-які зв’язки між ними відсутні). Часові затрати залежать від кількості можливих шляхів з початкової кімнати, та від глибини шляхів. На малюнку, що зображено ліворуч існує 9 можливих варіантів проходження з вершини 1 у вершину 9 (у випадку а), "а" у випадку "б" – таких варіантів є 16.
Текст програми
//вибірковий
…
var A:array of array of byte; //матриця зв’язків
ton,fromn:integer; //початок, кінець
found:boolean; //шлях знайдено
resultstring:string; //шлях
…
//Перевірка чи шлях проходив через дану кімнату
function checkpath(path:string;n:integer):boolean;
var ret:boolean;
i:integer;
begin
ret:=false;
for i:=1 to length(path) do
if ord(path[i])=n then ret:=true;
result:=ret
end;
//Пошук шляху
procedure REK(cn:integer;path:string);
var i:integer;
temppath:string;
begin
temppath:=path;
if not found then //if found then stop all
begin
for i:=1 to NewN-1 do //width
begin
if (i=ton) and (A[cn,i]=1) then
begin
found:=true;
resultstring:=path+chr(i)
end;
if A[cn,i]=1 then //if n==>i path present
if not checkpath(path,i) then
begin
temppath:=temppath+chr(i);
REK(i,temppath)
end;
temppath:=path; //try other
end;
end
end;
…
//main
resultstring:='';
found:=false;
fromn:=strtointdef(form1.edit1.Text,1);
ton:=strtointdef(form1.edit2.Text,1);
REK(fromn,chr(fromn));
end;
Результат викона...
