модификация алгоритма кратчайшего пути Dijkstra

Question

Я работаю над изображениями для личного проекта, и я застрял на одном шаге (более того, это относительно простой шаг). Мой вопрос, кстати, не связан с изображениями.

Я вычисляю значения int для каждого пикселя на изображении. И я хочу найти путь с минимальной стоимостью между пикселями (узлами). На самом деле у меня есть работающая реализация алгоритма A *. Но я не хочу использовать это, потому что я не хочу ограничивать «карту» узлами, которые вы можете передавать или не передавать только. Я хочу, чтобы каждый узел мог быть передан, но с затратами. Некоторые узлы будут стоить дорого, а некоторые - нет. Но не будет узлов, которые нельзя передать.

Я не думаю, что мне нужно дать какой-либо код, потому что это очень изолированная часть проекта. Поэтому я не хочу никого изнашивать. Но в основном у меня есть объект карты, который имеет список узлов. И узлы имеют id, x, y позиции. (верхний, нижний, левый и правый пиксели) и ссылку на узел, чтобы знать, откуда я пришел сюда и т. д.

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

Answer 1

Я думаю, что вижу проблему .. «Некоторые узлы будут дорого стоить, а некоторые не будут». На самом деле это не так, как работают алгоритмы, вы должны перевести проблему на узлы (без затрат) и на края (с затратами). Тогда это должно быть легко использовать A *, Dijkstra или любой другой алгоритм поиска пути.

В вашем случае каждый пиксель является узлом/вершиной. Каждый пиксель имеет 4 ребра (кроме границ на границах). Стоимость края будет значением int пикселя назначения.

Также вы не должны хранить ссылку на узлы в узлах, это задача алгоритмов отслеживать, откуда она взялась.

Надеюсь, это поможет.