Каков наилучший алгоритм для перемещения графика с отрицательными узлами и узлами петли

Question

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

1. узел А дает 10 баллов до объекта

2. узел В принимает 15 от объекта

3. узел С дает 20 баллов до объекта

route = ""

стартовый узел - это A, а endin г узел С

дал граф структура, как: -

a(+10)-----b(-15)-----c+20 

node() means the node loops to itself - and + are the adjustments 

узлы с нет петель не с + 20, так что узел с имеет положительную регулировку 20, но не имеет петель

если бот или объект имеет 10 очков в его ресурс, то лучший путь будет: -

a > b > c the object would have 25 points when it arrives at c 

маршрут = «а, б, в»

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

если бот начал только 5 очков, то лучший путь будет

a > a > b > c the bot would have 25 points when arriving at c 

маршрут = «а, а, б, в»

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

такой маршрут будет очередью возврата.

Более трудный пример приведет много вперед и назад

бот имеет 10 очков

a(+10)-----b(-5)-----c-30 

а> Ь> а> Ь> а> Ь> а> Ь> а> Ь > c с 5 очками влево.

другой способ бот может сделать это: -

а> а> а> Ь> с

это более эффективный способ, но как, черт возьми, вы можете запрограммировать это отчасти мой вопрос ,

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

может быть рекурсивным в некотором роде или в какой-то форме эвристики?

---

со ссылкой на вашу аналогию: -

Я думаю, что я получаю то, что вы имеете в виду, немного псевдо будет понятнее, до сих пор маршрут()

q.add(v) 
best=v 
hash visited(v,true) 

while(q is not empty) 
    q.remove(v) 
    for each u of v in G 

     if u not visited before 
      visited(u,true) 
      best=u=>v.dist 
     else 
      best=v=>u.dist 

Answer 1

Это простая проблема динамического программирования.

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

Предположим, что у нас есть эти данные для n шагов. Тогда для n + 1 мы начинаем с чистого листа, а затем берем каждый ответ для n'th, переместите его на один узел вперед, и если мы приземлимся на узел, у нас нет данных, или же, лучше, чем лучшее найденное, затем мы обновляем данные для этого узла с нашим улучшенным счетом и добавляем маршрут (только этот узел ссылается на предыдущий связанный список).

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

========

Вот реальный код реализации алгоритма:

class Graph: 
    def __init__(self, nodes=[]): 
     self.nodes = {} 
     for node in nodes: 
      self.insert(node) 

    def insert(self, node): 
     self.nodes[ node.name ] = node 

    def connect(self, name1, name2): 
     node1 = self.nodes[ name1 ] 
     node2 = self.nodes[ name2 ] 
     node1.neighbors.add(node2) 
     node2.neighbors.add(node1) 

    def node(self, name): 
     return self.nodes[ name ] 

class GraphNode: 
    def __init__(self, name, score, neighbors=[]): 
     self.name = name 
     self.score = score 
     self.neighbors = set(neighbors) 

    def __repr__(self): 
     return self.name 

def find_path (start_node, start_score, end_node): 
    prev_solution = {start_node: [start_score + start_node.score, None]} 
    room_to_grow = True 
    while end_node not in prev_solution: 
     if not room_to_grow: 
      # No point looping endlessly... 
      return None 
     room_to_grow = False 
     solution = {} 
     for node, info in prev_solution.iteritems(): 
      score, prev_path = info 
      for neighbor in node.neighbors: 
       new_score = score + neighbor.score 
       if neighbor not in prev_solution: 
        room_to_grow = True 
       if 0 < new_score and (neighbor not in solution or solution[neighbor][0] < new_score): 
        solution[neighbor] = [new_score, [node, prev_path]] 
     prev_solution = solution 
    path = prev_solution[end_node][1] 
    answer = [end_node] 
    while path is not None: 
     answer.append(path[0]) 
     path = path[1] 
    answer.reverse() 
    return answer 

А вот пример того, как использовать его:

graph = Graph([GraphNode('A', 10), GraphNode('B', -5), GraphNode('C', -30)]) 
graph.connect('A', 'A') 
graph.connect('A', 'B') 
graph.connect('B', 'B') 
graph.connect('B', 'B') 
graph.connect('B', 'C') 
graph.connect('C', 'C') 

print find_path(graph.node('A'), 10, graph.node('C')) 

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

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

Answer 2

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

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

Если ваш график имеет петли, которые полезны для перемещения (т. Е. Уменьшают стоимость или увеличивают точки с помощью корректировок), то лучший путь не определен, потому что повторение цикла еще раз улучшит вашу оценку.

Answer 3

Вот некоторые psuedocode

steps = [] 
steps[0] = [None*graph.#nodes] 
step = 1 
while True: 
    steps[step] = [None*graph.#nodes] 
    for node in graph: 
     for node2 in graph: 
      steps[step][node2.index] = max(steps[step-1][node.index]+node2.cost, steps[step][node2.index]) 

    if steps[step][lastnode] >= 0: 
     break;