компьютерный форум
Вернуться   Компьютерный форум > Программирование и вебстроительство > Программирование

Ответ
 
LinkBack Опции темы Опции просмотра
Старый 06.03.2006, 09:02   #1
Пользователи
 
Регистрация: 06.03.2006
Сообщений: 8
По умолчанию

Народ помогите с поиском пути по графу.
Надо найти альтернативный путь, если начальная и конечная точка совпадают...??? :help:




Cawboy вне форума  
Digg this Post!Bookmark Post in Technorati
Ответить с цитированием
06.03.2006, 09:02
Техник
реклама
По умолчанию

Старый 06.03.2006, 09:48   #2
Пользователи
 
Регистрация: 07.12.2004
Сообщений: 783
Post

Цитата:
[b]если начальная и конечная точка совпадают...???
Если они совпадают, то никакого пути не существует

Если я что-то не так понял - сформулируй вопрос понятнее
Andy вне форума  
Digg this Post!Bookmark Post in Technorati
Ответить с цитированием
Старый 06.03.2006, 10:07   #3
Пользователи
 
Регистрация: 06.03.2006
Сообщений: 8
По умолчанию

У меня есть граф (карта киева), представленная матрицей инциндентности...

Например на розвязке типа "четырёх листный клевер" мне надо развернуться, посути ищется цикл, правильно, я думаю использовать алгоритм Дейкстры или поиск в глубину/ширину. Но в том и том алгоритме у нас есть массив точек которые посещены, если их не делать мы можен никада не выйти с цикла. Так вот, как реализовать поиск пути что бы оно мне нашло путь с точки в точку если они совпадают.....??????? :blink:
Cawboy вне форума  
Digg this Post!Bookmark Post in Technorati
Ответить с цитированием
Старый 06.03.2006, 10:35   #4
Пользователи
 
Регистрация: 07.12.2004
Сообщений: 783
По умолчанию

Цитата:
[b] Но в том и том алгоритме у нас есть массив точек которые посещены, если их не делать мы можен никада не выйти с цикла.
Само собой, надо запоминать посещеннные вершины.....
Если, конечно, случай тривиальный (то есть, в цикле все вершины инцедентны друг-другу), то ничего запоминать не надо..... Но я думаю, что с картой Киева это не пройдет
Воспользуйся поиском в ширину.
Если ты пришел в посещенную вершину - значит есть цикл... => можно добраться до первой вершины....
Andy вне форума  
Digg this Post!Bookmark Post in Technorati
Ответить с цитированием
Старый 06.05.2006, 17:37   #5
Пользователи
 
Регистрация: 06.05.2006
Сообщений: 3
По умолчанию

2 года назад я писала по математике прогу с поиском пропускной способности графа. Так вот, прежде чем его вычислять, прога находила все возможные пути между заданными точками. Я пересылаю весь модуль, т к щас плохо помню, а разбираться некогда. Но он с комментариями, так что разобраться можно!

unit road_;

interface

uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls, Grids, Menus;

type
TForm1 = class(TForm)
GroupBox1: TGroupBox;
StringGrid1: TStringGrid;
Label4: TLabel;
Label3: TLabel;
Edit2: TEdit;
Button1: TButton;
Label8: TLabel;
Label1: TLabel;
GroupBox2: TGroupBox;
Memo1: TMemo;
StringGrid2: TStringGrid;
MainMenu1: TMainMenu;
N1: TMenuItem;
N2: TMenuItem;
N3: TMenuItem;
N4: TMenuItem;
N5: TMenuItem;
N6: TMenuItem;
N7: TMenuItem;
N8: TMenuItem;
procedure Edit2KeyPress(Sender: TObject; var Key: Char);
procedure Button1Click(Sender: TObject);
procedure N2Click(Sender: TObject);
procedure N5Click(Sender: TObject);
procedure N7Click(Sender: TObject);
procedure StringGrid1KeyPress(Sender: TObject; var Key: Char);
procedure N6Click(Sender: TObject);
procedure GroupBox2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;
n:integer;

implementation

uses Unit2;

{$R *.DFM}

procedure TForm1.Edit2KeyPress(Sender: TObject; var Key: Char);
var
i:integer;
begin
case Key of
'0'..'9', #8:;
#13:begin
n:=strtoint(edit2.Text);
stringgrid1.ColCount:=n+1;
stringgrid1.RowCount:=n+1;
stringgrid2.ColCount:=n+1;
stringgrid2.RowCount:=n+1;
button1.Enabled:=true;
// нумерация строк и столбцов
for i:=1 to n do
begin
StringGrid1.Cells[0,i]:=IntToStr(i);
StringGrid1.Cells[i,0]:=IntToStr(i);
StringGrid2.Cells[0,i]:=IntToStr(i);
StringGrid2.Cells[i,0]:=IntToStr(i);
end;
// описание предопределенной карты
StringGrid1.Cells[1,2]:='5';
StringGrid1.Cells[2,1]:='3';
StringGrid1.Cells[1,3]:='6';
StringGrid1.Cells[3,1]:='6';
StringGrid1.Cells[1,4]:='7';
StringGrid1.Cells[4,1]:='2';
StringGrid1.Cells[2,5]:='1';
StringGrid1.Cells[5,2]:='1';
StringGrid1.Cells[3,4]:='9';
StringGrid1.Cells[4,3]:='3';
StringGrid1.Cells[3,6]:='1';
StringGrid1.Cells[6,3]:='4';
StringGrid1.Cells[4,5]:='2';
StringGrid1.Cells[5,4]:='4';
StringGrid1.Cells[6,5]:='5';
StringGrid1.Cells[5,6]:='8';
end;
else key:=chr(0);
end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
map,put,x0:array[1..100,1..100]of LONGint; {Карта. map[i,j не 0, если точки i и j соединены }
road,odn:array[1..100]of integer; { Дорога - номера точек карты }
incl:array[1..100]of boolean; { incl[i] равен TRUE, если точка с номером i включена в road }
start,finish:integer; { Начальная и конечная точки }
found,per,wwod:boolean;
i,j,w,kp,max,max1,max2,k,st,min:integer;
str:string;
procedure step(s,f,p:integer);
var c,i:integer;{с - Номер точки,в которую делаем очередной шаг }
begin
if s=f
then begin
{ Точки s и f совпали !}
found:=TRUE;
str:='';
str:='Путь: ';
for i:=1 to p-1 do
begin
odn[w]:=road[i];
w:=w+1;
str:=str+IntToStr(road[i]);
end;
Memo1.Lines.Add(str);
end
else begin
{ выберем очередную точку }
for c:=1 to N do
begin { проверяем все вершины }
if(map[s,c] 0)and(NOT incl[c])and(c>s)
{ точка соединена с текущей и не включена в маршрут}
then begin
road[p]:=c;{ добавим вершину в путь }
incl[c]:=TRUE;{ пометим вершину как включенную }
step(c,f,p+1);
incl[c]:=FALSE;
road[p]:=0;
end;
end;
end;
end;{ конец процедуры step }

begin
Memo1.Lines.Clear;
{ инициализация массивов }
for i:=1 to N do road[i]:=0;
for i:=1 to N do incl[i]:=FALSE;
w:=1;
{ ввод описания карты из SrtingGrid.Cells}
for i:=1 to N do
for j:=1 to N do
if StringGrid1.Cells[i,j] ''
then map[i,j]:=StrToInt(StringGrid1.Cells[j,i])
else map[i,j]:=0;
start:=1;
finish:=StrToInt(Edit2.text);
road[1]:=start;{ внесем точку в маршрут }
incl[start]:=TRUE;{ пометим ее как включенную }
step(start,finish,2);{ищем вторую точку маршрута }
// проверим, найден ли хотя бы один путь
if not found
then Memo1.Lines.Add('Указанные точки не соединены!');
//kp - k-wo putej
kp:=0;
for i:=1 to w-1 do
if odn[i]=1
then kp:=kp+1;
//max - k-wo stolbzow
max:=0;
max1:=1;
max2:=0;
for i:=2 to w-1 do
if odn[i]1
then max1:=max1+1
else begin
if max2>max1
then max:=max2
else max:=max1;
max2:=max1;
max1:=1;
end;
//form-e dwumernogo massiwa
for i:=1 to kp do
for j:=2 to max do
put[i,j]:=0;
for i:=1 to kp do
put[i,1]:=1;
//
k:=1;
for i:=1 to kp do
begin
j:=2;
k:=k+1;
while (odn[k]1)and(k
АКИРА вне форума  
Digg this Post!Bookmark Post in Technorati
Ответить с цитированием
Ответ


Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Вкл.



Текущее время: 10:48. Часовой пояс GMT.


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd. Перевод: zCarot
Content Relevant URLs by vBSEO 3.5.0 RC2