Как найти многомерный путь с точной стоимостью 0 с весами 1, 0, -1 - программирование
Подтвердить что ты не робот

Как найти многомерный путь с точной стоимостью 0 с весами 1, 0, -1

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

Ответ 2

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