마감문제

Closure problem

그래프 이론과 조합 최적화에서 지시된 그래프의 폐쇄는 가장자리가 C를 떠나지 않는 정점 C의 집합이다.폐쇄 문제는 정점 가중 지시 그래프에서 최대 가중치 또는 최소 가중치 폐쇄를 찾는 작업이다.[1][2]최대 흐름 문제의 감소를 이용하여 다항식 시간에 해결할 수 있다.그것은 작업 쌍들 간의 의존성을 가지고, 한 예가 열린 피트 마이닝에 있는 상태에서, 수행할 작업의 최적 하위 집합을 선택하는 다양한 애플리케이션 문제를 모델링하는 데 사용될 수 있다.

알고리즘

응축

주어진 그래프 G의 최대 중량 폐쇄는 G의 전치 그래프의 최소 중량 폐쇄의 보완과 동일하므로 두 문제는 계산 복잡성에 있어서 동일하다.그래프의 두 꼭지점이 동일한 강하게 연결된 구성요소에 속하는 경우, 모든 닫힘에 대해 서로 동일하게 동작해야 한다. 즉, 닫힘이 다른 꼭지점을 포함하지 않고는 하나의 꼭지점을 포함할 수 없다.이러한 이유로 폐쇄 문제에 대한 입력 그래프는 응결로 대체될 수 있으며, 응결로 인해 강하게 연결된 모든 구성 요소가 단일 꼭지점으로 대체된다.응축은 항상 방향의 순환 그래프다.

최대 유량으로 감소

폐쇄에서 최대 흐름으로 감소

Picard(1976)가 보여주었듯이,[2][3] G에서 생성된 그래프 H에서 최대 유량 문제를 풀면 G로부터 최대 중량 폐쇄를 얻을 수 있다.G에서 양의 중량을 갖는 각 정점 v에 대해, 증강 그래프 H는 v의 중량에 해당하는 용량을 가진 s에서 v까지의 에지를 포함하며, G에서 음의 중량을 가진 각 정점 v의 경우, 증강 그래프 H는 v의 중량을 부정하는 용량을 가진 v에서 t까지의 에지를 포함한다. G의 모든 에지는 H의 무한 용량이 주어진다.[1]

이 그래프에서 s와 t를 분리하는 최소 절단은 절단면을 가로질러 전방 방향으로 지나가는 G의 어떤 가장자리도 가질 수 없다: 그러한 가장자리가 있는 절단은 무한정 용량을 가지며 최소 용량이 아닐 것이다.따라서 s와 같은 절단면의 정점 세트가 자동으로 폐쇄 C를 형성한다.컷의 용량은 모든 양의 무게 정점의 무게에서 C의 정점의 무게를 뺀 것과 같으며, C의 무게가 최대화되었을 때 최소화된다.max-flow min-cut organization에 의해, 최소 절삭, 그리고 그것으로부터 도출된 최적 폐쇄는 최대 흐름 문제를 해결함으로써 찾을 수 있다.[1]

대체 알고리즘

흐름을 계산하지 않는 최대 폐쇄 문제에 대한 대안 알고리즘도 연구되었다.[4][5][6]그들의 가동 시간은 알려진 가장 빠른 흐름 알고리즘과 유사하다.[4]

적용들

오픈 핏 채굴

열린 갱도는 그 바로 위의 모든 블록이 제거되면 채굴하여 제거할 수 있는 일련의 재료로 모델링할 수 있다.블록은 총 값을 가지고 있는데, 그 값에서 추출할 수 있는 광물의 값에서 제거와 추출 비용을 뺀 값과 같다. 어떤 경우에는 추출 값이 없지만 다른 블록에 도달하기 위해서는 제거해야 한다.어떤 사람은 광산의 블록을 정점으로 하여 각 블록에서 그 블록 위의 블록까지 가장자리가 있고 그것보다 먼저 제거되어야 하는 지뢰의 블록을 가진 순환 네트워크를 정의할 수 있다.이 네트워크에서 각 꼭지점의 무게는 블록의 총값이며, 채굴을 위한 가장 수익성 있는 계획은 최대 중량 폐쇄를 찾아낸 다음 이 폐쇄에서 블록의 위상학적 순서를 형성함으로써 결정될 수 있다.[1][5][7]

군사 표적화

군사작전에서는 지휘소 등 고부가가치 목표물이 방어체계 레이어에 의해 자주 보호되고, 이는 결국 다른 시스템에 의해 보호될 수도 있다.목표물에 도달하기 위해서는 그 방어력을 모두 격추시켜 제2의 목표물로 만들어야 한다.각 타깃은 공격이 성공하기 위해서는 일정량의 자원을 할당해야 한다.지출된 자원에 대해 가장 많은 가치를 얻기 위해 공격 대상의 최적 집합을 폐쇄 문제로 모델링할 수 있다.[1][8]

교통망설계

화물 운송 시스템 계획 문제는 정점이 도시를 나타내고 (간접) 가장자리는 도시 쌍 사이의 잠재적 화물 운송 경로를 나타내는 네트워크에 의해 모델링될 수 있다.각 노선은 일정한 수익을 얻을 수 있지만, 일정한 비용을 들여 양끝에 화물창고를 건설해야 이용할 수 있다.수익과 비용의 차이를 최대화하는 네트워크 설계 문제는 각 비간접적 가장자리를 두 개의 방향 에지로 세분화하여 폐쇄 문제로 해결할 수 있다.각 구획점의 무게는 양수, 해당 노선의 이익, 그리고 각 원래의 그래프 정점의 무게는 음수, 즉 그 도시에 디포를 건설하는 비용이다.[1][9]오픈 핏 채굴과 함께, 이것은 폐쇄 문제를 연구하기 위한 최초의 동기 부여 응용 프로그램 중 하나였다; 그것은 원래 1970년에 J. M. W. 라이스와 미셸 발린스키가 같은 저널의 같은 호에 게재한 두 개의 독립 논문에서 연구되었다.[9][10][11]

작업 스케줄링

시드니(1975)와 롤러(1978)는 한 번에 하나씩 수행하도록 스케줄링된 작업의 모음이 주어지는 잡샵 스케줄링 버전에 폐쇄 문제의 적용을 설명한다.각 작업에는 두 개의 숫자가 연관되어 있다: 무게 또는 우선순위, 처리 시간, 해당 작업을 수행하는 데 걸리는 시간.또한 태스크는 우선순위 제약조건이 있다. 특정 태스크는 다른 태스크보다 먼저 수행해야 한다.이러한 우선 순위 제약조건은 한 작업에서 다른 작업까지의 가장자리가 첫 번째 작업을 두 번째 작업보다 먼저 수행해야 함을 나타내는 지시된 반복 그래프 G로 설명할 수 있다.이러한 제약조건(G의 위상 순서)과 일치하는 순서를 선택하여 과제의 총 가중 완료 시간을 최소화하는 것이 목표다.[12][13]

(롤러가 보여주듯이) 이 스케줄링 문제는 일반적으로 NP-완전함이지만, 시드니는 같은 유형의 여러 작은 문제들로 줄여 문제를 해결하는데 도움을 줄 수 있는 분해 방법을 설명한다.특히 S가 (모든 서브셋 중) 총중량의 가능한 비율이 (전체 서브셋 중)의 총중량의 가능한 비율이 가장 큰 과제의 서브셋이고, 게다가 S가 같은 비율을 가진 모든 세트 중에서 최소인 경우, 다른 모든 과제에 앞서 S의 모든 과업을 수행하는 최적의 스케줄이 존재한다.S가 전체 태스크 집합이 아닌 한, 이 태스크의 파티션은 스케줄링 문제를 스케줄링 S와 나머지 태스크의 스케줄링의 두 가지 작은 문제로 분할한다.[12]S는 폐쇄(G에서 가장자리가 뒤바뀐 그래프의 경우)이지만, S의 값은 가중치의 합이 아니라 비율이기 때문에 S를 찾는 문제가 정확히 최대 중량 폐쇄 문제는 아니다.그럼에도 불구하고, Lawler는 검색의 각 단계가 닫힘 문제의 인스턴스를 서브루틴으로 사용하는 이진 검색 알고리즘에 의해 다항 시간 내에 S가 발견될 수 있다는 것을 보여준다.[13]

참조

  1. ^ a b c d e f Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), "19.2 Maximum weight closure of a graph", Network flows, Englewood Cliffs, NJ: Prentice Hall Inc., pp. 719–724, ISBN 0-13-617549-X, MR 1205775.
  2. ^ a b Cook, William J.; Cunningham, William H.; Pulleyblank, William R.; Schrijver, Alexander (2011), "Optimal closure in a digraph", Combinatorial Optimization, Wiley Series in Discrete Mathematics and Optimization, vol. 33, John Wiley & Sons, pp. 49–50, ISBN 9781118031391.
  3. ^ Picard, Jean-Claude (1976), "Maximal closure of a graph and applications to combinatorial problems", Management Science, 22 (11): 1268–1272, doi:10.1287/mnsc.22.11.1268, MR 0403596.
  4. ^ a b Hochbaum, Dorit S. (2001), "A new-old algorithm for minimum-cut and maximum-flow in closure graphs", Networks, 37 (4): 171–193, doi:10.1002/net.1012, MR 1837196.
  5. ^ a b Lerchs, H.; Grossmann, I. F. (1965), "Optimum design of open-pit mines", Transactions of the Canadian Institute of Mining and Metallurgy, 68: 17–24. 호치바움(2001)이 인용한 바와 같다.
  6. ^ Faaland, Bruce; Kim, Kiseog; Schmitt, Tom (1990), "A new algorithm for computing the maximal closure of a graph", Management Science, 36 (3): 315–331, doi:10.1287/mnsc.36.3.315.
  7. ^ Johnson, T. B. (1968), Optimum pit mine production scheduling, Technical Report, University of California, Berkeley, CA. 아후자가 인용한 바와 같이 마그난티&올린(1993)이다.
  8. ^ Orlin, D. (1987), "Optimal weapons allocation against layered defenses", Naval Research Logistics Quarterly, 34 (5): 605–617, doi:10.1002/1520-6750(198710)34:5<605::aid-nav3220340502>3.0.co;2-l. 아후자가 인용한 바와 같이 마그난티&올린(1993)이다.
  9. ^ a b Hochbaum, Dorit (2004), "50th Anniversary Article: Selection, Provisioning, Shared Fixed Costs, Maximum Closure, and Implications on Algorithmic Methods Today", Management Science, 50 (6): 709–723, doi:10.1287/mnsc.1040.0242.
  10. ^ Rhys, J. M. W. (1970), "A selection problem of shared fixed costs and network flows", Management Science, 17 (3): 200–207, doi:10.1287/mnsc.17.3.200.
  11. ^ Balinski, M. L. (1970), "On a selection problem", Management Science, 17 (3): 230–231, doi:10.1287/mnsc.17.3.230.
  12. ^ a b Sidney, Jeffrey B. (1975), "Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs", Operations Research, 23 (2): 283–298, doi:10.1287/opre.23.2.283.
  13. ^ a b Lawler, E. L. (1978), "Sequencing jobs to minimize total weighted completion time subject to precedence constraints", Ann. Discrete Math., Annals of Discrete Mathematics, 2: 75–90, doi:10.1016/S0167-5060(08)70323-6, ISBN 9780720410433, MR 0495156.