Поиск самого быстрого пути при дополнительных условиях

Ответ 1

Я думаю, вы можете изменить алгоритм Дейкстры, чтобы справиться с этим. Алгоритм Дейкстры в основном работает путем постепенного построения таблицы, содержащей кратчайший путь к каждому node. Вместо этого вы создадите таблицу с кратчайшим путем для каждого node по заданной стоимости. Вернее, при данной стоимости или меньше, то есть по заданному бюджету.

Более формально вы можете преобразовать исходный граф в другой граф, а затем применить Dijkstra к этому графу. Предполагая, что стоимость дополнительных_данных всегда является целым числом, это преобразование:

• Возьмите каждый оригинальный node n и создайте набор узлов (n, c) для каждого целочисленного значения c от 0 до значения бюджета (максимальная сумма дополнительных_данных, которые вы можете терпеть)
• Возьмите каждое исходное соединение n1 → n2 с весом w и дополнительными_датами a и создайте набор подключений от каждого node (n1, c) до node (n2, c + a), каждый с весом ж

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

Если вы хотите получить от A до Z с бюджетом x, тогда вы просто используете алгоритм Дейкстры, чтобы найти маршрут от (A, 0) до одного из узлов (Z, c <= x).

EDIT: я внедрил модифицированный алгоритм Дейкстры: https://bitbucket.org/twic/roadsproblem. Суть его в src/solver.py.

Ответ 2

Вот объяснение того, как алгоритм, который вы нашли, будет обрабатывать вашу примерную проблему.

Проблема заключается в том, чтобы найти кратчайший путь между node one и node four с дополнительным условием, что накопленная стоимость по пути не должна быть больше 7.

Решение, которое мы хотим найти, - это сначала перейти от node one в node node two, расстояние 190 и за счет 4. Затем перейдите от node two до node four, используя путь расстояния 195 и стоимость 3. В общем случае путь имеет расстояние 385 и стоимость 7.

Шаг 1

Итак, как алгоритм находит это? Первый шаг - настроить матрицу minArray(i,j) так же, как вы это сделали. Элемент (i,j) массива удерживает расстояние, которое вы должны преодолеть, чтобы добраться до node j с точно оставшимися деньгами i.

Запуск нет посещенных элементов, и поскольку мы начинаем с node one с 7 "monies", верхний левый элемент устанавливается равным нулю. Пустые пространства в приведенной выше таблице соответствуют значениям, установленным в infinity в массиве.

Шаг 2

Затем мы найдем наименьшее значение массива, это нуль в позиции (remaining money, node) = (7,1). Этот элемент имеет значение visited (состояние элемента отслеживается с использованием матрицы visitedArray того же размера, что и minArray), что означает, что мы выбрали node one. Теперь все узлы, которые подключаются к node one, обновляются значениями путем перемещения соответствующих ребер.

Здесь minArray(6,3) = 191, что означает, что мы прошли расстояние 191, чтобы добраться до node three, а оставшиеся деньги - 6, так как мы заплатили стоимость 1, чтобы добраться туда. Точно так же minArray(3,2) устанавливается на 190. Красный квадрат отмечает, что элемент (7,1) посещается.

Шаг 3

Теперь мы снова найдем самый низкий невидимый элемент (который является minArray(3,2) = 190), установите его в visited и обновите все элементы, которые подключаются к нему. Это означает, что расстояние накапливается, а оставшиеся деньги вычисляются путем вычитания стоимости из текущего значения.

Обратите внимание, что слишком дорого вернуться к node one из node two.

Шаг 4

Следующий шаг, выбор minArray(6,3) = 191 выглядит следующим образом.

Шаг 5

Через три шага массив выглядит так. Здесь выбраны два элемента, которые равны 382 и равны 383. Обратите внимание, что значение элемента обновляется только в том случае, если оно улучшает текущее значение (т.е. Ниже).

Шаг 6

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

Заключительный шаг

Последний шаг - найти общее расстояние, найдя самое низкое значение столбца четыре. Мы можем видеть, что минимальное значение minArray(0,4) = 385 соответствует правильному решению.

Примечание. Если все значения столбца четыре были бы бесконечными, это означало бы, что нет действительного решения. Алгоритм также указывает, что если в столбце четыре есть равные и минимальные расстояния, выбирается самый дешевый.

Ответ 3

Я не думаю, что алгоритм Дейкстры является хорошим решением этой проблемы, поскольку требуемое расстояние - это не только источник node и пункт назначения. Вот решение, основанное на алгоритме поиска A *.\

Сначала выполните FolydWarshall на основе weight, а затем на основе additional_data, чтобы получить наименьшее значение weight и наименьшее additional_data для каждой пары node на графике.

  FloydWarshall(Weights);
  FloydWarshall(Additional_datas);

Во-вторых, мы выполняем поиск A *, основанный на очереди приоритетов, с элементом, подобным следующей структуре (пример использования c-кода). Очередь приоритетов будет автоматически получать weight_sum наименее во всех кандидатах. weights_expected - лучшая догадка пути через текущий node к пункту назначения node, в то время как weights_now - текущий вес

  struct NODE
    {
        int node;
        int weights_expected;
            int weights_now;
        int additional_datas_now;
            bool visited;
    };
    bool operator < (const NODE &A,const NODE &B)
    {
        return A.weights_expected>B.weights_expected || (A.weights_expected==B.weights_expected && 
   A.additional_datas_now>B.additional_datas_now);
    }

В алгоритме поиска A *,

1) we first put the source node into priority queue. 
  2) while Priority Queue is not empty:
        Set **A** equal to the head of priority queue and pop out the head of priority queue. 
        A.visited=True;
        if A is the destination node **Dest**, **return** A.weights_expected. 
        For each neighbors **B** of node **A**, 
          if A.visited==False **and** A.additional_datas_sum+|AB|.additional_data+Additional_datas[B][Dest]<=x, 
               1) B.additional_datas_now=A.additional_datas_now+|AB|.additional_data;    
               2) B.weights_now=A.weights_now+|AB|.weight;
               3) B.weights_expected=B.weights_now+Weights[B][Dest];
               3) push node B into priority Queue. 
   3) Print "Do not find a proper path" //if code came to here, that means the if in 2) do not return a value. 

A * поиск будет по-прежнему NP трудным, поскольку в худшем случае он должен искать каждый возможный путь. Однако это будет намного быстрее, чем простой поиск DFS и выполнение множества сокращений пути поиска.

Ответ 4

Вы можете сделать копию node с 0 стоимостью между ними, которая добавит второй возможный путь.

Так же (псевдокод)

Node 1____
|         |
|path1    |
|cost=3   |path2 cost=5
|         |
Node 2____/

становится следующим:

Node 1____cost=0____Node 1a
|         path 1a     |
|path1                |path2
|cost=3               |cost=5
|                     |
Node 2________________/

Не уверен, что это сработает, но это идея.

Ответ 5

Дополнительное условие сломает Дейкстра. Подумайте об этом так: если у вас есть путь A- > B в графе и ребро B- > C в графе, то кратчайший путь A- > C, который включает B, безусловно, является минимальным путем A- > B → C. В вашем случае это условие не выполняется, потому что, хотя A- > B и B- > C могут быть действительными, A- > B- > C может быть недействительным.

Хорошо, это тот момент, когда вы захватываете листок бумаги и пытаетесь это сделать.

Если вы посмотрите на свой график и предположите, что хотите перейти от (1) - (4), обратите внимание, как вы можете устранить (3), введя следующие ребра:

• (1) → (4), [390, 2]
• (1) → (2), [383, 3]
• (2) → (4), [391, 3]

После устранения всех краев, но прямой линии, проблема будет несколько проще: для каждого node вы можете отслеживать, сколько [расстояние, дополнительное] будет стоить для достижения цели. Вам не нужно сохранять дополнительные > max или 'остающиеся дополнительные' < 0, так как это не жизнеспособное решение. Кроме того, если у вас есть несколько расстояний для равного дополнительного, нужно сохранить только минимальное расстояние.

Лучшим решением является теперь с минимальным расстоянием в последнем node (или первым, в зависимости от того, как вы его заказали). Если по дороге вы указали на то, как вы туда попали (например, если вы обновите значение в матрице, также сохраните элемент, из-за которого он изменился), вы также можете отменить путь.

Здесь вы должны отметить, что вы можете сделать то же самое, когда проблема была в неисчерпаемой форме с помощью матрицы, которую вы предлагаете: ось x в виде узлов, ось y как "список за node".

Это должно сделать это.

Ответ 6

вы можете использовать алгоритм bellman-ford с предположением, что ваш addittional-data​​strong > является числом параметров ребер в алгоритме bellman-ford.

Ответ 7

Эта проблема NP-полная. Ни один алгоритм не эффективнее, чем тот, который объясняется несколькими людьми (Tom Anderson, user1884905).

Доказательство: Уменьшая сумму подмножества для неотрицательных чисел.

Возьмем экземпляр A подмножества-суммы (числа N). Построить граф, где есть N + 1 узлов. Для узлов я и я + 1 сделайте 2 пути, один с весом = 0, дополнительный_дат = A [i], другой с весом = A [i], дополнительный_data = 0. Выберите x (предел для суммы дополнительных_данных).

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

Ответ 8

Ваше дополнительное условие усложняет задачу. Глядя на это, я думаю, что единственное, что вы можете сделать, - найти все возможные пути между источником и целью, отсортировать их по суммарному весу кромки, а затем проверить один за другим, если ваше дополнительное условие выполнено.

Однако проблема нахождения всех возможных путей между двумя вершинами NP-Hard. Немного измененная версия DFS могла бы сделать трюк, но, вероятно, не во всех случаях.