In [2]:

    

sss = set(['a', 'p', 's', 'h', 'm'])  
sss


    

    
Out[2]:





{'a', 'h', 'm', 'p', 's'}

In [8]:

    

import math
a = [1,2]
b = [3,4]


    

In [9]:

    

pow(2,3)
math.sqrt(4)

def heuristic_cost_estimate(start,goal):
	return math.sqrt(pow((start[0]-goal[0]),2)+pow((start[1]-goal[1]),2))


    

In [10]:

    

heuristic_cost_estimate(a,b)


    

    
Out[10]:





2.8284271247461903

In [21]:

    

import math

def heuristic_cost_estimate(start,goal):
    return math.sqrt(pow((start[0]-goal[0]),2)+pow((start[1]-goal[1]),2))


def dist_between(start,end):
    return math.sqrt(pow((start[0]-end[0]),2)+pow((start[1]-end[1]),2))


def get_best_f_score(input_set):
    idx = input_set.pop()
    best = idx
    bv = f_score[idx]
    for idx in input_set:
        if f_score[idx] < bv:
            best = idx
            bv = f_score[idx]
    return best  

def reconstruct_path(came_from, current_node):
    if came_from[current_node] is set:
        p = reconstruct_path(came_from, came_from[current_node])
        return p.append(current_node)
    else:
        return current_node
def shortest_path(M,start,goal):
    print("shortest path called")
    intersections = M.intersections
    roads = M.roads
    frontierset = set(start)
    explorededset = set()
    came_from = []
    g_score[start] = 0
    h_score[start] = heuristic_cost_estimate(intersections[start],intersections[goal])
    f_score[start] = g_score[start] + h_score[start]

    while frontierset:
        currentintersection = get_best_f_score(frontierset)
        explorededset.add(currentintersection)
        neighborsets = set(roads[currentintersection])
        if currentintersection == goal:
            return reconstruct_path(came_from, came_from[goal])
        else:
            for neighbor in neighborsets:
                if neighbor not in explorededset:
                    tentative_g_score = g_score[currentintersection] + dist_between(intersections[currentintersection],intersections[neighbor])
                    if neighbor not in frontierset:
                        frontierset.add(neighbor)
                        h_score[neighbor] = heuristic_cost_estimate(intersections[neighbor],intersections[goal])
                        tentative_is_better = true
                    elif (tentative_g_score < g_score[neighbor]):
                        tentative_is_better = true
                    else:
                        tentative_is_better = false

                    if tentative_is_better == true:
                        came_from[neighbor] = currentintersection
                        g_score[neighbor] = tentative_g_score
                        f_score[neighbor] = g_score[neighbor] + h_score[neighbor]

    return failure


    

In [ ]:

    

def reconstruct_path(came_from, current_node):
    if came_from[current_node] is set:
        p = reconstruct_path(came_from, came_from[current_node])
        return p.append(current_node)
    else:
        return current_node


    

In [25]:

    

g_score = {}
g_score[set] = 1
g_score[set] =5

g_score


    

    
Out[25]:





{set: 5}

In [4]:

    

def get_best_f_score(input_set,scoredict):
    print(input_set)
    idx = input_set.pop()
    print(input_set)
    print(idx)
    input_set.add(idx)
    print(input_set)
    best = idx
    bv = scoredict[idx]
    for idx in input_set:
        if scoredict[idx] < bv:
            best = idx
            bv = scoredict[idx]
    return best  

frontier = set([1,2,3,4,5])
score = {1:3,2:4,3:5,4:6,5:7}
get_best_f_score(frontier,score)


    

    




{1, 2, 3, 4, 5}
{2, 3, 4, 5}
1
{1, 2, 3, 4, 5}






    
Out[4]:





1