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

Ответ 1

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

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

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

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

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

Ответ 2

Питер де Риваз отметил в комментарии, что эта проблема включает HAMILTONIAN PATH как частный случай. Его объяснение было немного кратким, и мне потребовалось некоторое время, чтобы разобраться в деталях, поэтому я нарисовал несколько диаграмм на благо других, которые могли бы бороться. Я сделал эту публикацию сообщества сообщений.

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

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

Проще всего думать о том, что эта конструкция эквивалентна началу с оценкой 2 ⁿ - 1, а затем вычитая 2 ⁱ каждый раз, когда вы посещаете w _{IJсуб > . (Вот как я нарисовал график ниже.)}

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

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

Ответ 3

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

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

• Весы +/- 1.
• n - число вершин

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

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

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

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

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

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

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

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

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

Затем мы можем построить пути от источника к 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.

Если 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 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)

Ответ 4

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

Ответ 5

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

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

• 2D-массив bools, показывающий, где вы МОЖЕТЕ и где вы НЕ МОЖЕТЕ идти, это НЕ должно включать "запрещенные значения", например, перед отрицательным краем, вы можете добавить вертикальный и горизонтальный "перевод", чтобы убедиться, что он запускается в [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);
}

тогда просто запустите его с помощью function (StartingX, StartingY, 0);

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

Ответ 6

Я хотел бы прояснить несколько моментов:

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

Ответ 7

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

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

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

Ideas:

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

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

2. найти ближайший положительный цикл до начала node, обозначить расстояние от начала как 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.

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

Ответ 8

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

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

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

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

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

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

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

Ответ 9

Шаг 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)

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