Нахождение кратчайшего пути в графе без отрицательных префиксов

Question

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

Я пытался использовать модифицированный Bellman Ford, но не смог найти правильное решение.

---

Я хотел бы уточнить несколькобаллы:

1. да, могут быть отрицательные весовые циклы.
2. n - количество ребер.
3. Предположим, что путь длины O (n) существует, если задача имеет решение.
4. + 1 / -1 веса ребер.

Answer 1

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

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

Тогда эквивалентная двоичная задача о ранце пытается выбрать веса из набора { a ₀ , ..., a _n }, который максимизирует Σ a _i , где Σ a _i <<em> X .

В качестве примечания: если мы введем взвешенные циклы, то вместо этого легко будет построить задачу неограниченного ранца.

Следовательно, любой практический алгоритм, который вы можете выбрать, имеет время выполнения, которое зависит от того, что вы считаете «средним» случаем. Есть ли ограничение на проблему, которую я либо не рассматривал, либо не имел в своем распоряжении? Вы, похоже, уверены, что это проблема O ( n ³ ). (Хотя что в этом случае n )

Answer 2

Питер де Риваз указал в комментарии, что эта проблема включает ГАМИЛЬТОНСКИЙ ПУТЬ в качестве особого случая.Его объяснение было немного лаконичным, и мне потребовалось некоторое время, чтобы выяснить детали, поэтому я нарисовал некоторые диаграммы для блага других, которые могут бороться.Я сделал эту публикацию вики сообщества.

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

Для заданного неориентированного графа с n вершинами, для которых мы хотим найти гамильтоновый путь, мы строимновый взвешенный ориентированный граф с n ² вершинами, плюс вершины START и END.Пометьте исходные вершины v _i и новые вершины w _ik для 0≤ i , k <<em> n .Если есть грань между v _i и v _j в оригиналезатем для графика 0 ≤ k <<em> n -1 в новом графике есть ребра от w _ik до ш _{j ( k + 1)} с весом -2 ^j и от ш _ДжК до ш _{i ( k + 1)} с весом -2 ⁱ .Имеются ребра от START до w _i0 с весом 2 ⁿ - 2 ⁱ - 1 и от w _{i ( n -1)} до КОНЦА с весом 0.

Легче всего думать, что эта конструкция эквивалентна началу со счетом 2 ⁿ - 1 и затем вычитанию 2 ⁱ каждый раз, когда вы посещаете ш _ij .(Вот как я нарисовал график ниже.)

Каждый путь от START до END должен посещать ровно n + 2 вершины (по одной от каждой строки, плюс START и END), поэтомуединственный способ, чтобы сумма вдоль пути была равна нулю, это чтобы каждый столбец посещался ровно один раз.

Итак, вот исходный граф с шестью вершинами, преобразованный в новый граф с 38 вершинами.Исходный гамильтонов путь соответствует пути, выделенному жирным шрифтом.Вы можете проверить, что сумма вдоль пути равна нулю.

Answer 3

ОБНОВЛЕНИЕ: У ОП теперь было несколько раундов разъяснений, и теперь это другая проблема.Я оставлю это здесь для документирования моих идей для первой версии проблемы (точнее, моего понимания).Я попробую новый ответ для текущей версии проблемы. Конец ОБНОВЛЕНИЯ

Жаль, что ФП не прояснил некоторые открытые вопросы.Я предполагаю следующее:

1. Веса +/- 1.
2. n - количество вершин

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

Алгоритм, который я предлагаю, довольно прост и похож на известные алгоритмы графов.Я не эксперт по графику, поэтому я могу использовать неправильные слова в некоторых местах.Не стесняйтесь поправлять меня.

1. Для исходной вершины запомните стоимость 0. Добавьте (source, 0) в список задач.
2. Выдвиньте элемент из списка задач.Следуйте всем исходящим ребрам вершины, вычисляя новую стоимость c, чтобы достичь новой вершины v. Если новая стоимость действительна (c> = 0 и c <= n ^ 2 </strong>, см. Ниже), а незапоминается для v, добавьте к запомненным значениям стоимости v и добавьте (v, c) в свой список задач.
3. Если список задач не пуст, перейдите к шагу 2(Или прервитесь рано, если пункт назначения может быть достигнут со стоимостью 0).

Понятно, что каждый «шаг», который не является непосредственным тупиком, создает новую комбинацию (вершина, стоимость).Будет сохранено не более n * n ^ 2 = n ^ 3 этих комбинаций, и, таким образом, в определенном смысле этот алгоритм является O (n ^ 3).

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

Я думаю, что ясно, что единственное, что мы должны показать, это то, что условие c <= n ^ 2 является достаточным.</p>

Во-первых, отметим, что любая (достижимая) вершина может быть достигнута со стоимостью менее n.

Пусть (v, c) будет частью оптимального пути и c> n ^ 2.Поскольку c> n, должен быть некоторый цикл на пути до достижения (v, c), где стоимость цикла равна 0 м2> -n.

Кроме того, пусть v будет достижимым из источника со стоимостью 0 <= c1 <n по пути, который касается первого цикла, упомянутого выше,и пусть назначение будет достижимо из v со стоимостью 0 <= c2 <n, путем, который касается другого цикла, упомянутого выше. </p>

Тогда мы можем построить пути от источника до v с ценами c1, c1 + m1, c1 + 2 * m1, ... и пути от v до места назначения с затратами c2, c2 + m2, c2 + 2 * m2, ....Выберите 0 <= a <= m2 и 0 <= b <= m1 так, чтобы c1 + c2 + a * m1 + b * m2 был минимальным и, следовательно, стоил оптимальный путь.На этом оптимальном пути v будет иметь стоимость c1 + a * m1 <n ^ 2. </p>

Если gcd для m1 и m2 равен 1, тогда стоимость будет равна 0. Если gcd равен> 1,тогда можно было бы выбрать другие циклы, так что gcd становится равным 1. Если это невозможно, это также невозможно для оптимального решения, и для оптимального решения будут положительные затраты.

(Да, я могу видеть несколько проблем с этой попыткой доказательства. Возможно, необходимо взять gcd нескольких положительных или отрицательных затрат цикла и т. Д. Я бы очень заинтересовался контрпримером.)

Вотнекоторый (Python) код:

def f(vertices, edges, source, dest):
    # vertices: unique hashable objects
    # edges: mapping (u, v) -> cost; u, v in vertices, cost in {-1, 1}

    #vertex_costs stores the possible costs for each vertex
    vertex_costs = dict((v, set()) for v in vertices)
    vertex_costs[source].add(0) # source can be reached with cost 0

    #vertex_costs_from stores for each the possible costs for each vertex the previous vertex
    vertex_costs_from = dict()

    # vertex_gotos is a convenience structure mapping a vertex to all ends of outgoing edges and their cost
    vertex_gotos = dict((v, []) for v in vertices)
    for (u, v), c in edges.items():
        vertex_gotos[u].append((v, c))

    max_c = len(vertices) ** 2 # the crucial number: maximal cost that's possible for an optimal path

    todo = [(source, 0)] # which vertices to look at

    while todo:
        u, c0 = todo.pop(0)
        for v, c1 in vertex_gotos[u]:
            c = c0 + c1
            if 0 <= c <= max_c and c not in vertex_costs[v]:
                vertex_costs[v].add(c)
                vertex_costs_from[v, c] = u
                todo.append((v, c))

    if not vertex_costs[dest]: # destination not reachable
        return None # or raise some Exception

    cost = min(vertex_costs[dest])

    path = [(dest, cost)] # build in reverse order
    v, c = dest, cost
    while (v, c) != (source, 0):
        u = vertex_costs_from[v, c]
        c -= edges[u, v]
        v = u
        path.append((v, c))

    return path[::-1] # return the reversed path

И вывод для некоторых графиков (ребра и их вес / путь / стоимость в каждой точке пути; извините, нет хороших изображений):

AB+ BC+ CD+ DA+             AX+ XY+ YH+ HI- IJ- JK- KL- LM- MH-
 A  B  C  D  A  X  Y  H  I  J  K  L  M  H
 0  1  2  3  4  5  6  7  6  5  4  3  2  1
AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MH-
 A  B  C  D  E  F  G  A  B  C  D  E  F  G  A  B  C  D  E  F  G  A  X  Y  H  I  J  K  L  M  H  I  J  K  L  M  H  I  J  K  L  M  H  I  J  K  L  M  H
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MN- NH-
 A  X  Y  H
 0  1  2  3
AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MN- NO- OP- PH-
 A  B  C  D  E  F  G  A  B  C  D  E  F  G  A  B  C  D  E  F  G  A  B  C  D  E  F  G  A  B  C  D  E  F  G  A  B  C  D  E  F  G  A  X  Y  H  I  J  K  L  M  N  O  P  H  I  J  K  L  M  N  O  P  H  I  J  K  L  M  N  O  P  H  I  J  K  L  M  N  O  P  H  I  J  K  L  M  N  O  P  H
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0

Вот код для вывода:

def find_path(edges, source, path):
    from itertools import chain

    print(edges)
    edges = dict(((u, v), 1 if c == "+" else -1) for u, v, c in edges.split())
    vertices = set(chain(*edges))

    path = f(vertices, edges, source, dest)
    path_v, path_c = zip(*path)
    print(" ".join("%2s" % v for v in path_v))
    print(" ".join("%2d" % c for c in path_c))

source, dest = "AH"

edges = "AB+ BC+ CD+ DA+             AX+ XY+ YH+ HI- IJ- JK- KL- LM- MH-"
# uv+ means edge from u to v exists and has cost 1, uv- = cost -1
find_path(edges, source, path)

edges = "AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MH-"
find_path(edges, source, path)

edges = "AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MN- NH-"
find_path(edges, source, path)

edges = "AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MN- NO- OP- PH-"
find_path(edges, source, path)

Answer 4

Как отмечает Каганар, нам нужно сделать некоторые предположения, чтобы получить алгоритм polytime.Предположим, что длина ребер в {-1, 1}.Для данного графика создайте взвешенную контекстно-свободную грамматику, которая распознает допустимые пути от источника к месту назначения с весом, равным количеству лишних 1 ребер (это обобщает грамматику для сбалансированных скобок).Вычислите для каждого нетерминала стоимость самого дешевого производства, инициализируя все до бесконечности или 1, в зависимости от того, существует ли производство, у которого RHS не имеет нетерминала, и затем ослабляя n - 1 раз, где n - количество нетерминалов.

Answer 5

Шаг 1: обратите внимание, что ваш ответ будет не более 2 * n (если он существует).
Шаг 2: Создайте новый граф с вершинами, которые являются парами [вершина] [стоимость].(2 * n ^ 2 вершин)
Шаг 3: Обратите внимание, что у нового графа все ребра равны одному, и не более 2 * n для каждой пары [vertex] [cost].
Шаг 4: Выполнитеdfs над этим графиком, начиная с [start] [0]
Шаг 5: Найдите минимальное k, чтобы [finish] [k] было доступно.

Общая сложность не более O (n ^ 2) * O (n) = O (n ^ 3)

РЕДАКТИРОВАТЬ: Разъяснение на шаге 1.
Если есть положительный цикл, доступный с самого начала, вы можете пройти всепуть до п.Теперь вы можете перейти к любой доступной вершине, не превышающей n ребер, каждая из которых имеет +1 или -1, оставляя вас с диапазоном [0; 2n].В противном случае вы пройдете либо через отрицательные циклы, либо не более n +1, которые не находятся в отрицательном цикле, и у вас останется диапазон [0; n].

Answer 6

Текущие предположения:

1. да, могут быть отрицательные весовые циклы.
2. n - число ребер.
3. Предположим, что O (n) длина пути существует, если задача имеет решение.
4. + 1 / -1 веса ребер.

Мы можем без ограничения общности предположить, что число вершин не более n,Рекурсивно обходите график и запоминайте значения затрат для каждой вершины.Остановитесь, если стоимость уже была запомнена для вершины, или если стоимость будет отрицательной.

После O (n) шагов либо пункт назначения не был достигнут, и решение не найдено.В противном случае для каждой из O (n) вершин мы запомнили не более O (n) разных значений стоимости, и для каждой из этих O (n ^ 2) комбинаций могло быть до n неудачных попыток пройти к другим вершинам.,В общем, это O (n ^ 3).qed

Обновление: Конечно, опять что-то подозрительное.Что означает предположение 3: путь длины O (n) существует, если у задачи есть решение?Любое решение должно обнаружить это, потому что оно также должно сообщать, если нет решения.Но это невозможно обнаружить, потому что это не свойство отдельного графа, над которым работает алгоритм (это асимптотическое поведение).

(Очевидно также, что не все графы, для которых может быть достигнут пункт назначения, имеютпуть решения длины O (n): возьмем цепочку из m ребер весом -1, а до этого простой цикл из m ребер и общего веса +1).

[Теперь я понимаю, что большинствокод Python из моего другого ответа (попытка найти первую версию проблемы) можно использовать повторно.]

Answer 7

Хотя люди показали, что быстрого решения не существует (если только P = NP) ..

Я думаю, что для большинства графиков (95% +) вы сможете найти решение довольно быстро.

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

Ideas:

1.найти отрицательный цикл, который ближе всего к месту назначения.обозначим кратчайшее расстояние между циклом и пунктом назначения как d (end, negC)

(я думаю, что это возможно, одним из способов может быть использование floyds для обнаружения (i, j) с отрицательным циклом, а затем продолжайте поиск по месту назначения, пока не столкнетесь с чем-то, что связано с отрицательным циклом.)

2.найдите ближайший положительный цикл к начальному узлу, обозначьте расстояние от начала как d (start, posC)

(я утверждаю, что на 95% графиков вы можете легко найти эти циклы)

    Now we have cases:
a) there is both the positive and negative cycles were found:
The answer is d(end,negC).

b) no cycles were found:
simply use shortest path algorithm?

c) Only one of the cycles was found. We note in both these cases the problem is the same due to symmetry (e.g. if we swap the weights and start/end we get the same problem). I'll just consider the case that there was a positive cycle found.

find the shortest path from start to end without going around the positive cycle. (perhaps using modified breadth first search or something). If no such path exists (without going positive).. then .. it gets a bit tricky.. we have to do laps of the positive cycle (and perhaps some percentage of a lap).
If you just want an approximate answer, work out shortest path from positive cycle to end node which should usually be some negative number. Calculate number of laps required to overcome this negative answer + the distance from the entry point to the cycle to the exit point of the cycle. Now to do better perhaps there was another node in the cycle you should have exited the cycle from... To do this you would need to calculate the smallest negative distance of every node in the cycle to the end node.. and then it sort of turns into a group theory/ random number generator type problem... do as many laps of the cycle as you want till you get just above one of these numbers.

удачи и, надеюсь, мои решения будут работать в большинстве случаев.

Answer 8

Я хотел бы уточнить несколько моментов:

1. да, могут быть отрицательные весовые циклы.
2. n - количество ребер.
3. веса произвольны, а не только + 1 / -1.
4. Предположим, что путь длины O (n) существует, если у задачи есть решение. (n - количество ребер)

Answer 9

Я бы использовал здесь рекурсивное перебор: что-то вроде (псевдокод, чтобы убедиться, что он не зависит от языка)

вам понадобится:

• 2D-массив bools, показывающий, где выCAN и куда вы не можете пойти, это не должно включать «запрещенные значения», как перед отрицательным краем, вы можете добавить вертикальный и горизонтальный «перевод», чтобы убедиться, что он начинается в [0] [0]
• целое число (статическое), содержащее кратчайший путь
• 1D массив из 2 слотов, показывающий цель.[0] = x, [1] = y

вы сделаете:

function(int xPosition, int yPosition, int steps)
{
if(You are at target AND steps < Shortest Path)
    Shortest Path = steps
if(This Position is NOT legal)
    /*exit function*/
else
    /*try to move in every legal DIRECTION, not caring whether the result is legal or not
    but always adding 1 to steps, like using:*/
    function(xPosition+1, yPosition, steps+1);
    function(xPosition-1, yPosition, steps+1);
    function(xPosition, yPosition+1, steps+1);
    function(xPosition, yPosition-1, steps+1);
}

, затем просто запустите его с функцией (StartingX, StartingY, 0);

кратчайший путь будет содержаться в статическом внешнем int