поиск маршрута

Тема в разделе "Delphi - Multimedia, Графика, Игры", создана пользователем Phantom4nvkz, 8 май 2009.

  1. Phantom4nvkz

    Phantom4nvkz Гость

    Задача следующая:
    Некая географическая карта местности задана квадратной сеткой определенного масштаба. В узлах сетки известна высота над уровнем моря. Между соседними узлами высота меняется плавно. Имеется караван, перемещающийся только по линиям сетки, перемещение по диагоналям запрещается. Путь между двумя соседними точками с углом наклона больше 45 градусов считается непроходимым.
    Необходимо предложить возможные маршруты для перехода каравана из точки A(X1,Y1) в точку B(X2,Y2):
    - с наименьшим перепадом высот на маршруте;
    - по кратчайшему пути.
    Перепадом высот на маршруте называется разность высот между самой высокой и самой низкой точками маршрута.
    Разработать и реализовать удобный графический интерфейс пользователя.

    язык - Delphi

    Надеюсь на помощь.
     
  2. interrupt

    interrupt Гость

    В чем нужна помощь в алгоритмизации или программировании?

    Если по алгоритмизации то это типичная задача на графы и поиск кратчайшего пути между вершинами.
    Ищешь кратчайший путь алгоритмом Флойда (посчитает все пути) или Дейкстры (найдет один кратчайший), затем просматриваешь маршрут и находишь мин. высоту и макс.
    Граф представляешь как угодно, например матрицей смежности, но предварительно просматриваешь его и там где перепады высот более 45 убираешь ребра (или делаешь "бесконечные веса" для них)

    Если по реализации, то пользуйся поиском подобные задачи решались много раз не только на этом форуме.
    Не могу кидать конкретных ссылок т.к. запрещает п.3.1 правил.
     
Загрузка...

Поделиться этой страницей