ในยุคนี้ที่อะไร ๆ ก็ต้องเร็ว ต้องฉลาดและต้องหาให้เจอภายในพริบตา อัลกอริธึมการค้นหา (Search Algorithms) ก็กลายเป็นพระเอกที่อยู่เบื้องหลังหลายสิ่งรอบตัวเราโดยไม่รู้ตัว ไม่ว่าจะเป็นแอปนำทางที่พาเราเลี่ยงรถติดเช่น Google Maps เกมแข่งรถที่บอทรู้ทางลัดเช่น Forza Horizon
บทความนี้จะพาคุณไปรู้จักกับสองตัวท็อปของวงการค้นหาอย่าง Breadth-First Search (BFS) และ Depth-First Search (DFS) ผ่านตัวอย่างในภาษา Python ที่อ่านง่าย ใช้งานได้จริงกัน
Breadth-First Search (BFS) คืออะไร?
BFS เป็นอัลกอริธึมที่ค้นหาจากจุดเริ่มต้นไปยังจุดหมายโดยไล่ระดับความลึกทีละชั้น เหมือนกับการเดินทางไปทีละจุดใกล้ๆ ก่อน แล้วค่อยขยายวงกว้างออกไป
ลองนึกถึงการค้นหาหมายเลขโทรศัพท์ของเพื่อนในสมุดโทรศัพท์ คุณอาจไล่ดูรายชื่อจากตัวอักษร A ไป B แล้วไป C ซึ่งคล้ายกับแนวคิดของ BFS หรือหากคุณอยู่ในห้องสมุดแล้วต้องการหาหนังสือที่ต้องการ คุณอาจเริ่มจากการดูหมวดหมู่หลักก่อน แล้วค่อยลงลึกไปยังชั้นที่เฉพาะเจาะจงมากขึ้น
ถ้างั้นเราลองมาดูตัวอย่างโค้ดกัน
ขั้นตอนที่1 การกำหนดกราฟในรูปแบบ Dictionary
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}ขั้นตอนที่2 ลองใช้งาน BFS
โค้ดนี้เป็นจะการทำงานของอัลกอริธึมการค้นหาความกว้างโดยเริ่มจากโหนดต้นทางแล้วทำการเยี่ยมชมทุกโหนดในกราฟที่เชื่อมต่อกับโหนดต้นทางทีละขั้นตอน โดยใช้คิว (queue) ในการจัดลำดับการเยี่ยมชม
visited = []
queue = []
def bfs(visited, graph, node):
visited.append(node)
queue.append(node)
while queue:
m = queue.pop(0)
print (m, end = " ")
for neighbour in graph[m]:
if neighbour not in visited:
visited.append(neighbour)
queue.append(neighbour)
# Driver Code
print("BFS")
bfs(visited, graph, 'A')โดยโค้ดแต่ละส่วนจะมีการทำงานดังนี้ :
visited → ใช้เก็บว่าเคยไปเยี่ยมชมโหนดไหนแล้วบ้าง
queue → คิวที่ใช้เก็บโหนดที่ต้องไปต่อ
pop(0) → เป็นการดึงโหนดแรกเข้ามาทำงาน
ทีนี้ลองมาดูผลลัพธ์กันจากโค้ดเบื้องต้นกัน :
ผลลัพธ์จากการรันฟังก์ชัน BFS จะเป็นการแสดงโหนดที่ถูกเยี่ยมชมในลำดับที่กว้างที่สุดเป็นชั้น ๆ ชั้นหนึ่งแล้วไปยังระดับชั้นถัดไป โดยเริ่มจากโหนด ('A') และเยี่ยมชมโหนดที่เชื่อมต่อกับโหนดนั้นๆ ทีละระดับโดยใช้คิวในการจัดลำดับการเยี่ยมชมหรือก็คือมาก่อนได้ก่อนนั่นเอง
การทำงานของ BFS คือ:
เริ่มจาก 'A' และไปเยี่ยมชม 'B' และ 'C' (ที่อยู่ในระดับเดียวกันหรือชั้นเดียวกัน)
จากนั้นไปเยี่ยมชม 'D', 'E', และ 'F' ตามลำดับ
Depth-First Search (DFS) คืออะไร?
DFS เป็นอัลกอริธึมที่ค้นหาข้อมูลโดย เจาะลึก ลงไปตามเส้นทางหนึ่งให้สุดก่อน แล้วจึงย้อนกลับมาและลองเส้นทางถัดไป เหมือนกับการเดินเข้าไปในเขาวงกตโดยเลือกทางใดทางหนึ่ง แล้วเดินให้สุดทางก่อน หากไปต่อไม่ได้จึงย้อนกลับและลองทางอื่น
ลองนึกถึงคุณกำลังหาเพื่อนในอาคารที่มีหลายชั้นและแต่ละชั้นมีหลายห้อง
แทนที่จะเดินดูทีละห้องในแต่ละชั้นคุณอาจเลือกเดินเข้าไปในห้องแรก แล้วดูให้ลึกว่ามีห้องในห้องย่อยมั้ย ถ้ามีก็เข้าไปต่อเรื่อย ๆ จนสุดทางก่อน ค่อยย้อนกลับมาเริ่มใหม่กับห้องถัดไป นี่คือแนวคิดของ DFS
หรืออีกตัวอย่างง่าย ๆ ถ้าหากคุณกำลังหาไฟล์ในโฟลเดอร์คอมพิวเตอร์ DFS จะให้คุณเข้าไปในโฟลเดอร์แรกก่อน แล้วเปิดโฟลเดอร์ย่อยในนั้น ไล่ลงไปเรื่อย ๆ จนไม่มีอะไรจะเปิดอีกแล้ว ถึงจะย้อนกลับมาดูโฟลเดอร์อื่นในระดับเดียวกัน
เราลองมาดูตัวอย่างโค้ดกัน
ขั้นตอนที่3 ลองใช้งาน DFS
โค้ดนี้เป็นการทำงานของอัลกอริธึมการค้นหาความลึกโดยเริ่มจากโหนดต้นทางแล้วทำการเยี่ยมชมโหนดที่เชื่อมต่อกับโหนดต้นทางจนกว่าจะถึงโหนดที่ไม่มีโหนดต่อเชื่อม จากนั้นจะย้อนกลับและเยี่ยมชมโหนดที่ยังไม่ถูกเยี่ยมชม โดยใช้การเรียกฟังก์ชันซ้ำในการทำงาน
visited = set()
def dfs(visited, graph, node):
if node not in visited:
print (node)
visited.add(node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)
print("DFS :")
dfs(visited, graph, 'A')โดยโค้ดแต่ละส่วนจะมีการทำงานดังนี้ :
visited → ใช้เก็บว่าเคยไปเยี่ยมชมโหนดไหนแล้วบ้าง
dfs() → เป็นการค้นหาลึกเข้าไปเรื่อย ๆ จนสุดทางก่อนค่อยย้อนกลับ
ทีนี้ลองมาดูผลลัพธ์กันจากโค้ดเบื้องต้นกัน :
ผลลัพธ์ที่ได้จากการรันโค้ด DFS (Depth-First Search) คือการแสดงลำดับของโหนดที่ถูกเยี่ยมชม โดย DFS จะเลือก “ดำดิ่ง” ไปยังโหนดที่ลึกที่สุดก่อน แล้วค่อยย้อนกลับมาเก็บโหนดที่ยังตกค้างอยู่ภายหลัง
มาดูขั้นตอนแบบง่าย ๆ:
เริ่มจากโหนด 'A' → DFS จะเยี่ยมชม 'A' และมุ่งหน้าไปยัง 'B' เพราะเป็นโหนดที่เชื่อมต่อกับ 'A' เป็นลำดับแรก
จาก 'B' → ไปต่อที่ 'D' (ลึกสุดก่อนตามแนวทางของ DFS)
พอถึง 'D' → ไม่มีโหนดให้ไปต่อแล้ว → จึง “ย้อนกลับ” มาที่ 'B' แล้วไปยัง 'E'
เยี่ยมชม 'E' เสร็จ → กลับไปที่ 'A' อีกครั้ง
ตอนนี้ยังเหลือ 'C' ที่เชื่อมกับ 'A' → DFS เลยไปต่อที่ 'C'
จาก 'C' → เดินหน้าต่อไปยัง 'F'
สุดท้าย เยี่ยมชม 'F' เสร็จ → ย้อนกลับขึ้นมาเรื่อย ๆ จนครบทุกโหนดที่เชื่อมต่อ
ถ้าพูดง่าย ๆ คือ DFS จะเป็นการ “ลุยลึกก่อนคิดทีหลัง” คือไปให้สุดทางก่อน แล้วค่อยย้อนกลับมาเช็กว่าเรายังตกหล่นอะไรไว้บ้าง
ทีนี้เรามาดูตัวอย่างอื่นอีกกันโดยใช้เกมหนีซอมบี้กันบ้างดีกว่า
โดยก่อนเริ่มให้เรารันโค้ดนี้ลงไปใน Google Colab
import time
from collections import deque
import os
maze = [
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0]
]
player_pos = (0, 0)
zombie_pos = (4, 4)
def bfs(start, goal):
queue = deque([[start]])
visited = set()
while queue:
path = queue.popleft()
x, y = path[-1]
if (x, y) == goal:
return path
for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < 5 and 0 <= ny < 5 and maze[nx][ny] == 0 and (nx, ny) not in visited:
queue.append(path + [(nx, ny)])
visited.add((nx, ny))
return []
def print_maze(player, zombie):
os.system('cls' if os.name == 'nt' else 'clear')
for i in range(5):
row = ""
for j in range(5):
if (i, j) == player:
row += "P "
elif (i, j) == zombie:
row += "Z "
elif maze[i][j] == 1:
row += "# "
else:
row += ". "
print(row)
print()
while True:
print_maze(player_pos, zombie_pos)
if zombie_pos == player_pos:
print("ผีจับคุณได้แล้ว! Game Over.")
break
move = input("WASD เพื่อขยับ: ").upper()
dx, dy = 0, 0
if move == "W": dx, dy = -1, 0
elif move == "S": dx, dy = 1, 0
elif move == "A": dx, dy = 0, -1
elif move == "D": dx, dy = 0, 1
new_x = player_pos[0] + dx
new_y = player_pos[1] + dy
if 0 <= new_x < 5 and 0 <= new_y < 5 and maze[new_x][new_y] == 0:
player_pos = (new_x, new_y)
path = bfs(zombie_pos, player_pos)
if len(path) > 1:
zombie_pos = path[1]
time.sleep(0.1)โดยโค้ดแต่ละส่วนจะมีการทำงานดังนี้ :
visited → ใช้เก็บว่าเคยไปเยี่ยมชมโหนดไหนแล้วบ้าง
queue → คิวที่ใช้เก็บโหนดที่ต้องไปต่อ
pop(0) → เป็นการดึงโหนดแรกเข้ามาทำงาน
bfs → ฟังก์ชันที่ใช้ค้นหาเส้นทางจากตำแหน่งผีไปยังตำแหน่งผู้เล่น โดยจะเริ่มต้นจากตำแหน่งของผีและตรวจสอบไปในทิศทางต่าง ๆ
print_maze → ฟังก์ชันที่ใช้แสดงผลแผนที่ทุกครั้งหลังจากที่ผู้เล่นหรือผีทำการขยับ
โดยหลักการเกมนี้มีง่าย ๆ คือ :
ซอมบี้จะเดินตามทางสั้นที่สุดโดยใช้ BFS
ผู้เล่นควบคุมด้วยปุ่ม W A S D
ผีจะเดินทีละ 1 ช่องทุกตา สลับกับเรา
เมื่อเราลองรันแล้วจะได้หน้าตา Output ออกมาเป็นแบบนี้
โดยให้เราเดินโดยใช้ปุ่มที่ตั้งค่าในโค้ดซึ่งในตัวอย่างนี้ใช้เป็น (W, A, S, D) โดยให้เดินไปทีละตาสลับกับซอมบี้ที่จะเดินมาหาเรา
จนเมื่อซอมบี้ใช้หลักการ BFS จนหาผู้เล่นเจอก็จะปรากฏดังนี้
สรุปบทความนี้
จากบทความนี้ เราได้ทำความรู้จักกับอัลกอริธึมการค้นหายอดนิยมทั้งสองแบบคือ Breadth-First Search (BFS) และ Depth-First Search (DFS) พร้อมตัวอย่างโค้ดภาษา Python ที่สามารถนำไปทดลองและประยุกต์ใช้ได้จริง ไม่ว่าจะเป็นการยกตัวอย่างของโหนดต่าง ๆ และการหาเส้นทางในแผนที่เกม แม้อัลกอริธึมเหล่านี้จะดูเรียบง่าย แต่ก็สามารถต่อยอดไปสู่การแก้ปัญหาที่ซับซ้อนมากขึ้นได้มากขึ้นในอนาคต เช่น เกมที่ใช้ AI ในการประมวลผลเส้นทาง, ระบบนำทาง, หรือแม้แต่การวิเคราะห์เครือข่ายสังคมออนไลน์ ลองนำความรู้ที่ได้ไปประยุกต์ใช้ดูนะครับ
ใครลองทำอะไรเจ๋ง ๆ มา แชร์กันได้เลยครับ 😄
Reference :
https://favtutor.com/blogs/breadth-first-search-python
https://favtutor.com/blogs/depth-first-search-python