중요 경로와 최장 경로 간의 관계

Question

중요 경로는 parallel precedence-constrained scheduling 문제를 해결하는 본질입니다.

문제점 : 특정 기간이 끝나기 전에 특정 작업을 완료해야한다는 것을 지정하는 선행 제약 조건이있는 지정된 기간의 작업 집합이 주어지면 동일한 프로세서 (예 : 필요에 따라) 제약 조건을 준수하면서 최소 시간 내에 완료됩니다.

그래프와 가장 긴 경로 사이의 연결을 이해하는 데 어려움을 겪고 있습니다. 이는 분명히 해결책입니다. 나는 우리가 최소한의 시간을 원하기 때문에 대답은 가장 짧은 시간이라고 가정 할 것이다. 왜 이것이 최단 경로가 아닌 가장 긴 경로와 관련이 있습니까?

Answer 1

가장 짧은 일정의 길이는 가장 긴 경로보다 빠르게 수행되도록하기 위해 처리 할 수있는 프로세서의 수와 관계없이 수행 할 수있는 것이 없으므로 가장 긴 경로와 관련이 있습니다. 이전 작업이 완료되기 전에 가장 긴 경로의 작업을 시작할 수 없으므로 순서대로 수행해야합니다.

절대로 프로세서를 다 사용한 적이 없다면, 작업이 끝난 직후에 작업을 시작할 수 있으므로 끝점에 대한 가장 긴 경로가 끝나면 각 작업이 완료되고 전체 가장 긴 경로를 완료하면 작업이 완료됩니다.

Answer 2

1. 끝 상태를 나타내는 꼭지점을 만듭니다.
2. 모든 작업마다 하나의 정점을 만듭니다. (최종 상태에 대한) T에 따라 각 작업의 T2에 대한 각 작업의 T
   1. 1. 가 T2의 정점에 E의
      2. 설정 무게를 T의 정점에서 지시 에지 E를 만들기 위해

      T.

필요한 시간은 그 후, 임계 경로는 그래프를 통해 긴 경로이다. 이것을 조금 생각하고 이것이 사실임을 납득 시키십시오.

생각이 기차

이 날 수 있습니다 :

중요한 경로가 최종 상태에서 어떤 종속 작업과 끝과 시작해야합니다. 모든 종속성이 충족 될 때까지는 작업을 완료 할 수 없습니다.

작업 A가 B보다 먼저 수행되어야하고 B가 C보다 먼저 수행되어야하는 경우 작업 A에서 작업 C까지의 시간은 적어도 A -> B + B -> C입니다.

C가 종속성 A를 갖는 다른 종속성 B '를 갖는 경우, A에서 C까지의 시간은 적어도 A -> B'+ B '-> C입니다.

따라서 길이가 가장 길다. A부터 C까지의 경로가 중요하다.

일부 작업 종속성이 충족되어야하는 경우 최단 경로를 통해 문제를 해결할 수 있습니다. 가장 긴 경로는 모두 종속성을 만족해야 할 때 문제를 해결합니다.