Пятница, 24.01.2025
Pascal 4 All
[ · Новые сообщения · Участники · Правила форума · Поиск · RSS ]

 

  • Страница 1 из 1
  • 1
Модератор форума: Seqular, Pavel  

Задачка на тему Графы....
M@DДата: Вторник, 25.11.2008, 03:17 | Сообщение # 1
Знакомый
Группа: Пользователи
Сообщений: 16
Репутация: 0
Замечания: 0%
Статус: Offline
Задан граф, имеются 2 вершины : исходная и конечная...Необходимо найти наибольшую пропускную способность графа....
P.S.как я понял кол-во вершин задается юзером, ребра м/у вершинами являются пропускной способностью...Например [а,б]=с;
где а,б-вершины, с-пропускная способность м/у ними....

Вот мой вариант, только тут есть маленький партак.....Он выводит общее кол-во путей...А необходимо наибольший поток данных...

uses wincrt;
var
map:array [1..30,1..30] of integer;{Карта: map[i,j] не 0, если точки i и j соединены}
road:array [1..30] of integer;{маршрут-номера точек карты}
road1:array [1..30] of integer;
incl:array [1..30] of boolean;{incl[i]=true, если точка с номером i включена в road}
len:integer; {Длина последнего найденного маршрута}
c_len:integer; {длина текущего маршрута}
start,finish:integer;{Начальная и конечная точки}
i,j:integer;
n:integer; {Кол-во вершин в графе}
potok:integer; {Пропускная способность}
w,z,max:integer;
procedure init;
begin
writeln('Введите кол-во вершин в графе-> ');
readln(n);
for i:=1 to N do road[i]:=0;
for i:=1 to N do incl[i]:=false;
for i:=1 to n do
for j:=1 to n do map [i,j]:=0;
end;

procedure creat;
begin
w:=0;
while w<>2 do
begin
writeln('1-добавление связи м/у 2-мя вершинами');
writeln('2-выход');
readln(w);
case w of
1:begin
write('Введите ч/з пробел номера вершин-> ');
readln(i,j);
writeln('Введите пропускную способность м/у ними-> ');
readln(potok);
map[i,j]:=potok;
end;
end;
end;
end;

procedure step(s,f,p:integer);
var c:integer; {номер точки в которую делаем очередной шаг}
begin
if s=f then
begin
len:=c_len; {сохраняем длинну найденного маршрута}
write('путь: ');
for i:=1 to p-1 do write(road[i],' ');
writeln (' Пропускная способность: ',len);
end
else
{выбираем очередную точку}
for c:=1 to n do {проверяем все вершины}
if (map[s,c]<>0) and (not incl[c]) {and ((len=0) or (c_len+map[s,c]>len)) }
{точка соединена с текущей и не включена в маршрут}
then
begin
road[p]:=c; {добавим вершину в путь}
incl[c]:=true; {пометим вершину, как включенную}
if c_len=0 then c_len:=map[s,c];
if c_len>map[s,c] then
c_len:=map[s,c];

step(c,f,p+1);
incl[c]:=false;
road[p]:=0;
c_len:=0;
end;
end;

{procedure maximum;
begin
for i:=1 to n do
begin
writeln('Максимальный поток данных проходит ч/з ');
writeln('Путь ',road[i+1]);
writeln('Пропускная способность ',max);
end;
end;}

procedure run_map;
begin
init;
creat;
write ('Введите через пробел номера начальной и конечной точек -> ');
readln (start,finish);
road [1]:=start; {Внесем точку в маршрут}
incl [start]:=true;{пометим ее как включенную}
len:=0;
c_len:=0;
step (start,finish,2); {ищем вторую точку}
{maximum;}
writeln ('Для завершения нажмите <Enter>');
readln;
end;

begin
run_map;
end.

помогите додеоать ее.....


ПросТИте За коРявЫй ПочЕрКК...
 
AlexanderДата: Вторник, 25.11.2008, 03:40 | Сообщение # 2
Всевышний
Группа: Модераторы
Сообщений: 475
Репутация: 16
Замечания: 0%
Статус: Offline
Алгоритм Форда в чистом виде, был такой на лекции? Там нужно находить произвольный путь, вычитать пропускную способность минимального ребра из этого пути, а промежуточный результат увеличить на это число и искать другой путь и т.д. пока граф не "распадётся".

Скажем дружно- нафиг нужно!
 
M@DДата: Вторник, 25.11.2008, 03:53 | Сообщение # 3
Знакомый
Группа: Пользователи
Сообщений: 16
Репутация: 0
Замечания: 0%
Статус: Offline
на лекции не было.....Взял из книжки..Там пример нахождения мин.дороги....(процедура step)
Путь не произвольный....Он задается юзером(кол-вом вершин)....я вот тут и завис .....на данном этапе выводит все возможные пути и их пропускную способность......макс путь чет ненаю...


ПросТИте За коРявЫй ПочЕрКК...
 
AlexanderДата: Вторник, 25.11.2008, 04:28 | Сообщение # 4
Всевышний
Группа: Модераторы
Сообщений: 475
Репутация: 16
Замечания: 0%
Статус: Offline
не-не-не.... не так тут.
пусть на входе имеем такой граф:
Х 7 8 0
7 Х 3 1
8 3 Х 2
0 1 2 Х
Графически это выглядит так:

найдём пропускную способность из 1 в 3.
Случайным образом выбираем маршрут, например 1-2-3, 2-3 имеет минимальную пропускную способность, мы её запоминаем и вычитаем из всех веток маршрута, получаем такой граф:

Снова выбираем случайный маршрут, например 1-3, его пропускная способность 8, вычитаем её из всего маршрута и прибавляем к общей(до этого момента там была тройка). Теперь граф такой:

Опять ищем путь. Находим 1-2-4-3, минимальная пропускная способность равна единице 2-4. Добавляем единицу к общей пропускной способности, она уже равна 3+8+1=12 и вычитаем из всех веток маршрута. Граф теперь такой:

Больше путей нет, поэтому 12- это окончательный ответ.
Прикрепления: 5426675.png (9.9 Kb) · 2461594.png (7.7 Kb) · 6702554.png (5.5 Kb)


Скажем дружно- нафиг нужно!

Сообщение отредактировал Alexander - Вторник, 25.11.2008, 04:35
 
M@DДата: Среда, 26.11.2008, 01:20 | Сообщение # 5
Знакомый
Группа: Пользователи
Сообщений: 16
Репутация: 0
Замечания: 0%
Статус: Offline
wacko
Не, не..Я вот как говорил так оно и есть.....Сеня с преподом говорил....
Тот код,который я выше выложил полностью рабочий...
Мне его как говорится удтвердили.......Только есть одно но,надо условие добавить чтобы он не все возможные пути выдавал, а один с максимальной пропускной способностью....
Quote
Случайным образом выбираем маршрут

маршрут задает юзер.........
И еще пропускные способности не складываются!!!На всем маршруте находится мин пропускная способность....она и будет пропускной способностью всего заданного маршрута.....

Добавлено (25.11.2008, 18:20)
---------------------------------------------
де тута файл моно прикрепить??Невижу....


ПросТИте За коРявЫй ПочЕрКК...

Сообщение отредактировал M@D - Среда, 26.11.2008, 01:11
 
AlexanderДата: Среда, 26.11.2008, 01:34 | Сообщение # 6
Всевышний
Группа: Модераторы
Сообщений: 475
Репутация: 16
Замечания: 0%
Статус: Offline
http://ru.wikipedia.org/wiki/Алгоритм_Форда_—_Фалкерсона
http://rain.ifmo.ru/cat....on-2008


Скажем дружно- нафиг нужно!
 
M@DДата: Среда, 26.11.2008, 01:47 | Сообщение # 7
Знакомый
Группа: Пользователи
Сообщений: 16
Репутация: 0
Замечания: 0%
Статус: Offline
Quote
http://ru.wikipedia.org/wiki/Алгоритм_Форда_—_Фалкерсона
http://rain.ifmo.ru/cat....on-2008

Чет не один линк не работает...


ПросТИте За коРявЫй ПочЕрКК...
 
AlexanderДата: Среда, 26.11.2008, 01:51 | Сообщение # 8
Всевышний
Группа: Модераторы
Сообщений: 475
Репутация: 16
Замечания: 0%
Статус: Offline
Проверил. Оба работают, только второй грузится долго, там визуализация алгоритма.

Скажем дружно- нафиг нужно!
 
M@DДата: Среда, 26.11.2008, 01:55 | Сообщение # 9
Знакомый
Группа: Пользователи
Сообщений: 16
Репутация: 0
Замечания: 0%
Статус: Offline
Во вторйо прогрузил,а который из википедии говорит что Запрашиваемое название страницы неправильно

ПросТИте За коРявЫй ПочЕрКК...
 
AlexanderДата: Среда, 26.11.2008, 02:04 | Сообщение # 10
Всевышний
Группа: Модераторы
Сообщений: 475
Репутация: 16
Замечания: 0%
Статус: Offline
хм. Я тыкаю по ссылке и оказываюсь на нужной странице. Попробуй по этому сообщению тыкнуть.

Скажем дружно- нафиг нужно!

Сообщение отредактировал Alexander - Среда, 26.11.2008, 02:05
 
M@DДата: Среда, 26.11.2008, 02:16 | Сообщение # 11
Знакомый
Группа: Пользователи
Сообщений: 16
Репутация: 0
Замечания: 0%
Статус: Offline
Я не понимаю че там написано..В коде форда

Добавлено (25.11.2008, 19:15)
---------------------------------------------
|f| := |f| + h[T];
->>>>что ето??

Добавлено (25.11.2008, 19:16)
---------------------------------------------

Quote (Alexander)
хм. Я тыкаю по ссылке и оказываюсь на нужной странице. Попробуй по этому сообщению тыкнуть.

Недопустимое название
Запрашиваемое название страницы неправильно.

Возможные причины:

в названии используются недопустимые символы;
название пусто;
некорректно указан префикс на межъязыковое или интервики название;


ПросТИте За коРявЫй ПочЕрКК...
 
AlexanderДата: Среда, 26.11.2008, 03:15 | Сообщение # 12
Всевышний
Группа: Модераторы
Сообщений: 475
Репутация: 16
Замечания: 0%
Статус: Offline
Quote (M@D)
Недопустимое название
Запрашиваемое название страницы неправильно.

Возможные причины:

в названии используются недопустимые символы;
название пусто;
некорректно указан префикс на межъязыковое или интервики название;


Значит у тебя браузер кириллицу в адресах не поддерживает, учись сам пользоваться поиском.
Quote (M@D)
|f| := |f| + h[T];
->>>>что ето??

это шаг алгоритма, все обозначения там описаны.


Скажем дружно- нафиг нужно!
 
M@DДата: Понедельник, 08.12.2008, 02:56 | Сообщение # 13
Знакомый
Группа: Пользователи
Сообщений: 16
Репутация: 0
Замечания: 0%
Статус: Offline
Quote (Alexander)
это шаг алгоритма, все обозначения там описаны.

я ненаю етот язык..

Добавлено (07.12.2008, 19:56)
---------------------------------------------

Code

uses wincrt;

procedure scan_graf;  {ПРоцедура проверки правельности введенного графа}
var p,g,q:integer;
     a,s,d:boolean;
begin

      q:=0;
      for i:=1 to n do
      begin
           p:=0;
           for j:=1 to n do

           if map[i,j]<>0 then inc(p);
           if p=0 then inc(q);
      end;
      if q=1 then
         begin
         q:=0;
         for i:=1 to n do
             begin
                  p:=0;
                  for j:=1 to n do

                  if map[i,j]<>0 then inc(p);
                  if p=0 then inc(q);
             end;
         end;
      if q=1 then {begin writeln('Является');}a:=true {end }
      else a:=false;
      if a<>true then begin writeln('Ошибка при вводе данный. Программа завершает работу!');
      HAlt;
      end;
end;

procedure step(s,f,p:integer);{нахождение максимальной пропускной способности}
var c:integer;                          {номер точки в которую делаем очередной шаг}
begin

if s=f then
            begin

            len:=c_len;          {сохраняем длинну найденного маршрута}
            if max<len then max:=len;

            for i:=1 to p-1 do begin  k:=0;
                    if max=len then begin
                    inc(k);
                    road1[i]:=road[i];
                    inc(schet);
                    end;
                    end;
           { writeln (' Пропускная способность: ',len);}
            c_len:=0;
            end
        else
{выбираем очередную точку}
        for c:=1 to n do         {проверяем все вершины}
        if (map[s,c]<>0) and (not incl[c])
        {точка соединена с текущей и не включена в маршрут}
        then
            begin
            road[p]:=c;          {добавим вершину в путь}
            incl[c]:=true;       {пометим вершину, как включенную}

            if c_len=0 then c_len:=map[s,c];
            if c_len>map[s,c] then
            c_len:=map[s,c];

            step(c,f,p+1);
            incl[c]:=false;
            road[p]:=0;

            end;
end;

Вот ....Я ее все таки осилил))
Осталось тока все в файл записать..И вкршины ьрать из файла..
Редактирование предусмотреть!!


ПросТИте За коРявЫй ПочЕрКК...
 
  • Страница 1 из 1
  • 1
Поиск:

Copyright MyCorp © 2025
Используются технологии uCoz
javascript:;" rel="nofollow" onclick="loginPopupForm(); return false;