작업과 작업의 두 가지 데이터 유형이 있습니다. 작업은 완료하는 데 일정한 시간이 걸리며이 작업으로 구성된 작업 집합이 필요합니다. 작업에는 일련의 작업이 있으며 작업은 그 중 하나를 선택하는 것입니다. 따라서 :작업을 수행하기위한 작업을 최적으로 선택하기위한 알고리즘
class Task { Set<Action> choices; }
class Action { float time; Set<Task> dependencies; }
예를 들어 기본 작업은 "집을 얻으십시오"일 수 있습니다. 이 작업의 가능한 작업 : "집 구입"또는 "집 만들기". "주택 건설"작업은 10 시간이 걸리고 "벽돌 가져 오기"(6 시간 소요) 및 "시멘트 가져 오기"(9 시간 소요) 등의 종속성이 있습니다.
총 시간은 수행해야 할 작업 (이 경우 10 + 6 + 9 시간)의 모든 시간의 합계입니다. 우리는 총 시간이 최소가되도록 조치를 선택하려고합니다.
종속성은 다이아몬드 모양 일 수 있습니다. 예를 들어 "벽돌 가져 오기"에는 "자동차 가져 오기"(벽돌 운반)가 필요하고 "시멘트 가져 오기"에는 자동차가 필요합니다. "벽돌 가져 오기"와 "시멘트 가져 오기"를 할지라도 차를 가져 오는 데 걸리는 시간은 단지 입니다.
종속성은 순환 될 수 있습니다. 예 : "돈"-> "직업"-> "자동차"-> "돈". 이것은 우리에게 아무런 문제가되지 않으며 단순히 "돈", "직업"및 "자동차"모두를 선택합니다. 총 시간은 단순히이 3 가지 시간의 합계입니다.
수학 설명 :
하자가 선택한 행동이 될 actions.
valid(task) = ∃action ∈ task.choices. (action ∈ actions ∧ ∀tasks ∈ action.dependencies. valid(task))
time = sum {action.time | action ∈ actions}
minimize time subject to valid(primaryTask)
나는 최적의 솔루션뿐만 아니라 대략적인 솔루션에도 관심이 있습니다. 아마도 일종의 역동적 인 프로그래밍이 도움이 될까요? 문제가 트리 구조라면 다이나믹 프로그래밍은 다항식 시간에 최적의 솔루션을 제공 할 수 있지만 다이아몬드 구조는 문제를 훨씬 더 어렵게 만듭니다. 알고리즘이 있지만 사이클이있는 경우 작동하지 않으면 게시하십시오! 나는 아직도 많은 것을 배울 수 있습니다.
상자는 작업을 대표하고 원 (작업이 원에 수행 할 수있는 시간을) 작업을 나타냅니다. 해당 작업이 작업에 대한 종속성 인 경우 작업에는 작업에 대한 줄이 있습니다. 그림의 관점에서 다시 문제에 대한 설명이 있습니다 : 사각형 (= 작업)이 선택되면 내부의 원 (= 동작) 중 하나를 선택해야합니다. 원이 선택되면 모든 연결된 사각형의을 선택해야합니다. 목표는 선택한 서클의 숫자 합계를 최소화하는 것입니다.
이 경우 최적의 솔루션은 맨 위 작업에서 시간이 2 인 작업을 선택하고 맨 아래 작업에서 시간이 1 인 작업을 선택하는 것입니다. 총 시간은 2 + 1 + 1 = 4입니다. 이 경우에는 2 가지 최적 해법이 있습니다. 두 번째 해결책은 맨 위 작업에서 시간이 3 인 작업을 선택하고 맨 아래 오른쪽 작업에서 시간이 1 인 작업을 선택하는 것입니다. 총 시간은 다시 3 + 1 = 4입니다. 시간이 3 인 작업을 최상위 작업에서 선택하면 왼쪽 작업을 수행 할 필요가 없습니다. 시간이 3 인 작업과 왼쪽 작업 사이에 선이 없기 때문입니다.나는 시시한 도면에 대해 사과
)) 그리고 두 더 많은 예제는 (각각에 대한 최적의 솔루션은 파란색으로 표시하고 있으며, 기본 작업은 회색으로 표시되었습니다 이 
작업이 일정 시간 (Action.time)을 어떻게 잡을 수 있습니까? 액션의 시간은 Action.dependencies의 각 태스크를 수행하는 데 걸리는 시간에 의존해서는 안됩니까? – mbeckish
네가 맞다. 용어는 불행하다. 작업이 수행하는 총 시간은 실제로 action.time + 모든 종속성의 총 시간입니다. action.time은 종속성 시간을 제외하고 해당 작업에 대한 시간입니다. – Jules
질문에서, 필요할 때마다 수행해야 할 작업이 있다고 가정하면서 ("Get a car") 한 번만 수행해야하는 작업 ("벽돌 가져 오기")을 수행해야한다는 요구 사항을 암시합니다. 데이터 구조에 표시된 Task의이 속성은 어떻게됩니까? – mbeckish