#?-*-?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