Cấu trúc dữ liệu và Giải thuật Bài 86: Thuật toán A* Search - Định tuyến tìm đường đi ngắn nhất sử dụng Heuristic.

Trong các bài toán định tuyến cơ bản, thuật toán Dijkstra luôn đảm bảo tìm ra đường đi ngắn nhất. Tuy nhiên, Dijkstra có một điểm yếu chí mạng: Nó bị "mù". Dijkstra lan tỏa sự tìm kiếm ra mọi hướng theo hình tròn giống như việc ném một hòn đá xuống hồ nước. Nếu bạn muốn tìm đường từ ga Bến Thành đến ga Suối Tiên, Dijkstra sẽ khám phá cả những con đường ngược hướng đi về miền Tây trước khi nhận ra mục tiêu thực sự nằm ở phía Đông.

Khi tối ưu hóa lộ trình giao hàng cho shipper hoặc lập trình AI cho NPC trong game, sự lãng phí tính toán này là không thể chấp nhận. Để cấp cho thuật toán một "đôi mắt" có khả năng nhìn về phía đích, năm 1968, các nhà khoa học tại Stanford đã tạo ra _A (A-Star)_*. Đây là thuật toán định tuyến phổ biến nhất thế giới hiện nay, trái tim của Google Maps và mọi hệ thống bản đồ số.

1. Công thức Ma thuật: Trí tuệ nhân tạo Heuristic

A* vẫn sử dụng Hàng đợi ưu tiên (Priority Queue) giống như Dijkstra để quyết định xem nên bước đi vào đỉnh nào tiếp theo. Tuy nhiên, thay vì chỉ dựa vào khoảng cách đã đi, A* đánh giá một đỉnh $n$ bằng hàm tổng quát:

$f(n) = g(n) + h(n)$

Trong đó:

$g(n)$ (Chi phí thực tế): Khoảng cách chính xác từ Điểm xuất phát (Start) đến đỉnh $n$ hiện tại. (Phần này giống hệt Dijkstra).
$h(n)$ (Hàm Heuristic - Trực giác): Ước lượng khoảng cách từ đỉnh $n$ đến Điểm đích (Goal). Đây chính là "đôi mắt" của A*.
$f(n)$ (Tổng chi phí ước tính): Thuật toán sẽ luôn ưu tiên lấy đỉnh có $f(n)$ nhỏ nhất trong hàng đợi ra để duyệt trước.

Nhờ hàm $h(n)$ , thay vì lan tỏa vòng tròn, A* sẽ bị "lực hấp dẫn" của Điểm đích kéo luồng tìm kiếm kéo giãn ra thành hình elip, hướng thẳng về phía mục tiêu, bỏ qua các đỉnh nằm ngược hướng.

2. Lựa chọn Hàm Heuristic: Chìa khóa của sự chính xác

Thuật toán A* chỉ đảm bảo tìm được đường đi ngắn nhất tuyệt đối nếu hàm $h(n)$ là Admissible (Có thể chấp nhận được) — nghĩa là $h(n)$ không bao giờ được phép ước lượng cao hơn chi phí thực tế. Nếu nó đánh giá quá cao, A* có thể bỏ lỡ con đường tốt nhất.

Tùy vào địa hình, chúng ta có các hàm Heuristic tiêu chuẩn:

Manhattan Distance: Dùng cho bản đồ dạng Lưới (Grid) chỉ cho phép đi 4 hướng (Lên, Xuống, Trái, Phải) như đường phố quy hoạch bàn cờ.

$h(n) = \vert{}x_{node} - x_{goal}\vert{} + \vert{}y_{node} - y_{goal}\vert{}$
Euclidean Distance (Đường chim bay): Dùng cho bản đồ cho phép di chuyển tự do mọi hướng.

$h(n) = \sqrt{(x_{node} - x_{goal})^2 + (y_{node} - y_{goal})^2}$
4. Triển khai A* Search bằng Golang

Dưới đây là cài đặt cốt lõi của A* trên hệ tọa độ Lưới 2D (Grid) 4 hướng. (Để mã nguồn trong sáng, phần interface heap của Golang được giả định đã tích hợp).

package main

import (
	"fmt"
	"math"
)

// Cấu trúc một điểm trên bản đồ lưới
type Point struct {
	X, Y int
}

// Cấu trúc Node trong Hàng đợi ưu tiên
type AStarNode struct {
	P      Point
	G      float64      // Chi phí từ Start đến Node này
	H      float64      // Chi phí ước tính từ Node này đến Goal
	F      float64      // F = G + H
	Parent *AStarNode   // Dùng để truy xuất ngược lại đường đi
}

// Hàm Heuristic: Khoảng cách Manhattan
func manhattan(p, goal Point) float64 {
	return math.Abs(float64(p.X-goal.X)) + math.Abs(float64(p.Y-goal.Y))
}

// Mảng 4 hướng di chuyển (Lên, Xuống, Trái, Phải)
var directions = []Point{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

// Thuật toán A*
func AStar(grid [][]int, start, goal Point) []*AStarNode {
	// (Giả lập) Khởi tạo Priority Queue (Min-Heap) dựa trên giá trị F
	// openSet := &PriorityQueue{}
	// closedSet lưu các đỉnh đã duyệt
	closedSet := make(map[Point]bool)

	startNode := &AStarNode{P: start, G: 0, H: manhattan(start, goal)}
	startNode.F = startNode.G + startNode.H
	
	// openSet.Push(startNode) // Giả định Push vào Heap
	
	// Khởi tạo vòng lặp mô phỏng
	// for openSet.Len() > 0 {
		// current := openSet.Pop().(*AStarNode) // Lấy Node có F nhỏ nhất
		current := startNode // (Mô phỏng)

		// 1. Kiểm tra điều kiện đích
		if current.P == goal {
			return reconstructPath(current)
		}

		closedSet[current.P] = true

		// 2. Mở rộng các ô lân cận
		for _, dir := range directions {
			neighbor := Point{X: current.P.X + dir.X, Y: current.P.Y + dir.Y}

			// Bỏ qua nếu ra khỏi bản đồ, là vật cản (grid == 1), hoặc đã duyệt qua
			if !isValid(grid, neighbor) || grid[neighbor.Y][neighbor.X] == 1 || closedSet[neighbor] {
				continue
			}

			// Chi phí đi 1 bước bằng 1
			tentativeG := current.G + 1

			// Tính toán Node mới
			// neighborNode := &AStarNode{
			//	 P: neighbor,
			//	 G: tentativeG,
			//	 H: manhattan(neighbor, goal),
			//	 Parent: current,
			// }
			// neighborNode.F = neighborNode.G + neighborNode.H
			
			// Cập nhật lại trong openSet nếu tìm được G tốt hơn (Code thực tế cần cập nhật lại Heap)
			// openSet.Push(neighborNode)
		}
	// }
	return nil // Không tìm thấy đường
}

// Hàm truy vết đường đi từ Đích ngược về Start
func reconstructPath(node *AStarNode) []*AStarNode {
	var path []*AStarNode
	for node != nil {
		path = append([]*AStarNode{node}, path...) // Chèn lên đầu
		node = node.Parent
	}
	return path
}

func isValid(grid [][]int, p Point) bool {
	return p.Y >= 0 && p.Y < len(grid) && p.X >= 0 && p.X < len(grid[0])
}

func main() {
	// Lưới 5x5. 0 là đường đi, 1 là tường.
	grid := [][]int{
		{0, 0, 0, 0, 0},
		{0, 1, 1, 1, 0},
		{0, 0, 0, 1, 0},
		{0, 1, 0, 0, 0},
		{0, 0, 0, 0, 0},
	}
	start := Point{0, 0}
	goal := Point{4, 4}

	fmt.Printf("Tìm đường từ %v đến %v...\n", start, goal)
	// Gọi AStar (đã rút gọn mô phỏng)
}

5. Phân tích Hiệu năng và Ứng dụng Thực tế

Thời gian Truy vấn (Time Complexity): Ở trường hợp xấu nhất (bản đồ trống rỗng hoặc heuristic tồi $h(n)=0$ ), A* thoái hóa thành thuật toán Dijkstra, tốn $O(E + V \log V)$ . Với hàm heuristic xuất sắc, thời gian tiệm cận $O(d)$ (với $d$ là độ dài đường đi ngắn nhất), cực kỳ chớp nhoáng.
Không gian (Space Complexity): $O(V)$ vì thuật toán phải lưu toàn bộ các Node biên (Frontier) vào trong RAM để quản lý Priority Queue. Đây là giới hạn lớn nhất của A* đối với các bản đồ khổng lồ, dẫn đến sự ra đời của các biến thể tiết kiệm RAM như IDA (Iterative Deepening A).

Ứng dụng cốt lõi:

AI Di chuyển trong Game (Pathfinding): Các nhân vật NPC, lính gác, hoặc quái vật tìm đường chạy đến nhân vật chính trong địa hình phức tạp có chướng ngại vật.
Định tuyến Logistics: Khi hệ thống tự động hóa điều phối robot nâng hàng (AGV) trong các kho bãi khổng lồ, A* định tuyến mượt mà để né các giá kệ và robot khác.
Công nghệ Bản đồ (Maps & Navigation): Các hệ thống chỉ đường thời gian thực kết hợp A* với đồ thị mạng lưới đường giao thông để liên tục tính toán lại quỹ đạo.

Khi bài toán định tuyến đi qua một điểm đích đã hoàn thành, thách thức vĩ mô tiếp theo của các kỹ sư mạng là làm sao để bơm một "dòng chảy" dữ liệu hoặc hàng hóa qua một mạng lưới ống dẫn có sức chứa (Capacity) giới hạn mà không làm tắc nghẽn hệ thống.

cấu trúc dữ liệu

1. Công thức Ma thuật: Trí tuệ nhân tạo Heuristic

2. Lựa chọn Hàm Heuristic: Chìa khóa của sự chính xác

4. Triển khai A* Search bằng Golang

5. Phân tích Hiệu năng và Ứng dụng Thực tế

Mục lục