Thuật Toán Tham Lam (Greedy Algorithm) Trong JavaScript: Bài Toán Đồng Xu và MST

Bạn đã bao giờ gặp một tình huống mà bạn phải ra quyết định từng bước một, hy vọng rằng mỗi quyết định sẽ đưa bạn đến giải pháp tối ưu nhất? Nếu có, bạn đã nếm trải một chút của thuật toán tham lam. Trong bài viết này, chúng ta sẽ cùng nhau tìm hiểu về thuật toán tham lam qua hai bài toán kinh điển: bài toán đồng xu và bài toán cây khung nhỏ nhất (MST) trong JavaScript.

Thuật toán tham lam không chỉ thú vị mà còn là nền tảng của nhiều ứng dụng thực tế trong lĩnh vực công nghệ. Hãy cùng khám phá chúng qua ngôn ngữ lập trình JavaScript và xem tại sao nó lại có giá trị trong ngành phát triển phần mềm ngày nay!

1. Tổng Quan Về Thuật Toán Tham Lam

Thuật toán tham lam là một cách tiếp cận giải quyết vấn đề bằng cách đưa ra những lựa chọn tối ưu tại mỗi bước của quá trình giải quyết. Thuật toán này luôn chọn giải pháp tốt nhất có thể trong từng bước, với hy vọng rằng tổng thể các quyết định đó sẽ tạo ra một giải pháp tối ưu toàn cục.

Ứng Dụng Thực Tế Của Thuật Toán Tham Lam

Các thuật toán tham lam có rất nhiều ứng dụng trong cuộc sống thực:

• Công nghệ mạng: Thuật toán tham lam giúp tối ưu hóa đường đi trong các mạng lưới lớn.
• Định tuyến GPS: Tìm đường đi ngắn nhất từ điểm A đến điểm B bằng cách lựa chọn các tuyến đường tối ưu tại từng bước.
• Tối ưu hóa kinh doanh: Thuật toán tham lam giúp lựa chọn sản phẩm hoặc dịch vụ nào để tối ưu hóa lợi nhuận với nguồn lực có hạn.

Giờ hãy đi vào chi tiết của từng bài toán để xem cách thuật toán tham lam hoạt động trong JavaScript.

2. Bài Toán Đồng Xu

Bài toán đồng xu yêu cầu bạn tìm ra cách dùng ít đồng xu nhất để trả lại một số tiền nhất định. Ví dụ, bạn có các mệnh giá đồng xu là 1, 5, 10, và 25 xu, và bạn cần trả lại 63 xu. Cách tiếp cận tham lam sẽ là luôn chọn đồng xu có mệnh giá lớn nhất mà không vượt quá số tiền cần trả.

Cách Giải Quyết Bằng Thuật Toán Tham Lam

Dưới đây là cách triển khai thuật toán tham lam cho bài toán đồng xu trong JavaScript:

function minCoins(coins, amount) {
  let result = [];
  let i = coins.length - 1; // Bắt đầu từ đồng xu có mệnh giá lớn nhất

  while (amount > 0) {
    if (coins[i] <= amount) {
      result.push(coins[i]);
      amount -= coins[i]; // Trừ số tiền cần trả
    } else {
      i--; // Nếu đồng xu lớn hơn số tiền còn lại, chuyển sang đồng xu nhỏ hơn
    }
  }

  return result;
}

const coins = [1, 5, 10, 25]; // Các mệnh giá đồng xu
const amount = 63;

console.log(minCoins(coins, amount)); 
// Output: [25, 25, 10, 1, 1, 1] -> Cách dùng ít đồng xu nhất để trả 63 xu

Giải Thích Đoạn Code:

1. Input: Danh sách các mệnh giá đồng xu và số tiền cần trả.
2. Output: Danh sách các đồng xu sử dụng để trả số tiền đó.
3. Ý tưởng: Tại mỗi bước, chọn đồng xu có mệnh giá lớn nhất có thể. Khi số tiền còn lại nhỏ hơn mệnh giá đồng xu hiện tại, chuyển sang đồng xu nhỏ hơn.

3. Cây Khung Nhỏ Nhất (MST)

Cây khung nhỏ nhất (MST) là một bài toán kinh điển khác mà thuật toán tham lam được áp dụng. Bài toán yêu cầu bạn tìm cây khung (một đồ thị con không có chu trình) với tổng trọng số các cạnh nhỏ nhất có thể.

Thuật Toán Prim Trong JavaScript

Chúng ta sẽ sử dụng thuật toán Prim để giải quyết bài toán này. Đây là một ví dụ tuyệt vời về cách thuật toán tham lam hoạt động trong đồ thị.

class Graph {
  constructor(vertices) {
    this.V = vertices;
    this.graph = Array.from({ length: vertices }, () => []);
  }

  addEdge(u, v, w) {
    this.graph[u].push({ node: v, weight: w });
    this.graph[v].push({ node: u, weight: w }); // Vì đồ thị vô hướng
  }

  primMST() {
    const key = new Array(this.V).fill(Infinity); // Khởi tạo key của các đỉnh là vô hạn
    const parent = new Array(this.V).fill(-1);    // Để lưu cây khung
    const inMST = new Array(this.V).fill(false);  // Để theo dõi đỉnh đã có trong MST chưa
    key[0] = 0; // Bắt đầu từ đỉnh 0
    for (let count = 0; count < this.V - 1; count++) {
      let u = this.minKey(key, inMST);
      inMST[u] = true;

      for (let { node: v, weight: w } of this.graph[u]) {
        if (!inMST[v] && w < key[v]) {
          key[v] = w;
          parent[v] = u;
        }
      }
    }

    this.printMST(parent);
  }

  minKey(key, inMST) {
    let min = Infinity, minIndex = -1;
    for (let v = 0; v < this.V; v++) {
      if (!inMST[v] && key[v] < min) {
        min = key[v];
        minIndex = v;
      }
    }
    return minIndex;
  }

  printMST(parent) {
    console.log("Cạnh \tTrọng số");
    for (let i = 1; i < this.V; i++) {
      console.log(parent[i] + " - " + i + "\t" + this.graph[i].find(edge => edge.node === parent[i]).weight);
    }
  }
}

const g = new Graph(5);

g.addEdge(0, 1, 2);
g.addEdge(0, 3, 6);
g.addEdge(1, 2, 3);
g.addEdge(1, 3, 8);
g.addEdge(1, 4, 5);
g.addEdge(2, 4, 7);
g.addEdge(3, 4, 9);

g.primMST();

Giải Thích Đoạn Code:

1. Graph class: Định nghĩa đồ thị với số lượng đỉnh và các cạnh.
2. primMST method: Áp dụng thuật toán Prim để tìm cây khung nhỏ nhất bằng cách chọn cạnh có trọng số nhỏ nhất không tạo chu trình.
3. minKey method: Tìm đỉnh có giá trị trọng số nhỏ nhất chưa nằm trong MST.

4. Tại Sao Thuật Toán Tham Lam Quan Trọng?

Thuật toán tham lam không phải lúc nào cũng đưa ra giải pháp tối ưu, nhưng với các bài toán như đồng xu hoặc MST, chúng là cách tiếp cận đơn giản và hiệu quả nhất. Việc hiểu cách chúng hoạt động không chỉ giúp bạn giải quyết các bài toán cụ thể mà còn phát triển tư duy lập trình logic.

5. Kết Luận

Thuật toán tham lam trong JavaScript là một công cụ mạnh mẽ khi bạn cần giải quyết các bài toán mà quyết định tại mỗi bước không thay đổi được tương lai. Từ bài toán đồng xu đến bài toán cây khung nhỏ nhất, thuật toán tham lam mang lại nhiều giá trị thực tế và giúp đơn giản hóa các vấn đề phức tạp.

Bạn có thể thử áp dụng các đoạn mã trên vào bài toán của riêng mình, và đừng quên kiểm tra thêm các bài toán khác mà thuật toán tham lam có thể giải quyết. Nếu bạn muốn tìm hiểu thêm về lập trình, hãy ghé qua blog VNTALKING để khám phá nhiều chủ đề thú vị khác!