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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 24.04.2007, 00:48
NewRon

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

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

Заранее благодарен любой помощи...


Поиск в графе (поиск в ширину).
Задача состоит в том, найти путь из вершины A в вершину B. Будем задавать граф матрицей смежности, т.е. квадратной таблицей NxN, в которой на пересечении i-й строки и j-го столбца значение TRUE, если i и j соединены ребром, и FALSE в противном случае.
Для реализации алгоритма понадобятся:
матрица m[1..n, 1..n] - матрица смежности графа;
вспомогательный массив queue[1..n], в котором будет формироваться очередь, т.е. тип данных первый вошел – первый вышел (FIFO). Размер его достаточен, так как мы не посещаем вершины дважды. С массивом queue связаны две переменные - head и tail. В переменной head будет находиться номер текущей вершины, из которой идет волна, а при помощи переменной tail новые вершины помещаются в "хвост" очереди queue;
вспомогательный массив visited[1..n], который нужен для того, чтобы отмечать уже пройденные вершины (visited[i]=TRUE <=> вершина i пройдена);
вспомогательный массив prev[1..n] для хранения пройденных вершин. В этом массиве и будет сформирован искомый путь;
переменная f, которая примет значение TRUE, когда путь будет найден.
Кроме того, мы введем несколько вспомогательных переменных, которые понадобятся при организации циклов.

Program breadth_first_search;
Const n=9;
m:array[1..n, 1..n] of boolean =

(

(False, True, True, False, False, False, False, False, False),

(True, False, True, False, False, False, True, True, False),

(True, True, False, True, True, False, False, False, False),

(False, False, True, False, True, False, False, False, False),

(False, False, True, True, False, True, False, True, False),

(False, False, False, False, True, False, True, True, True ),

(False, True, False, False, False, True, False, True, True ),

(False, True, False, False, True, True, True, False, False),

(False, False, False, False, False, True, True, False, False)

);

Var A, B: integer;
Procedure A_to_B(A, B: integer);
Var
Visited: array[1..n] of boolean;
Prev: array[1..n] of integer;
c: array[1..n] of integer;
head, tail: integer;
f: boolean;
i, v, k: integer;
Begin
head:=1;
tail:=1;
f:=False;
For i:=1 to n do
Begin
Visited[i]:=False;
Prev[i]:=0
End;
C[tail]:=A;
Visited[A]:=True;
While (head<=tail) and not f do
Begin
v:=C[head];
head:=head+1;
For k:=1 to n do
if m[v, k] and not Visited[k] then
Begin
tail:=tail+1;
C[tail]:=k;
Visited[k]:=True;
Prev[k]:=v;
if k=B then
Begin
f:=true;
break
End
End
End;
if f then
Begin
k:=B;
Write(B);
While Prev[k]<>0 do
Begin
Write('<-', Prev[k]);
k:=Prev[k]
end
End
else
Write('Пути из ', A, ' в ', B, ' нет')
end;
Begin
Write('A= '); readln(A);
Write('B= '); readln(B);
A_to_B(A, B)
End.
  #2  
Старый 13.05.2007, 14:07
незарегистрированный

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

1 что это за язык - Паскаль или Дельфи?
2 если дельфи - пишет Runtime Error 105 at 00403C5B
у меня Delphi 2005, если что
  #3  
Старый 01.03.2008, 14:39
exescript

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

гениальный вопрос...
По-моему видно что это паскаль...мдя...
  #4  
Старый 04.03.2008, 00:53
Новичок

Отправить личное сообщение для Tesla.rus Посмотреть профиль Найти все сообщения от Tesla.rus
 
Регистрация: 26.02.2008
Сообщений: 4

Переделывается под си (не билдер)
//юзайте студию, или DEV-C++

#include <stdio.h>
#define False 0
#define True 1
const int n=9;
int A , B;
char m[n*n] =

(

(False, True, True, False, False, False, False, False, False),

(True, False, True, False, False, False, True, True, False),

(True, True, False, True, True, False, False, False, False),

(False, False, True, False, True, False, False, False, False),

(False, False, True, True, False, True, False, True, False),

(False, False, False, False, True, False, True, True, True ),

(False, True, False, False, False, True, False, True, True ),

(False, True, False, False, True, True, True, False, False),

(False, False, False, False, False, True, True, False, False)

);

void A_to_B(int A, int B);

void main()
{
printf("A= "); scanf("%d",A);
printf("B= "); scanf("%d",B);
A_to_B(A, B)
}

void A_to_B(int A, int B)
{
char Visited[n];
int Prev[n];
int c[n];
int head, tail;
char f;
int i, v, k;

head=0;
tail=0;
f=False;
for(i=0;i<n;i++)
{
Visited[i]=False;
Prev[i]=0
}

C[tail]=A;
Visited[A]=True;
while ((head<=tail) && !f)
{
v=C[head];
head++;
for(k=0;k<n;k++)
if(m[v*n+k] && ! Visited[k])
{
tail++;
C[tail]=k;
Visited[k]=True;
Prev[k]=v;
if(k==B)
{
f=true;
break;
}
}
}
if(f)
{
k=B;
printf("%d",B);
while(Prev[k]!=0)
{
printf("<-%d",Prev[k]);
k=Prev[k];
}
}
else
printf("Пути из %d в %d нет",A,B);
}
//PS могу и ошибиться в коде...
  #5  
Старый 20.05.2009, 19:03
гость

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

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


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
подскажыте алгоритм решения задачи Pioneer Задачи 15 01.07.2010 09:04
подскажыте алгоритм решения задачи Pioneer Оффтопик 8 18.07.2007 03:52
подскажите алгоритм Человекъ Математические алгоритмы 6 24.03.2007 22:24
подскажите алгоритм обхода препятствий на Vb 6.0 IgNik500 Оффтопик 0 11.12.2006 13:44
задачи с школьного полуфинала по сибири - подскажите, как решить? незарегистрированный Задачи 15 02.11.2006 16:59