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

В студенческие 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 Удачи.

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