Самый дешевый путь алгоритм - PullRequest
2 голосов
/ 05 февраля 2010

Я изучил алгоритм динамического программирования, чтобы найти «самый дешевый» путь от A до B. Каждый подпуть имеет связанную стоимость.

Каждый угол рассчитывается с использованием
D(i,j).value = min( (D(i-1,j).value + D(i,j).x), (D(i,j-1).value + D(i,j).y))
Где x и y - стоимость пути слева от узла и ниже узла.

Теперь у меня проблемы с поиском количества самых дешевых путей в наилучшее возможное время.

Есть предложения?

Ответы [ 7 ]

8 голосов
/ 05 февраля 2010

Вы ищете алгоритм Дейкстры . Это алгоритм поиска в графе, который решает проблему кратчайшего пути из одного источника для графа с неотрицательными затратами на ребро, создавая дерево кратчайшего пути.

2 голосов
/ 06 февраля 2010

Подход динамического программирования, который вы описываете, называется Кратчайший путь DAG . Он работает только с ориентированными ациклическими графами (то есть графами без циклов). Его асимптотическое время выполнения - O (V + E) (где V и E - число вершин и ребер соответственно), что быстрее, чем алгоритм Дейкстры.

Я не уверен, но вы спрашиваете, как рассчитать количество путей, длина которых равна кратчайшему пути?

Вы можете сделать это, поддерживая информацию предшественника при расчете длины кратчайшего пути. Когда вы переходите на узел j, сохраняйте все пары (i, j) таким образом, чтобы переход от i к j был частью кратчайшего пути. Одним из способов реализации этого является добавление двух полей, D (x, y) .optimalUp и D (x, y) .optimalRight (тип данных логический), указывающих, если вы получите оптимальное решение, если вы ввели (x, y), перейдя вверх или вправо соответственно. Например, установите для D (x, y) .optimalUp значение true, если переход от (x, y-1) приведет к самому дешевому пути.

Затем вы можете сделать второй проход, чтобы подсчитать количество самых дешевых путей, используя динамическое программирование. Добавьте другое поле, скажем, D (x, y) .count (целое число), которое содержит количество способов перейти от A к (x, y) самым дешевым способом. Есть два способа достичь (x, y): через (x-1, y) и (x, y-1). Счет (x, y-1) должен быть добавлен к счету (x, y), только если возможно достичь самого дешевого пути к (x, y), пройдя через (x, y-1). Тот же принцип справедлив для (x-1, y).

Затем мы получаем повторение:

D(x,y).count =
    D(x,y).optimalUp   ? D(x,y-1).count : 0
  + D(x,y).optimalDown ? D(x-1,y).count : 0

(?: Это условный оператор в C / C ++ / Java.)

Судя по вашей картинке, кажется, что ваш график - это сетка. Помните, что движение только вверх или вправо не обязательно приведет к кратчайшему пути. На приведенном ниже графике самый короткий путь от A до B - 8, но вы не можете достичь лучшего, чем 12, если идете только направо и вверх.

x -1-- x -1-- B
|      |      |
1      9      9
|      |      |
x -1-- x -1-- x
|      |      |
9      9      1
|      |      |
A -1-- x -1-- x

Поскольку это помечено как домашнее задание, я пока не буду предоставлять больше подробностей, чем это. Тем не менее, это должно быть толчком в правильном направлении (если я правильно понял вашу проблему). Не стесняйтесь задавать дополнительные вопросы.

1 голос
/ 07 февраля 2010

Похоже, вы работаете с графиком, где узлы являются точками на 2D-сетке, и каждый узел имеет направленный край к узлу над ним, а другой - к узлу справа.

Я не думаю, что применение алгоритма Дейкстры здесь сработает. Он находит один самый дешевый путь, и на самом деле нет способа изменить его, чтобы найти все самые короткие пути.

Поскольку это такой специальный граф (то есть направленный и ациклический), вы можете вычислить количество самых дешевых путей, если вы знаете, какова стоимость самого дешевого пути, используя простое повторение. Обратите внимание, что

number_paths(i,j)=number_of_paths(i-1,j)+number_of_paths(i,j-1)

т.е. количество путей от любого узла является суммой пути от узлов выше и справа от него. (Это исключает базовые случаи, когда текущий узел является пунктом назначения, а узел назначения недоступен из текущего узла.)

Единственное, что нужно, это изменить это, чтобы считать только те пути, которые являются самыми дешевыми. Теперь мы уже знаем, что самый дешевый путь имеет некоторую стоимость X. Мы можем использовать его для увеличения нашего повторения, чтобы он учитывал только самый дешевый путь. На начальном узле мы знаем, что стоимость оставшегося пути равна X. От любого из смежных узлов до начального узла (то есть от узлов, расположенных выше и справа от него), поэтому стоимость равна Xe, где e - это стоимость края между этими узлами. Это правило применяется к любому узлу, для которого известна стоимость достижения текущего узла. Таким образом, мы знаем, что прошли самый дешевый путь, когда достигаем узла назначения, и значение этого узла равно 0 (то есть мы вычли все затраты на ребра, которые образуют самый дешевый путь).

Таким образом, мы можем просто увеличить нашу повторяемость, чтобы сохранить 3 значения вместо 2, координаты и оставшуюся стоимость пути (по сути, преобразование в ту же задачу для трехмерного графика, где третье измерение - это стоимость). Начальный узел имеет форму (x_start,y_start,cost), конечный узел имеет форму (x_end,y_end,0). Наше повторение будет выглядеть так:

paths(x,y,cost_left)=
                 0         if x_end,y_end is unreachable from x,y or cost_left<0
                 1         if x==X-end and y==y_end and cost_left==0
                 paths(x-1,y,cost_left-edge(x,y,x-1,y))+paths(x,y-1,cost_left-edge(x,y,x,u-1))   otherwise

Сложность алгоритма должна быть O (n m C), где n и m - размеры сетки, а C - стоимость самого дешевого пути.

0 голосов
/ 05 февраля 2010

Попробуйте поискать алгоритмы "кратчайшего пути", но есть одна загвоздка.

Во многих поисках по кратчайшему пути оценочное расстояние до цели используют как эвристику, которая часто должна удовлетворять определенным условиям. A *, например, использует функцию оценки расстояния до цели и гарантированно находит кратчайший путь, если он никогда не занижает расстояние до цели. Так как вы ищете путь с наименьшими произвольными затратами, вы не будете иметь такой доступной эвристики. Кроме того, вы знаете длину пути, поэтому такие алгоритмы, как итеративное углубление, не будут полезны.

Любой детерминированный алгоритм, такой как Алгоритм Дейкстры , должен работать нормально.

0 голосов
/ 05 февраля 2010

A * лучший в первую очередь и, вероятно, будет хорошо работать для вас.

0 голосов
0 голосов
/ 05 февраля 2010

Ознакомьтесь с алгоритмами Hillclimbing и A-star в Википедии.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...