Поиск с подкреплением на ориентированных взвешенных графах
Мир абстракции выхолощено чист. Реальность и не полна, и изменяема.
В студенческие 90-е годы пришлось переходить границу в районе г. Печеры Псковской обл. Был ноябрь. Спустился ранним утром с холма. Перед речкой болотистая местность. Приходилось местами раздеваться и, держа одежду в одной руке, или переходить по пояс, или переплывать. Слышал по лаю собак, как наши погранцы пошли по следу. Но ни собакам, ни служивым в воду лезть уже не хотелось. Потом вечер. Темно. Ушел по полярной звезде к жд на северо-запад. Назад через 2 месяца почти также.
Хорошо, когда есть чёткие ориентиры. Искать маршруты, не имея всей информации — типичная и востребованная задача. На ориентированных взвешенных графах с ней лучше всего справляется алгоритм Дейкстры. Но этот алгоритм обхода «волной» не совсем похож на то, как движется человек.
Задача статьи показать как можно скрестить поиск с подкреплением и взвешенные ориентированные графы.
При такой постановке успешность будет зависеть от величины награды (величины ориентира) и дисконта ребер графа. Если величина награды больше суммы стоимости ребер по маршруту, то никаких проблем ориентирования не возникает. Это похоже на то, как вначале производится поиск и, если цель найдена, на этом месте ставим гору Алтая Белуху. По сути, получаем на выходе топографическую карту местности. Градиент которой всегда показывает направление к цели.
Высота над уровнем моря: 4 506 м
В противном случае могут возникнуть отрицательные значения по 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, 12, 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 Удачи.
