Как найти многомерный путь точной стоимости 0 с весами 1, 0, -1 - PullRequest
12 голосов
/ 29 апреля 2019

Мне был дан ориентированный граф с n узлами и ребрами с весами векторов (каждый вектор имеет длину m) чисел 1, 0, -1.Я хотел бы найти любой путь (или сказать, что такой путь не существует) от одного узла к другому (мы можем посещать узлы много раз), такая сумма его весов равна вектору только из нулей.Я думал о алгоритме обратного отслеживания bruteforce, но он не гарантирован, что он закончится.Можем ли мы как-то ограничить длину такого пути в терминах n и m?Пример графика для n = 8, m = 2 enter image description here Пример пути enter image description here

1 Ответ

0 голосов
/ 08 июля 2019

Мы можем ограничить длину пути сверху, отметив, что если такой путь существует, он должен состоять из смеси простого пути и некоторых циклов. Каждый из этих путей может иметь не более длины n. Для каждого цикла мы можем эффективно применить вектор, который соответствует изменению, которое происходит, пройдя один из таких циклов. Мы можем построить только m циклов, которые линейно независимы друг от друга (обратите внимание, что нам может потребоваться идти в обоих направлениях), что достаточно для покрытия любого вектора, который стоит сам простой путь, поэтому мы можем разрешить любой остаток, пройдя каждый цикл нужное количество раз (это зависит от стоимости такого преимущества). Количество раз, которое мы должны пройти через различные циклы, ограничено сверху чем-то, эквивалентным наименьшему общему множителю для эффективных длин каждого из векторов эффектов различных циклов, который имеет (грубую) асимтотическую границу O(n^2m). Если эта верхняя граница справедлива (вы можете построить случай, достаточно близкий к нему, разделив n на m областей размером примерно n / m, а затем сделать так, чтобы их длины простых чисел отсчитывались от n / m, а затем объединить их зависимости, что даст ´O ((n / m) ^ m) `), а затем решение в виде экспоненциального размера, что означает, что любой алгоритм, использующий (и сообщающий) несжатые длины пути, не поместится в PSPACE (который является надмножеством P и NP). ).

...