singlepost

задача на нахождение кратчайшего пути в координатной плоскости << На главную или назад  

По заданным натуральным числам (-10<=x, y <=10, (x,y) не равно (0,0)) найти длину кратчайшего пути от точки (0,0) до точки (х,у) по сторонам (длины 1) или диагоналям леток, и количество таких путей.

Задача была на городской олимпиаде по информатике. Времени было мало, я сделал таким образом: увеличивала х, пока не наткнешься на х искомой точки, или х точки-препятствия; затем увеличивала у таким же образом; если не доходишь до точки – снова увеличиваешь х, итд. Работает, но далеко не на все случаи (чаще всего выдает не кратчайший путь). Как оптимизировать алгоритм и как посчитать количество путей?

12 ответов в теме “задача на нахождение кратчайшего пути в координатной плоскости”

  1. 12
    Денис Лисов ответил:

    Эльмира, а препятствия там все-таки есть или нет?
    Если нет и стоимости диагонали и стороны равны, то длина
    L = max( abs(x), abs(y) )
    И число путей тоже считается аналитически.

  2. 11
    Evgenia Antokolskaya ответил:

    Хм. А формула Пифагора не тянет?

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

    А условие (-10<=x, y <=10, (x,y) не равно (0,0) дается для того, чтобы найти возможное количество таких путей, т.е. комбинаций х и у, где они меняются на 1. Эта другая функция. В функции применяются циклы while или for с прибавлением единицы к x и у каждый раз. Там же все просчитывается, выдается ответ. Это если в лоб решать. А так – лучше, конечно, формулы из комбинаторики применять.

    Я, наверно, не поняла задание, потому что слишком бы легко было.

  3. 10
    Богдан Пилипенко ответил:

    Воспринимаю задание таким образом:
    По заданным натуральным числам x и y найти длину кратчайшего пути от точки (0,0) до точки (х,у) по сторонам или диагоналям клеток (на выбор), а также количество таких путей. При этом:
    1) -10<=x<=10;
    2) -10<=y<=10;
    3) x не равно 0;
    4) y не равно 0;

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

    Матрица сама по себе большая (число строк увеличивается геометрически в зависимости от значений пределов x и y), так что с целью экономии ресурсов памяти можно выбросить её и обойтись рекурсией в купе с парой-тройкой значимых переменных, однако при этом значительно усложнится часть дополнительных проверок, которая находится в теле цикла рекурсии. Если решение не требует скорости выполнения расщетов, то проще использовать матрицу.

    Остается только поколдавать над телом рекурсивного цикла, задача которого – построить матрицу…

  4. 9
    Александр Lert ответил:

    Видимо, надо поправить, сумма количеств путей до вершин, из которых можно попасть в эту вершину по кратчайшему пути. Нам же надо найти в результате количество кратчайших путей.

  5. 8
    Михаил Асташкевич ответил:

    Ну просто кол-во путей для вершины – сумма количеств путей до вершин, из которых можно попасть в эту вершину.

  6. 7
    Эльмира Бугазова ответил:

    2 Веном int 0×80 Кац: Объясните, пожалуйста, какой алгоритм Вы имеете в виду, я постараюсь разобраться. Что насчет олимпиады – там вообще не смотрели исходники, делай как знаешь, хоть рандомом ответы генерируй.
    2 Михаил [The_Grass_Was_Greener] Асташкевич: В таком случае как искать количество путей?

  7. 6
    Евгений кросовкин ответил:

    а по прямой нельзя чтоль?

  8. 5
    Александр Lert ответил:

    Тут вроде есть какие-то точки-препятствия.

  9. 4
    Михаил Асташкевич ответил:

    Найдем.

  10. 3
    Михаил Асташкевич ответил:

    А почему бы не написать просто поиск в ширину\глубину? Или алгоритм Дейкстры?

  11. 2
    Александр Lert ответил:

    Количество путей не найдете.

  12. 1
    Веном Кац ответил:

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

Клуб программистов работает уже ой-ой-ой сколько, а если поточнее, то с 2007 года.