рекурсивная работа с матрицей, задачка с шахматным конем Опции

[madrabbit]

Здравствуйте.
Помогите пожалуйста с алгоритмом. хотя бы просто на пальцах или отправьте к соответствующим ссылкам.
Интересует следующий алгоритм:

Предположим задана некоторая матрица размерности N на N( положим поле больше шахматной доски), а также
координаты двух точек(элементы массива a[i,j], b[i1,j1]),

Задача. Найти оптимальный путь межды этими точками "шахматным конем".

Решал так:
забил всю матрицу нулями, два элемента - "1".
функция проверки "не является ли элемент массива =1. Если нет, то в функцию передаются новые координаты(причем 8 различных точек, куда может шагнуть конь с текущего места). таким образом это приводит к многократному зацикливанию и росту рекурсивных вложений...

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

спасибо вам заранее за помощь! :molitva:

Сообщение отредактировано: madrabbit - 18.12.2004 21:53

[madrabbit]

ВОПРОС! не пойму почему не получается. 8(
вроде правильно написано.
но судя по результатам все действия просиходят на одной и той же матрице.
Хотя по идее для каждой ветки рекурсии ДОЛЖНА определяться своя матрица!
(не знаю, понятно ли объяснил)

ну и пока я не дописал хранение промежуточных результатов.

Проблема в том(как я уже писал), чтобы для каждого нового дерева бралась чистая матрица!
Подскажите, в чем ошибка...

[volvo]

Хотя по идее для каждой ветки рекурсии ДОЛЖНА определяться своя матрица!

Тогда попробуй генерировать динамическую матрицу при каждом входе в рекурсию... Но вот хватит ли памяти...

[madrabbit]

Тогда попробуй генерировать динамическую матрицу при каждом входе в рекурсию... Но вот хватит ли памяти...

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

[volvo]

так я  так и делаю, каждый раз в рекурсию передается матрица, которая,
как я понимаю, должна "копироваться по значению".

Ну так вот что я нашел:

Код

procedure recurse(var m:mass;i,j:integer);

Это передача "по значению"? Тогда как передать "по ссылке"? Нет, madrabbit, тут как раз и происходит передача матрицы по ссылке, т.е. ВСЕ вызовы процедуры Recurse работают с одной и той же копией матрицы...

Сразу хочу предупредить, что при попытке передать матрицу размером 100х100 по значению, переполнение стека наступит очень быстро... Единственное, что можно попробовать -

генерировать динамическую матрицу при каждом входе в рекурсию...

, то есть не в стеке, а в динамической памяти...

Удачи...

[madrabbit]

Ну так вот что я нашел:

Код

procedure recurse(var m:mass;i,j:integer);

Это передача "по значению"? Тогда как передать "по ссылке"? Нет, madrabbit, тут как раз и происходит передача матрицы по ссылке, т.е. ВСЕ вызовы процедуры Recurse работают с одной и той же копией матрицы...

Сразу хочу предупредить, что при попытке передать матрицу размером 100х100 по значению, переполнение стека наступит очень быстро... Единственное, что можно попробовать - , то есть не в стеке, а в динамической памяти...

Удачи...

спасибо.
я приблизительно это и имел ввиду.
А именно: "Как передавать матрицу по значению???"
а переполнения не должно быть, так как сразу после нахождения первого удачного варианта, все более длинные ветки будут рубиться, а каждый более коротнкий путь
будет браться за образец, пока мы не найдем самый оптимальный...
Вопрос, как именно передавать матрицу или формировать новую...

[volvo]

"Как передавать матрицу по значению???"

Код

Type matrix = array[1 .. 100] of integer;
var mx: matrix;

procedure p1(var x: matrix);
 begin end;
procedure p2(x: matrix);
 begin end;

begin
 p1(mx); { по ссылке }
 p2(mx); { по значению }
end.

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

Вся проблема в том, что стек (по умолчанию) ограничен 16К, а передача матрицы целых размером 100х100 = 20000 байт ... и что будет?

[madrabbit]

Огромное спасибо, ну наконец-то я понял!
Теперь все работает.
Теперь новые вопросы :
не могу найти, вроде видел тут про динамические массивы и работу с ними(хочу результаты хранить промежуточные)
и графы(в принципе не понимаю, что это такое) сказали, что при их помощи задачу легче решать...

Код

program ChessHorse;
uses crt;
label 1;
type
mass=array[1..15,1..15] of integer;
line=array[1..100] of integer;


var i,j,n,k:integer;

  matrix:mass;

  procedure Readlines(var men:mass; n:integer);
  var i,j:integer;
  begin
  for i:=1 to n do
   for j:=1 to n do
     men[i,j]:=0;
     end;



     procedure Writelines(m:mass; n:integer);
     var i,j:integer;
     begin
     for i:=1 to (n+1) do
      begin
        for j:=1 to (n+1) do
                             if (i=1) and (j=1) then write('   ') else
                             if j=1 then write((i-1):2,'*') else
                             if i=1 then write((j-1):2) else
           write(m[i-1,j-1]:2);
             writeln
               end
               end;

               procedure recurse(mo:mass;i,j,turn:integer);

               begin

               if (mo[i, j] = 3) or (i>N) or (j>N) or (i<1) or (j<1) or (turn>=k) then exit
               else
               if mo[i,j]=2 then begin
                                writeln('gotcha');
                                writelines(mo,n);
                                k:=turn;
                                readln;
                                exit
                                end;

                 begin
                   if mo[i,j]<>1 then mo[i, j] := 3;
                   recurse(mo, i+2, j+1,turn+1);
                   recurse(mo, i+2, j-1,turn+1);
                   recurse(mo, i+1, j+2,turn+1);
                   recurse(mo, i+1, j-2,turn+1);
                   recurse(mo, i-2, j+1,turn+1);
                   recurse(mo, i-2, j-1,turn+1);
                   recurse(mo, i-1, j+2,turn+1);
                   recurse(mo, i-1, j-2,turn+1);
                  end;
                       end;



                                                procedure readpoint(var m:mass;point:integer);
                                                var i,j,a:integer;
                                                begin
                                                writeln('input entry point ', point,', use "xx" format:');
                                                readln(a);
                                                i:=a div 10;
                                                j:=a mod 10;
                                                m[i,j]:=point;
                                                if point=1 then begin
                                                                clrscr;
                                                                                recurse(matrix,i,j,0)
                                                                                                end
                                                                                                end;

                                   BEGIN
                                   1: clrscr;
                                   writeln('please input n<=15');
                                   readln(n);
                                   k:=n;
                                   if (n>0) and (n<=15) then
                                   readlines(matrix,n)
                                   else goto 1;
                                   writelines(matrix,n);
                                   readpoint(matrix,2);
                                   readpoint(matrix,1);
                                   writeln('Done!');
                                   readln
                                   END
                                   .

Спасибо всем за помощь!
особенно Volvo. Теперь задачу можно с решением вместе смело постить в олимпиадные.

[volvo]

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

Посмотри вот это...
FAQ: Динамические массивы
FAQ: Задачи на графы