Алгоритмы сетки

Question

Это мой первый пост на stackoverflow, поэтому извините, если я задаю вопрос, на который уже дан ответ.Может кто-нибудь направить меня к хорошему учебнику, чтобы помочь мне решить проблемы с сеткой, где мы должны решить эту проблему за «минимальное» количество возможных шагов.Иногда BFS помогает, но этого недостаточно для других подобных проблем.Спасибо:)

Answer 1

Если вы хотите уменьшить сложность и порядок сетки, вы можете использовать кривую заполнения пространства, например, кривую z, гильбертову или кривую Пеано.

Answer 2

Без дополнительной информации сложно дать хороший ответ.Хорошие алгоритмы зависят от точной постановки задачи.

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

Если некоторые ребра существуют или ребра имеют переменные веса, которые являются положительными, я бы предложил алгоритм Дейкстры.Если некоторые края отрицательны, есть варианты, такие как Bellman-Ford.

В любом случае, вам нужно уточнить настройку, чтобы мы могли помочь вам.