Помощь - Поиск - Пользователи - Календарь
Полная версия: Кратчайший путь
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Vovik777
Помогите пожалуйста решить такую задачу:
Дана квадратная матрица NxN.

A11 A12 … A1n
A21 A22 … A2n
…………
An1 An2 … Ann

Нужно найти кратчайший путь из A11 в Ann при условии, что переходить можно только на элемент, который больше или равен настоящему. Двигаться можно во всех направлениях (в т.ч. и по диагонали).

Никак не могу придумать сам алгоритм поиска пути. Хотя бы в какую сторону копать?
Буду очень признателен…
SHnur
Vovik777 , проверяй все соседние еллементы ночиная с правого нижнего , в обе стороны . И если подходит по условию , то переходи туда .

Цитата
* - текущий эллемент
# - соседние эллементы
< - проверяемый ..
! - проверенный , не подошедший по условию.

###
#*#
###

###
#*#
##<

###
#*<
#<!

и т.д ...


Думаю так всё получится .
volvo
SHnur
А почему с правого нижнего а не с левого верхнего? Чем обусловлен именно такой выбор? ;)
SHnur
volvo , Ну имеется ввиду начиная с самого приближённого к Ann положения .


А можно я , думаю методом волновой трассировки воспользоваться .
Подробнее тут :

http://www.codemanual.net/main/algo/alg20.htm

Vovik777 , вообше-то надо поиском по форуму пользоваться , там много чего есть .
volvo
SHnur
А оценить быстродействие своего метода сможешь?

Просто я сегодня к похожей задаче подошел через графы (алгоритм Дейкстры)... Работает очень быстро. (Буквально за 1 проход по матрице).
SHnur
Думаю , что работать будет очень долго , но работать должно . ;)
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.