Поиск с подкреплением на ориентированных взвешенных графах

Мир абстракции выхолощено чист. Реальность и не полна, и изменяема.

В студенческие 90-е годы пришлось переходить границу в районе г. Печеры Псковской обл. Был ноябрь. Спустился ранним утром с холма. Перед речкой болотистая местность. Приходилось местами раздеваться и, держа одежду в одной руке, или переходить по пояс, или переплывать. Слышал по лаю собак, как наши погранцы пошли по следу. Но ни собакам, ни служивым в воду лезть уже не хотелось. Потом вечер. Темно. Ушел по полярной звезде к жд на северо-запад. Назад через 2 месяца почти также.

Хорошо, когда есть чёткие ориентиры. Искать маршруты, не имея всей информации — типичная и востребованная задача. На ориентированных взвешенных графах с ней лучше всего справляется алгоритм Дейкстры. Но этот алгоритм обхода «волной» не совсем похож на то, как движется человек.

Задача статьи показать как можно скрестить поиск с подкреплением и взвешенные ориентированные графы.

При такой постановке успешность будет зависеть от величины награды (величины ориентира) и дисконта ребер графа. Если величина награды больше суммы стоимости ребер по маршруту, то никаких проблем ориентирования не возникает. Это похоже на то, как вначале производится поиск и, если цель найдена, на этом месте ставим гору Алтая Белуху. По сути, получаем на выходе топографическую карту местности. Градиент которой всегда показывает направление к цели.

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

Возникает вопрос: если цель все же найдена, но нет возможности построить такую карту, то можно ли все же проложить хоть какой-то маршрут, пусть и неоптимальный? Конечно, есть. Удалим в таком еще loop-ы наподобие того, например, как здесь: [1, 2, 3, 5, 2, 4, 9] -> [1, 2, 4, 9]

import random  zero = 0  roundLim = 3 #величина округления числа visited = {} #для отслеживания количества посещений состояний (вершин) cGraph = {} #пошагово переносятся состояния и переходы графа G qGraph = {} #пошагово обновляются q: currentSate: {nextState:q}) routes = {} #хранит маршруты, найденные в процессе поиска targetState limit = 100 #глубина поиска в графе epoch = 100 #количество попыток поиска цели targetCost = 4506 #величина награды (reward) #г. Белуха - высота над уровнем моря: 4 506 м targetState = 19 #целевое состояние (для сгенерированного графа ниже)  k = len(str(targetCost)) gamma = int('9'*k)/int('1'+'0'*k)#коэффициент дисконтирования  def set_q(currentState, nextStates):     for nextState in nextStates:         cMax = zero         if nextState in qGraph:             nnextStates = [nnextState for nnextState in qGraph[nextState]]             for nnextState in nnextStates:                 if gamma*qGraph[nextState][nnextState] > cMax:                     cMax = gamma*qGraph[nextState][nnextState]             if cMax - cGraph[currentState][nextState] > zero:                 qGraph[currentState][nextState] = \                   round(cMax - gamma*cGraph[currentState][nextState], \                   roundLim)             else: qGraph[currentState][nextState] = zero         if nextState == targetState:             qGraph[currentState][nextState] = targetCost - \               cGraph[currentState][nextState]             return          def get_path(currentState):     lim = limit     path = []     while lim > 0 and currentState != None:         path += [currentState];         visited[currentState] +=1         lim -=1         if currentState == targetState:             return path           nextStateQ = best_q(currentState)              if len(path) ==1:             currentState = best_q(currentState)             continue         currentState = nextStateQ     return []   def get_first_route(startState):     for state in routes:         if targetState in routes[state] and startState in routes[state]:             startStateInd = routes[state].index(startState)             return routes[state][startStateInd:]              def best_q(currentState):     try:         toSorted = [(nextState, qGraph[currentState][nextState]) \           for nextState in qGraph[currentState]]         nextState = sorted(toSorted, key = lambda t: t[1], \           reverse=True)[0][0]         return  nextState     except:          return       def next_states(currentState):     if currentState not in cGraph:         cGraph[currentState] = G[currentState]         qGraph[currentState] = {}         for nextState in cGraph[currentState]:             qGraph[currentState][nextState] = zero     if currentState not in visited:         visited[currentState] = 1     else:          visited[currentState] += 1     nextStates = [nextState for nextState in G[currentState]]     for nextState in nextStates:        if nextState not in visited:            visited[nextState] = zero     set_q(currentState, nextStates)     return nextStates        def less_visited(currentState, nextStates):     if not nextStates: return     toSorted = [(nextState, visited[nextState]) \       for nextState in nextStates]     sortedStates = sorted(toSorted, key = lambda t: t[1])     minVisited = [nextState for nextState in sortedStates \       if sortedStates[0][1] == nextState[1]]     nextState = random.choice(minVisited)[0]     visited[nextState] +=1     return nextState      def search_target(currentState, route):     lim = limit     route.append(currentState)     nextStates = next_states(currentState)     while lim > 0:         if not nextStates:              return []         lim -=1         if currentState == targetState:             return route          currentState = less_visited(currentState, nextStates)         route.append(currentState)         nextStates = next_states(currentState)         return []      def delete_loop(route):     sRoute = []     i = 0     while i < len(route)-1:         if route[i] in route[i+1:]:             i = len(route) - route[::-1].index(route[i]) -1          sRoute.append(route[i])         i +=1     if route[-1] not in sRoute:          sRoute.append(route[-1])     return sRoute  #сгенерирован с помощью pyrgg.     G = {   0 : {6: 7, 14: 7, 0: 16},   16 : {3: 9, 17: 1},   6 : {18: 0, 11: 7, 17: 3},   14 : {18: 9, 17: 3, 8: 4},   1 : {17: 5, 2: 2, 12: 2, 3: 1, 5: 6, 18: 4, 1: 12},   12 : {7: 2, 19: 6, 3: 8, 2: 2},   18 : {10: 8, 2: 6},   5 : {16: 9, 2: 6, 13: 2, 9: 2, 19: 9, 15: 2, 10: 4},   3 : {15: 5, 19: 2, 8: 0, 10: 6},   17 : {},   2 : {11: 5},   11 : {0: 0, 13: 0, 17: 9},   10 : {13: 3, 12: 7, 2: 6},   8 : {9: 0, 15: 6, 14: 9},   19 : {15: 6, 0: 6},   15 : {16: 6},   4 : {8: 2, 18: 4, 11: 9, 16: 0, 10: 8, 15: 5, 14: 0, 9: 6, 5: 9, 4: 14},   9 : {13: 8, 18: 7, 12: 8, 17: 0, 2: 4, 16: 0},   13 : {18: 7},   7 : {19: 6, 9: 7, 7: 12}, }       def main():     gStates = [state for state in G]         route = []     startState = 0     for i in range(1, epoch+1):         initState = random.choice(gStates)         #initState = startState         rRoute = search_target(initState, route.copy())         if rRoute:             routes[rRoute[0]] = delete_loop(rRoute)          currentState = startState      path = get_path(currentState)     #print(rRoute, "\n\n", visited, "\n\n", cGraph, "\n\n", qGraph)       if path:         print("\npath =", path)     else:         path = get_first_route(startState)         print("get_first_route =", path)      main() 

Наиболее частотный найденный путь: path = [0, 14, 8, 9, 16, 3, 19]

Изменим targetCost. Приравняем пяти, например. В этом случае придется извлекать из памяти «то, что есть». Маршрут может быть не найден вообще. Или найден хоть какой-то, например, такой: path = [0, 14, 8, 15, 16, 3, 19]

Для сравнения … из мира истины.

import math  graph = { 0 : {6: 7, 14: 7, 0: 16} , 16 : {3: 9, 17: 1} , 6 : {18: 0, 11: 7, 17: 3} , 14 : {18: 9, 17: 3, 8: 4} , 1 : {17: 5, 2: 2, 12: 2, 3: 1, 5: 6, 18: 4, 1: 12} , 12 : {7: 2, 19: 6, 3: 8, 2: 2} , 18 : {10: 8, 2: 6} , 5 : {16: 9, 2: 6, 13: 2, 9: 2, 19: 9, 15: 2, 10: 4} , 3 : {15: 5, 19: 2, 8: 0, 10: 6} , 17 : {} , 2 : {11: 5} , 11 : {0: 0, 13: 0, 17: 9} , 10 : {13: 3, 12: 7, 2: 6} , 8 : {9: 0, 15: 6, 14: 9} , 19 : {15: 6, 0: 6} , 15 : {16: 6} , 4 : {8: 2, 18: 4, 11: 9, 16: 0, 10: 8, 15: 5, 14: 0, 9: 6, 5: 9, 4: 14} , 9 : {13: 8, 18: 7, 12: 8, 17: 0, 2: 4, 16: 0} , 13 : {18: 7} , 7 : {19: 6, 9: 7, 7: 12} , }  source = 0 destination = 19  unvisited = graph shortest_distances = {} route = [] path_nodes = {}  for nodes in unvisited:     shortest_distances[nodes] = math.inf shortest_distances[source] = 0  while unvisited:     min_node = None     for current_node in unvisited:         if min_node is None:             min_node = current_node         elif shortest_distances[min_node] \             > shortest_distances[current_node]:             min_node = current_node     for (node, value) in unvisited[min_node].items():         if value + shortest_distances[min_node] \             < shortest_distances[node]:             shortest_distances[node] = value \                 + shortest_distances[min_node]             path_nodes[node] = min_node     unvisited.pop(min_node) node = destination  while node != source:     try:         route.insert(0, node)         node = path_nodes[node]     except Exception:         print('Path not reachable')         break route.insert(0, source)  print(route) #[0, 14, 8, 9, 16, 3, 19] print("\n", shortest_distances)

PS Удачи.