Thuật toán giảm thiểu giỏ hàng

Question

Tôi có danh sách products, bao gồm danh sách shops, đã bán nó.

{ 
    'Book A': [ShopA, ShopB, ShopC], 
    'Book B': [ShopC, ShopD], 
    'Movie C': [ShopA, ShopB, ShopD, ShopE], 
    ... 
} 

(Giá khác nhau giữa các cửa hàng)

Mỗi cửa hàng cũng có một chi phí vận chuyển. Đó là chi phí giao hàng "cho mỗi đơn đặt hàng", không quan trọng có bao nhiêu mục trong giỏ hàng của tôi. Và nó khác nhau giữa các cửa hàng.

Ex: nếu tôi mua "Book A" từ ShopA, "Book B" từ ShopC và "Phim C" từ ShopA, giá kết quả là: Book A price in ShopA + Book B price in ShopC + Movie C price in ShopA + ShopC shipping cost + ShopA shipping cost

Nếu chi phí giao hàng bằng 0 hoặc trên cơ sở mỗi mặt hàng và không đổi, tôi sẽ chỉ sắp xếp danh sách phiếu mua hàng theo trường price+shipping và tìm nạp kết quả đầu tiên từ mỗi bộ.

tôi cần phải mua tất cả các mục lần và tìm ra mức giá tối thiểu và tập kết quả.

Tôi không giỏi về thuật toán tối ưu hóa và lập trình động nên tôi cần giải pháp hoặc chỉ cần gật đầu đúng hướng.

Answer 1

Với quá ít mục, tôi có giải pháp. Nó là năng động.

Chúng tôi sẽ xử lý tất cả các cửa hàng lặp lại. Ở mỗi bước, chúng tôi lưu trữ giá tốt nhất hiện tại mà chúng tôi có thể bao gồm tất cả các tập hợp con của các mục. Ban đầu tất cả trong số đó là infinity giá ngoại trừ tập hợp con trống là 0 giá. Lưu ý rằng tất cả các tập con là 2^Num_products nhưng trong trường hợp của bạn chỉ là khoảng 1000.

Bây giờ chúng ta xử lý tiếp theo theo cửa hàng như thế nào: Hãy xem xét mọi tập hợp con có thể có của sản phẩm với cửa hàng này cửa hàng thực sự có thể cung cấp) và tất cả các sản phẩm còn lại được bao phủ bởi các cửa hàng bạn đã quan sát, do đó cải thiện chi phí tối thiểu bao gồm mọi tập hợp con. Bước này mất 2^Num_products*2^Num_products=4^Num_products, vẫn còn khoảng một triệu mà là bareable. Bạn làm điều này cho mỗi cửa hàng và cuối cùng câu trả lời là chi phí bao gồm tất cả các yếu tố. Toàn bộ độ phức tạp của giải pháp được đề xuất là 4^Num_products * num_shops, khoảng 50 triệu là tốt.

Lưu ý rằng điều này vẫn theo cấp số nhân và điều này không đáng ngạc nhiên. Cảm ơn bạn đã làm cho bằng chứng khó tin của mình về NP khó.

EDIT Thêm giải thích thêm của thuật toán trong giả:

init: 
cost[subset] = infi 
cost[{}] = 0 
for shop in shops 
new_prices = costs.dup() 
for set : subsets 
    for covered_set : all_subsets(set) 
    price = covered_set == {} ? 0 : delivery[shop] 
    remaining = set 
    for element : covered_set 
     if shop do not sale element 
     break for, choose next covered_set 
     price += el_price[element] 
     remaining.remove(element) 
    price += costs[remaining] 
    new_prices[set] = min(new_prices[set], price) 
costs = new_prices 
return costs[all] 

Lưu ý rằng ở đây tôi sử dụng bộ như index - đây là vì tôi thực sự sử dụng các đại diện bitmask của các tập con ví dụ như 1101 là một tập hợp con chứa yếu tố thứ nhất, thứ 2 và thứ tư. Do đó, một lần lặp của tất cả các bộ là for (int i = 0; i < (1 << n); i++).

Ngoài ra còn có một điều nữa: nếu bạn muốn chu kỳ tất cả các tập hợp con của một tập con S, bạn có thể thực hiện nhanh hơn lặp lại tất cả các tập con của tập hợp ban đầu và kiểm tra xem tập hợp con có tập hợp con là S hay không. Nếu S cũng được biểu diễn bằng bitmask bit_mask thì vòng lặp này sẽ thực hiện công việc: for(int i = bit_mask; i > 0; i = (i - 1) & bitmask). Sử dụng phương pháp này, bạn giảm độ phức tạp của thuật toán xuống 3^Num_products * num_shops. Tuy nhiên, điều này khó hiểu hơn một chút và có lẽ bạn sẽ cần viết một ví dụ để đảm bảo vòng lặp mà tôi đã viết thực sự xoay vòng tất cả các tập con của S. Về sự phức tạp - hãy tin tôi đi.

EDIT2 Đã chỉnh sửa điều kiện ngắt.cũng để tôi xây dựng trên tập hợp remaining và tính toán của nó: như dmzkrsk chỉ ra phần giả đề cập xóa khỏi tập hợp, nhưng bạn thực sự có thể chỉ định remaining = set^covered_set (hoạt động bit một lần nữa) trong trường hợp sử dụng bitmask để đại diện cho tập con.

Answer 2

Sự cố này là NP Hard.
Chúng tôi sẽ hiển thị giảm từ Hitting Set problem.
đánh Đặt vấn đề: Với bộ S1,S2,...,Sn và một số k: đã chọn thiết lập kích thước Sk, như vậy mà cho mỗi Si có một yếu tố s trong S mà s là trong Si. [định nghĩa thay thế: giao lộ giữa mỗi Si và S không trống].

Giảm:
Với một thể hiện của đánh bộ, dưới hình thức của (S1,...,Sn,k) tạo một thể hiện của vấn đề này:

All books cost nothing. In order to buy from each store you pay 1. 
The book i is sold by each store denoted in Si, minimal price for this instance is k. 

bằng chứng:
đánh Set -> Vấn đề này : Giả sử có một bộ nhấn tối thiểu trong (S1,...,Sn) kích thước k. Hãy để thiết lập hit này là S. Bằng cách mua từ mỗi cửa hàng ở S, chúng tôi có thể mua tất cả sách của mình với chi phí k, vì sách không có chi phí [trong xây dựng của chúng tôi] và chúng tôi đã mua tất cả sách và chúng tôi đã thanh toán cho đơn hàng từ các cửa hàng chính xác k. là k.
Vấn đề này -> Nhấn đặt: Giả sử có giá là k cho sự cố tại câu hỏi. Sau đó, từ việc xây dựng vấn đề và vì sách không có chi phí, chúng tôi cần mua ở k các cửa hàng khác nhau để nhận tất cả sách. Hãy để các cửa hàng này là S.Từ khi xây dựng vấn đề, S là một tập hợp đánh đối với (S1,...,Sn)
Q.E.D.

Kết luận:
Như vậy, vấn đề này là "không dễ dàng hơn sau đó" đánh Đặt vấn đề, và không có giải pháp đa thức nổi tiếng về vấn đề này, vì vậy - bức ảnh đẹp nhất của bạn, nếu bạn muốn giải pháp tối ưu, có lẽ là một số mũ, chẳng hạn như backtracking [Kiểm tra tất cả các khả năng và trả về giải pháp tối thiểu].

Answer 3

Một heuristic tốt có thể là tối ưu hóa thuộc địa kiến. Tôi sử dụng nó để giải quyết vấn đề người bán hàng du lịch. Bạn có thể tìm thấy một ví dụ làm việc từ google tsp solver. Đó là một thư viện javascript sử dụng một lực lượng vũ phu và một giải pháp lập trình động. AOC được sử dụng khi bạn có nhiều thành phố để tính toán thì giới hạn hiện tại là 20 thành phố. Tôi tin rằng bạn có thể sử dụng thư viện để giải quyết vấn đề của bạn và nó chỉ cần một chút viết lại. Với 20 thành phố, chương trình phải kiểm tra 20! posibilites. Trong trường hợp của bạn đó là một chút nhẹ hơn nhưng có lẽ chỉ có một cường độ.

Answer 4

Tôi đã xử lý vấn đề chính xác này một lần. Tôi đã không đưa ra bất kỳ giải pháp khác hơn là chỉ thử nghiệm tất cả các kết hợp có thể có của các cửa hàng nhưng có một cách dễ dàng để lọc ra nhiều cửa hàng trong mỗi sản phẩm.

1. Tính giá thấp nhất (bao gồm chi phí vận chuyển) của mỗi sản phẩm, hãy gọi nó là best_price.

2. Trong mỗi sản phẩm, chỉ giữ lại các cửa hàng mà giá của các cửa hàng (không có chi phí vận chuyển) < = best_price (với chi phí vận chuyển)

3. Kiểm tra tất cả các kết hợp có thể có của cửa hàng cho rẻ nhất.