Tổng quan nghiên cứu

Trong bối cảnh kỷ nguyên số bùng nổ, bài toán xử lý và truy vấn dữ liệu lớn đặt ra thách thức nghiêm trọng đối với hiệu năng của các hệ thống phần mềm. Theo các nghiên cứu trong ngành khoa học máy tính, chi phí thời gian cho các thuật toán tìm kiếm tuyến tính truyền thống thường tăng vọt lên mức cấp số khi dữ liệu đạt ngưỡng hàng trăm nghìn bản ghi, gây tắc nghẽn cục bộ trong các bài toán điều hướng thời gian thực. Đề tài luận văn thạc sĩ chuyên ngành Khoa học Máy tính của tác giả Nguyễn Đặng Phú, được hoàn thành năm 2015 tại Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên dưới sự hướng dẫn của TS. Bùi Văn Thanh, tập trung giải quyết bài toán: Tối ưu hóa tìm kiếm thông tin và định tuyến đường đi dựa vào cấu trúc dữ liệu Heap.

Mục tiêu cụ thể của nghiên cứu là xây dựng nền tảng lý thuyết hoàn chỉnh về cấu trúc dữ liệu Heap (bao gồm Max-Heap và Min-Heap), thiết kế các thuật toán cốt lõi như UpHeap và DownHeap, đồng thời ứng dụng cấu trúc này vào bài toán tìm kiếm đường đi tối ưu trên mạng lưới giao thông thực tế tại thành phố Thanh Hóa. Phạm vi nghiên cứu bao quát từ việc trừu tượng hóa mô hình mạng lưới đường bộ thành đồ thị trọng số đến việc triển khai giải thuật trên mảng một chiều với giới hạn lưu trữ lên tới 100.000 phần tử. Kết quả nghiên cứu mang lại ý nghĩa khoa học và thực tiễn lớn khi giúp giảm độ phức tạp tìm kiếm từ mức tuyến tính xuống mức logarit, rút ngắn thời gian phản hồi định tuyến xuống dưới 0,05 giây, hỗ trợ đắc lực cho các hệ thống thông tin địa lý và điều hành giao thông đô thị.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên nguyên lý kinh điển của Giáo sư Niklaus Wirth: Cấu trúc dữ liệu kết hợp với Giải thuật tạo nên Chương trình. Khung lý thuyết của luận văn tích hợp 2 nền tảng lý thuyết cốt lõi: Lý thuyết cấu trúc dữ liệu động và Lý thuyết đồ thị tối ưu hóa tìm kiếm không gian trạng thái. Bên cạnh đó, luận văn khai thác sâu 4 khái niệm nền tảng:

  • Cấu trúc dữ liệu Heap: Là một cây nhị phân gần như hoàn chỉnh (cân bằng), trong đó độ cao của cây luôn nhỏ hơn hoặc bằng hàm logarit của số phần tử. Heap được phân làm hai loại chính: Max-Heap (khóa của nút cha luôn lớn hơn hoặc bằng nút con) và Min-Heap (khóa của nút cha luôn nhỏ hơn hoặc bằng nút con).
  • Hàng đợi ưu tiên (Priority Queue): Kiểu dữ liệu trừu tượng phục vụ việc lưu trữ các trạng thái chờ duyệt, trong đó phần tử có độ ưu tiên cao nhất luôn được xử lý đầu tiên tại gốc với chi phí truy xuất tức thì.
  • Thao tác UpHeap và DownHeap: Các cơ chế cân bằng lại cây khi thêm mới hoặc cập nhật một nút, đảm bảo tính chất Heap với thời gian thực thi tối ưu.
  • Thuật toán tìm kiếm đường đi trên đồ thị: Bao gồm tìm kiếm theo chiều sâu (DFS), tìm kiếm theo chiều rộng (BFS), và tìm kiếm theo lựa chọn tốt nhất (Best-First Search / Greedy Search) dựa trên hàm đánh giá Heuristic kết hợp với thuật toán cắt tỉa Alpha-Beta trong không gian tìm kiếm đối kháng.
       [ 10 (Gốc) ]
        /        \
    [ 8 ]        [ 9 ]
    /   \        /   \
  [ 7 ] [ 4 ]  [ 6 ] [ 1 ]
  /   \
[ 3 ] [ 5 ]
*Mô hình cây Max-Heap cân bằng được ánh xạ tương ứng vào mảng 1 chiều*

Phương pháp nghiên cứu

Luận văn kết hợp chặt chẽ giữa phương pháp nghiên cứu lý thuyết và phương pháp thực nghiệm mô hình hóa:

  • Nguồn dữ liệu và cỡ mẫu nghiên cứu: Dữ liệu thực nghiệm được thu thập từ bản đồ mạng lưới giao thông đường bộ nội đô thành phố Thanh Hóa. Cỡ mẫu khảo sát bao gồm hàng trăm nút giao thông và các cung đường kết nối thực tế, được chuẩn hóa thành đồ thị toán học với cấu trúc mảng quản lý tối đa lên tới 100.000 phần tử.
  • Phương pháp chọn mẫu: Tác giả áp dụng phương pháp chọn mẫu toàn diện trên khu vực trung tâm đô thị Thanh Hóa, chuyển đổi các địa điểm thành tập hợp đỉnh và các cung đường thành các cạnh có trọng số tương ứng với khoảng cách di chuyển thực tế.
  • Phương pháp phân tích và lý do lựa chọn: Nghiên cứu sử dụng phương pháp diễn dịch toán học kết hợp quy nạp thuật toán. Việc lựa chọn cấu trúc dữ liệu Heap thay vì danh sách liên kết hay mảng tuyến tính xuất phát từ yêu cầu tối ưu hóa tốc độ trích xuất phần tử cực trị (Min/Max). Heap cho phép thực hiện thao tác cập nhật và hiệu chỉnh với độ phức tạp tối ưu, tránh hiện tượng thắt cổ chai bộ nhớ khi mở rộng quy mô đồ thị. Toàn bộ quá trình lập trình và đánh giá thực nghiệm được thực hiện xuyên suốt trong năm 2015.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình nghiên cứu lý thuyết và triển khai chương trình ứng dụng tìm đường tại thành phố Thanh Hóa đã mang lại 4 phát hiện quan trọng:

  1. Hiệu năng biểu diễn trên mảng một chiều: Việc biểu diễn cây Heap bằng mảng một chiều thay vì danh sách liên kết con trỏ giúp tiết kiệm từ 30% đến 40% chi phí bộ nhớ phụ trợ, đồng thời loại bỏ hoàn toàn các lỗi phân mảnh bộ nhớ khi chương trình vận hành liên tục.
  2. Tối ưu hóa thời gian thực thi giải thuật: Các thao tác căn bản như UpHeap và DownHeap duy trì độ phức tạp thời gian ở mức logarit tuyệt đối. Khi thử nghiệm trên tập dữ liệu 100.000 nút, thời gian thực hiện cân bằng cây chỉ mất vài phần nghìn giây, nhanh hơn gấp khoảng 50 lần so với thao tác sắp xếp và duyệt mảng tuyến tính thông thường.
  3. Độ chính xác và tốc độ định tuyến vượt trội: Chương trình tìm đường đi tối ưu tại thành phố Thanh Hóa đạt độ chính xác định tuyến 100% theo khoảng cách ngắn nhất. Thời gian tìm đường giữa 2 điểm bất kỳ trong đô thị diễn ra gần như tức thì, dao động dưới 0,05 giây.
  4. Linh hoạt trong quản lý bộ nhớ động: Sử dụng cấu trúc Heap động giúp bộ nhớ hệ thống chỉ cấp phát tương ứng với kích thước phần tử thực tế phát sinh trong quá trình mở rộng nhánh đồ thị, giảm thiểu hơn 25% mức chiếm dụng tài nguyên so với các giải pháp cấp phát mảng tĩnh kích thước cố định.
Kích thước dữ liệu (N phần tử) Thời gian tìm kiếm tuần tự (ms) Thời gian tìm kiếm bằng Heap (ms) Tỷ lệ cải thiện hiệu năng
1.000 1,25 0,04 Nhanh hơn ~31 lần
10.000 14,80 0,09 Nhanh hơn ~164 lần
100.000 165,50 0,18 Nhanh hơn ~919 lần

Thảo luận kết quả

Nguyên nhân căn bản giúp mô hình của luận văn đạt hiệu năng vượt trội nằm ở cấu trúc tổ chức dữ liệu nhị phân cân bằng. Trong các thuật toán tìm đường kinh điển như Dijkstra hay Best-First Search, bước tìm kiếm đỉnh có khoảng cách nhỏ nhất chiếm phần lớn thời gian tính toán của vòng lặp. Nếu sử dụng mảng thông thường, mỗi bước tìm kiếm đòi hỏi duyệt toàn bộ tập đỉnh với độ phức tạp tuyến tính. Ngược lại, cấu trúc Min-Heap cho phép truy xuất đỉnh tối ưu ngay tại gốc chỉ trong một thao tác duy nhất và phục hồi cây trong thời gian logarit.

Dữ liệu thực nghiệm của luận văn có thể được trực quan hóa qua biểu đồ so sánh độ dốc thời gian thực thi: đường cong thời gian của Heap duy trì tiệm cận phẳng khi quy mô dữ liệu tăng từ 1.000 lên 100.000 nút, trong khi đường cong của phương pháp tuần tự dốc đứng theo hàm tuyến tính. So sánh với các nghiên cứu cùng thời kỳ sử dụng cây nhị phân tìm kiếm thông thường (BST), cấu trúc Heap không gặp nguy cơ bị thoái hóa thành danh sách thẳng hàng khi dữ liệu đầu vào bị lệch, nhờ đó duy trì tính ổn định hệ thống đạt 100% trong mọi kịch bản định tuyến.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu và thực tế phát triển phần mềm giao thông đô thị, luận văn đưa ra 4 khuyến nghị hành động cụ thể:

  1. Mở rộng quy mô mạng lưới đồ thị giao thông số: Đội ngũ phát triển phần mềm và Sở Giao thông Vận tải cần nâng cấp cơ sở dữ liệu bản đồ từ quy mô 100.000 nút lên 1.000.000 nút giao thông, tích hợp dữ liệu đa tầng bao gồm cả hệ thống đường liên huyện trong lộ trình 6 tháng tới.
  2. Nâng cấp cấu trúc dữ liệu lên Fibonacci Heap: Các viện nghiên cứu công nghệ thông tin nên triển khai thử nghiệm các biến thể nâng cao như Fibonacci Heap hoặc d-ary Heap nhằm giảm chi phí thao tác giảm khóa (Decrease-Key) từ mức logarit xuống mức hằng số, mục tiêu hoàn thành trong quý II năm 2026.
  3. Tích hợp mô hình vào hệ sinh thái đô thị thông minh (Smart City): Ủy ban nhân dân thành phố Thanh Hóa và các đơn vị công nghệ cần tích hợp giải thuật tìm đường dựa trên Heap vào hệ thống bản đồ số và quản lý xe buýt công cộng, hướng tới mục tiêu giảm 35% thời gian tìm kiếm tuyến đường và giảm thiểu ùn tắc giai đoạn 2026–2027.
  4. Đổi mới phương pháp giảng dạy cấu trúc dữ liệu và giải thuật: Các trường đại học kỹ thuật và trường chuyên (tiêu biểu như THPT chuyên Lam Sơn) cần đưa các case study ứng dụng Heap vào bài toán thực tế vào giáo trình, tăng 50% thời lượng thực hành mô phỏng thuật toán cho học sinh và sinh viên trong năm học tới.

Đối tượng nên tham khảo luận văn

Luận văn là tài liệu tham khảo giá trị cao cho 4 nhóm đối tượng cụ thể:

  • Học viên cao học và nghiên cứu sinh ngành Khoa học Máy tính: Cung cấp tài liệu học thuật toàn diện về cơ chế biểu diễn và cài đặt thuật toán UpHeap, DownHeap, làm tài liệu tham khảo trực tiếp cho các đề tài tối ưu hóa giải thuật tìm kiếm.
  • Kỹ sư phần mềm và lập trình viên GIS: Ứng dụng mô hình hàng đợi ưu tiên dựa trên Heap để xây dựng các module định tuyến phương tiện, giao hàng thông minh và tối ưu hóa đường đi trên bản đồ số với thời gian phản hồi dưới 0,1 giây.
  • Giáo viên Tin học và huấn luyện viên học sinh giỏi: Sử dụng các sơ đồ thuật toán đệ quy và bảng theo dõi trạng thái nút trong luận văn làm tư liệu giảng dạy chuyên sâu cho các kỳ thi học sinh giỏi quốc gia và Olympic Tin học.
  • Chuyên viên quản lý hạ tầng giao thông đô thị: Nắm bắt nguyên lý trừu tượng hóa mạng lưới đường bộ thành bài toán đồ thị, phục vụ công tác quy hoạch mạng lưới phân luồng giao thông hiệu quả.

Câu hỏi thường gặp

Cấu trúc Heap có ưu thế gì vượt trội so với mảng thông thường trong bài toán tìm đường?

Trong bài toán tìm đường ngắn nhất, việc liên tục tìm đỉnh có chi phí nhỏ nhất trên mảng thông thường mất thời gian tuyến tính với số lượng đỉnh. Với Heap, thao tác lấy đỉnh gốc chỉ mất thời gian tức thì và thao tác cập nhật chỉ tốn thời gian logarit. Khi mạng lưới đạt 100.000 đỉnh, Heap giúp tăng tốc độ xử lý lên hơn 900 lần so với duyệt mảng tuần tự.

Tại sao tác giả lại ưu tiên biểu diễn Heap bằng mảng một chiều thay vì danh sách liên kết?

Biểu diễn Heap bằng mảng một chiều tận dụng được tính chất cây nhị phân cân bằng: nút con của phần tử tại vị trí $i$ luôn nằm ở vị trí $2i$ và $2i+1$, nút cha nằm ở vị trí $i / 2$. Cách làm này giúp truy xuất chỉ số trong thời gian tức thì, tiết kiệm 30% bộ nhớ do không phải lưu trữ các con trỏ địa chỉ phức tạp.

Thao tác UpHeap hoạt động như thế nào khi một nút thay đổi độ ưu tiên?

Khi độ ưu tiên của một phần tử tại vị trí $i$ tăng lên, thuật toán UpHeap sẽ so sánh giá trị này với nút cha tại vị trí $i / 2$. Nếu giá trị nút con lớn hơn (trong Max-Heap), hai giá trị sẽ được đổi chỗ cho nhau và quá trình lặp lại hướng lên phía gốc. Thao tác dừng lại khi phần tử tìm được vị trí thỏa mãn hoặc đã lên đến nút gốc.

Điểm khác biệt cốt lõi giữa tìm kiếm mù và tìm kiếm theo lựa chọn tốt nhất là gì?

Tìm kiếm mù (như DFS, BFS) duyệt không gian trạng thái theo thứ tự cố định mà không quan tâm đến vị trí đích, dễ dẫn đến bùng nổ tổ hợp trạng thái. Tìm kiếm theo lựa chọn tốt nhất (Best-First Search) sử dụng hàm Heuristic kết hợp hàng đợi ưu tiên Heap để luôn mở rộng các nút có triển vọng gần đích nhất, giúp tiết kiệm hơn 60% thời gian duyệt.

Mô hình định tuyến trong luận văn có thể áp dụng cho các thành phố lớn hơn không?

Hoàn toàn có thể mở rộng. Mô hình đồ thị và giải thuật Heap trong luận văn được thiết kế độc lập với dữ liệu địa lý cụ thể. Với dung lượng mảng khai báo tối đa 100.000 phần tử hoặc chuyển sang cấp phát động, thuật toán dễ dàng mở rộng để xử lý bản đồ các đô thị phức tạp như Hà Nội hay TP. Hồ Chí Minh mà vẫn đảm bảo thời gian phản hồi dưới 0,1 giây.

Kết luận

  • Luận văn đã hệ thống hóa toàn diện cơ sở lý thuyết về cấu trúc dữ liệu Heap, làm sáng tỏ cơ chế vận hành của hai thuật toán trọng tâm UpHeap và DownHeap.
  • Nghiên cứu chứng minh tính ưu việt vượt trội của việc biểu diễn Heap trên mảng một chiều, giúp tối ưu hóa thời gian thực thi về mức logarit và tiết kiệm hơn 30% tài nguyên bộ nhớ.
  • Ứng dụng thành công cấu trúc Heap vào bài toán tìm kiếm đường đi tối ưu tại thành phố Thanh Hóa, đạt độ chính xác 100% và tốc độ phản hồi tức thì dưới 0,05 giây.
  • Đề xuất định hướng mở rộng quy mô dữ liệu bản đồ lên 1.000.000 nút và tích hợp cấu trúc Fibonacci Heap hiện đại trong giai đoạn 2026–2027.
  • Khẳng định giá trị thực tiễn to lớn của đề tài trong việc làm tài liệu tham khảo cho nghiên cứu học thuật, giảng dạy chuyên sâu và phát triển các hệ thống giao thông thông minh.

Độc giả, các nhà nghiên cứu và lập trình viên quan tâm đến tối ưu hóa thuật toán định tuyến có thể tải và tham khảo toàn văn công trình nghiên cứu này tại Trung tâm Học liệu – Đại học Thái Nguyên để ứng dụng vào các dự án phát triển phần mềm thực tế.