Câu hỏi Thuật toán để chọn hành động tối ưu để thực hiện tác vụ


Có hai loại dữ liệu: nhiệm vụ và hành động. Một hành động tốn một thời gian nhất định để hoàn thành và một tập hợp các tác vụ mà hành động này bao gồm. Một nhiệm vụ có một tập hợp các hành động, và công việc của chúng tôi là chọn một trong số chúng. Vì thế:

class Task { Set<Action> choices; }
class Action { float time; Set<Task> dependencies; }

Ví dụ: nhiệm vụ chính có thể là "Nhận nhà". Các hành động có thể có cho tác vụ này: "Mua nhà" hoặc "Xây dựng nhà". Hành động "Xây nhà" tốn 10 giờ và có phụ thuộc "Lấy gạch" (có thể mất 6 giờ) và "Mua xi măng" (có giá 9 giờ), v.v.

Các Tổng thời gian là tổng của tất cả thời gian của các hành động cần thiết để thực hiện (trong trường hợp này là 10 + 6 + 9 giờ). Chúng tôi muốn chọn các hành động sao cho tổng thời gian là tối thiểu.

Lưu ý rằng các phụ thuộc có thể là hình kim cương. Ví dụ: "Lấy gạch" có thể yêu cầu "Nhận xe" (để vận chuyển viên gạch) và "Lấy xi măng" cũng sẽ yêu cầu xe hơi. Ngay cả khi bạn làm "Nhận gạch" và "Nhận xi măng", bạn chỉ phải tính thời gian cần để có được một chiếc xe hơi Một lần.

Cũng lưu ý rằng các phụ thuộc có thể là hình tròn. Ví dụ: "Tiền" -> "Công việc" -> "Xe" -> "Tiền". Đây không phải là vấn đề đối với chúng tôi, chúng tôi chỉ cần chọn tất cả "Tiền", "Công việc" và "Xe hơi". Tổng thời gian chỉ đơn giản là tổng thời gian của 3 điều này.

Mô tả toán học:

Để cho actions là những hành động được chọn.

valid(task) = ∃action ∈ task.choices. (action ∈ actions ∧ ∀tasks ∈ action.dependencies. valid(task))
time = sum {action.time | action ∈ actions}
minimize time subject to valid(primaryTask)

Tôi quan tâm đến một giải pháp tối ưu mà còn trong một giải pháp gần đúng. Có lẽ một số loại chương trình năng động có thể giúp đỡ ở đó? Nếu vấn đề là cây có cấu trúc thì lập trình động có thể đưa ra một giải pháp tối ưu trong thời gian đa thức, nhưng cấu trúc kim cương dường như làm cho vấn đề trở nên khó khăn hơn nhiều. Nếu bạn có một thuật toán nhưng nó không hoạt động nếu có chu kỳ, hãy đăng nó! Tôi có lẽ vẫn có thể học được rất nhiều từ nó.

alt text

Các hộp đại diện cho các nhiệm vụ và các vòng tròn đại diện cho các hành động (thời gian để thực hiện hành động nằm trong vòng tròn). Một hành động có một dòng cho một nhiệm vụ nếu nhiệm vụ đó là một sự phụ thuộc cho hành động. Đây là mô tả của vấn đề một lần nữa về hình ảnh: nếu một hình chữ nhật (= nhiệm vụ) được chọn, sau đó một trong những vòng tròn (= hành động) bên trong phải được chọn. Nếu một vòng tròn được chọn, thì tất cả các các hình chữ nhật được kết nối phải được chọn. Mục đích là để giảm thiểu tổng số trong các vòng kết nối đã chọn.

Một giải pháp tối ưu trong trường hợp này là chọn hành động với thời gian 2 trong nhiệm vụ hàng đầu và các hành động với thời gian 1 trong các tác vụ phía dưới. Tổng thời gian là 2 + 1 + 1 = 4. Trong trường hợp này có 2 giải pháp tối ưu. Giải pháp thứ hai là chọn hành động với thời gian 3 trong nhiệm vụ hàng đầu, và hành động với thời gian 1 trong nhiệm vụ dưới cùng bên phải. Tổng thời gian là 3 + 1 = 4 lần nữa. Nếu chúng ta chọn hành động với thời gian 3 trong nhiệm vụ hàng đầu, chúng ta không phải thực hiện nhiệm vụ dưới cùng bên trái, bởi vì không có dòng giữa hành động với thời gian 3 và nhiệm vụ phía dưới bên trái.

Tôi xin lỗi vì bản vẽ crappy;) Và hai ví dụ khác (giải pháp tối ưu cho từng được chỉ định bằng màu xanh dương và nhiệm vụ chính đã được chỉ định bằng màu xám): alt text


7
2018-06-06 14:57


gốc


Làm thế nào một hành động có thể mất một khoảng thời gian cố định (Action.time)? Không nên một thời gian của hành động phụ thuộc vào thời gian cần thiết để hoàn thành mỗi nhiệm vụ của nó trong Action.dependencies? - mbeckish
Có bạn nói đúng, thuật ngữ là không may. Tổng thời gian thực hiện hành động thực sự là action.time + tổng thời gian của tất cả các phụ thuộc. action.time chỉ là thời gian cho hành động đó, không bao gồm thời gian cho các phụ thuộc. - Jules
Trong câu hỏi, bạn ám chỉ đến yêu cầu rằng một số nhiệm vụ chỉ cần được thực hiện một lần ("Nhận một chiếc xe hơi"), trong khi tôi cho rằng một số sẽ phải được thực hiện mỗi khi chúng được yêu cầu ("Lấy gạch"?). Thuộc tính này của một Tác vụ được trình bày trong cấu trúc dữ liệu của bạn như thế nào? - mbeckish
Mỗi tác vụ được thực hiện tối đa một lần. Nếu cần phải thực hiện nhiều lần thì có nhiều bản sao trong cấu trúc dữ liệu (ví dụ: "Lấy gạch cho ngôi nhà 1" và "Lấy gạch cho ngôi nhà 2"). Điều này xảy ra gần như không bao giờ mặc dù. - Jules
Bạn đang làm cách nào để tạo mô hình "Lấy gạch cho ngôi nhà 1" và "Lấy gạch cho ngôi nhà 2"? - mbeckish


Các câu trả lời:


Bạn có thể đang tìm kiếm thuật toán Lập kế hoạch đặt hàng một phần: http://blackcat.brynmawr.edu/~dkumar/UGAI/planning.html#algorithms


1
2018-06-07 05:24



Đây không phải là chính xác cùng một vấn đề nhưng có những ý tưởng tốt mà tôi có thể sử dụng. Con người của mathoverflow chỉ ra rằng vấn đề của tôi là NP-cứng, do đó, một giải pháp thời gian đa thức có lẽ là quá nhiều để yêu cầu;) - Jules


Bạn có thể lập mô hình này làm biểu đồ và sử dụng thuật toán đường ngắn nhất để tìm ra giải pháp. Mỗi Tác vụ sẽ là một nút và Hành động sẽ là các cạnh trong biểu đồ.

Trong thực tế, có thể sẽ dễ dàng hơn để biểu diễn các nút như các trạng thái và các cạnh như các hành động cần thiết để làm các cạnh chuyển tiếp giữa các trạng thái.

Nếu bạn xem xét một nhiệm vụ đơn giản chỉ là tổng hợp các hành động và bạn mô hình hóa các nút như các trạng thái và các hành động như là sự chuyển tiếp giữa các hành động đó. Thay vì nghĩ đến "Lấy ngôi nhà" làm nhiệm vụ chính, hãy xem xét "Bắt đầu" và "Có một ngôi nhà" làm 2 nút và "Lấy ngôi nhà" làm chuyển đổi giữa chúng. Hành động chuyển đổi "Lấy nhà" có thể được phân tách thành biểu đồ đại diện cho các trạng thái và hành động trung gian (tức là các nút và cạnh). Bạn có thể phân tích vấn đề xuống mức cần thiết và tính toán đường đi ngắn nhất từ ​​biểu đồ kết quả.


4
2018-06-06 15:01



Cảm ơn. Con đường ngắn nhất giữa các nút nào? Tôi giả định giữa nhiệm vụ chính và ...? - Jules
Tôi không thấy làm thế nào điều này có thể làm việc vì nói chung bạn cần phải chọn một biểu đồ con của đồ thị, không chỉ là một con đường. - Jules
Điều này nghe có vẻ giống như một vấn đề có thể được mô hình hóa với một biểu đồ, nhưng mô hình phải phức tạp hơn điều này. Lưu ý rằng bạn phải tính đến các yêu cầu "và" (để xây nhà bạn cần gạch và xi măng) cũng như "hoặc" yêu cầu (để có nhà bạn cần xây nhà hoặc nhà), cần được thể hiện khác nhau. - sepp2k
Chính xác. Biểu đồ là một loại biểu đồ "hai cấp", xen kẽ một mức độ hành động với một mức công việc. - Jules
@ sepp2k - Tôi tin rằng ngữ nghĩa là: mỗi Hành động trong Task.choices là một yêu cầu "HOẶC", và mỗi Nhiệm vụ trong Action.dependencies là một yêu cầu "AND". - mbeckish


Tôi nghĩ rằng tôi đã làm điều này từ lâu trong bối cảnh biểu đồ PERT.

Các mạng này lớn đến mức nào và tần suất bạn cần để giải quyết chúng? Bạn không thực sự có vấn đề về hiệu suất cho đến khi bạn thấy một vấn đề.

Tôi sẽ sử dụng lập trình động. Tôi sẽ không cho rằng các nhiệm vụ được chia sẻ sẽ là một vấn đề cho đến khi tôi phát hiện ra từ kinh nghiệm mà họ đã làm.


1
2018-06-06 17:09



Các cấu trúc đôi khi nhỏ và đôi khi lớn hàng nghìn và đôi khi hàng triệu nút, nhưng cấu trúc có thể là "dễ dàng" (ví dụ như chủ yếu là cây). Tuy nhiên, các phần phụ được chia sẻ vẫn phổ biến nên thuật toán chắc chắn cần phải tính đến các thuật toán đó. Tôi vẫn muốn biết một thuật toán tối ưu mà tôi có thể sử dụng trên các phiên bản nhỏ. - Jules
BTW thuật toán không phải là để lập kế hoạch nhiệm vụ và hành động của con người trên thế giới thực. Điều đó có nghĩa là kích thước vấn đề nhỏ. Đầu vào cho thuật toán này được tạo ra bởi mã khác, và nó có thể lớn. Và tôi biết chắc chắn rằng các nhiệm vụ phụ được chia sẻ sẽ xảy ra. - Jules
@ Jules: Sau đó, tôi sẽ bắt đầu bằng cách tạo ra một tập dữ liệu trường hợp xấu nhất, và mã hóa nó bất kỳ cách nào cả, và làm việc chuyển tiếp từ đó. Tôi đã học được không để đối phó với các vấn đề trong trừu tượng. - Mike Dunlavey
Điều đó sẽ không hoạt động mà không biết một thuật toán tốt, và tôi đã biết rằng tôi có thể làm một thuật toán xấu. Chỉ cần lặp qua tất cả các lựa chọn hành động có thể có, trong đó có 2 ^ n cho nhiệm vụ n. Đối với n = một triệu điều này chắc chắn sẽ không hoạt động. - Jules
Ngoài ra, vấn đề không trừu tượng trong quan điểm của tôi. Các điều kiện được xác định khá rõ ràng, đơn giản là không nhiều. - Jules


Có nguy cơ bị quá cầu kỳ, điều này có vẻ là một vấn đề về Phương pháp Đường dẫn Quan trọng (CPM) cổ điển hơn là PERT. PERT giả định thời gian hoàn thành tồi tệ nhất, tốt nhất và trung bình cho mỗi tác vụ trong khi Jules đã chỉ định một lần cho mỗi tác vụ. Điều đó nói rằng, bạn có thể sử dụng lập trình tuyến tính để tìm ra con đường quan trọng và tạo ra thời gian bắt đầu sớm nhất, thời gian kết thúc mới nhất, vv cho mỗi hoạt động. Đây là một mô tả trang hữu ích về cách tiếp cận này.


1
2018-06-07 15:37



CTM là khác nhau: mục tiêu của việc đó là lịch trình (tức là chọn một đơn đặt hàng) các nhiệm vụ trong khi vấn đề này đang chọn hành động nào cần thực hiện (không theo thứ tự nào). Thứ hai, CTM cố gắng giảm thiểu con đường quan trọng trong khi tôi muốn giảm thiểu tổng thời gian nếu công việc được giải quyết bởi 1 công nhân. - Jules
CPM = CTM? Tại liên kết tới CPM: "a) Đường dẫn tới hạn là con đường dài nhất thông qua mạng - đó là thời gian tối thiểu mà mạng có thể được hoàn thành". Đây không phải là điều bạn muốn - để giảm thiểu tổng thời gian cần thiết để hoàn thành toàn bộ các hoạt động? "Lập lịch CPM" thực sự là quá trình sử dụng CPM để hỗ trợ lập kế hoạch. Trường hợp phần lập kế hoạch đi vào là "quá trình" sử dụng CPM trên cơ sở liên tục để theo dõi và sửa đổi lịch biểu. - Grembo


Phân loại topo


0
2018-06-06 15:28



Xin hãy giải thích. Tôi không nghĩ rằng việc phân loại topo không thực sự liên quan đến điều này. Đối với một đồ thị có thể được tuần hoàn, và phân loại topo không tối ưu hóa bất cứ điều gì. - Jules
Chào. Nếu bạn có một biểu đồ tuần hoàn thì có một nhiệm vụ (1) không thể cạnh tranh được, bởi vì nó cần một nhiệm vụ khác (2) để được tuân thủ trước khi nó được yêu cầu (1) để được tuân thủ ... bạn sẽ nhận được kết quả tối ưu vì bạn đã chọn để tạo thành một tác vụ không phụ thuộc vào bất kỳ công việc nào khác và Nghìn thứ tự "nhiệm vụ quan trọng" là tốt nhất. Nếu bạn muốn làm cho thuật toán tốt hơn bạn luôn có thể chọn hành động mở rộng ít nhất từ ​​Tập hợp tất cả các nút không có cạnh đến. Hy vọng nó giúp. - tsinik


Tôi tin rằng mỗi đường dẫn thực thi có thể phải kết thúc bằng một nhiệm vụ có tập hợp các lựa chọn bao gồm hoàn toàn các hành động không phụ thuộc.

Nếu điều đó là đúng, thì bạn có thể dễ dàng xác định thời gian tối thiểu cho mỗi Tác vụ như vậy.

Sau đó, làm việc ngược trở lại Tác vụ chỉ phụ thuộc vào Tác vụ mà bạn đã "giải quyết" và tính tổng thời gian của chúng.

Làm việc ngược lại qua tất cả các đường dẫn có thể cho đến khi bạn bắt đầu.

Thời gian chạy phải là O (số lượng các nút trong biểu đồ), nên thời gian chạy giống nhau để tạo biểu đồ.


0
2018-06-06 23:04



Mô tả sự cố cho phép các chu kỳ. - Nabb
Có, và thậm chí nếu chu kỳ không được phép tôi vẫn không thấy làm thế nào để làm điều đó. Hình dạng kim cương là vấn đề. Cho tôi xin vài phút. - Jules
@ Tôi nghĩ rằng bất kỳ con đường thực hiện mà không đi vào một vòng lặp vô hạn phải có một kết thúc. - mbeckish
mbeckish, bạn đang suy nghĩ về đường dẫn thực hiện. Sự cố không chỉ định thứ tự thực hiện. Các nhiệm vụ phụ thuộc có thể được thực thi trước hoặc sau hành động, nó không quan trọng. Bạn nên suy nghĩ về nó như chọn một tập con của các hành động, thứ tự không quan trọng. - Jules
Dưới đây là ví dụ về cách tiếp cận của bạn không hoạt động: i.imgur.com/DjhuO.jpg Xin lỗi graphviz trả về lộn ngược ... Giải pháp tối ưu là chọn 5 và hai 0 và 0. Tuy nhiên nếu bạn nhìn vào một trong hai nhiệm vụ được kết nối với chính trong sự cô lập thì giải pháp tối ưu là chọn 4 thay vì 0 +5. - Jules