Bài 6.4 - Thuật toán Python: tìm cặp phần tử gần nhất

Chào mừng bạn đến với bài học hôm nay, nơi chúng ta sẽ cùng nhau khám phá một bài toán kinh điển trong lập trình: tìm cặp phần tử gần nhau nhất trong một tập hợp các số. Đây là một vấn đề có nhiều ứng dụng thực tế, từ phân tích dữ liệu, xử lý hình ảnh, cho đến các bài toán tối ưu hóa trong nhiều lĩnh vực khác. "Gần nhau nhất" ở đây được hiểu là cặp hai phần tử có hiệu tuyệt đối nhỏ nhất.

Trong bài viết này, chúng ta sẽ xem xét hai cách tiếp cận chính để giải quyết vấn đề này bằng Python: một phương pháp đơn giản nhưng kém hiệu quả và một phương pháp tối ưu hơn đáng kể.

Định nghĩa Bài toán

Cho một danh sách (list) các số. Yêu cầu là tìm ra cặp hai số (a, b) trong danh sách sao cho giá trị của abs(a - b) là nhỏ nhất.

Ví dụ: Với danh sách [5, 2, 8, 1, 9], các cặp có thể có và hiệu tuyệt đối của chúng là:

(5, 2): abs(5 - 2) = 3
(5, 8): abs(5 - 8) = 3
(5, 1): abs(5 - 1) = 4
(5, 9): abs(5 - 9) = 4
(2, 8): abs(2 - 8) = 6
(2, 1): abs(2 - 1) = 1
(2, 9): abs(2 - 9) = 7
(8, 1): abs(8 - 1) = 7
(8, 9): abs(8 - 9) = 1
(1, 9): abs(1 - 9) = 8

Hiệu tuyệt đối nhỏ nhất trong trường hợp này là 1, đạt được bởi hai cặp: (2, 1) và (8, 9). Thông thường, bài toán chỉ yêu cầu trả về một trong các cặp đó.

Cách tiếp cận "Vét cạn" (Brute Force)

Cách đơn giản và trực quan nhất để giải quyết bài toán này là kiểm tra tất cả các cặp có thể có trong danh sách, tính hiệu tuyệt đối của chúng và ghi nhận cặp nào cho hiệu nhỏ nhất. Đây được gọi là cách tiếp cận "vét cạn" hay brute force.

Để làm điều này, chúng ta sẽ sử dụng hai vòng lặp lồng nhau. Vòng lặp ngoài chọn phần tử thứ nhất, và vòng lặp trong chọn phần tử thứ hai khác phần tử thứ nhất và chưa từng được ghép cặp với phần tử thứ nhất trước đó.

Code Python (Vét cạn)

import math # Can thiet cho math.inf

def tim_cap_gan_nhat_naive(danh_sach):
    """
    Tim cap phan tu gan nhat trong danh sach bang thuat toan vet can.

    Args:
        danh_sach: Mot list cac so.

    Returns:
        Mot tuple (cap_phan_tu, hieu_nho_nhat) hoac None neu danh sach co < 2 phan tu.
    """
    # Kiem tra truong hop danh sach khong hop le
    if len(danh_sach) < 2:
        print("Danh sach phai co it nhat 2 phan tu.")
        return None, None # Hoac co the raise mot exception tuy vao yeu cau

    min_diff = float('inf') # Khoi tao hieu nho nhat voi gia tri vo cung lon
    cap_gan_nhat = None      # Khoi tao cap gan nhat

    n = len(danh_sach)

    # Duyet qua tat ca cac cap (i, j) voi i < j
    for i in range(n):
        for j in range(i + 1, n): # Bat dau tu i + 1 de tranh so sanh voi chinh no va cac cap da xet
            phan_tu_i = danh_sach[i]
            phan_tu_j = danh_sach[j]
            diff = abs(phan_tu_i - phan_tu_j) # Tinh hieu tuyet doi

            # Neu tim thay hieu nho hon hieu nho nhat hien tai
            if diff < min_diff:
                min_diff = diff          # Cap nhat hieu nho nhat
                cap_gan_nhat = (phan_tu_i, phan_tu_j) # Cap nhat cap gan nhat

    return cap_gan_nhat, min_diff

# --- Cac vi du minh hoa cho thuat toan vet can ---

print("--- Vi du cho thuat toan vet can ---")

# Vi du 1: Danh sach don gian
danh_sach_1 = [5, 2, 8, 1, 9]
cap_1, hieu_1 = tim_cap_gan_nhat_naive(danh_sach_1)
print(f"Danh sach: {danh_sach_1}")
if cap_1:
    print(f"Cap gan nhat: {cap_1}, Hieu nho nhat: {hieu_1}")
else:
    print("Khong tim thay cap nao (danh sach qua ngan).")

print("-" * 20)

# Vi du 2: Danh sach co so am
danh_sach_2 = [-10, -3, 0, 7, 15]
cap_2, hieu_2 = tim_cap_gan_nhat_naive(danh_sach_2)
print(f"Danh sach: {danh_sach_2}")
if cap_2:
    print(f"Cap gan nhat: {cap_2}, Hieu nho nhat: {hieu_2}")
else:
    print("Khong tim thay cap nao (danh sach qua ngan).")

print("-" * 20)

# Vi du 3: Danh sach co cac so gan nhau
danh_sach_3 = [1.5, 2.1, 3.8, 4.0, 2.2]
cap_3, hieu_3 = tim_cap_gan_nhat_naive(danh_sach_3)
print(f"Danh sach: {danh_sach_3}")
if cap_3:
    print(f"Cap gan nhat: {cap_3}, Hieu nho nhat: {hieu_3}")
else:
    print("Khong tim thay cap nao (danh sach qua ngan).")

print("-" * 20)

# Vi du 4: Danh sach co phan tu trung lap
danh_sach_4 = [3, 1, 4, 1, 5, 9, 2, 6]
cap_4, hieu_4 = tim_cap_gan_nhat_naive(danh_sach_4)
print(f"Danh sach: {danh_sach_4}")
if cap_4:
    print(f"Cap gan nhat: {cap_4}, Hieu nho nhat: {hieu_4}")
else:
    print("Khong tim thay cap nao (danh sach qua ngan).")

print("-" * 20)

# Vi du 5: Danh sach qua ngan
danh_sach_5 = [10]
cap_5, hieu_5 = tim_cap_gan_nhat_naive(danh_sach_5)
print(f"Danh sach: {danh_sach_5}")
if cap_5:
    print(f"Cap gan nhat: {cap_5}, Hieu nho nhat: {hieu_5}")
else:
    print("Khong tim thay cap nao (danh sach qua ngan).")

print("-" * 20)

Giải thích Code (Vét cạn)

Hàm tim_cap_gan_nhat_naive(danh_sach) nhận vào một list là danh_sach.
Đầu tiên, chúng ta kiểm tra xem danh sách có ít nhất 2 phần tử hay không. Nếu không, không thể tạo thành cặp, nên hàm trả về None.
Biến min_diff được khởi tạo bằng float('inf'). Đây là một giá trị vô cùng lớn, đảm bảo rằng hiệu tuyệt đối của cặp đầu tiên chúng ta kiểm tra sẽ nhỏ hơn nó, và min_diff sẽ được cập nhật ngay lập tức.
Biến cap_gan_nhat lưu trữ cặp phần tử tìm được, ban đầu là None.
Hai vòng lặp for lồng nhau duyệt qua tất cả các cặp phân biệt. Vòng lặp ngoài i đi từ chỉ số 0 đến n-1. Vòng lặp trong j đi từ i + 1 đến n-1. Điều này đảm bảo mỗi cặp chỉ được xét một lần và không so sánh một phần tử với chính nó.
Bên trong vòng lặp, chúng ta lấy ra hai phần tử danh_sach[i] và danh_sach[j].
abs(phan_tu_i - phan_tu_j) tính hiệu tuyệt đối.
Nếu diff nhỏ hơn min_diff hiện tại, chúng ta cập nhật min_diff bằng diff mới và lưu lại cặp (phan_tu_i, phan_tu_j) vào cap_gan_nhat.
Cuối cùng, hàm trả về cap_gan_nhat và min_diff tương ứng.

Đánh giá (Vét cạn)

Thuật toán này chính xác và dễ hiểu. Tuy nhiên, nó có một nhược điểm lớn về hiệu suất. Với một danh sách có n phần tử, chúng ta cần kiểm tra khoảng n * (n-1) / 2 cặp. Số lượng thao tác tăng theo bình phương số lượng phần tử. Trong thuật ngữ độ phức tạp thời gian, thuật toán này có độ phức tạp là O(n^2). Điều này có nghĩa là nếu kích thước danh sách tăng gấp đôi, thời gian chạy sẽ tăng khoảng bốn lần. Với danh sách lớn, thuật toán vét cạn sẽ trở nên rất chậm.

Cách tiếp cận Tối ưu hóa (Sắp xếp)

Liệu có cách nào nhanh hơn không? Câu trả lời là có, và chìa khóa nằm ở việc sắp xếp danh sách trước.

Hãy suy nghĩ một chút: Nếu danh sách đã được sắp xếp theo thứ tự tăng dần, các phần tử "gần nhau nhất" rất có khả năng nằm cạnh nhau. Thực tế, một cách chứng minh toán học cho thấy cặp phần tử có hiệu tuyệt đối nhỏ nhất phải là một cặp phần tử liền kề trong danh sách đã được sắp xếp.

Vì vậy, thuật toán tối ưu sẽ bao gồm hai bước:

Sắp xếp danh sách các số.
Duyệt qua các phần tử liền kề trong danh sách đã sắp xếp và tìm cặp có hiệu tuyệt đối nhỏ nhất.

Code Python (Sắp xếp)

import math # Can thiet cho math.inf

def tim_cap_gan_nhat_toi_uu(danh_sach):
    """
    Tim cap phan tu gan nhat trong danh sach bang thuat toan sap xep.

    Args:
        danh_sach: Mot list cac so.

    Returns:
        Mot tuple (cap_phan_tu, hieu_nho_nhat) hoac None neu danh sach co < 2 phan tu.
    """
    # Kiem tra truong hop danh sach khong hop le
    if len(danh_sach) < 2:
        print("Danh sach phai co it nhat 2 phan tu.")
        return None, None

    # Buoc 1: Sao chep danh sach va sap xep
    # Su dung sorted() de tao mot ban sao da sap xep, khong lam thay doi danh sach goc
    danh_sach_sorted = sorted(danh_sach)

    min_diff = float('inf') # Khoi tao hieu nho nhat
    cap_gan_nhat = None      # Khoi tao cap gan nhat

    # Buoc 2: Duyet qua cac phan tu lien ke trong danh sach da sap xep
    # Duyet den phan tu thu n-2 vi can cap (i, i+1)
    for i in range(len(danh_sach_sorted) - 1):
        phan_tu_i = danh_sach_sorted[i]
        phan_tu_i_plus_1 = danh_sach_sorted[i+1]
        diff = abs(phan_tu_i - phan_tu_i_plus_1) # Tinh hieu tuyet doi giua hai phan tu lien ke

        # Neu tim thay hieu nho hon
        if diff < min_diff:
            min_diff = diff          # Cap nhat hieu nho nhat
            cap_gan_nhat = (phan_tu_i, phan_tu_i_plus_1) # Cap nhat cap gan nhat

    return cap_gan_nhat, min_diff

# --- Cac vi du minh hoa cho thuat toan sap xep ---

print("\n--- Vi du cho thuat toan sap xep ---")

# Vi du 1: Danh sach don gian
danh_sach_1_sort = [5, 2, 8, 1, 9]
cap_1_sort, hieu_1_sort = tim_cap_gan_nhat_toi_uu(danh_sach_1_sort)
print(f"Danh sach goc: {danh_sach_1_sort}")
print(f"Danh sach da sap xep: {sorted(danh_sach_1_sort)}") # In them de minh hoa
if cap_1_sort:
    print(f"Cap gan nhat: {cap_1_sort}, Hieu nho nhat: {hieu_1_sort}")
else:
    print("Khong tim thay cap nao (danh sach qua ngan).")

print("-" * 20)

# Vi du 2: Danh sach co so am va so duong
danh_sach_2_sort = [-10, -3, 0, 7, 15]
cap_2_sort, hieu_2_sort = tim_cap_gan_nhat_toi_uu(danh_sach_2_sort)
print(f"Danh sach goc: {danh_sach_2_sort}")
print(f"Danh sach da sap xep: {sorted(danh_sach_2_sort)}")
if cap_2_sort:
    print(f"Cap gan nhat: {cap_2_sort}, Hieu nho nhat: {hieu_2_sort}")
else:
    print("Khong tim thay cap nao (danh sach qua ngan).")

print("-" * 20)

# Vi du 3: Danh sach co cac so thuc gan nhau
danh_sach_3_sort = [1.5, 2.1, 3.8, 4.0, 2.2]
cap_3_sort, hieu_3_sort = tim_cap_gan_nhat_toi_uu(danh_sach_3_sort)
print(f"Danh sach goc: {danh_sach_3_sort}")
print(f"Danh sach da sap xep: {sorted(danh_sach_3_sort)}")
if cap_3_sort:
    print(f"Cap gan nhat: {cap_3_sort}, Hieu nho nhat: {hieu_3_sort}")
else:
    print("Khong tim thay cap nao (danh sach qua ngan).")

print("-" * 20)

# Vi du 4: Danh sach co nhieu phan tu trung lap
danh_sach_4_sort = [3, 1, 4, 1, 5, 9, 2, 6]
cap_4_sort, hieu_4_sort = tim_cap_gan_nhat_toi_uu(danh_sach_4_sort)
print(f"Danh sach goc: {danh_sach_4_sort}")
print(f"Danh sach da sap xep: {sorted(danh_sach_4_sort)}")
if cap_4_sort:
    print(f"Cap gan nhat: {cap_4_sort}, Hieu nho nhat: {hieu_4_sort}")
else:
    print("Khong tim thay cap nao (danh sach qua ngan).")

print("-" * 20)

# Vi du 5: Danh sach da sap xep truoc
danh_sach_5_sort = [10, 15, 20, 22, 30]
cap_5_sort, hieu_5_sort = tim_cap_gan_nhat_toi_uu(danh_sach_5_sort)
print(f"Danh sach goc: {danh_sach_5_sort}")
print(f"Danh sach da sap xep: {sorted(danh_sach_5_sort)}")
if cap_5_sort:
    print(f"Cap gan nhat: {cap_5_sort}, Hieu nho nhat: {hieu_5_sort}")
else:
    print("Khong tim thay cap nao (danh sach qua ngan).")

print("-" * 20)

# Vi du 6: Danh sach qua ngan
danh_sach_6_sort = [100]
cap_6_sort, hieu_6_sort = tim_cap_gan_nhat_toi_uu(danh_sach_6_sort)
print(f"Danh sach goc: {danh_sach_6_sort}")
if cap_6_sort:
    print(f"Cap gan nhat: {cap_6_sort}, Hieu nho nhat: {hieu_6_sort}")
else:
    print("Khong tim thay cap nao (danh sach qua ngan).")

Giải thích Code (Sắp xếp)

Tương tự như thuật toán vét cạn, chúng ta kiểm tra độ dài danh sách.
Điểm khác biệt mấu chốt: Chúng ta sử dụng hàm sorted(danh_sach) để tạo ra một bản sao đã sắp xếp của danh sách gốc. Điều này không làm thay đổi thứ tự các phần tử trong danh_sach ban đầu.
Các biến min_diff và cap_gan_nhat vẫn được khởi tạo như trước.
Bây giờ, chúng ta chỉ cần một vòng lặp duyệt qua danh sách đã sắp xếp từ chỉ số 0 đến n-2. Lý do là ở mỗi bước lặp i, chúng ta so sánh phần tử tại chỉ số i với phần tử liền kề nó tại chỉ số i+1. Vòng lặp kết thúc khi i là n-2 (phần tử áp chót), vì khi đó i+1 là n-1 (phần tử cuối cùng), và đó là cặp cuối cùng có thể tạo ra từ các phần tử liền kề.
abs(phan_tu_i - phan_tu_i_plus_1) tính hiệu tuyệt đối giữa hai phần tử liền kề.
Nếu hiệu này nhỏ hơn min_diff hiện tại, chúng ta cập nhật min_diff và cap_gan_nhat.
Cuối cùng, hàm trả về cặp và hiệu nhỏ nhất.

Đánh giá (Sắp xếp)

Thuật toán này cũng chính xác và hiệu quả hơn nhiều so với cách vét cạn. Độ phức tạp thời gian của thuật toán này phụ thuộc vào hai bước:

Sắp xếp: Sử dụng thuật toán sắp xếp hiệu quả (như Timsort mà Python sử dụng cho list) có độ phức tạp là O(n log n).
Duyệt liền kề: Duyệt qua danh sách đã sắp xếp chỉ mất O(n) thời gian (vì chỉ cần một vòng lặp đơn giản).

Tổng cộng, độ phức tạp thời gian của thuật toán này là O(n log n) + O(n), mà trong phân tích độ phức tạp, phần trội hơn sẽ quyết định, nên tổng là O(n log n).

So với O(n^2) của thuật toán vét cạn, O(n log n) là tốt hơn rất nhiều, đặc biệt với danh sách lớn. Ví dụ, nếu n = 1000, n^2 là 1,000,000, trong khi n log n (với log cơ số 2) chỉ khoảng 1000 * 10 = 10,000. Sự khác biệt này càng lớn khi n tăng lên.

Mở rộng: Tìm tất cả các cặp gần nhất

Các thuật toán trên chỉ trả về một cặp gần nhất. Nếu có nhiều cặp cùng có hiệu tuyệt đối nhỏ nhất (ví dụ: [1, 2, 4, 5], cả (1, 2) và (4, 5) đều có hiệu là 1), chúng ta có thể muốn nhận được tất cả các cặp đó.

Chúng ta có thể dễ dàng sửa đổi thuật toán sắp xếp để đạt được điều này. Thay vì chỉ cập nhật cap_gan_nhat khi tìm thấy hiệu nhỏ hơn, chúng ta sẽ sử dụng một danh sách để lưu trữ các cặp. Khi tìm thấy hiệu nhỏ hơn, chúng ta xóa sạch danh sách cũ và thêm cặp mới vào. Khi tìm thấy hiệu bằng với min_diff, chúng ta thêm cặp mới vào danh sách.

import math

def tim_tat_ca_cap_gan_nhat_toi_uu(danh_sach):
    """
    Tim TAT CA cac cap phan tu gan nhat trong danh sach bang thuat toan sap xep.

    Args:
        danh_sach: Mot list cac so.

    Returns:
        Mot list cac tuple (phan_tu_1, phan_tu_2) chua cac cap gan nhat,
        hoac mot list rong neu danh sach co < 2 phan tu.
    """
    if len(danh_sach) < 2:
        print("Danh sach phai co it nhat 2 phan tu.")
        return [] # Tra ve danh sach rong

    danh_sach_sorted = sorted(danh_sach)

    min_diff = float('inf')
    danh_sach_cap_gan_nhat = [] # Su dung list de luu tru nhieu cap

    for i in range(len(danh_sach_sorted) - 1):
        phan_tu_i = danh_sach_sorted[i]
        phan_tu_i_plus_1 = danh_sach_sorted[i+1]
        diff = abs(phan_tu_i - phan_tu_i_plus_1)

        if diff < min_diff:
            # Tim thay hieu nho hon --> reset danh sach cap gan nhat
            min_diff = diff
            danh_sach_cap_gan_nhat = [(phan_tu_i, phan_tu_i_plus_1)]
        elif diff == min_diff:
            # Tim thay hieu bang hieu nho nhat --> them vao danh sach
            danh_sach_cap_gan_nhat.append((phan_tu_i, phan_tu_i_plus_1))

    # Co the tra ve min_diff cung voi list neu can
    return danh_sach_cap_gan_nhat

# --- Cac vi du minh hoa cho thuat toan tim tat ca cap gan nhat ---

print("\n--- Vi du cho thuat toan tim tat ca cap gan nhat ---")

# Vi du 1: Co nhieu cap cung gan nhat
danh_sach_multi_1 = [1, 5, 2, 8, 9]
# Sorted: [1, 2, 5, 8, 9]
# Pairs & Diffs: (1,2)=1, (2,5)=3, (5,8)=3, (8,9)=1
cap_multi_1 = tim_tat_ca_cap_gan_nhat_toi_uu(danh_sach_multi_1)
print(f"Danh sach goc: {danh_sach_multi_1}")
print(f"Danh sach da sap xep: {sorted(danh_sach_multi_1)}")
print(f"Tat ca cap gan nhat: {cap_multi_1}") # Expected: [(1, 2), (8, 9)]

print("-" * 20)

# Vi du 2: Chi co mot cap gan nhat duy nhat
danh_sach_multi_2 = [10, 30, 5, 40, 25]
# Sorted: [5, 10, 25, 30, 40]
# Pairs & Diffs: (5,10)=5, (10,25)=15, (25,30)=5, (30,40)=10
cap_multi_2 = tim_tat_ca_cap_gan_nhat_toi_uu(danh_sach_multi_2)
print(f"Danh sach goc: {danh_sach_multi_2}")
print(f"Danh sach da sap xep: {sorted(danh_sach_multi_2)}")
print(f"Tat ca cap gan nhat: {cap_multi_2}") # Expected: [(5, 10), (25, 30)] -- Oh wait, sorted is [5, 10, 25, 30, 40], diffs are 5, 15, 5, 10. Smallest diff is 5. Pairs are (5,10) and (25,30). Correct output.

print("-" * 20)

# Vi du 3: Danh sach co phan tu trung lap
danh_sach_multi_3 = [3, 1, 4, 1, 5, 9, 2, 6]
# Sorted: [1, 1, 2, 3, 4, 5, 6, 9]
# Pairs & Diffs: (1,1)=0
cap_multi_3 = tim_tat_ca_cap_gan_nhat_toi_uu(danh_sach_multi_3)
print(f"Danh sach goc: {danh_sach_multi_3}")
print(f"Danh sach da sap xep: {sorted(danh_sach_multi_3)}")
print(f"Tat ca cap gan nhat: {cap_multi_3}") # Expected: [(1, 1)]

print("-" * 20)

# Vi du 4: Danh sach qua ngan
danh_sach_multi_4 = [99]
cap_multi_4 = tim_tat_ca_cap_gan_nhat_toi_uu(danh_sach_multi_4)
print(f"Danh sach goc: {danh_sach_multi_4}")
print(f"Tat ca cap gan nhat: {cap_multi_4}") # Expected: []

Giải thích Code (Tìm tất cả cặp)

Hàm tim_tat_ca_cap_gan_nhat_toi_uu về cơ bản giống với tim_cap_gan_nhat_toi_uu, nhưng thay vì lưu trữ một tuple duy nhất trong cap_gan_nhat, nó sử dụng một danh sách tên là danh_sach_cap_gan_nhat.
Khi một diff nhỏ hơn min_diff hiện tại được tìm thấy, điều đó có nghĩa là chúng ta đã tìm thấy một hiệu nhỏ nhất mới. Chúng ta xóa sạch danh sách danh_sach_cap_gan_nhat hiện tại và chỉ thêm cặp mới tìm được vào.
Khi một diff bằng với min_diff hiện tại được tìm thấy, điều đó có nghĩa là chúng ta đã tìm thấy một cặp khác cũng có cùng hiệu nhỏ nhất. Chúng ta thêm cặp này vào danh sách danh_sach_cap_gan_nhat mà không xóa các cặp cũ.
Nếu diff lớn hơn min_diff, chúng ta không làm gì cả.
Hàm trả về danh sách danh_sach_cap_gan_nhat.

Tóm kết các cách tiếp cận

Chúng ta đã xem xét hai cách chính để tìm cặp phần tử gần nhất trong danh sách:

Vét cạn (Naive): Kiểm tra mọi cặp có thể. Đơn giản, dễ hiểu nhưng kém hiệu quả với độ phức tạp O(n^2). Chỉ nên dùng cho danh sách rất nhỏ hoặc khi việc code nhanh quan trọng hơn hiệu suất.
Sắp xếp (Optimized): Sắp xếp danh sách rồi duyệt các phần tử liền kề. Hiệu quả hơn nhiều với độ phức tạp O(n log n), phù hợp cho danh sách có kích thước từ trung bình đến lớn.

Phiên bản tối ưu hóa dựa trên sắp xếp là lựa chọn nên dùng trong hầu hết các trường hợp thực tế khi xử lý bài toán này. Việc mở rộng để tìm tất cả các cặp gần nhất cũng khá đơn giản khi đã có danh sách được sắp xếp.

Hy vọng qua bài viết này, bạn đã nắm vững cách tiếp cận và cài đặt các thuật toán tìm cặp phần tử gần nhất trong Python. Chúc bạn luyện tập vui vẻ!

Comments

There are no comments at the moment.