У меня странная ошибка при реализации поиска UCS aka Dijkstra. Мои узлы представлены позицией (x, y), направлением и типом земли. Чтобы быть более точным, я хочу иметь кратчайший путь между текущей позицией (программа о черепахе, которая хочет пить и может двигаться, поворачивая вправо или влево или идя вперед) и ближайшим источником воды.
У меня странная ошибка, когда в алгоритме поиска у меня нет тех же соседей вершин, которые уже проверены.
Это код для структуры данных:
import utils as ut
import copy
from collections import defaultdict
actions = ['forward','right','left']
class Node:
def __init__(self, x, y, direction, land):
self.x = x
self.y = y
self.direction = direction
self.land = land
def isWater(self):
return self.land=='water'
def realDirection(self):
if (self.direction == 0):
return 'North'
elif (self.direction == 1):
return 'East'
elif (self.direction == 2):
return 'South'
else:
return 'West'
def __eq__(self,other):
return (self.x,self.y,self.direction) == (other.x,other.y,other.direction)
def __str__(self):
return '('+str(self.x)+','+str(self.y)+')' + ' ' + self.realDirection()+ ' ' + self.land
def __hash__(self):
return hash((self.x, self.y, self.direction))
def action(self,other):
index = other.direction - self.direction
return actions[index%2]
class Vertex:
def __init__(self, node):
self.id = node
self.adjacent = {}
def __str__(self):
return str(self.id) + ' adjacent: ' + str([str(x.id) for x in self.adjacent])
def add_neighbor(self, neighbor, weight=0):
self.adjacent[neighbor] = weight
def get_connections(self):
return self.adjacent.keys()
def get_id(self):
return self.id
def get_weight(self, neighbor):
return self.adjacent[neighbor]
class Graph:
def __init__(self):
self.vert_dict = {}
self.num_vertices = 0
def __iter__(self):
return iter(self.vert_dict.values())
def add_vertex(self, node):
self.num_vertices = self.num_vertices + 1
new_vertex = Vertex(node)
self.vert_dict[node] = new_vertex
return new_vertex
def get_vertex(self, n):
if n in self.vert_dict:
return self.vert_dict[n]
else:
return None
def add_same_position_edges(self,position, cost = 1):
positions = [position]
base_dir = position.direction
positions.extend([copy.deepcopy(position) for i in range(3)])
# for v in positions:
# print(str(v))
index = 0
for pos in positions:
pos.direction = (base_dir + index) % 4
index+=1
self.add_vertex(pos)
print(str(pos))
for pos in positions :
if pos not in self.vert_dict:
self.add_vertex(pos)
n = len(positions)
for i in range(n):
self.vert_dict[positions[i]].add_neighbor(self.vert_dict[positions[(i+1)%n]], 1)
self.vert_dict[positions[i]].add_neighbor(self.vert_dict[positions[(i-1)%n]], 1)
def add_edge(self, frm, to, cost = 1):
"""if frm not in self.vert_dict:
self.add_vertex(frm)
if to not in self.vert_dict:
self.add_vertex(to)"""
self.add_same_position_edges(frm)
self.add_same_position_edges(to)
self.vert_dict[frm].add_neighbor(self.vert_dict[to], cost)
if frm.direction == to.direction:
fromprime,toprime = copy.deepcopy(frm),copy.deepcopy(to)
toprime.direction = (3-frm.direction) %3
fromprime.direction = (3-frm.direction) %3
if toprime not in self.vert_dict:
self.add_vertex(toprime)
if fromprime not in self.vert_dict:
self.add_vertex(fromprime)
self.vert_dict[toprime].add_neighbor(self.vert_dict[fromprime], cost)
else:
self.vert_dict[to].add_neighbor(self.vert_dict[frm], cost)
def get_vertices(self):
return self.vert_dict.keys()
и этот код для реализации UCS:
def UCS(graph, start):
frontier = ut.PriorityQueue()
frontier.push(start, 0)
came_from = {start: None}
cost_so_far = {start: 0}
while not frontier.isEmpty():
current , priority = frontier.pop()
if current.get_id().isWater():
return reconstruct_path(came_from,start,current)
for next in current.get_connections():
print(str(next))
new_cost = cost_so_far[current] + current.get_weight(next)
if next not in cost_so_far or new_cost < cost_so_far[next]:
cost_so_far[next] = new_cost
priority = new_cost
frontier.push(next, priority)
came_from[next] = current
print('here')
return came_from, cost_so_far
def reconstruct_path(came_from, start, goal):
current = goal
path = [current]
actions = []
while current != start:
previous = current
current = came_from[current]
current_action = previous.get_id().action(current.get_id())
path.append(current)
actions.append(current_action)
path.reverse()
actions.reverse()
actions.append('drink')
return path,actions
Мой тестовый код
if __name__ == '__main__':
gprime = Graph()
aprime = Node(1,1,0,'free')
gprime.add_vertex(aprime)
gprime.add_same_position_edges(aprime)
for v in gprime:
print('gprime.vert_dict[%s]=%s' %(str(v.get_id()), gprime.vert_dict[v.get_id()]))
g = Graph()
a = Node(1,1,0,'free')
b = Node(1,1,1,'free')
c = Node(1,2,1,'free')
d = Node(1,3,1,'free')
f = Node(1,4,1,'free')
j = Node(1,5,1,'free')
h = Node(1,6,1,'water')
g.add_vertex(a)
g.add_vertex(b)
g.add_vertex(c)
g.add_vertex(d)
g.add_vertex(f)
g.add_vertex(j)
g.add_vertex(h)
"""g.add_vertex('d')
g.add_vertex('e')
g.add_vertex('f')"""
g.add_edge(a, b, 1)
g.add_edge(b, c, 2)
g.add_edge(c, d, 2)
g.add_edge(d, f, 2)
g.add_edge(f, j, 2)
g.add_edge(j, h, 2)
"""g.add_edge('a', 'f', 14)
g.add_edge('b', 'c', 10)
g.add_edge('b', 'd', 15)
g.add_edge('c', 'd', 11)
g.add_edge('c', 'f', 2)
g.add_edge('d', 'e', 6)
g.add_edge('e', 'f', 9)"""
for v in g:
for w in v.get_connections():
vid = v.get_id()
wid = w.get_id()
print('( %s , %s, %3d)' % ( str(vid), str(wid), v.get_weight(w)))
for v in g:
print('g.vert_dict[%s]=%s' %(str(v.get_id()), g.vert_dict[v.get_id()]))
# print(a.action(b))
# print(b.action(c))
print(str(g.get_vertex(c))) # Different result than in the UCS
# in this line the result is:
# g.vert_dict[(1,2) East free]=(1,2) East free adjacent: ['(1,2) South free', '(1,2) North free', '(1,3) East free']
# And in the UCS THE RESULT IS (1,2) East free adjacent: ['(1,2) South free', '(1,2) North free']
# This is an example of where the problem is
path, actions = UCS(g,g.get_vertex(a))
print(actions)
Спасибо, что нашли время:)