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

[madrabbit]

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

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

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

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

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

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

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

[Digitalator]

А нафиг тут вообще рекурсия нужна? ээ вообщето она никогда ненужна.........

Используй так называемое "динамическое програмирование" для решения этой и уймы других подобных задач. подробности спрашивай у Яндекса.

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

[volvo]

Digitalator
Еще один такой пост - накажу. Если человек пишет, что надо с рекурсией - значит надо с рекурсией. Если нечего сказать по теме - не надо просто так отмечаться.

[madrabbit]

volvo.
помоги советом

[Digitalator]

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

Лучше бы чем сами что-нибудь подсказали челу, чем других тыкать.

Если нечего сказать по теме - не надо просто так отмечаться.

Вы намекаете на флуд? Хороший совет модеру - Не надо нигде вынюхивать флуд, он всегда сразу виден. Если флуда не видно с первого взгляда, значит его нет. К чему это? К тому что не стоит сканировать каждый пост, и везде подозревать флудеров. Хороший модер - это тот, который незаметен, но без него плохо. Ваша красная надпись очень незаметна.

ЗЫ: Это все вынужденный offtop

[madrabbit]

спасибо вам ребята...

[Digitalator]

Эй, чувак, не расстраивайся!

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

Рекурсией решать подобные задачи не советую. :no:

[APAL]

Рекурсией решать подобные задачи не советую

но можно...

Если на пальцах:

1. Для начальной позиции ищем все возможности хода.
2. Для каждой такой возможности рекурсивно вызываем ту же процедуру поиска возможностей хода.

Замечания:
ИМХО: место куда надо попасть лучше отметить, например "2"
Ставить единицы туда куда походили и не затирая старые единица. Это чтобы наша процедура поиска вариантов хода "не ходила" на одну клетку дважды.
Теперь только организовать запись найденных вариантов и произвести поиск никратчашего/-их.

[Digitalator]

имхо с рекурсией все усложняеться и больше места для ошибок

[madrabbit]

но можно...

Если на пальцах:

1. Для начальной позиции ищем все возможности хода.
2. Для каждой такой возможности рекурсивно вызываем ту же процедуру поиска возможностей хода.

Замечания:
ИМХО: место куда надо попасть лучше отметить, например "2"
Ставить единицы туда куда походили и не затирая старые единица. Это чтобы наша процедура поиска вариантов хода "не ходила" на одну клетку дважды.
Теперь только организовать запись найденных вариантов и произвести поиск никратчашего/-их.

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

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

[APAL]

проблема в том, каким конкретно способом обрывать процедуру(каким оператором)

Обрывать принудительно не надо - закончить процедуру если мы попали на 2-ку или некуда ходить (т.е. все возможные варианты хода уже имеют "1").

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

Вот здесь надо подумать как реализовать хранение результатов....
Например запись в файл/файлы или в динамическую память (это быстрее), а потом только сделать поиск... а можно уже при работе искать короткий путь, т.е. увеличивать счетчик для следующей итерации - если достигнут финал (2), то проверяем предидущий результат и если он хуже - запоминаем текущий.

[APAL]

Для начала было бы неплохо ввести еще одно значение матрицы - 3, т.е. то поле куда конь уже ходил, чтобы не рассматривать повторы.
Вложенная процедура обрывается командой EXIT;

[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: Задачи на графы