Created
December 6, 2017 07:51
-
-
Save serser/94f90cc9453efab6ef34bf77939a1b27 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# https://classroom.udacity.com/courses/cs373/lessons/48646841/concepts/486468390923 | |
# ----------- | |
# User Instructions: | |
# | |
# Modify the the search function so that it becomes | |
# an A* search algorithm as defined in the previous | |
# lectures. | |
# | |
# Your function should return the expanded grid | |
# which shows, for each element, the count when | |
# it was expanded or -1 if the element was never expanded. | |
# | |
# If there is no path from init to goal, | |
# the function should return the string 'fail' | |
# ---------- | |
grid = [[0, 1, 0, 0, 0, 0], | |
[0, 1, 0, 0, 0, 0], | |
[0, 1, 0, 0, 0, 0], | |
[0, 1, 0, 0, 0, 0], | |
[0, 0, 0, 0, 1, 0]] | |
heuristic = [[9, 8, 7, 6, 5, 4], | |
[8, 7, 6, 5, 4, 3], | |
[7, 6, 5, 4, 3, 2], | |
[6, 5, 4, 3, 2, 1], | |
[5, 4, 3, 2, 1, 0]] | |
init = [0, 0] | |
goal = [len(grid)-1, len(grid[0])-1] | |
cost = 1 | |
delta = [[-1, 0 ], # go up | |
[ 0, -1], # go left | |
[ 1, 0 ], # go down | |
[ 0, 1 ]] # go right | |
delta_name = ['^', '<', 'v', '>'] | |
def search(grid,init,goal,cost,heuristic): | |
# ---------------------------------------- | |
# modify the code below | |
# ---------------------------------------- | |
closed = [[0 for col in range(len(grid[0]))] for row in range(len(grid))] | |
closed[init[0]][init[1]] = 1 | |
expand = [[-1 for col in range(len(grid[0]))] for row in range(len(grid))] | |
action = [[-1 for col in range(len(grid[0]))] for row in range(len(grid))] | |
x = init[0] | |
y = init[1] | |
g = 0 | |
open = [[g, x, y]] | |
found = False # flag that is set when search is complete | |
resign = False # flag set if we can't find expand | |
count = 0 | |
while not found and not resign: | |
if len(open) == 0: | |
resign = True | |
return "Fail" | |
else: | |
open.sort() | |
open.reverse() | |
next = open.pop() | |
x = next[1] | |
y = next[2] | |
g = next[0] | |
expand[x][y] = count | |
count += 1 | |
if x == goal[0] and y == goal[1]: | |
found = True | |
else: | |
buf = [] | |
for i in range(len(delta)): | |
x2 = x + delta[i][0] | |
y2 = y + delta[i][1] | |
if x2 >= 0 and x2 < len(grid) and y2 >=0 and y2 < len(grid[0]): | |
if closed[x2][y2] == 0 and grid[x2][y2] == 0: | |
g2 = g + cost | |
buf.append([g2, x2, y2]) | |
#print 'buf',buf, 'found:', found | |
if len(buf): | |
buf_s = sorted(buf, key=lambda x:heuristic[x[1]][x[2]], reverse=False) | |
open.append(buf_s[0]) | |
closed[buf_s[0][1]][buf_s[0][2]] = 1 | |
return expand | |
print search(grid,init,goal,cost,heuristic) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment