python的BFS，DFS，UCS，A星算法

python的搜索算法，例如深度优先算法，A星算法，其中的h函数可以优化，原文件只采用了欧氏距离。

# -*- coding: utf-8 -*-
from queue import LifoQueue
from queue import Queue
from queue import PriorityQueue

class Graph:
    “““
    Defines a graph with edges each edge is treated as dictionary
    look up. function neighbors pass in an id and returns a list of 
    neighboring node
    
    “““
    def __init__（self）:
        self.edges = {}
        self.edgeWeights = {}
        self.locations = {}

    def neighbors（self id）:
        if id in self.edges:
            return self.edges[id]
        else:
            print（“The node “ id  “ is not in the graph“）
            return False

    # this function get the g（n） the cost of going from from_node to 
    # the to_node
    def get_cost（selffrom_node to_node）:
        #print（“get_cost for “ from_node to_node）
        nodeList = self.edges[from_node]
        #print（nodeList）
        try:
            edgeList = self.edgeWeights[from_node]
            return edgeList[nodeList.index（to_node）]
        except ValueError:
            print（“From node “ from_node “ to “ to_node “ does not exist a direct connection“）
            return False


def reconstruct_path（came_from start goal）:
    “““
    Given a dictionary of came_from where its key is the node 
    character and its value is the parent node the start node
    and the goal node compute the path from start to the end

    Arguments:
    came_from -- a dictionary indicating for each node as the key and 
                 value is its parent node
    start -- A character indicating the start node
    goal --  A character indicating the goal node

    Return:
    path. -- A list storing the path from start to goal. Please check 
             the order of the path should from the start node to the 
             goal node
    “““
    path = []
    ### START CODE HERE ### （≈ 6 line of code）





    ### END CODE HERE ###
    # return path

def heuristic（graph current_node goal_node）:
    “““
    Given a graph a start node and a next nodee
    returns the heuristic value for going from current node to goal node
    Arguments:
    graph -- A dictionary storing the edge information from one node to a list
             of other nodes
    current_node -- A character indicating the current node
    goal_node --  A character indicating the goal node

    Return:
    heuristic_value of going from current node to goal node
    “““
    heuristic_value = 0
    ### START CODE HERE ### （≈ 15 line of code）



    ### END CODE HERE ###
    return heuristic_value

def A_star_search（graph start goal）:
    “““
    Given a graph a start node and a goal node
    Utilize A* search algorithm by finding the path from 
    start node to the goal node
    Use early stoping in your code
    This function returns back a dictionary storing the information of each node
    and its corresponding parent node
    Arguments:
    graph -- A dictionary storing the edge information from one node to a list 
             of other nodes
    start -- A character ind

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-09-19 16:20  Homework1\
     目录           0  2018-09-18 13:45  Homework1\Homework1\
     文件        5792  2018-09-18 13:19  Homework1\Homework1\AStarSearch.py
     文件        4841  2018-09-18 13:20  Homework1\Homework1\BFSvsDFS.py
     文件      157476  2018-09-18 13:44  Homework1\Homework1\homework1.pdf
     文件        4722  2018-09-18 13:20  Homework1\Homework1\UniformCostSearch.py