Các thuật toán tham lam giống như các thuật toán lập trình động thường được sử dụng để giải quyết các vấn đề tối ưu (tìm giải pháp tốt nhất của vấn đề theo một tiêu chí cụ thể).

Các thuật toán tham lam thực hiện các lựa chọn địa phương tối ưu với hy vọng rằng những lựa chọn đó sẽ dẫn đến một giải pháp toàn cầu tối ưu để giải quyết vấn đề. Các thuật toán tham lam thường không quá khó để thiết lập, nhanh chóng (độ phức tạp thời gian thường là một hàm tuyến tính hoặc rất nhiều chức năng thứ hai). Bên cạnh đó, các chương trình này không khó để gỡ lỗi và sử dụng ít bộ nhớ hơn. Nhưng kết quả không phải lúc nào cũng là một giải pháp tối ưu.

Các chiến lược tham lam thường được sử dụng để giải quyết vấn đề tối ưu hóa tổ hợp bằng cách xây dựng một tùy chọn A. Tùy chọn A được xây dựng bằng cách chọn từng thành phần Ai của A cho đến khi hoàn thành (đủ n thành phần). Đối với mỗi Ai, bạn chọn Ai một cách tối ưu. Bằng cách này, có thể ở bước cuối cùng, bạn không có gì để chọn ngoài việc chấp nhận giá trị còn lại cuối cùng.

Có hai thành phần quan trọng của các quyết định tham lam:

  1. Cách lựa chọn. Bạn có thể chọn giải pháp nào là tốt nhất hiện tại và sau đó giải quyết tiểu từ việc thực hiện lựa chọn cuối cùng. Việc lựa chọn các thuật toán tham lam có thể phụ thuộc vào các lựa chọn trước đó. Thuật toán phát triển theo cách làm cho các lựa chọn trong một vòng lặp, đồng thời thu hẹp vấn đề nhất định thành các tiểu từ nhỏ hơn.
  2. Cấu trúc phụ tối ưu. Bạn thực hiện cấu trúc con tối ưu cho một vấn đề nếu giải pháp tối ưu của vấn đề này chứa các giải pháp tối ưu cho các subproblems của nó.

Các thành phần của thuật toán tham lam

  1. Một tập hợp các ứng cử viên, từ đó tạo ra các giải pháp.
  2. Một chức năng lựa chọn, để chọn ứng cử viên tốt nhất để thêm vào giải pháp.
  3. Một chức năng khả thi được sử dụng để quyết định xem một ứng cử viên có thể được sử dụng để xây dựng một giải pháp hay không.
  4. Một hàm khách quan, cố định giá trị của một giải pháp hoặc một giải pháp không đầy đủ.
  5. Một chức năng đánh giá, cho biết khi nào bạn tìm thấy một giải pháp hoàn chỉnh.

Trong hướng dẫn này, bạn sẽ tìm hiểu

Ý tưởng về tham lam một

Với ý tưởng đầu tiên, bạn có các bước sau của Greedy One:

  • Sắp xếp theo thứ tự giá trị không tăng.
  • Đổi lại, hãy xem xét các gói hàng đã đặt hàng, đặt gói cân nhắc vào knapsack nếu công suất còn lại của knapsack là đủ để chứa nó (có nghĩa là tổng trọng lượng của các gói đã được đưa vào ba gói và trọng lượng xem xét các gói không vượt quá công suất của knapsack).

Tuy nhiên, thuật toán tham lam này không phải lúc nào cũng đưa ra giải pháp tối ưu. Ở đây bạn có một ví dụ phản đối:

  • Các tham số của vấn đề là: n = 3; M = 19.
  • Các gói: {i = 1; W[i] = 14; V[i] = 20}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 8} -> lớn nhưng cũng có trọng lượng lớn.
  • Thuật toán sẽ chọn gói 1 với tổng giá trị là 20, trong khi giải pháp tối ưu của vấn đề được chọn (gói 2, gói 3) với tổng giá trị là 24.

Ý tưởng về Tham lam hai

Với ý tưởng thứ hai, bạn có các bước sau của Greedy Two:

  • Sắp xếp theo thứ tự trọng lượng không giảm.
  • Đổi lại, hãy xem xét các gói hàng đã đặt hàng, đặt gói cân nhắc vào knapsack nếu công suất còn lại của knapsack là đủ để chứa nó (có nghĩa là tổng trọng lượng của các gói đã được đưa vào ba gói và trọng lượng xem xét các gói không vượt quá công suất của knapsack).

Tuy nhiên, thuật toán tham lam này không phải lúc nào cũng đưa ra giải pháp tối ưu. Ở đây bạn có một ví dụ phản đối:

  • The parameters of the problem are: n = 3; M = 11.
  • Các gói: {i = 1; W[i] = 5; V[i] = 10}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 28} -> Trọng lượng nhẹ nhưng giá trị cũng rất nhẹ.
  • Thuật toán sẽ chọn (gói 1, gói 2) với tổng giá trị là 26, trong khi giải pháp tối ưu của vấn đề là (gói 3) với tổng giá trị là 28.

Ý tưởng về tham lam ba

Với ý tưởng thứ ba, bạn có các bước sau của Greedy Three. Trên thực tế, đây là thuật toán được sử dụng rộng rãi nhất.

  • Sắp xếp các gói theo thứ tự không tăng giá trị của chi phí đơn vị . Bạn có:

  • Đổi lại, hãy xem xét các gói hàng đã đặt hàng, đặt gói cân nhắc vào knapsack nếu công suất còn lại của knapsack là đủ để chứa nó (có nghĩa là tổng trọng lượng của các gói đã được đưa vào ba gói và trọng lượng xem xét các gói không vượt quá công suất của knapsack).

Ýtưởng : Ý tưởng tham lam của vấn đề đó là tính tỷ lệ của mỗi . Sau đó sắp xếp các tỷ lệ này với thứ tự giảm dần. Bạn sẽ chọn gói cao nhất và dung lượng của knapsack có thể chứa gói đó (vẫn > wI). Mỗi khi một gói được đưa vào knapsack, nó cũng sẽ làm giảm công suất của knapsack.

Cách chọn các gói:

  • Xem xét mảng chi phí đơn vị. Bạn chọn gói theo giảm chi phí đơn vị.

  • Giả sử bạn tìm thấy một giải pháp một phần: (x1, …, xI).
  • Giá trị của knapsack thu được:

  • Tương ứng với trọng lượng của các gói hàng đã được đưa vào knapsack:

  • Do đó, giới hạn trọng lượng còn lại của knapsack là:

Các bước của thuật toán tham lam: 

Bạn thấy đây là một vấn đề của việc tìm kiếm max. Danh sách các gói hàng được sắp xếp theo thứ tự giảm dần của chi phí đơn vị để xem xét phân nhánh.

  • Bước 1: Node root đại diện cho trạng thái ban đầu của knapsack, nơi bạn chưa chọn bất kỳ gói nào.
    • TotalValue = 0.
    • Giới hạn trên của nút gốc UpperBound = M * Chi phí đơn vị tối đa.
  • Bước 2: Gốc nút sẽ có các nút con tương ứng với khả năng chọn gói có chi phí đơn vị lớn nhất. Đối với mỗi nút, bạn tính toán lại các tham số:
    • TotalValue = TotalValue (cũ) + số lượng gói đã chọn * giá trị của mỗi gói hàng.
    • M = M (cũ) – số lượng gói hàng được chọn * trọng lượng của mỗi gói hàng.
    • UpperBound = TotalValue + M (mới) * Chi phí đơn vị của packaced sẽ được xem xét tiếp theo.
  • Bước 3: Trong các nút con, bạn sẽ ưu tiên phân nhánh cho nút có giới hạn trên lớn hơn. Con cái của nút này tương ứng với khả năng chọn gói tiếp theo có chi phí đơn vị lớn. Đối với mỗi nút, bạn phải tính toán lại các tham số TotalValue, M, UpperBound theo công thức được đề cập trong bước 2.
  • Bước 4: Lặp lại Bước 3 với ghi chú: đối với các nút có giới hạn trên là giá trị thấp hơn hoặc bằng với chi phí tối đa tạm thời của một tùy chọn được tìm thấy, bạn không cần phải phân nhánh cho nút đó nữa.
  • Bước 5: Nếu tất cả các nút được phân nhánh hoặc cắt bỏ, tùy chọn đắt nhất là tùy chọn cần tìm.

Mã giả cho thuật toán:

Fractional Knapsack (Array W, Array V, int M)
1. for i <- 1 to size (V)
2. 	calculate cost[i] <- V[i] / W[i]
3. Sort-Descending (cost)
4. i ← 1
5. while (i <= size(V))
6. 	if  W[i] <= M 
7.		M ← M – W[i]
8.		total ← total + V[i];
9. 	if  W[i] > M
10. 		i ← i+1

Độ phức tạp của thuật toán:

  • Nếu sử dụng thuật toán sắp xếp đơn giản (lựa chọn, bong bóng…) thì độ phức tạp của toàn bộ vấn đề là O(n2).
  • Nếu sử dụng sắp xếp nhanh hoặc sắp xếp hợp nhất thì độ phức tạp của toàn bộ vấn đề là O(nlogn).

Mã Java cho Greedy Three

  • Đầu tiên, bạn định nghĩa class KnapsackPackage. Lớp này có các thuộc tính là: trọng lượng, giá trị và chi phí tương ứng của mỗi gói hàng. Chi phí thuộc tính của lớp này được sử dụng để sắp xếp tác vụ trong thuật toán chính. Giá trị của từng chi phí là tỷ lệ của từng gói.
public class KnapsackPackage {
	
	private double weight;
	private double value;
	private Double cost;
	
	public KnapsackPackage(double weight, double value) {
		super();
		
		this.weight = weight;
		this.value = value;
		this.cost = new Double(value / weight);
	}

	public double getWeight() {
		return weight;
	}

	public double getValue() {
		return value;
	}

	public Double getCost() {
		return cost;
	}

}
  • Sau đó, bạn tạo một hàm để thực hiện thuật toán Greedy Three.
public void knapsackGreProc(int W[], int V[], int M, int n) {
	KnapsackPackage[] packs = new KnapsackPackage[n];
	for (int i = 0; i < n; i ++) {
		packs[i] = new KnapsackPackage(W[i], V[i]);
	}
	
	Arrays.sort(packs, new Comparator<KnapsackPackage>() {
		@Override
		public int compare(KnapsackPackage kPackA, KnapsackPackage kPackB) {
			return kPackB.getCost().compareTo(kPackA.getCost());
		}
	});
	
	int remain = M;	
double result = 0d;
	
	int i = 0;
	boolean stopProc = false;
	while (!stopProc) {
		if (packs[i].getWeight() <= remain) {
			remain -= packs[i].getWeight();
			result += packs[i].getValue();
			
			System.out.println("Pack " + i + " - Weight " + packs[i].getWeight() + " - Value " + packs[i].getValue());
		}
		
		if (packs[i].getWeight() > remain) {
			i ++;
		}
		
		if (i == n) {
			stopProc = true;
		}
	}
	
	System.out.println("Max Value:\t" + result);
}

Giải thích mã:

  1. Khởi tạo trọng lượng và giá trị cho mỗi gói knapsack.
  2. Sắp xếp các gói knapsack theo chi phí với đơn đặt hàng giảm dần.
  3. Nếu chọn gói i.
  4. Nếu chọn số lượng gói i là đủ.
  5. Dừng lại khi duyệt tất cả các gói.

Trong hướng dẫn này, bạn có hai ví dụ. Dưới đây là mã java để chạy chương trình trên với hai ví dụ:

public void run() {
	/*
	 * Pack and Weight - Value
	 */
//int W[] = new int[]{15, 10, 2, 4};
	int W[] = new int[]{12, 2, 1, 1, 4};
	
//int V[] = new int[]{30, 25, 2, 6};
	int V[] = new int[]{4, 2, 1, 2, 10};
	
	/*
	 * Max Weight
	 */
//int M = 37;
	int M = 15;
	int n = V.length;
	
	/*
	 * Run the algorithm
	 */
	knapsackGreProc(W, V, M, n);
}

Bạn có đầu ra:

  • Ví dụ đầu tiên:
Pack 0 - Weight 10.0 - Value 25.0
Pack 0 - Weight 10.0 - Value 25.0
Pack 0 - Weight 10.0 - Value 25.0
Pack 2 - Weight 4.0 - Value 6.0
Pack 3 - Weight 2.0 - Value 2.0
Max Value:	83.0
  • Ví dụ thứ hai:
Pack 0 - Weight 4.0 - Value 10.0
Pack 0 - Weight 4.0 - Value 10.0
Pack 0 - Weight 4.0 - Value 10.0
Pack 1 - Weight 1.0 - Value 2.0
Pack 1 - Weight 1.0 - Value 2.0
Pack 1 - Weight 1.0 - Value 2.0
Max Value:	36.0

Phân tích ví dụ đầu tiên:

  • The parameters of the problem are: n = 4; M = 37.
  • Các gói: {i = 1; W[i] = 15; V[i] = 30; Chi phí = 2,0}; {i = 2; W[i] = 10; V[i] = 25; Chi phí = 2,5}; {i = 3; W[i] = 2; V[i] = 4; Chi phí = 1,0}; {i = 4; W[i] = 4; V[i] = 6; Chi phí = 1,5}.
  • Bạn sắp xếp các gói theo thứ tự không làm tăng giá trị của chi phí đơn vị. Bạn có: {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.

Các bước áp dụng thuật toán cho ví dụ đầu tiên:

  • Xác định x1, x2, x3, x4 là số lượng của mỗi gói đã chọn, tương ứng với gói {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.
  • Nút gốc N đại diện cho trạng thái mà bạn chưa chọn bất kỳ gói nào. Sau đó:
    • TotalValue = 0.
    • M = 37 (như đề xuất).
    • UpperBound = 37 * 2.5 = 92.5, trong đó 37 là M và 2.5 là đơn giá của gói {i = 2}.
  • Với gói {i = 2}, bạn có 4 khả năng: chọn 3 gói {i = 2} (x1 = 3); chọn 2 gói {i = 2} (x1 = 2); chọn 1 gói {i = 2} (x1 = 1) và không chọn gói {i = 2} (x1 = 0). Theo 4 khả năng này, bạn phân nhánh nút gốc N cho 4 trẻ em N [1], N [2], N [3] và N [4].
  • Đối với nút con N1, bạn có:
    • TotalValue = 0 + 3 * 25 = 75, trong đó 3 là số gói {i = 2} được chọn và 25 là giá trị của mỗi gói {i = 2}.
    • M = 37 – 3 * 10 = 7, trong đó 37 là số lượng ban đầu của knapsack, 3 là số lượng gói {i = 2}, 10 là trọng lượng của mỗi gói {i = 2}.
    • UpperBound = 75 + 7 * 2 = 89, trong đó 75 là TotalValue, 7 là trọng lượng còn lại của knapsack và 2 là chi phí đơn vị của gói {i = 1}.
  • Tương tự, bạn có thể tính toán các tham số cho các nút N[2], N [3] và N [4], trong đó UpperBound lần lượt là 84, 79 và 74.

  • Trong số các nút N [1], N [2], N [3] và N [4], nút N [1] có UpperBound lớn nhất, vì vậy bạn sẽ phân nhánh nút N [1] đầu tiên với hy vọng rằng sẽ có một kế hoạch tốt từ hướng này.
  • Từ nút N[1], bạn chỉ có một nút con N[1-1] tương ứng với x2 = 0 (do trọng lượng còn lại của ba lô là 7, trong khi trọng lượng của mỗi gói {i = 1} là 15). Sau khi xác định các tham số cho nút N[1-1], bạn có UpperBound của N [1-1] là 85,5.
  • tiếp tục phân nhánh nút N[1-1]. Node N[1-1] có 2 con N[1-1-1] và N[1-1-2] tương ứng với x3 = 1 và x3 = 0. Sau khi xác định các tham số cho hai nút này, bạn thấy rằng UpperBoundary của N [1-1-1] là 84 và N [1-1-2] là 82, bạn tiếp tục phân nhánh nút N [1-1-1].
  • Node N[1-1-1] có hai con, N[1-1-1-1] và N[1-1-1-1-2], tương ứng với x4 = 1 và x4 = 0. Đây là hai nút lá (đại diện cho tùy chọn) bởi vì đối với mỗi nút, số lượng gói đã được chọn. Trong đó nút N[1-1-1-1] đại diện cho tùy chọn x1 = 3, x2 = 0, x3 = 1 và x4 = 1 cho 83, trong khi nút N[1-1-1-1-2] đại diện cho tùy chọn x1 = 3, x2 = 0, x3 = 1 và x4 = 01 tại 81. Vì vậy, giá trị tối đa tạm thời ở đây là 83.
  • Quay trở lại nút N[1-1-2], bạn thấy rằng UpperBound của N [1-1-2] là 82 < 83, vì vậy bạn cắt nút N [1-1-2].

  • Quay trở lại nút N2, bạn thấy rằng UpperBound của N2 là 84 > 83, vì vậy bạn tiếp tục phân nhánh nút N2. Nút N2 có hai con N[2-1] và N[2-2] tương ứng với x2 = 1 và x2 = 0. Sau khi tính toán các tham số cho N [2-1] và N [2-2], bạn thấy UpperBound của N [2-1] là 83 và N [2-2] là 75,25. Cả hai giá trị này đều không lớn hơn 83 nên cả hai nút đều được cắt tỉa.
  • Cuối cùng, các nút N3 và N4 cũng được cắt tỉa.
  • Vì vậy, tất cả các nút trên cây được phân nhánh hoặc cắt tỉa vì vậy giải pháp tạm thời tốt nhất là giải pháp cần tìm kiếm. Theo đó, bạn cần chọn 3 gói {i = 2}, 1 gói {i = 4} và một gói {i = 3} với tổng giá trị là 83, tổng trọng lượng là 36.

Với cùng một phân tích của ví dụ thứ hai, bạn có kết quả: chọn gói 4 (3 lần) và gói 5 (3 lần).

Python3 mã cho Greedy Three

  • Đầu tiên, bạn định nghĩa class KnapsackPackage.
class KnapsackPackage(object): 
      
    """ Knapsack Package Data Class """
    def __init__(self, weight, value): 
        self.weight = weight 
        self.value = value 
        self.cost = value / weight 
  
    def __lt__(self, other): 
        return self.cost < other.cost
  • Sau đó, bạn tạo một hàm để thực hiện thuật toán Greedy Three.
class FractionalKnapsack(object):
    def __init__(self):
        
    def knapsackGreProc(self, W, V, M, n):
        packs = []
        for i in range(n): 
            packs.append(KnapsackPackage(W[i], V[i]))
            
        packs.sort(reverse = True)
        
        remain = M
        result = 0
        
        i = 0
        stopProc = False
        
        while (stopProc != True):
            if (packs[i].weight <= remain):
                remain -= packs[i].weight;
                result += packs[i].value;
                
                print("Pack ", i, " - Weight ", packs[i].weight, " - Value ", packs[i].value)
            
            if (packs[i].weight > remain):
                i += 1
                
            if (i == n):
                stopProc = True            
        
        print("Max Value:\t", result)   
                                Hàm knapsackGreProc() trong Python

Giải thích mã:

  1. Khởi tạo trọng lượng và giá trị cho mỗi gói knapsack.
  2. Sắp xếp các gói knapsack theo chi phí với đơn đặt hàng giảm dần.
  3. Nếu chọn gói i.
  4. Nếu chọn số lượng gói i là đủ.
  5. Dừng lại khi duyệt tất cả các gói.

Dưới đây là mã Python3 để chạy chương trình trên với ví dụ đầu tiên:

if __name__ == "__main__": 
    W = [15, 10, 2, 4] 
    V = [30, 25, 2, 6] 
    M = 37
    n = 4
    
    proc = FractionalKnapsack()
    proc.knapsackGreProc(W, V, M, n)

Bạn có đầu ra:

Pack  0  - Weight  10  - Value  25
Pack  0  - Weight  10  - Value  25
Pack  0  - Weight  10  - Value  25
Pack  2  - Weight  4  - Value  6
Pack  3  - Weight  2  - Value  2
Max Value:	 83

Mã C# cho Greedy Three

  • Đầu tiên, bạn định nghĩa class KnapsackPackage.
using System;
namespace KnapsackProblem
{
    public class KnapsackPackage
    {
        private double weight;
        private double value;
        private double cost;

        public KnapsackPackage(double weight, double value)
        {
            this.weight = weight;
            this.value = value;

            this.cost = (double) value / weight;
        }

        public double Weight
        {
            get { return weight; }
        }

        public double Value
        {
            get { return value; }
        }

        public double Cost
        {
            get { return cost; }
        }
    }
}
  • Sau đó, bạn tạo một hàm để thực hiện thuật toán Greedy Three.
using System;
namespace KnapsackProblem
{
    public class FractionalKnapsack
    {
        public FractionalKnapsack()
        {
        }

        public void KnapsackGreProc(int[] W, int[] V, int M, int n)
        {
            KnapsackPackage[] packs = new KnapsackPackage[n];
            for (int k = 0; k < n; k++)
                packs[k] = new KnapsackPackage(W[k], V[k]);

            Array.Sort<KnapsackPackage>(packs, new Comparison<KnapsackPackage>(
                 (kPackA, kPackB) => kPackB.Cost.CompareTo(kPackA.Cost)));

            double remain = M;
            double result = 0d;

            int i = 0;
            bool stopProc = false;

            while (!stopProc)
            {
                if (packs[i].Weight <= remain)
                {
                    remain -= packs[i].Weight;
                    result += packs[i].Value;

                    Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight + " - Value " + packs[i].Value);
                }

                if (packs[i].Weight > remain)
                {
                    i++;
                }

                if (i == n)
                {
                    stopProc = true;
                }
            }

            Console.WriteLine("Max Value:\t" + result);
        }        
    }
}
Hàm KnapsackGreProc() trong C #

Giải thích mã:

  1. Khởi tạo trọng lượng và giá trị cho mỗi gói knapsack.
  2. Sắp xếp các gói knapsack theo chi phí với đơn đặt hàng giảm dần.
  3. Nếu chọn gói i.
  4. Nếu chọn số lượng gói i là đủ.
  5. Dừng lại khi duyệt tất cả các gói.

Dưới đây là mã C# để chạy chương trình trên với ví dụ đầu tiên:

public void run()
{
    /*
     * Pack and Weight - Value
     */
    int[] W = new int[]{15, 10, 2, 4};
    //int[] W = new int[] { 12, 2, 1, 1, 4 };

    int[] V = new int[]{30, 25, 2, 6};
    //int[] V = new int[] { 4, 2, 1, 2, 10 };

    /*
     * Max Weight
     */
    int M = 37;
    //int M = 15;
    int n = V.Length;

    /*
     * Run the algorithm
     */
    KnapsackGreProc(W, V, M, n);
}

Bạn có đầu ra:

Pack 0 - Weight 10 - Value 25
Pack 0 - Weight 10 - Value 25
Pack 0 - Weight 10 - Value 25
Pack 2 - Weight 4 - Value 6
Pack 3 - Weight 2 - Value 2
Max Value:	83

Counter-ví dụ về Greedy Three

Thuật toán của Greedy Three giải quyết nhanh chóng và cũng có thể tối ưu trong một số trường hợp. Tuy nhiên, trong một số trường hợp đặc biệt, nó không đưa ra giải pháp tối ưu. Ở đây bạn có một ví dụ phản đối:

  • The parameters of the problem are: n = 3; M = 10.
  • Các gói: {i = 1; W[i] = 7; V[i] = 9; Chi phí = 9/7}; {i = 2; W[i] = 6; V[i] = 6; Chi phí = 1}; {i = 3; W[i] = 4; V[i] = 4; Chi phí = 1}.
  • Thuật toán sẽ chọn (gói 1) với tổng giá trị là 9, trong khi giải pháp tối ưu của vấn đề là (gói 2, gói 3) với tổng giá trị là 10.

Dưới đây là code java để chạy chương trình trên với counter-example:

public void run() {
	/*
	 * Pack and Weight - Value
	 */
	int W[] = new int[]{7, 6, 4};
	
	int V[] = new int[]{9, 6, 4};
	
	/*
	 * Max Weight
	 */
	int M = 10;
	int n = V.length;
	
	/*
	 * Run the algorithm
	 */
	knapsackGreProc(W, V, M, n);
}

Đây là kết quả:

Pack 0 - Weight 7.0 - Value 9.0
Max Value:	9.0

Đó là tất cả cho vấn đề Fractional Knapsack.