Trung tâm cá nhân
cuốn sách gpt4 ai đã làm

Thuật toán tìm danh mục tối ưu của các dự án có ràng buộc cụ thể

In lại Tác giả: Taklimakan Thời gian cập nhật: 2023-11-03 03:10:04 27 4
mua khóa gpt4 Nike

Tôi sẽ cố gắng giải thích vấn đề này bằng ngôn ngữ toán học.
Giả sử tôi có một bộ vật phẩm X = {x_1, x_2, ..., x_n}. X Mỗi mục thuộc về bộ S_1, S_2, ..., S_5 một trong những. tôi nghĩ X Tất cả các tập hợp con của chứa 5 mục:{x_i1, x_i2, ..., xi5} 所以 x_i1 thuộc về S_1, ..., x_i5thuộc về S_5.
Một số tập hợp con được coi là đúng và một số tập hợp con được coi là không chính xác. Một tập hợp con được coi là đúng nếu nó không chứa các mục xung đột. Tôi có hàm f1 xác định xem một cặp mục có xung đột hay không.
Tôi cũng có hàm f2 để so sánh các tập hợp con chính xác này và cho biết tập hợp con nào tốt hơn (chúng cũng có thể bằng nhau).
Tôi cần tìm tập hợp con tốt nhất không xung đột.

Thuật toán tôi sử dụng:
Tôi đã xây dựng tất cả các tập hợp con và loại bỏ những tập hợp con không chính xác. Sau đó, tôi sử dụng f2 làm hàm sắp xếp để sắp xếp các tập hợp con chính xác và lấy tập hợp con tốt nhất đầu tiên (tôi sử dụng thuật toán quicksort). Trong phạm vi có một số lượng lớn các tập hợp con, quá trình này không đủ thời gian.

Có cách nào tốt hơn về mặt tiêu thụ thời gian?

đã cập nhật
Chúng ta hãy coi x_i là một khoảng có điểm cuối là số nguyên. Nếu hai khoảng không giao nhau, f1 trả về true, nếu không thì trả về false. f2 so sánh tổng chiều dài các khoảng trong các tập hợp con.

câu trả lời hay nhất

Câu hỏi này là một biến thể của thuật toán lập kế hoạch khoảng thời gian có trọng số tối đa. Độ phức tạp đa thức của thuật toán DP làO(N*log(N)). Và TRÊN)không gian cho những câu hỏi ngây thơ, vàO(2^G * N * logn(N)) O(2^G * N) Sự phức tạp của không gian vấn đề đang thay đổi này, trong đó G , Nbiểu thị tổng số nhóm/tập hợp con (ở đây là 5) và các khoảng tương ứng.

Nếu x_i không đại diện cho một khoảng thì vấn đề nằm ở NP, như các giải pháp khác đã chứng minh.

Đầu tiên chúng ta sẽ giải thích giải pháp quy hoạch động để lập kế hoạch khoảng thời gian có trọng số tối đa, sau đó giải quyết vấn đề biến phân.

  • Chúng tôi nhận được điểm bắt đầu và kết thúc của khoảng thời gian. cho phépbắt đầu(i) , kết thúc(i) , trọng lượng(tôi)Điểm bắt đầu, điểm kết thúc và độ dài của khoảngTôitương ứng.
  • Sắp xếp các khoảng theo thứ tự xuất xứ tăng dần.
  • Đặt thứ tự sắp xếp của các khoảng là1, 2,...N .
  • cho phéptiếp theo(i)có nghĩa là không với khoảng thời gian Tôi Khoảng tiếp theo trùng lặp.
  • Chúng ta hãy xác định một bài toán conS(tôi)là khoảng thời gian có trọng số tối đa chỉ xem xét các công việc tôi, tôi+1, ... N .
  • S(1)là giải pháp có tính đến 1,2,...N tất cả công việc trong và trả về khoảng thời gian có trọng số tối đa.
  • Bây giờ chúng ta hãy định nghĩaS(tôi)đệ quy.

.

S(i) = trọng lượng(i) if(i==N) // công việc cuối cùng
      = max(trọng lượng(i)+S(tiếp theo(i)), S(i+1)

Độ phức tạp của giải pháp này là O(N*log(N) + N) . N*log(N)đang tìm kiếm tiếp theo(i)cho mọi công việc và Nđược sử dụng để giải các bài toán con. không gian làTRÊN)Được sử dụng để lưu lời giải cho các bài toán con.

Bây giờ, hãy giải quyết các biến thể của vấn đề này.

  • Chúng ta hãy cùng nhau xem xét tất cả các khoảng trong X. Mỗi khoảng thuộc về một trong các tập S_1,... S_5.
  • cho phépbắt đầu(i) , kết thúc(i) , trọng lượng(tôi) , tập hợp con(i)là điểm bắt đầu, điểm kết thúc, độ dài khoảng và tập hợp con của khoảngTôitương ứng.
  • Sắp xếp các khoảng theo thứ tự xuất xứ tăng dần.
  • Đặt thứ tự sắp xếp của các khoảng là1, 2,...N .
  • cho phéptiếp theo(i)có nghĩa là không với khoảng thời gian Tôi Khoảng tiếp theo trùng lặp.
  • Chúng ta hãy xác định một bài toán conS(i,đang chờ xử lý)là khoảng thời gian có trọng số tối đa chỉ xem xét các công việc tôi, tôi+1, ... NVà chưa giải quyếtlà danh sách các tập hợp con mà chúng ta phải chọn một khoảng.
  • S(1, {S_1,...S_5})là một giải pháp xem xét mọi công việc1,...N , vì S_1,...S_5 Mỗi lựa chọn một khoảng thời gian và trả về khoảng thời gian có trọng số tối đa.
  • Bây giờ chúng ta hãy định nghĩaS(tôi)Sự đệ quy như sau.

.

S(i, đang chờ xử lý) = 0 if(pending==empty_set) // có thể kết hợp
               = -inf if(i==N && đang chờ xử lý!={group(i)}) // kết hợp sai
               = S(i+1, đang chờ xử lý) if(nhóm(i) không phải là thành phần đang chờ xử lý)
               = max(weight(i)+S(next(i), đang chờ xử lý nhóm(i)),
                     S(i+1, đang chờ xử lý)

Xin lưu ý rằng tôi có thể thiếu một số tình huống cơ bản.

Độ phức tạp của thuật toán này là O(2^G * N * logn(N))Và O(2^G * N)không gian. 2^G*Nđại diện cho kích thước của bài toán con.

Theo ước tính, đối với G<=10 Các giá trị nhỏ và cao của N>=100000 , thuật toán này chạy rất nhanh. vì G>=20 giá trị trung bình của N<=10000Để thuật toán hội tụ thì nó cũng phải ở mức thấp. Và đối với G>=40 Đối với giá trị cao của , thuật toán không hội tụ.

Về thuật toán tìm danh mục dự án tối ưu theo các ràng buộc cụ thể, chúng tôi đã tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/8800226/

27 4 0
Bài viết khuyến nghị: Làm thế nào để tìm ra cách tốt nhất để sắp xếp 8 phần tử và chứng minh rằng không có cách nào tốt hơn (không có cách nào hiệu quả hơn)?
Bài viết khuyến nghị: java - 锁拆分与锁 strip 化
Bài viết khuyến nghị: Java có tự động lưu các câu lệnh 'đánh giá' trong các biến Java được xác định trước không?
Bài viết khuyến nghị: Làm thế nào để giải 2 câu đố quả cầu thủy tinh bằng lập trình?
Taklimakan
Hồ sơ

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá taxi Didi miễn phí
Phiếu giảm giá taxi Didi
Các bài viết phổ biến trên toàn bộ trang web
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress