Найти путь в ориентированном графе заданной длины с учетом циклов и отрицательных длин - PullRequest
Новая
       61

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

0 голосов
/ 27 апреля 2018

У меня есть ориентированный граф с максимум 7 узлами. Каждый узел связан с каждым другим узлом (не включая себя, конечно) с направленным ребром, и ребра могут иметь как положительные, так и отрицательные веса. Моя цель - найти путь от одного данного узла к другому, чтобы путь имел определенную длину. Тем не менее, есть подвох. Мало того, что я могу использовать циклы, если я достигну конечного узла, путь не должен заканчиваться немедленно. Это означает, что у меня может быть простой путь, ведущий к конечному узлу, и затем петля из конечного узла, ведущая обратно в себя, что в конечном итоге. В то же время мне нужно максимизировать количество уникальных узлов, посещенных по этому пути, чтобы при наличии нескольких путей желаемой длины я получил тот, в котором больше всего узлов.

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

Кстати, я пишу это на python.

РЕДАКТИРОВАТЬ: Еще одна вещь, которую я забыл упомянуть, что пары направленных ребер между узлами не обязательно должны иметь одинаковый вес. Таким образом, A -> B может иметь вес -1, а B -> A может иметь вес 9.

РЕДАКТИРОВАТЬ 2: В соответствии с запросом, здесь ввод и вывод: мне дан график, начальный и конечный узлы и желаемая длина, и я возвращаю путь желаемой длины с наибольшим посещенные узлы.

1 Ответ

0 голосов
/ 27 апреля 2018

Звучит как проблема с комбинациями. Поскольку у вас нет фиксированного конечного состояния.

Давайте перечислим то, что мы знаем.

  • Каждый узел связан с любым другим узлом, хотя и направлен. Это полный орграф. Ссылка: https://en.wikipedia.org/wiki/Complete_graph.
  • Вы можете отключить алгоритм, когда он превысит желаемое расстояние.
  • Будьте осторожны с бесконечным циклом; возможно, если отрицательные веса могут равняться положительным.

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

def recursion(depth, graph, path, previous_node, score, results):
    // 1A. Return if max depth exceeded
    // 1B. Return if score exceeded 
    // 1C. Return if score match AND append path to results

    // 2. iterate and recurse through graph:
    for node in graph:
        path.append(node.name)
        score += node.weight
        recursion(depth, graph, path, node, score, results)

    return results

# The results should contain all the possible paths with the given score.

Это то, с чего я бы начал. Удачи.

...