Паскаль. Найти путь.

Question

Паскаль. Найти путь.

голубев саша Ученик (230), на голосовании 8 лет назад

На карте местности имеется N населенных пунктов, пронумерованных от 1 до N (N<= 10). Некоторые из пунктов соединены между собой дорогами. Информация о дорогах задается в виде последовательности пар чисел i, j (i<j), указывающих, что i-й и j-й пункты соединены дорогой, признак конца этой последовательности — пара нулей. Определить, можно ли попасть по этим дорогам из первого пункта в n-й.

Мне сказали, что нужно решать, используя алгоритм поиска в глубину, но я как то не особо его понял. Есть ли ещё какие то способы решения данной задачи?
Var Minc : Array[1..10,1..10] Of Integer;
Var Chk : Array[1..10] Of Integer;
Var flg : Boolean;
Var Path : String;
Var i,j : integer;

Function posRev(s : string; f : char) : integer;
Var i : integer;
Begin
for i:=length(s) downto 1 Do
if s[i]=f then begin
posRev:=i;
exit;
end;
posRev:=0;
End;

Procedure DFS(n : Integer; m : Integer);

Var i,k : Integer;

Begin

If flg Then Exit;

Chk[n]:= 1;

if length(Path)=0 then
Path:=inttostr(n)
else
Path := Path + ';' +inttostr(n);

For i:= 1 To 10 do

If (Minc[i, n] <> 0) And (Chk[i] = 0) Then Begin

If i = m Then Begin
flg:= True;
writeln(Path,';',m);
Exit;
End;

DFS(i,m);

k:= posRev(Path, ';');

if (k >0) then Path:= copy(Path,1,(k-1));

End

End;

Begin

For i:= 1 To 10 Do Begin
Chk[i]:= 0;
For j:= 1 To 10 Do
Minc[i, j]:= 0;
End;

Minc[1, 5]:=1;
Minc[5, 1]:=1;

Minc[2, 5]:=1;
Minc[5, 2]:=1;

Minc[3, 5]:=1;
Minc[5, 3]:=1;

Minc[6, 5]:=1;
Minc[5, 6]:=1;

Minc[6, 7]:=1;
Minc[7, 6]:=1;

Minc[4, 5]:=1;
Minc[5, 4]:=1;

Minc[9, 8]:=1;
Minc[8, 9]:=1;

Minc[8, 10]:=1;
Minc[10, 8]:=1;

flg:= False;

Path:='';

DFS(1,7);

If flg Then
writeln('Путь найден')
Else
writeln('Путь не существует');

End.

Answer 1

Pandacrash Мудрец (13356) 8 лет назад

Возможно я не понял, но здесь же деревья должны быть?

голубев сашаУченик (230) 8 лет назад

Как это реализовать не подскажете?

Metotron Искусственный Интеллект (114903) Двусвязный список? Но если у одного города может быть несколько связей (вплоть до n-1, где n - общее число городов), то придётся хранить связи как-то отдельно. В PHP/JS я бы легко сделал на динамических массивах, а в паскале уже давно не шарю.

MetotronИскусственный Интеллект (114903) 8 лет назад

Почему же деревья? Ведь города могут быть объединены в кольцо, а это уже не дерево. В дереве между двумя узнали единственный маршрут, с городами это не обязательно.

Pandacrash Мудрец (13356) Да, действительно.

Answer 2

Metotron Искусственный Интеллект (114903) 8 лет назад

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

голубев сашаУченик (230) 8 лет назад

А как рекурсивно её решить? Я не знаю. Можете сам алгоритм хотя бы рассказать?

Metotron Искусственный Интеллект (114903) Заходишь в узел, запоминаешь его, смотришь соседей, повторяешь то же самое для всех соседей поочерёдно. Если в соседях найдена конечная цель, то маршрут построен, нужно только взять список запомненных узлов. Этот список нужно передавать на следующий уровень рекурсии, чтобы знать пройденный путь.

Answer 3

Вопрос очень сильно зависит от того, как вы представляете граф.

Например, можно возвести матрицу переходов в квадрат. То есть из матрицы переходов город->город за 1 шаг построить матрицу переходов да 1 и 2 шага. Потом возвести её в квадрат ещё раз, получится матрица переходов за 1…4 шаг. Так будет сделано за log(n) действий и мы увидим перечни городов в которые мы можем попасть из каждого города.

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

Если на пальцах, то поиск в глубину - это попытки достичь определённой вершины, имея список уже посещенных вершин. В уже посещенные вершины возвращаться нельзя.
Как бы вы действовали в жизни?
Я бы написал списочек, куда пойти можно. Он может быть:
1. пуст - зашли в тупик, но так и не нашли, путь неправильный, надо вернуться (остановка ветви поиска)
2. в списке оказалась искомая вершина. Мы имеем путь к текущей, текущую и искомую - решение найдено.
3. в нем есть какие-то вершины - идём дальше. Надо добавить себя к списку посещенных вершин и с обновленным списком посещенных перебрать все вершины из доступных к переходу, повторяя алгоритм для каждой из них.

Если конкретный путь не важен, можно поступить интереснее:
Иметь вектор признаков (нет_пути | есть_путь | в_процессе), в который можно попасть из вершины 1. Изначально его заполнить исходящими из 1 с признаком в_процессе, остальные - нет_пути.
Если в этом векторе есть вершина X с признаком в_процессе, то нужно добавить в вектор все исходящие из неё вершины. Добавление обновляет признак нет_пути, заменяя его на в_процессе, признаки есть_путь и в_процессе не изменяются. После этого вершина X меняет признак с в_процессе на есть_путь. Повторять алгоритм пока в векторе либо не останется вершин в_процессе (это будет, когда в вершину n нет пути из 1), либо появится вершина n с признаком отличным от нет_пути.