Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Нахождение пути по карте

Автор: Alexandr87 7.1.2005, 20:18

вощем есть задача, дана карта. Матрица m*n. Заполенная цифрам от 0 до 9. Есть стартовый и конечный пункт движения. Для простоты будет считать стартовым левый верхний угол матрицы. А конечный пункт правый нижний.
Нужно попасть из начального пункта движения в конечный пункт движения. Продвигать можно по вертикали и горизонтали. Нужно найти такой маршрут, при прохождении по которому сумма цифр в клетках по которым лежит маршрут была минимальной.

Вот я тут написал, но она глючит. Скорее всего происходит переполнение стека.

Код


{Algoritm obhoda karti}
program kart;
uses crt;
const maxit=20;
var
mas:array[1..10,1..10] of byte;
masb:array[0..11,0..11] of byte;
mascor:array[1..100,1..2] of byte;
kolcor:integer;
prio:array[1..4] of byte; {1-UP, 2-DOWN, 3-RIGHT, 4-LEFT}
it:byte;

n,m:byte;
x,y:byte;
f:text;
sum,oldsum:integer;

procedure cout(code:integer);
var x,y:byte;
begin
writeln;
writeln;
if code=0 then
   for x:=0 to n+1 do
   begin
        for y:=0 to m+1 do
            write(masb[x,y]:2);
        writeln;
   end;
if code=1 then
   for x:=1 to n do
   begin
        for y:=1 to m do
            write(mas[x,y]:2);
        writeln;
   end;
end;

procedure gomap(c1,c2,prior:byte);
var nc1,nc2:byte;
begin
{where go}
if (it<=maxit) then

begin
it:=it+1;
nc1:=c1;
nc2:=c2;
if prior=1 then {UP}
   nc1:=c1-1;
if prior=2 then {DOWN}
   nc1:=c1+1;
if prior=3 then {RIGHT}
   nc2:=c2-1;
if prior=4 then {LEFT}
   nc2:=c2+1;
{map set}
{mapb[nc1,nc2]=3;}

if ((masb[nc1,nc2]<>0)and(masb[nc1,nc2]<>3)) then {main cond}
begin
     if (masb[nc1,nc2]<>4) then
     begin
          masb[nc1,nc2]:=3;
          gomap(nc1,nc2,prio[1]);
          gomap(nc1,nc2,prio[2]);
          gomap(nc1,nc2,prio[3]);
          gomap(nc1,nc2,prio[4]);
     end
     else   {if end go point}
     begin
          sum:=0;
          for x:=1 to n do
              for y:=1 to m do
                  if masb[x,y]=3 then
                     sum:=sum+mas[x,y];
          if sum>oldsum then
          begin
               kolcor:=1;
               oldsum:=sum;
               for x:=1 to n do
                   for y:=1 to m do
                       if masb[x,y]=3 then
                       begin
                            mascor[kolcor,1]:=x;
                            mascor[kolcor,2]:=y;
                            kolcor:=kolcor+1;
                       end;
         { writeln(sum);}
          end;
     end;

end;

masb[nc1,nc2]:=1;
end;
it:=it-1;
end;


begin
clrscr;
{draw karta}
assign(f,'kart.in');
reset(f);
readln(f,n,m);
for x:=1 to n do
begin
     for y:=1 to m do
     begin
         read(f,mas[x,y]);
         masb[x,y]:=1;
     end;
     readln(f);
end;
close(f);
{writeln('asd');}
for x:=0 to m+1 do
begin
     masb[0,x]:=0;
     masb[n+1,x]:=0;
end;
for x:=0 to n+1 do
begin
     masb[x,0]:=0;
     masb[x,m+1]:=0;
end;
masb[1,1]:=3;
masb[n,m]:=4;
for x:=1 to 4 do  {set prioritets of move}
    prio[x]:=x;
oldsum:=0;
it:=0;
gomap(1,1,prio[1]);
gomap(1,1,prio[2]);
gomap(1,1,prio[3]);
gomap(1,1,prio[4]);
cout(0);
cout(1);
writeln(sum);

readln;
end.

Автор: podval 8.1.2005, 10:18

Цитата(Alexandr87 @ 7.1.2005, 20:18)

Вот я тут написал, но она глючит. Скорее всего происходит переполнение стека.

Если дело не в алгоритме, то может это в раздел Дельфи?

Автор: Alexandr87 8.1.2005, 11:05

Он уже лижит в паскале, с темой "ошибка". Но там люди говорят, что мол алгоритм кривой (может быть и такое так как писал в спешке.)
Так вот, нужно чтоб ктондь посотрел на это, разобрался и сказал, что не так (если таковое имеется). Или может есть какие еще мысли

Автор: maxim1000 8.1.2005, 14:20

если вопрос по алгоритму, то его лучше описать словами, а то код читать очень неудобно, да и большое количество людей, программирующих, например, на C и не знающих Pascal, отсекается

Автор: Alexandr87 8.1.2005, 15:02

Ну лано тады вощем:
Задание
Написать программу, которая по заданной карте определить наиболее удобный маршрут из пункта А в пункт Б.
Карта представляет собой двумерный массив с элементами целочисленного типа. Каждый элемент массива содержит цифру в десятичной СС (от 0 до 9). Наиболее удобным считается маршрут, при прохождении которого сумма цифр, содержащихся в элементах, находящихся на маршруте будет минимальной.
Входные данные:
координаты начальной точки движения и конечной точки движения
размерность карты
ну и собественно сама карта.

Мой алгоритм решения
Существует две матрицы, одна исходная с числами, другая рабочая размер рабочей матрицы размер исходной +2 столба и 2строки. Для границ. Границы заполняются нулями. Все остальные числа рабочей матрицы заполняются 1(код свободности участка). Начальный пункт движения обозначается 3, конечный пункт движения 4.
Вощем сделал я функцию с тремя параметрами (старая координата х, страрая координата у, направления движения)
функция выполняет следующее:
1.первоначально из входных параметров определяется текущее местоположение.
2.Затем идет условие проверки, если в рабочей матрице на текущей позиции не стоит 3 или 0, т.е. это не граница и мы уже там не были то переходим к следующему пункту, иначе переходим к шагу 5
4.Если это не конечный пункт движения то вызываем эту же функцию 4 раза со следующими параметрами (первые два параметра - текущее местоположение), третий параметр - направление (поэтому и 4 раза). Если все же конечный, то подсчитвыем сумму всех элементов по которым прошли. и если она меньше суммы, которая была получена раньше, то переписываем её а также координаты
5.Так как главное условие позади, записываем в массив, в текущие координаты цифру 1. Тобиш мы здеся не были.

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

Автор: Fedor 8.1.2005, 16:09

Мое решение:

Цитата(Fedor)

Идешь это первой клетки ко всем соседям. Соседей этих сохраняешь в очередь, а в ячейки новой матрицы в клетки, соотв этим соседям, пишеш путь от первой вершины. Далее береш первого из очереди и ДЛЯ ВСЕХ его соседей делаешь ту же саму операцию только с оговрокой что если ты эту клетку уже находил, то идешь в нее только в том случае если это уменьшает число, которое в ней находится.
Если нужно потом узнать путь, по которому прошел, то идешь от последней клетки второй матрицы (матрицы путей) и берешь на каждом шаге минимального ее соседа. Так получаешь с обратной стороны твой путь.

Автор: Alexandr87 8.1.2005, 19:17

Fedor
Большое спасибо

Автор: [Last]Wizard 10.1.2005, 12:18

Это называется метод динамического программирования.

Автор: podval 10.1.2005, 16:16

Цитата(Fedor @ 8.1.2005, 16:09)

Мое решение:

Цитата(Fedor)

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

Автор: Alexandr87 10.1.2005, 17:37

есть линки или инфа по методу динамического программирования

Автор: Fedor 10.1.2005, 19:19

Цитата

Wizard, 10.1.2005, 11:18]Это называется метод динамического программирования.

Нет. Это - похоже на динамическое программирование.
В динамике мы решаем задачу n-той размерности если мы знаем как решать задачу размерности n-1. А тут не так немного. Мы ж можем и назад вернуться...
Добавлено @ 19:20
Alexandr87 Вообще, если ты хочешь серьезно заниматься олимпиадным программированием, советую тебе не задавать вопросы на форумах, а самому рыться в литературе.
Вот например классная (просто супер) книга - Кормен, Лейзерсон, Ривест - "Алгоритмы. Построение и анализ". Просто незаменимая книга. Но стоит порядка 25 букозоидов.

Автор: Alexandr87 11.1.2005, 08:18

2Fedor
Спасибо учту

Автор: sonic 11.1.2005, 17:52

Задача класическая.
Возми любой учебник по иследованию операций или математическому программированию.

Автор: Б а Т о Н 30.1.2005, 03:11

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

Дейкстра пишется в несколько строк и работает быстро. Описание алгоритма можешь легко найти в поисковиках. Данное решение является лучшим и самым быстрым.

Искать ошибку в твоём огромном коде - дело гиблое. Так как реализация на самом деле гораздо проще, и лучше тебе написать заново.

Надеюсь, мой ответ тебе помог.

Автор: neutrino 4.2.2005, 11:48

Я также решал эту задачу с немного модифицированным алгоритмом Дийкстры. Мне это нужно было для соединения блоков в блок-схеме.