Помогите пожалуйста с программкой: "Поиск кратчайшего пути в графе методом полного перебора в ширину с использованием АТД очередь" Сам алгоритм у меня есть, но ничего не знаю про АТД очередь, ни у кого нет примеров такой программы?
Толку мало, прочитал, а смысла 0. Там только процедуры описаны как записать в стек, как оттуда достать и т.д. А у меня есть конкретная задача и я не знаю как их связать. работать с очередями, стеками и деками целый семестр, поэтому хотелось бы поподробнее.
Мне дан такой алгоритм:
procedure Quepush(start); While not QueueEmpty do begin Current:=Quepop Finished:=Current=finish; j:=1; while j<=N do begin if (M[Current,j]<>0) and not visited(j,way) then begin Way[j]:=Current; Finished:=j=finish; if not Finished then QueuePush(j) else begin i:=finish; while i<>start do begin write(Way[i]:3); i:=Way[i]; end; writeln; end; inc(j); end; end; end;
Start, current, finish - начальная. текущая и конечная вершина; Finished - флаг окончания поиска; Visited - функция, проверяющая принадлежность текущей вершины построенной части пути, M - матрица смежности вершин графа.
И как совместить это я вообще не подозреваю. Если кто-то может чем-то помочь - помогите.
работать с очередями, стеками и деками целый семестр, поэтому хотелось бы поподробнее.
Что именно "поподробнее"? Ты ж сказал, что у тебя есть алгоритм, но ты не знаешь про очереди. Все, что тебе надо знать - это то, что есть операции Put и Get, все остальное - уже детали реализации (на то он и абстрактный тип данных).
Цитата
Мне дан такой алгоритм:
Не-не... Ты перепутал все на свете... Это не процедура называется Quepush... Вот так выглядит программа в простейшем случае:
function visited(what: integer; path: WayType): boolean; var i: integer; begin visited := true; for i := low(path) to high(path) do if path[i] = what then exit; visited := false; end;
var q: TQueue; i, j, start, finish, current: integer; finished: boolean; Way: WayType;
begin q.init;
start := 1; finish := 5;
q.put(start); While not q.isEmpty do begin Current := q.get; Finished := Current = finish; j:=1; while j<=N do begin if (M[Current,j] <> 0) and not visited(j, way) then begin Way[j] := Current; Finished:=(j = finish); // если не закончили перебор - добавляем очередную вершину // в очередь, чтобы потом к ней вернуться... if not Finished then q.put(j) end; inc(j); end; end;
// а когда закончили - то печатаем путь // от конечной вершины к начальной i:=finish; write(i:3);
while i<>start do begin write(Way[i]:3); i:=Way[i]; end; writeln;
end.
(я использовал собственный модуль queue_oop, в принципе можешь использовать любой другой, по названиям методов понятно, что они делают: Put - забрасывает элемент в конец очереди, Get - вытаскивает элемент из ее начала)
procedure TForm1.FormActivate(Sender: TObject); var i:integer; begin // нумерация строк for i:=1 to 10 do StringGrid1.Cells[0,i]:=IntToStr(i); // нумерация колонок for i:=1 to 10 do StringGrid1.Cells[i,0]:=IntToStr(i); // описание предопределенной карты StringGrid1.Cells[1,2]:='1'; StringGrid1.Cells[2,1]:='1'; StringGrid1.Cells[1,3]:='1'; StringGrid1.Cells[3,1]:='1'; StringGrid1.Cells[1,4]:='1'; StringGrid1.Cells[4,1]:='1'; StringGrid1.Cells[3,7]:='1'; StringGrid1.Cells[7,3]:='1'; StringGrid1.Cells[4,6]:='1'; StringGrid1.Cells[6,4]:='1'; StringGrid1.Cells[5,6]:='1'; StringGrid1.Cells[6,5]:='1'; StringGrid1.Cells[5,7]:='1'; StringGrid1.Cells[7,5]:='1'; StringGrid1.Cells[6,7]:='1'; StringGrid1.Cells[7,6]:='1'; end;
procedure TForm1.Button1Click(Sender: TObject); var M:array[1..N,1..N] of integer; q: TQueue; i, j, start, finish, current: integer; finished: boolean; Way: WayType;
function visited(what: integer; path: WayType): boolean; var i: integer; begin visited := true; for i := low(path) to high(path) do if path[i] = what then exit; visited := false; end;
procedure step; begin queueinit(q); queuepush(q,start); While not queueEmpty(q) do begin Current := queuepop(q); Finished := Current = finish; j:=1; while j<=N do begin if (M[Current,j] <> 0) and not visited(j, way) then begin Way[j] := Current; Finished:=(j = finish); if not Finished then queuepop(q) end; inc(j); end; end; i:=finish; while i<>start do begin i:=Way[i]; end; Label1.Caption:=label1.Caption+' '+IntToStr(way[i]); end;
begin Label1.caption:='';
for i:=1 to N do for j:=1 to N do if StringGrid1.Cells[i,j] <> '' then M[i,j]:=StrToInt(StringGrid1.Cells[i,j]) else M[i,j]:=0; start:=StrToInt(Edit1.text); finish:=StrToInt(Edit2.text); step;
end;
end.
и прикреплен юнит с Объектом очередь, скачан отсюда, с форума
procedure step; begin queueinit(q); queuepush(q, start); While not queueEmpty(q) do begin Current := queuepop(q); Finished := Current = finish; j := 1; while j<=N do begin if (M[Current,j] <> 0) and not visited(j, way) then begin Way[j] := Current; Finished:=(j = finish); if not Finished then queuepush(q, j) // <--- Здесь и в оригинале было q.put(j), а не q.get end; inc(j); end; end;
// Label1 заполняется вот так: Label1.Caption := IntToStr(finish); i := finish; while i <> start do begin i := Way[i]; Label1.Caption := Label1.Caption + ' ' + IntToStr(i); end; end;
procedure step; begin queueinit(q); queuepush(q,start); While not queueEmpty(q) do begin Current := queuepop(q); Finished := Current = finish; j:=1; while j<=N do begin if (M[Current,j] <> 0) and not visited(j, way) then begin Way[j] := Current; Finished:=(j = finish); if not Finished then queuepop(q) end; inc(j); end; end; end;
begin Label1.caption:='';
for i:=1 to N do for j:=1 to N do if StringGrid1.Cells[i,j] <> '' then M[i,j]:=StrToInt(StringGrid1.Cells[i,j]) else M[i,j]:=0; start:=StrToInt(Edit1.text); finish:=StrToInt(Edit2.text); step; while i<>start do begin Label1.caption:=IntToStr(way[i]); end;
end;
end.
Помогите пожалуйста доделать ... Я программирую в Delphi недавно и поэтому вопрос ламерский: как вывести массив в форме? Пытаюсь сделать уже несколько дней Со StringGrid вроде как разобрался, считается тоже все хорошо, но вывести на экран не могу.
в предыдущем посте... Что там тебе не понравилось?
Добавлено через 2 мин. P.S. И опять у тебя программа нерабочая, та же самая ошибка: queuepop вместо queuepush... Ты ответы что, не читаешь? Тогда зачем их пишут?
И опять у тебя программа нерабочая, та же самая ошибка: queuepop вместо queuepush... Ты ответы что, не читаешь? Тогда зачем их пишут?
Извини, я просто скопировал фрагмент из прошлого своего поста и забыл поменять quepop на queuepush, то, что ты написал я сделал, всё получилось ... вот с label1 что-то у меня вывод не правильно получается ...
вот с label1 что-то у меня вывод не правильно получается ...
тебе же написали, как надо:
Цитата
// Label1 заполняется вот так: Label1.Caption := IntToStr(finish); i := finish; while i <> start do begin i := Way[i]; Label1.Caption := Label1.Caption + ' ' + IntToStr(i); end;
--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует. На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
Я бы просто так не писал, у меня все написано также, но какие бы значения не забивал, у меня выводится неправильно! Вот даже программку мою могу выложить...