พื้นฐาน AI 🤖: EP 2 Classical Search
หัวข้อใน ep นี้ได้แก่
1. Problem-solving agent
Problem-solving agent คือ เมื่อไม่ชัดเจนว่าการกระทำ (action) ที่ถูกต้องคืออันไหน agent จะมีการวางแผนล่วงหน้า (planning) โดยพิจารณาลำดับการกระทำที่นำไปสู่เป้าหมาย โดยขั้นตอนการคำนวณเพื่อสร้างลำดับการกระทำนั้นเรียกว่าการ “search”
องค์ประกอบของปัญหา search
- state space: S คือ set สถานะทั้งหมดที่เป็นไปได้
- initial state: s₀ คือ สถานะเริ่มต้น
- action: A(s) คือ set ของการกระทำทั้งหมดที่เป็นไปได้ ณ สถานะ s
- transition model: Result(s, a) คือ ผลลัพธ์ของการกระทำ a ณ สถานะ s
- goal test: G(s) เช็คว่าสถานะ s คือสถานะเป้าหมายหรือไม่
- action cost: c(s, a, s’) ต้นทุนของการกระทำ a ณ สถานะ s เพื่อไปสถานะ s’
โดยลำดับการกระทำจากสถานะเริ่มต้นไปยังสถานะเป้าหมายเรียกว่า “solution”, “optimal solution” คือ solution ที่มีต้นทุน (cost) น้อยที่สุด
2. ตัวอย่างปัญหา
เที่ยวรอบเกาะรัตนโกสินทร์ โดยเดินทางจากพิพิธภัณฑสถานแห่งชาติไปภูเขาทอง ซึ่งมี landmark ต่างๆให้ผ่านตามภาพด้านล่าง ดังนั้นกำหนดองค์ประกอบของปัญหา search นี้ได้ว่า
S = {พระบรมหาราชวัง, วัดโพธิ์, พิพิธภัณฑสถานแห่งชาติ, ป้อมพระสุเมรุ, อนุสาวรีย์ประชาธิปไตย, เสาชิงช้า, ภูเขาทอง}
s₀ = พิพิธภัณฑสถานแห่งชาติ
A(s) = ไป landmark อื่นที่อยู่ติดกัน
Result(s, a) = ถึง landmark ถัดไป
G(s) = s ปัจจุบันคือภูเขาทองหรือไม่
c(s, a, s`) = ระยะทางจาก s ไป s`
ทำเป็นเส้นทาง (path) อย่างง่ายตามภาพด้านล่าง (ตัวเลขบนเส้นแทนระยะทาง หน่วยกิโลเมตร)
3. Search Algorithm
การออกแบบ search algorithm สิ่งที่ต้องคำนึงได้แก่ state space graphs และ search trees
State Space Graphs
คือการแสดงออกทางคณิตศาสตร์ของปัญหา search มีส่วนประกอบคือ set ของ node แทนสถานะ และเส้นเชื่อม (edge) แทนการเปลี่ยนสถานะ โดยหัวลูกศรชี้ไปสถานะใหม่ที่สามารถเปลี่ยนไปได้ ถ้ามีคู่สถานะที่สามารถเปลี่ยนกลับไปมาได้ เส้นเชื่อมก็จะมีลูกศรทั้ง 2 หัว จากปัญหาเที่ยวรอบเกาะรัตนโกสินทร์ เขียน state space graph ได้ตามภาพด้านล่าง
เขียนในภาษา python ได้
graph = {
"Phra_Sumen_Fort" : ["National_Museum", "Democracy_Monument", "Golden_Mount"],
"National_Museum" : ["Phra_Sumen_Fort", "Democracy_Monument", "Giant_Swing", "Grand_Palace"],
"Democracy_Monument" : ["Phra_Sumen_Fort", "National_Museum", "Golden_Mount", "Giant_Swing"],
"Golden_Mount" : ["Phra_Sumen_Fort", "Democracy_Monument", "Giant_Swing"],
"Grand_Palace" : ["National_Museum", "Wat_Pho"],
"Giant_Swing" : ["National_Museum", "Democracy_Monument", "Golden_Mount", "Wat_Pho"],
"Wat_Pho" : ["Grand_Palace", "Giant_Swing"]
}Search Trees
เป็นแผนผังต้นไม้โดย root ด้านบนคือสถานะเริ่มต้น และ node ลูกด้านล่างคือสถานะใหม่ทั้งหมดที่สามารถเปลี่ยนไปได้ ดังนั้นสถานะเดิมใน search tree สามารถปรากฏได้หลายครั้ง (เส้นประคือละรายละเอียดด้านล่างเอาไว้) จากปัญหาเที่ยวรอบเกาะรัตนโกสินทร์ เขียน search tree ได้ตามภาพด้านล่าง
เขียนในภาษา python ได้
class tree:
def __init__ (self, value):
self.value = value
self.children = []
Phra_Sumen_Fort = tree("Phra_Sumen_Fort")
National_Museum = tree("National_Museum")
Democracy_Monument = tree("Democracy_Monument")
Golden_Mount = tree("Golden_Mount")
Grand_Palace = tree("Grand_Palace")
Giant_Swing = tree("Giant_Swing")
Wat_Pho = tree("Wat_Pho")
Phra_Sumen_Fort.children = [National_Museum, Democracy_Monument, Golden_Mount]
National_Museum.children = [Phra_Sumen_Fort, Democracy_Monument, Giant_Swing, Grand_Palace]
Democracy_Monument.children = [Phra_Sumen_Fort, National_Museum, Golden_Mount, Giant_Swing]
Golden_Mount.children = [Phra_Sumen_Fort, Democracy_Monument, Giant_Swing]
Grand_Palace.children = [National_Museum, Wat_Pho]
Giant_Swing.children = [National_Museum, Democracy_Monument, Golden_Mount, Wat_Pho]
Wat_Pho.children = [Grand_Palace, Giant_Swing]
จากกราฟเห็นได้ว่า agent เข้าไปในลูปซ้ำแล้วซ้ำเล่า วิธีการแก้ปัญหาคือ
- กำหนดความลึกของแผนผังการ search
- ไม่อนุญาตให้เปลี่ยนมาเป็นสถานะเดิมหลายครั้ง
4. Uninformed Search
หรือ blind search คือการ search โดยปราศจากข้อมูลอื่นนอกจากส่วนที่เป็นองค์ประกอบของปัญหา search มี search algorithm ที่เกี่ยวข้องได้แก่ Breadth-First Search, Depth-First Search, Uniform-Cost Search และ Iterative deepening depth-first search
Breadth-First Search (ฺBFS)
กรณีเป็น graph เข้าถึง node เริ่มต้นก่อน แล้วไป node เพื่อนบ้านทุก node ของ node นั้น แล้วค่อยไปทุก node เพื่อนบ้านของเพื่อนบ้านไปเรื่อยๆ การเขียนโค๊ตใข้หลักการ FIFO (First-In-First-Out) หรือ queue จากภาพด้านล่างสีดำคือ node ที่ถูกเข้าถึงแล้ว สีเทาคือ node เพื่อนบ้านของ node ที่ถูกเข้าถึง และจะถูกเข้าถึงในลำดับต่อไป
จากภาพด้านบนเขียนในภาษา python ได้
import queue
graph = {
"A" : ["B", "C"],
"B" : ["A", "D", "E"],
"C" : ["A", "F", "G"],
"D" : ["B"],
"E" : ["B", "F", "H"],
"F" : ["C", "E", "G"],
"G" : ["C", "F"],
"H" : ["E"]
}
def bfs(graph, start):
# สร้าง set ที่เก็บ node ที่เคยเข้าถึง
visited = set()
# นำ node เริ่มต้นเข้าไปใน queue และ visited
Q = queue.Queue()
Q.put(start)
visited.add(start)
while not Q.empty():
# ดึงสมาชิกตัวแรกของ queue ออกมา
current = Q.get()
print(current, end=" ")
# เช็ค node เพื่อนบ้านของสมาชิกตัวแรกของ queue และหาก node เพื่อนบ้านนั้นยังไม่ถูกเข้าถึงนำต่อเข้าไปใน queue และ visited
for neighbor in graph[current]:
if neighbor not in visited:
Q.put(neighbor)
visited.add(neighbor)
bfs(graph, "A")กรณีเป็น tree จะเข้าถึง node เรียงตามระดับความลึก โดยเริ่มจาก root ก่อน แล้วไป children node ทุก node ของ root แล้วลงมาเรื่อยๆจนกว่าจะครบทุก node การเขียนโค๊ตใข้หลักการ FIFO เช่นกัน
จากภาพด้านบนเขียนในภาษา python ได้
class tree:
def __init__ (self, value):
self.value = value
self.children = []
root = tree(1)
node2 = tree(2)
node3 = tree(3)
node4 = tree(4)
node5 = tree(5)
node6 = tree(6)
node7 = tree(7)
node8 = tree(8)
node9 = tree(9)
node10 = tree(10)
root.children = [node2, node3, node4]
node2.children = [node5]
node3.children = [node6, node7]
node4.children = [node8]
node5.children = [node9]
node6.children = [node10]
def bfs(root):
# ถ้าเป็นต้นไม้เปล่าไม่ต้องทำอะไร
if not root:
return
# นำ root เข้าไปใน queue แล้วรันลูปจนกว่า queue จะว่าง
queue = [root]
while queue:
# เข้าถึงสมาชิกตัวแรกของ queue
current = queue.pop(0)
print(current.value, end=" ")
# นำ node ลูกแต่ละ node เข้าไปใน queue
for child in current.children:
queue.append(child)
bfs(root)Depth-first search (DFS)
กรณีเป็น graph เข้าถึง node เริ่มต้นก่อน แล้วไป 1 ใน node เพื่อนบ้านของ node นั้น แล้ว ค่อยไป 1 ใน node เพื่อนบ้านของเพื่อนบ้านไปเรื่อยๆ ไปไกลที่สุดเท่าที่จะไปได้ เมื่อไปสุดท้ายแล้ว กลับมา node ที่ใกล้ node แรกมากที่สุดที่ยังไม่ถูกเข้าถึง แล้วทำแบบเดิมจนกว่าจะไปครบทุก node การเขียนโค๊ตใช้หลักการ LIFO (Last-In-First-Out) หรือ stack
จากภาพด้านบนเขียนเป็นภาษา python ได้
graph = {
"1" : ["2", "3"],
"2" : ["3", "4"],
"3" : ["5"],
"4" : ["3"],
"5" : ["7"],
"6" : ["4", "5"],
"7" : ["6"]
}
def dfs(graph, start):
# สร้าง set ที่เก็บ node ที่เคยเข้าถึง
visited = set()
# นำ node เริ่มต้นเข้าไปใน queue และ visited
stack = [start]
visited.add(start)
while stack:
# ดึงสมาชิกตัวแรกของ stack ออกมา
current = stack.pop()
print(current, end=" ")
# เช็ค node เพื่อนบ้านของสมาชิกตัวล่าสุดที่เพิ่งเข้ามาของ stack และหาก node เพื่อนบ้านนั้นยังไม่ถูกเข้าถึงนำต่อเข้าไปใน stack และ visited
for neighbor in reversed(graph[current]):
if neighbor not in visited:
stack.append(neighbor)
visited.add(neighbor)
dfs(graph, "1")กรณีเป็น tree เข้าถึง node จาก root ลงไปยัง leaf แล้วกลับขึ้นมา node ที่ใกล้ root ที่สุดที่ยังไม่ถูกเข้าถึง แล้วไล่ลงไปยัง leaf อีกครั้ง ทำแบบเดิมไปมาจนกว่าจะเข้าถึงครบทุก node การเขียนโค๊ตใช้หลักการ LIFO เช่นกัน
จากภาพด้านบนเขียนเป็นภาษา python ได้
class tree:
def __init__ (self, value):
self.value = value
self.children = []
root = tree(1)
node2 = tree(2)
node3 = tree(3)
node4 = tree(4)
node5 = tree(5)
node6 = tree(6)
node7 = tree(7)
node8 = tree(8)
node9 = tree(9)
node10 = tree(10)
root.children = [node2, node5, node9]
node2.children = [node3]
node3.children = [node4]
node5.children = [node6, node8]
node6.children = [node7]
node9.children = [node10]
def dfs(root):
# ถ้าเป็นต้นไม้เปล่าไม่ต้องทำอะไร
if not root:
return
# นำ root เข้าไปใน stack แล้วรันลูปจนกว่า stack จะว่าง
stack = [root]
while stack:
# เข้าถึงสมาชิกตัวแรกของ stack
current = stack.pop()
print(current.value, end=" ")
# นำ node ลูกแต่ละ node เข้าไปใน stack
for child in reversed(current.children):
stack.append(child)
dfs(root)Uniform-cost search (UCS)
เลือกเข้าถึง node (กำหนดเป็น node n) ที่มี cost ของเส้นทางต่ำสุด (กำหนดเป็น g(n)) การเขียนโค๊ตใช้ queue เช่นเดียวกับ BFS แต่ค่าที่เรียงเรียงตาม g(n) จากปัญหาเที่ยวรอบเกาะรัตนโกสินทร์ เขียน UCS ในภาษา python ได้
import heapq
graph = {
"Phra_Sumen_Fort" : {"National_Museum": 1.6, "Democracy_Monument": 1.3, "Golden_Mount": 2.1},
"National_Museum" : {"Phra_Sumen_Fort": 1.6, "Democracy_Monument": 2.4, "Giant_Swing": 2.8, "Grand_Palace": 2.9},
"Democracy_Monument" : {"Phra_Sumen_Fort": 1.3, "National_Museum": 2.4, "Golden_Mount": 1.2, "Giant_Swing": 0.8},
"Golden_Mount" : {"Phra_Sumen_Fort": 2.1, "Democracy_Monument": 1.2, "Giant_Swing": 1.7},
"Grand_Palace" : {"National_Museum": 2.9, "Wat_Pho": 1.4},
"Giant_Swing" : {"Golden_Mount": 1.7, "Democracy_Monument": 0.8, "National_Museum": 2.8, "Wat_Pho": 1.6},
"Wat_Pho" : {"Grand_Palace": 1.4, "Giant_Swing": 1.6}
}
start = "National_Museum"
goal = "Golden_Mount"
def ucs(graph, start, goal):
# สร้าง queue ที่เรียงตาม cost
Q = [(0, start, [start])] # (cost นับตั้งแต่ start, node ปัจจุบัน, เส้นทางตั้งแต่ start จนถึง node ปัจจุบัน)
heapq.heapify(Q)
# dict ที่เก็บ cost ต่ำสุดในการเข้าถึงแต่ละ node
min_cost = {start: 0}
while Q:
current_cost, current_node, path = heapq.heappop(Q)
# ถ้าเจอ node เป้าหมายแล้ว ก็ return เส้นทางนั้นออกมา
if current_node == goal:
return path
# เช็คทุก node ที่ต่อกับ node ปัจจุบัน
for neighbor, cost in graph.get(current_node).items():
new_cost = current_cost + cost
new_path = path + [neighbor]
# ถ้า node นั้นยังไม่เคยเข้าถึง หรือ เจอเส้นทางที่ใช้ cost น้อยกว่าในการไป node นั้น เพิ่มข้อมูลเส้นทางนั้นเข้าไปใน queue
if neighbor not in min_cost or new_cost < min_cost[neighbor]:
min_cost[neighbor] = new_cost
heapq.heappush(Q, (new_cost, neighbor, new_path))
# ถ้าเช็คทุก node แล้ว ไม่เจอเส้นทางจาก node เริ่มต้นไป node เป้าหมาย return เป็นค่าว่าง
return None
print(ucs(graph, start, goal))ได้ผลลัพธ์คือ ['National_Museum', 'Democracy_Monument', 'Golden_Mount']
จาก search ทั้ง 3 แบบ ข้างต้นสามารถวิคราะห์คุณสมบัติมา 4 ด้านคือ
- Complete: รับประกันว่าสามารถหาคำตอบเจอ หากว่าปัญหานั้นมีคำตอบอยู่จริง
- Optimal: รับประกันว่าจะเจอเส้นทางที่สั้นที่สุด
- Time Complexity: ความซับซ้อนด้านเวลา / เวลาที่ต้องใช้ในการ run algorithm
- Space Complexity: ความซับซ้อนด้านพื้นที่ / memory ที่ต้องใช้ในการ run algorithm
โดย
- b: จำนวน node ลูกของแต่ละ node (branching factor)
- m: ความลึกสูงสุด
- s: ความลึกของคำตอบที่สั้นที่สุด
- C*: cost ที่ต่ำสุดของคำตอบ
- ϵ: cost ที่ต่ำสุดของเส้นเชื่อม (edge)
สาเหตุที่ DFS ไม่รับรองว่าสามารถหาคำตอบเจอ เพราะมีบางปัญหาเมื่อสร้างเป็น tree แล้ว จะมีความลึกเป็นอนันต์ (เช่น ปัญหาเที่ยวรอบเกาะรัตนโกสินทร์)
Iterative deepening depth-first search (IDS)
คือการผสมกันระหว่างข้อดีด้านความซับซ้อนด้านเวลาของ BSF และความซับซ้อนด้านพื้นที่ DFS โดยกำหนดความลึกสูงสุด ออกมาเป็น subtree แล้วค่อยเพิ่มความลึกไปทีละ 1 คล้าย BFS แต่ในsubtree ใช้ DFS ในการเข้าถึง node ดังนั้นได้ความซับซ้อนด้านเวลาคือ O(b^s) และความซับซ้อนด้านพื้นที่คือ O(bs) จากปัญหาเที่ยวรอบเกาะรัตนโกสินทร์เขียนเป็นภาษา python ได้ (ไม่สนใจ cost)
class tree:
def __init__ (self, value):
self.value = value
self.children = []
Phra_Sumen_Fort = tree("Phra_Sumen_Fort")
National_Museum = tree("National_Museum")
Democracy_Monument = tree("Democracy_Monument")
Golden_Mount = tree("Golden_Mount")
Grand_Palace = tree("Grand_Palace")
Giant_Swing = tree("Giant_Swing")
Wat_Pho = tree("Wat_Pho")
Phra_Sumen_Fort.children = [National_Museum, Democracy_Monument, Golden_Mount]
National_Museum.children = [Phra_Sumen_Fort, Democracy_Monument, Giant_Swing, Grand_Palace]
Democracy_Monument.children = [Phra_Sumen_Fort, National_Museum, Golden_Mount, Giant_Swing]
Golden_Mount.children = [Phra_Sumen_Fort, Democracy_Monument, Giant_Swing]
Grand_Palace.children = [National_Museum, Wat_Pho]
Giant_Swing.children = [National_Museum, Democracy_Monument, Golden_Mount, Wat_Pho]
Wat_Pho.children = [Grand_Palace, Giant_Swing]
def depth_limited_dfs(root, goal, depth_limit):
# stack เก็บ path ของแต่ละ node
stack = [(root, [root.value])]
while stack:
node, path = stack.pop()
if node.value == goal:
return path
# เช็คความลึกจากความยาว path
if len(path) <= depth_limit:
# นำ node ลูกเข้าไปใน stack แบบ DFS
for child in reversed(node.children):
stack.append((child, path + [child.value]))
return None
def ids(root, goal):
depth_limit = 0
# ถ้ายังไม่เจอ goal เพิ่มความลึกไปเรื่อยๆทีละ 1
while True:
result = depth_limited_dfs(root, goal, depth_limit)
if result is not None:
return result
depth_limit += 1
root = National_Museum
goal = "Golden_Mount"
print(ids(root, goal))ได้ผลลัพธ์คือ ['National_Museum', 'Phra_Sumen_Fort', 'Golden_Mount']
5. Heuristic Function
กำหนดเป็น h(n) คือ cost ประมาณการที่ต้องใช้เพื่อย้ายจากจุดเริ่มต้นไปยังเป้าหมาย ซึ่งเป็นเทคนิคเพื่อให้แก้ปัญหาได้เร็วขึ้น โดยหน้าตา function มีได้หลายรูปแบบ แล้วแต่จะออกแบบ เช่นกำหนด h(n) ประมาณ cost ขั้นต่ำจาก node ปัจจุบันไป node เป้าหมายโดยใช้ระยะทางแบบยุคลิดตามภาพด้านล่าง
สมมุติจากปัญหาเที่ยวรอบเกาะรัตนโกสินทร์ กำหนดค่า h(n) ของแต่ละที่ตามภาพด้านล่าง
6. Informed Search
หรือ Best-first search คือการ search ที่ใช้ข้อมูลอื่นเพิ่มเติมนอกจากส่วนที่เป็นองค์ประกอบของปัญหา search มี search algorithm ที่เกี่ยวข้องได้แก่ Greedy search และ A* search
ใน best-first search มีการกล่าวถึง Open List และ Closed List ซึ่งที่จริงเคยถูกใช้ตั้งแต่ใน uninformed search แล้ว โดยแนวคิดคือ
- Open List: list ที่เก็บ node เพื่อนบ้านของ node ที่ถูกเข้าถึง (generated node) เพื่อที่จะเรียงลำดับความสำคัญของ node (priority) ซึ่งเกณฑ์การเรียงก็แล้วแต่ชนิดของ search เพื่อเตรียมเข้าถึงในอนาคต โดยจากตัวอย่างโค๊ต python ในเรื่อง uninformed search ด้านบน ก็คือตัวแปร
Qใน BFS และ UCS และตัวแปรstackใน DFS - Closed List: list ที่เก็บ node ที่เคยถูกเข้าถึงไปแล้ว (expanded node) เพื่อป้องกันการเข้าถึง node เดิมซ้ำแล้วซ้ำเล่า โดยจากตัวอย่างโค๊ต python ในเรื่อง uninformed search ด้านบน ก็คือตัวแปร
visited
Greedy Search
คล้ายกับ UCS แต่ค่าที่เรียงเรียงตาม h(n) จากปัญหาเที่ยวรอบเกาะรัตนโกสินทร์ เขียนในภาษา python ได้
import heapq
class tree:
def __init__ (self, value, heuristic):
self.value = value
self.children = []
self.heuristic = heuristic
# กำหนดให้เปรียบเทียบค่า heuristic ตอนเรียงเข้าไปใน queue
def __lt__(self, other):
return self.heuristic < other.heuristic
Phra_Sumen_Fort = tree("Phra_Sumen_Fort", heuristic=3)
National_Museum = tree("National_Museum", heuristic=6)
Democracy_Monument = tree("Democracy_Monument", heuristic=5)
Golden_Mount = tree("Golden_Mount", heuristic=0)
Grand_Palace = tree("Grand_Palace", heuristic=2)
Giant_Swing = tree("Giant_Swing", heuristic=2)
Wat_Pho = tree("Wat_Pho", heuristic=2)
Phra_Sumen_Fort.children = [National_Museum, Democracy_Monument, Golden_Mount]
National_Museum.children = [Phra_Sumen_Fort, Democracy_Monument, Giant_Swing, Grand_Palace]
Democracy_Monument.children = [Phra_Sumen_Fort, National_Museum, Golden_Mount, Giant_Swing]
Golden_Mount.children = [Phra_Sumen_Fort, Democracy_Monument, Giant_Swing]
Grand_Palace.children = [National_Museum, Wat_Pho]
Giant_Swing.children = [National_Museum, Democracy_Monument, Golden_Mount, Wat_Pho]
Wat_Pho.children = [Grand_Palace, Giant_Swing]
def greedy_search(start, goal):
open_list = []
closed_list = set()
# สมาชิกแต่ละตัวใน queue คือ (node, เส้นทางมายัง node นั้นจาก start)
heapq.heappush(open_list, (start, [start]))
while open_list:
current, path = heapq.heappop(open_list)
if current.value == goal:
return [node.value for node in path]
closed_list.add(current)
for child in current.children:
if child.value not in closed_list:
heapq.heappush(open_list, (child, path+[child]))
# กรณีจาก start ไม่สามารถไป goal ได้
return None
start = National_Museum
goal = "Golden_Mount"
print(greedy_search(start, goal))ได้ผลลัพธ์คือ ['National_Museum', 'Giant_Swing', 'Golden_Mount']
A* Search
คือการรวมกันระหว่าง UCS และ Greedy Search โดย evaluation function f(n) = g(n) + h(n), g(n) คือ cost เส้นทางตั้งแต่ node เริ่มต้นมายัง node n และ h(n) คือ ค่า heuristic ของ node n การ search เรียงตามค่า f(n)
จากปัญหาเที่ยวรอบเกาะรัตนโกสินทร์ เขียนในภาษา python ได้
import heapq
class tree:
def __init__(self, value, heuristic):
self.value = value
self.children = {}
self.heuristic = heuristic
def __lt__(self, other):
return self.heuristic < other.heuristic
Phra_Sumen_Fort = tree("Phra_Sumen_Fort", heuristic=3)
National_Museum = tree("National_Museum", heuristic=6)
Democracy_Monument = tree("Democracy_Monument", heuristic=5)
Golden_Mount = tree("Golden_Mount", heuristic=0)
Grand_Palace = tree("Grand_Palace", heuristic=2)
Giant_Swing = tree("Giant_Swing", heuristic=2)
Wat_Pho = tree("Wat_Pho", heuristic=2)
Phra_Sumen_Fort.children = {National_Museum: 1.6, Democracy_Monument: 1.3, Golden_Mount: 2.1}
National_Museum.children = {Phra_Sumen_Fort: 1.6, Democracy_Monument: 2.4, Giant_Swing: 2.8, Grand_Palace: 2.9}
Democracy_Monument.children = {Phra_Sumen_Fort: 1.3, National_Museum: 2.4, Golden_Mount: 1.2, Giant_Swing: 0.8}
Golden_Mount.children = {Phra_Sumen_Fort: 2.1, Democracy_Monument: 1.2, Giant_Swing: 1.7}
Grand_Palace.children = {National_Museum: 2.9, Wat_Pho: 1.4}
Giant_Swing.children = {Golden_Mount: 1.7, Democracy_Monument: 0.8, National_Museum: 2.8, Wat_Pho: 1.6}
Wat_Pho.children = {Grand_Palace: 1.4, Giant_Swing: 1.6}
def a_star(start, goal):
open_list = []
closed_list = set()
# สมาชิกแต่ละตัวใน queue คือ (ค่า heuristic ของ node นั้น, node นั้น, เส้นทางมายัง node นั้น, cost ในการมา node นั้น)
heapq.heappush(open_list, (start.heuristic, start, [start], 0))
while open_list:
_, current, path, cost_so_far = heapq.heappop(open_list)
if current.value == goal:
return [node.value for node in path]
closed_list.add(current)
for neighbor, cost in current.children.items():
if neighbor not in closed_list:
new_cost = cost + cost_so_far
priority = new_cost + neighbor.heuristic
heapq.heappush(open_list, (priority, neighbor, path + [neighbor], new_cost))
return None
start = National_Museum
goal = "Golden_Mount"
print(a_star(start, goal))ได้ผลลัพธ์คือ ['National_Museum', 'Phra_Sumen_Fort', 'Golden_Mount']
A* search สามารถรับประกันได้ว่าจะเจอเส้นทางที่สั้นที่สุดปัญหานั้นมีคำตอบอยู่จริง แต่มีอยู่ 2 เงื่อนไขที่ต้องเป็นจริงคือ admissibility และ consistency
Admissibility: หรือ never overestimate คือ h(n) ≤ h*(n) โดย
- h(n): cost ที่ประมาณการจาก node n ไปยัง goal
- h*(n): cost จริงของเส้นทางที่สั้นที่สุดจาก node n ไปยัง goal
Consistency: หรือ monotonicity คือ h(n) ≤ c(n, a, n′) + h(n′) โดย
- h(n): cost ที่ประมาณการจาก node n ไปยัง goal
- c(n, a, n′): cost ที่ต้องใช้เพื่อไป node n′ จาก node n
- h(n′): cost ที่ประมาณการจาก node n′ ไปยัง goal
อ้างอิง
หนังสือ Artificial Intelligence: A Modern Approach (4th edition)
