hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
라스베이거스 알고리즘 정의
(유형 1과 유형 2는 유형 3의 특수한 경우이다.)
시간 제한이 없는 유형 1의 경우, 평균 실행 시간이 실행 시간 동작을 나타낼 수 있다. 유형 2의 경우와는 다르다.
여기서 P(RT ≤ tmax), 즉 시간 내에 해결책을 찾을 확률이 실행 시간 동작을 설명한다.
유형 3의 경우, 실행 시간 동작은 rtd(t) = P(RT ≤ t)로 정의되는 실행 시간 분포 함수 rtd: R → [0,1] 또는 그 근사치로만 나타낼 수 있다.
실행 시간 분포(RTD)는 라스베이거스 알고리즘의 실행 시간 동작을 설명하는 독특한 방법이다.
이 데이터를 통해 평균 실행 시간, 표준 편차, 중앙값, 백분위수 또는 임의의 시간 제한 t에 대한 성공 확률 P(RT ≤ t)와 같은 다른 기준을 쉽게 얻을 수 있다.
라스베이거스 알고리즘 응용
라스베이거스 알고리즘은 탐색 문제에서 자주 발생한다. 예를 들어, 온라인에서 정보를 찾는 사람은 원하는 정보를 얻기 위해 관련 웹사이트를 검색할 수 있다. 따라서 시간 복잡도는 "운이 좋아" 즉시 콘텐츠를 찾는 것부터 "운이 없어" 많은 시간을 소비하는 것까지 다양하다. 올바른 웹사이트를 찾으면 오류가 발생할 가능성은 없다.
간단한 예로는 확률적 퀵 정렬이 있다. 여기서 피벗은 무작위로 선택되며, 요소를 피벗보다 작은 요소, 피벗과 같은 요소, 피벗보다 큰 요소의 세 부분으로 나눈다. 퀵 정렬은 항상 이 경우 정렬된 배열인 해결책을 생성한다. 불행히도 시간 복잡도는 그렇게 분명하지 않다. 실행 시간은 어떤 요소를 피벗으로 선택하는지에 따라 달라진다.
퀵 정렬의 실행 시간은 피벗이 얼마나 잘 선택되는지에 크게 의존한다. 피벗 값이 너무 크거나 작으면 분할이 불균형하여 효율성이 떨어진다. 그러나 피벗 값이 배열의 중간에 가까우면 분할이 상당히 균형을 이루어 더 빠른 실행 시간을 제공한다. 피벗이 무작위로 선택되므로 실행 시간은 대부분의 경우 좋고 때때로 나쁘다.
라스베이거스 알고리즘 응용
평균적인 경우, 분석이 입력 분포에 의존하는 것이 아니라 알고리즘이 내리는 무작위 선택에 의존하므로 결정하기 어렵다. 퀵 정렬의 평균은 알고리즘이 피벗을 선택할 때 내릴 수 있는 모든 가능한 무작위 선택에 대해 계산된다.
최악의 실행 시간은 Θ(n2)이지만, 평균 실행 시간은 Θ(nlogn)이다. 최악의 경우는 자주 발생하지 않는 것으로 밝혀졌다. n 값이 클수록 실행 시간은 높은 확률로 Θ(nlogn)이다.
피벗이 매번 중간 값 요소일 확률은 n개의 숫자 중 하나이므로 매우 드물다. 그러나 분할이 50%-50% 대신 10%-90%인 경우에도 재귀 트리의 깊이가 여전히 O(logn)이고 각 재귀 수준에서 O(n) 시간이 소요되므로 실행 시간은 동일하다.
8퀸 문제는 일반적으로 퇴각검색 알고리즘으로 해결된다. 그러나 라스베이거스 알고리즘을 적용할 수 있으며, 사실 퇴각검색보다 더 효율적이다.
라스베이거스 알고리즘 응용
체스판에 8개의 퀸을 서로 공격하지 않도록 놓는다. 퀸은 같은 행, 열, 대각선에 있는 다른 말들을 공격한다는 것을 기억하자.
k개의 행, 0 ≤ k ≤ 8이 퀸으로 성공적으로 채워졌다고 가정한다.
k = 8이면 성공적으로 중지한다. 그렇지 않으면 k + 1행을 채우는 작업을 계속한다.
기존 퀸에 의해 공격받지 않는 이 행의 모든 위치를 계산한다. 그러한 위치가 없으면 실패한다. 그렇지 않으면 하나를 무작위로 선택하고, k를 증가시킨 후 반복한다.
퀸을 놓을 수 없으면 알고리즘은 단순히 실패한다는 점에 유의한다. 그러나 이 과정은 반복될 수 있으며 매번 다른 배열을 생성할 것이다.
라스베이거스 알고리즘 복잡도 종류
기댓값 다항식 실행 시간을 가진 라스베이거스 알고리즘을 가진 결정 문제의 복잡도 종류는 ZPP이다.
다음과 같이 밝혀졌다.
이는 라스베이거스 알고리즘이 때때로 구성되는 방식과 밀접하게 연결되어 있다. 즉, RP 클래스는 올바른 답이 "아니오"일 때 항상 올바르게 답하지만, 답이 "예"일 때 1에서 벗어난 특정 확률로 틀릴 수 있는 확률적 다항 시간 알고리즘이 존재하는 모든 결정 문제로 구성된다. 문제와 그 보수(답이 "예"와 "아니오"로 바뀌는) 모두에 대해 그러한 알고리즘이 존재할 때, 두 알고리즘을 동시에 반복적으로 실행할 수 있다. 즉, 각각의 알고리즘을 일정한 수의 단계 동안 교대로 실행하여 하나가 명확한 답을 반환할 때까지 진행한다. 이것이 기대 다항 시간으로 실행되는 라스베이거스 알고리즘을 구성하는 표준적인 방법이다. 일반적으로 라스베이거스 알고리즘의 실행 시간에는 최악의 경우 상한이 없다는 점에 유의한다.
라스베이거스 알고리즘 최적의 라스베이거스 알고리즘
라스베이거스 알고리즘을 최적으로 만들기 위해서는 예상 실행 시간을 최소화해야 한다. 이는 다음을 통해 수행할 수 있다.
최적 전략의 존재는 매력적인 이론적 관찰일 수 있다. 그러나 TA(x) 분포에 대한 정보를 찾는 것이 쉽지 않기 때문에 실제 생활에서는 실용적이지 않다. 더욱이 대부분의 경우 x에 대한 답이 한 번만 필요하므로 분포에 대한 정보를 얻기 위해 실험을 반복적으로 실행할 필요가 없다.
라스베이거스 알고리즘 몬테카를로 알고리즘과의 관계
라스베이거스 알고리즘은 사용되는 자원은 제한되지만 답변이 특정(일반적으로 작은) 확률로 틀릴 수 있는 몬테카를로 알고리즘과 대조된다. 라스베이거스 알고리즘은 정해진 시간 동안 실행하고 종료되지 않으면 무작위 답변을 생성함으로써 몬테카를로 알고리즘으로 변환할 수 있다. 마르코프 부등식을 적용하여 라스베이거스 알고리즘이 고정된 한계를 초과할 확률에 대한 상한을 설정할 수 있다.
다음은 라스베이거스 알고리즘과 몬테카를로 알고리즘을 비교한 표이다.
정확성 테스트를 위한 결정론적인 방법이 있다면 몬테카를로 알고리즘을 라스베이거스 알고리즘으로 바꿀 수 있다. 하지만 알고리즘을 테스트할 방법이 없다면 몬테카를로 알고리즘을 라스베이거스 알고리즘으로 바꾸기 어렵다. 반면에 라스베이거스 알고리즘을 몬테카를로 알고리즘으로 바꾸는 것은 쉽다. 이는 신뢰도 매개변수로 주어진 특정 시간 동안 라스베이거스 알고리즘을 실행함으로써 가능하다. 알고리즘이 시간 내에 해를 찾으면 성공이고, 그렇지 않으면 "죄송합니다"라고 출력할 수 있다.
라스베이거스 알고리즘 몬테카를로 알고리즘과의 관계
다음은 비교를 위한 라스베이거스 및 몬테카를로 알고리즘의 예시이다.
짝수 n 길이를 가진 배열이 있다고 가정하자. 배열의 절반은 0이고 나머지 절반은 1이다. 여기서 목표는 1을 포함하는 인덱스를 찾는 것이다.
라스베이거스 알고리즘은 배열에서 1을 찾을 때까지 끝나지 않으므로, 정확성을 놓고 도박을 하는 것이 아니라 실행 시간을 놓고 도박을 한다. 반면에 몬테카를로 알고리즘은 300번 실행되므로 코드를 실제로 실행하기 전까지는 300번의 루프 내에서 배열에서 "1"을 찾을지 알 수 없다. 해를 찾을 수도 있고 찾지 못할 수도 있다. 따라서 라스베이거스 알고리즘과 달리 몬테카를로 알고리즘은 실행 시간이 아니라 정확성을 놓고 도박을 한다.
최대 유량 문제
최적화 이론에서 최대 유량 문제(maximum flow problem)는 최대 가능한 유량을 얻는 네트워크 흐름을 통한 실행 가능한 흐름을 찾는 것을 포함한다.
최대 유량 문제는 순환 문제와 같은 더 복잡계 네트워크 흐름 문제의 특별한 경우로 볼 수 있다. s-t 흐름(즉, 소스 s에서 싱크 t로의 흐름)의 최대값은 최대 유량 최소 컷 정리에 명시된 바와 같이 네트워크에서 s-t 컷 (즉, s를 t에서 분리하는 컷)의 최소 용량과 같다.
최대 유량 문제 역사
최대 유량 문제는 1954년 T. E. 해리스와 F. S. 로스에 의해 소련 철도 교통 흐름의 단순화된 모델로 처음 공식화되었다.
1955년에 레스터 R. 포드 주니어와 D. R. 풀커슨은 최초로 알려진 알고리즘인 포드-풀커슨 알고리즘을 만들었다. 1955년 논문에서 포드와 풀커슨은 해리스와 로스의 문제가 다음과 같이 공식화되었다고 썼다( 5페이지 참조):
연결된 두 도시를 여러 중간 도시를 거쳐 연결하는 철도 네트워크를 고려하고, 네트워크의 각 링크에는 그 용량을 나타내는 숫자가 할당된다. 정상 상태 조건을 가정하고, 한 주어진 도시에서 다른 도시로의 최대 흐름을 찾아라.
1962년 저서 《네트워크 흐름》에서 포드와 풀커슨은 다음과 같이 썼다:
1955년 봄에 T. E. 해리스가 F. S. 로스 장군(퇴역)과 함께 철도 교통 흐름의 단순화된 모델을 공식화하고 이 특정 문제를 모델이 제시하는 핵심 문제로 지목했다 [11].
여기서 [11]은 1955년 해리스와 로스의 비밀 보고서 《철도 네트워크 용량 평가 방법의 기본》을 참조한다( 5페이지 참조).
최대 유량 문제 역사
수년에 걸쳐 최대 흐름 문제에 대한 다양한 개선된 솔루션이 발견되었는데, 특히 에드먼즈와 카프, 그리고 독립적으로 디니츠의 최단 증대 경로 알고리즘, 디니츠의 블로킹 흐름 알고리즘, 밀어내기-재표시 알고리즘인 골드버그와 타잔의 알고리즘, 골드버그와 라오의 이진 블로킹 흐름 알고리즘이 있다. 셔먼과 켈너, 리, 오레키아, 시드포드의 알고리즘은 각각 대략적으로 최적의 최대 흐름을 찾지만 무방향 그래프에서만 작동한다.
2013년 제임스 B. 올린은  알고리즘을 설명하는 논문을 발표했다.
2022년 리 천, 라스무스 킹, 양 P. 리우, 리처드 펭, 막시밀리안 프로브스트 구텐베르크, 수샨트 사흐데바는 최대 흐름 문제의 특정 사례인 최소 비용 흐름 문제를 위해 으로 실행되는 거의 선형 시간 알고리즘을 발표했다. 음수 가중치를 갖는 단일 원천 최단 경로 문제의 또 다른 특정 최소 비용 흐름 문제의 경우 거의 선형 시간 알고리즘도 보고되었다. 두 알고리즘 모두 2022년 컴퓨터 과학의 기초 심포지엄에서 최고 논문으로 선정되었다.
최대 유량 문제 정의
먼저 몇 가지 표기법을 설정한다:
정의. 간선의 용량은 간선을 통해 통과할 수 있는 최대 흐름량이다. 형식적으로는  함수이다.
정의. 흐름은 다음을 만족하는  함수이다:
비고. 흐름은 대칭 왜곡적이다: 모든 에 대해 이다.
정의. 흐름의 값은 소스에서 싱크로 통과하는 흐름의 양이다. 형식적으로 인 흐름에 대해 다음으로 주어진다:
정의. 최대 흐름 문제는 소스에서 싱크로 가능한 한 많은 흐름을 보내는 것이다. 즉, 최대 값을 갖는 흐름 를 찾는 것이다.
여러 개의 최대 흐름이 존재할 수 있으며, (정수뿐만 아니라) 임의의 실수 (또는 임의의 유리수) 흐름 값이 허용되는 경우, 기본 최대 흐름의 무한한 선형 조합이 있기 때문에 정확히 하나의 최대 흐름이 있거나 무한히 많은 최대 흐름이 있다. 즉, 한 최대 흐름에서 간선 에  단위의 흐름을 보내고 다른 최대 흐름에서  단위의 흐름을 보낸다면, 각 에 대해 에  단위를 보내고 나머지 간선에 흐름을 적절히 라우팅하여 다른 최대 흐름을 얻을 수 있다. 흐름 값이 임의의 실수 또는 유리수일 수 있다면, 각 쌍 에 대해 무한히 많은  값이 존재한다.
최대 유량 문제 알고리즘
다음 표는 최대 흐름 문제를 해결하기 위한 알고리즘의 역사적 발전을 보여준다. 나열된 많은 출판물에는 초기 연구와 결과를 비교하는 유사한 표가 포함되어 있다.
강한 다항 시간 알고리즘은 입력 수에만 의존하고 이 숫자의 크기에는 의존하지 않는 다항 시간 경계를 가진다. 여기서 입력은 정점(로 표기)과 간선(로 표기)이다. 각 알고리즘의 복잡도는 빅 O 표기법을 사용하여 명시된다.
강한 다항 흐름 알고리즘 개발과 병행하여 입력 용량의 크기에 따라 실행 시간이 달라지는 의사 다항 시간 및 약한 다항 시간 경계가 오랫동안 존재했다. 여기서  값은 모든 용량을 정수 값으로 재조정했을 때 가장 큰 간선 용량을 나타낸다. (네트워크에 무리수 용량이 포함된 경우, 이 재조정은 불가능할 수 있으며 이러한 알고리즘은 정확한 솔루션을 생성하지 못하거나 근사 솔루션으로도 수렴하지 못할 수 있다.) 의사 다항 시간과 약한 다항 시간의 차이점은 의사 다항 시간 경계는 에 대해 다항식일 수 있지만, 약한 다항 시간 경계는 에 대해서만 다항식일 수 있다는 점이다.
최대 유량 문제 정수 흐름 정리
정수 흐름 정리(integral flow theorem)는 다음을 명시한다.
흐름 네트워크의 각 간선이 정수 용량을 가진다면, 정수 최대 흐름이 존재한다.
이 주장은 흐름의 값이 정수라는 것뿐만 아니라(이는 최대 유량 최소 컷 정리에서 직접 파생된다), 모든 간선에 대한 흐름이 정수라는 것이다. 이는 많은 조합론적 응용(아래 참조)에서 중요하며, 간선을 가로지르는 흐름은 해당 간선에 해당하는 항목이 탐색되는 집합에 포함되어야 하는지 여부를 인코딩할 수 있다.
최대 유량 문제 응용
하나의 소스와 하나의 싱크 대신, 소스 집합 과 싱크 집합 을 갖는 네트워크 가 주어졌을 때, 을 가로지르는 최대 흐름을 찾아야 한다. 이 다중 소스 다중 싱크 문제는 의 각 정점에 연결되는 통합 소스와 의 각 정점에 연결되는 통합 싱크(슈퍼소스 및 슈퍼싱크라고도 함)를 각 간선에 무한 용량을 할당하여 최대 흐름 문제로 변환할 수 있다(그림 4.1.1 참조).
이분 그래프 가 주어졌을 때, 에서 최대 매칭을 찾아야 한다. 이는 가능한 가장 많은 수의 간선을 포함하는 매칭이다. 이 문제는 다음과 같이 네트워크 를 구성하여 최대 흐름 문제로 변환할 수 있다.
그러면 의 최대 흐름 값은 의 최대 매칭 크기와 같으며, 정수 최대 흐름에서 흐름이 인 간선을 선택하여 최대 매칭을 찾을 수 있다.
유향 비순환 그래프 가 주어졌을 때, 의 각 정점을 덮는 최소 수의 정점-분리 경로를 찾아야 한다. 로부터 이분 그래프 를 구성할 수 있는데, 여기서
그러면 가 크기 의 매칭 을 갖는 경우에만 가 개의 간선과 개의 경로를 포함하는 정점-분리 경로 커버 를 갖는다는 것을 보일 수 있다. 여기서 은 의 정점 수이다. 따라서 이 문제는 에서 최대 매칭을 찾음으로써 해결할 수 있다.
최대 유량 문제 응용
의 매칭 을 찾고 그로부터 커버 를 구성했다고 가정하자. 직관적으로  두 정점이 에서 매칭되면, 간선 는 에 포함된다. 분명히 의 간선 수는 이다. 가 정점-분리임을 보이기 위해 다음을 고려한다.
따라서 어떤 정점도 에서 두 개의 들어오는 간선이나 두 개의 나가는 간선을 가지지 않으며, 이는 의 모든 경로가 정점-분리임을 의미한다.
커버 의 크기가 임을 보이기 위해, 빈 커버에서 시작하여 점진적으로 구축한다. 커버에 정점 를 추가하려면, 기존 경로에 추가하거나, 해당 정점에서 시작하는 길이가 0인 새 경로를 생성할 수 있다. 전자의 경우는 이고 커버의 어떤 경로가 에서 시작하거나, 이고 어떤 경로가 에서 끝날 때 적용 가능하다. 후자의 경우는 항상 적용 가능하다. 전자의 경우 커버의 총 간선 수는 1 증가하고 경로 수는 동일하게 유지된다. 후자의 경우 경로 수는 증가하고 간선 수는 동일하게 유지된다. 이제 모든 개 정점을 덮은 후 커버의 경로 수와 간선 수의 합이 이라는 것이 분명하다. 따라서 커버의 간선 수가 이면 경로 수는 이다.
최대 유량 문제 응용
를 네트워크라고 하자. 간선 용량 외에 각 노드에 용량이 있다고 가정하자. 즉, 인 맵핑이 있어서, 흐름 는 용량 제약과 흐름 보존뿐만 아니라 다음 정점 용량 제약도 만족해야 한다.
즉, 정점을 통과하는 흐름의 양은 해당 용량을 초과할 수 없다. 을 가로지르는 최대 흐름을 찾기 위해 을 확장하여 문제를 원래의 최대 흐름 문제로 변환할 수 있다. 먼저, 각 는 과 으로 대체되는데, 여기서 은 로 들어가는 간선에 연결되고 은 에서 나오는 간선에 연결된다. 그리고 과 을 연결하는 간선에 용량 를 할당한다(그림 4.4.1 참조). 이 확장된 네트워크에서는 정점 용량 제약이 제거되므로 문제는 원래의 최대 흐름 문제로 취급될 수 있다.
유향 그래프 와 두 정점 , 가 주어졌을 때, 에서 까지의 최대 경로 수를 찾아야 한다. 이 문제는 몇 가지 변형이 있다.
1. 경로는 간선-분리여야 한다. 이 문제는 로부터 네트워크 를 구성하고, 와 를 각각 의 소스와 싱크로 삼으며, 각 간선에 용량을 로 할당함으로써 최대 흐름 문제로 변환될 수 있다. 이 네트워크에서 최대 흐름이 이면 개의 간선-분리 경로가 존재한다.
최대 유량 문제 응용
2. 경로는 독립적이어야 한다. 즉, ( 와 를 제외하고) 정점-분리여야 한다. 모든 정점과 모든 간선의 용량이 인 정점 용량을 가진 로부터 네트워크 를 구성할 수 있다. 그러면 최대 흐름의 값은 에서 까지의 독립 경로의 최대 수와 같다.
3. 경로가 간선-분리 또는 정점-분리일 뿐만 아니라, 경로 길이에 대한 제약도 있다. 즉, 길이가 정확히 이거나 최대 인 경로만 계산한다. 이 문제의 대부분의 변형은 작은  값을 제외하고는 NP-완전이다.
유향 그래프의 클로저는 간선이 C를 떠나지 않는 정점들의 집합 C이다. 클로저 문제는 정점 가중 유향 그래프에서 최대 가중치 또는 최소 가중치 클로저를 찾는 과제이다. 이 문제는 최대 흐름 문제로의 환원을 사용하여 다항 시간에 해결될 수 있다.
최대 유량 문제 실제 응용
야구 토너먼트 탈락 문제에서는 n개의 팀이 리그에서 경쟁한다. 리그 시즌의 특정 단계에서, 는 팀 i의 승리 횟수이고 는 팀 i가 남은 경기 수이며, 는 팀 j와의 남은 경기 수이다. 팀은 시즌을 1위로 마칠 기회가 없으면 탈락된다. 야구 토너먼트 탈락 문제의 과제는 시즌 중 각 시점에서 어떤 팀이 탈락되는지 결정하는 것이다. 슈워츠는 이 문제를 최대 네트워크 흐름으로 환원하는 방법을 제안했다. 이 방법에서는 팀 k가 탈락되는지 여부를 결정하기 위해 네트워크가 생성된다.
최대 유량 문제 실제 응용
가 각각 소스와 싱크인 네트워크 라고 하자. 두 팀 간의 경기 수를 나타내는 게임 노드를 추가한다. 또한 각 팀에 대한 팀 노드를 추가하고, 각 게임 노드  (i < j)를 에 연결하고, 각각을 에서 용량 (두 팀 간의 경기 수)를 가진 간선으로 연결한다. 또한 각 팀에 대한 팀 노드를 추가하고, 각 게임 노드 를 두 팀 노드 i와 j에 연결하여 그 중 하나가 이기도록 한다. 이 간선들의 흐름 값은 제한할 필요가 없다. 마지막으로, 팀 노드 i에서 싱크 노드 t로 간선을 만들고 wk + rk – wi의 용량을 설정하여 팀 i가 보다 많이 이기는 것을 방지한다.
를 리그에 참가하는 모든 팀의 집합이라고 하고
.
이 방법에서는 팀 k가 네트워크 G에서 크기 의 흐름 값이 존재하는 경우에만 탈락하지 않는다고 주장한다. 언급된 기사에서는 이 흐름 값이 에서 까지의 최대 흐름 값임을 증명한다.
최대 유량 문제 실제 응용
항공 산업에서 주요 문제 중 하나는 승무원 스케줄링이다. 항공사 스케줄링 문제는 확장된 최대 네트워크 흐름의 응용으로 간주될 수 있다. 이 문제의 입력은 각 항공편이 어디서 언제 출발하고 도착하는지에 대한 정보를 포함하는 항공편 집합 F이다. 항공사 스케줄링의 한 버전에서는 최대 k개의 승무원으로 실행 가능한 스케줄을 생성하는 것이 목표이다.
이 문제를 해결하기 위해 네트워크 흐름 문제의 일반화인 경계 순환(bounded circulation)이라는 순환 문제의 변형을 사용하는데, 이는 간선 흐름에 대한 하한이라는 추가 제약이 있다.
가 각각 소스 및 싱크 노드인 네트워크 라고 하자. 각 항공편 i의 출발지 및 목적지에 대해, 항공편 i의 소스 노드 와 목적지 노드 를 에 추가한다. 또한 에 다음 간선들을 추가한다.
언급된 방법에서, 와  사이에서  값의 흐름을 찾는 것은 F 항공편 집합에 대해 최대 명의 승무원으로 실행 가능한 스케줄을 찾는 것과 같다고 주장하고 증명된다.
최대 유량 문제 실제 응용
항공사 스케줄링의 또 다른 버전은 모든 항공편을 수행하는 데 필요한 최소 승무원 수를 찾는 것이다. 이 문제에 대한 해답을 찾기 위해 이분 그래프 가 생성되는데, 여기서 각 항공편은 집합 A와 집합 B에 복사본을 가진다. 동일한 비행기가 항공편 i 다음에 항공편 j를 수행할 수 있다면, i∈A는 j∈B에 연결된다. 에서의 매칭은 F에 대한 스케줄을 유도하며, 분명히 이 그래프에서의 최대 이분 매칭은 최소 승무원 수로 항공사 스케줄을 생성한다. 이 문서의 응용 부분에서 언급된 바와 같이, 최대 이분 매칭은 최대 흐름 문제의 응용이다.
물건을 생산하는 공장과 물건을 배달해야 하는 마을이 있다. 이들은 도로 네트워크로 연결되어 있으며, 각 도로에는 최대 물건 흐름을 위한 용량 가 있다. 이 문제는 수요를 만족하는 순환이 존재하는지 찾는 것이다.
이 문제는 최대 흐름 문제로 변환될 수 있다.
이 새로운 네트워크를 라고 하자. 수요를 만족하는 순환은 다음 경우에만 존재한다:
.
순환이 존재한다면, 최대 흐름 해를 통해 특정 도로에서 수요를 만족하기 위해 얼마만큼의 물건을 보내야 하는지에 대한 답을 얻을 수 있다.
일부 간선에 흐름의 하한을 추가하여 문제를 확장할 수 있다.
클라인베르크와 타르도스는 그들의 책에서 이미지를 분할하는 알고리즘을 제시한다. 그들은 이미지에서 배경과 전경을 찾는 알고리즘을 제시한다. 더 정확히 말하면, 이 알고리즘은 다음과 같이 모델링된 비트맵을 입력으로 받는다. 은 픽셀 i가 전경에 속할 가능성, 은 픽셀 i가 배경에 속할 가능성, 는 두 인접 픽셀 i와 j가 하나는 전경에, 다른 하나는 배경에 놓일 경우의 페널티이다. 목표는 다음 양을 최대화하는 픽셀 집합의 분할 (A, B)을 찾는 것이다.
,
실제로 A에 있는 픽셀(전경으로 간주)의 경우 를 얻고, B에 있는 모든 픽셀(배경으로 간주)의 경우 를 얻는다. 경계에서는 두 인접 픽셀 i와 j 사이에 를 잃는다. 이는 다음 양을 최소화하는 것과 동등하다.
왜냐하면
이제 노드가 픽셀인 네트워크에 소스와 싱크를 추가하여 구축한다(오른쪽 그림 참조). 소스에서 픽셀 i로 가중치 인 간선을 연결한다. 픽셀 i에서 싱크로 가중치 인 간선을 연결한다. 픽셀 i에서 픽셀 j로 가중치 인 간선을 연결한다. 이제 이 네트워크에서 최소 컷(또는 동등하게 최대 흐름)을 계산하는 것이 남았다. 마지막 그림은 최소 컷을 보여준다.
최대 유량 문제 확장
1. 최소 비용 흐름 문제에서는 각 간선 (u,v)가 용량 외에 비용 계수 도 가진다. 간선을 통한 흐름이 이면, 총 비용은 이다. 주어진 크기 의 흐름을 최소 비용으로 찾는 것이 요구된다. 대부분의 변형에서 비용 계수는 양수 또는 음수일 수 있다. 이 문제에 대한 다양한 다항 시간 알고리즘이 존재한다.
2. 최대 흐름 문제는 선택적 제약으로 보강될 수 있다. 음의 선택적 제약은 특정 쌍의 간선이 동시에 0이 아닌 흐름을 가질 수 없음을 나타낸다. 양의 선택적 제약은 특정 쌍의 간선 중 적어도 하나는 0이 아닌 흐름을 가져야 함을 나타낸다. 음의 제약이 있는 경우, 문제는 단순한 네트워크에서도 강하게 NP-난해가 된다. 양의 제약이 있는 경우, 분수 흐름이 허용되면 문제는 다항식으로 풀리지만, 흐름이 정수여야 할 때는 강하게 NP-난해일 수 있다.
최대 유량 문제 더 읽어보기
Joseph Cheriyan and Kurt Mehlhorn (1999). 《An analysis of the highest-level selection rule in the preflow-push max-flow algorithm》. 《Information Processing Letters》 69. 239–242쪽. CiteSeerX 10.1.1.42.8563. doi:10.1016/S0020-0190(99)00019-8.
Daniel D. Sleator and Robert E. Tarjan (1983). 《A data structure for dynamic trees》 (PDF). 《Journal of Computer and System Sciences》 26. 362–391쪽. doi:10.1016/0022-0000(83)90006-5. ISSN 0022-0000.
안정 매칭 문제
수학, 경제학, 컴퓨터 과학에서 안정 매칭 문제(Stable matching problem)는 각 요소에 대한 선호도 순서가 주어졌을 때, 두 개의 동일한 크기의 요소 집합 사이에 안정적인 매칭을 찾는 문제이다. 매칭은 한 집합의 요소에서 다른 집합의 요소로의 전단사이다. 매칭은 다음의 경우 불안정하다.
다시 말해, 매칭은 (A, B) 쌍이 서로를 현재 매칭된 상대보다 선호하는 경우가 없을 때 안정적이다.
안정 결혼 문제는 다음과 같이 서술되었다.
n명의 남성과 n명의 여성이 주어지고, 각 사람은 이성 구성원 모두를 선호도 순서대로 순위를 매겼을 때, 남성과 여성을 짝지어 현재 배우자보다 서로를 더 선호하는 이성 쌍이 없도록 한다. 그러한 쌍이 없을 때, 결혼 집합은 안정적이라고 간주된다.
서로 짝을 이루어야 할 두 계층(이 예에서는 이성애자 남성과 여성)의 존재는 이 문제를 안정 룸메이트 문제와 구별한다.
안정 매칭 문제 응용
안정 결혼 문제의 해결책을 찾는 알고리즘은 다양한 실제 상황에서 응용된다. 이 중 가장 잘 알려진 것은 졸업하는 의대생을 첫 병원 배치에 배정하는 것이다. 2012년, 노벨 경제학상은 로이드 S. 섀플리와 앨빈 E. 로스에게 "안정적인 할당 이론과 시장 설계의 실제"에 대한 공로로 수여되었다.
안정 매칭 문제 응용
안정 결혼의 중요하고 대규모 응용 중 하나는 대규모 분산 인터넷 서비스에서 사용자를 서버에 할당하는 것이다. 수십억 명의 사용자가 인터넷에서 웹 페이지, 비디오 및 기타 서비스에 액세스하며, 각 사용자는 해당 서비스를 제공하는 전 세계 수십만 개의 서버 중 하나에 매칭되어야 한다. 사용자는 요청된 서비스에 대해 더 빠른 응답 시간을 제공할 만큼 근접한 서버를 선호하여 각 사용자에 대한 서버의 (부분적인) 선호도 순서를 생성한다. 각 서버는 낮은 비용으로 서비스를 제공할 수 있는 사용자를 선호하여 각 서버에 대한 사용자의 (부분적인) 선호도 순서를 생성한다. 전 세계 콘텐츠 및 서비스의 대부분을 배포하는 콘텐츠 전송 네트워크는 이러한 거대하고 복잡한 사용자-서버 간의 안정 결혼 문제를 수십 초마다 해결하여 수십억 명의 사용자가 요청된 웹 페이지, 비디오 또는 기타 서비스를 제공할 수 있는 각 서버와 매칭되도록 한다.
안정 매칭을 위한 게일-섀플리 알고리즘은 히브리 유니언 칼리지 졸업 랍비를 유대인 회중에게 배정하는 데 사용된다.
안정 매칭 문제 다른 안정 매칭
일반적으로 여러 가지 안정 매칭이 있을 수 있다. 예를 들어, 세 명의 남성(A, B, C)과 세 명의 여성(X, Y, Z)이 다음의 선호도를 가지고 있다고 가정해 보자.
A: YXZ   B: ZYX   C: XZY
X: BAC   Y: CBA   Z: ACB
이 매칭 배열에는 세 가지 안정적인 해결책이 있다.
세 가지 모두 안정적이다. 불안정성은 두 참가자 모두 다른 대안 매칭에 더 만족해야 하기 때문이다. 한 그룹에게 첫 번째 선택을 주는 것은 매칭이 안정적임을 보장하는데, 이는 그들이 다른 어떤 제안된 매칭에도 불만족할 것이기 때문이다. 모든 사람에게 두 번째 선택을 주는 것은 다른 어떤 매칭도 당사자 중 한 명에게 불만을 일으킬 것임을 보장한다. 일반적으로 안정 결혼 문제의 모든 인스턴스에 대한 해결책 집합은 유한 분배 격자의 구조를 가질 수 있으며, 이 구조는 안정 결혼에 관한 여러 문제에 대한 효율적인 알고리즘을 이끌어낸다.
안정 매칭 문제 다른 안정 매칭
n명의 남성과 n명의 여성이 있는 안정 결혼 문제의 균일 무작위 인스턴스에서 안정 매칭의 평균 수는 점근적으로 이다.
안정 매칭의 최대 수를 갖도록 선택된 안정 결혼 인스턴스에서 이 수는 n의 지수 함수이다.
주어진 인스턴스에서 안정 매칭의 수를 세는 것은 #P-완전이다.
안정 매칭 문제 알고리즘적 해결책
1962년, 데이비드 게일과 로이드 섀플리는 대학 입학과 결혼을 원하는 개인들의 맥락에서, 다른 그룹에 동일한 수의 개체가 있을 경우 모든 결과적인 짝짓기/매칭 요소가 안정적이도록 항상 짝지어진 커플로 해결하는 것이 가능함을 증명했다. 그들은 이를 위한 알고리즘을 제시했다.
게일-섀플리 알고리즘 (지연 수락 알고리즘이라고도 함)은 여러 "라운드"(또는 "반복")를 포함한다.
첫 번째 라운드에서, 먼저 a) 아직 약혼하지 않은 각 남성은 자신이 가장 선호하는 여성에게 청혼하고, 다음으로 b) 각 여성은 자신이 가장 선호하는 구혼자에게 "아마도"라고 답하고 다른 모든 구혼자에게는 "아니오"라고 답한다. 그런 다음 그녀는 지금까지 가장 선호하는 구혼자와 잠정적으로 "약혼"하고, 해당 구혼자도 그녀와 잠정적으로 약혼한다.
안정 매칭 문제 알고리즘적 해결책
각 후속 라운드에서, 먼저 a) 아직 약혼하지 않은 각 남성은 자신이 아직 청혼하지 않은 여성 중 가장 선호하는 여성에게 청혼하고 (여성이 이미 약혼했는지 여부와 관계없이), 다음으로 b) 각 여성은 현재 약혼하지 않았거나 현재 잠정적 배우자보다 이 남성을 더 선호하는 경우 "아마도"라고 답한다 (이 경우 그녀는 현재 잠정적 배우자를 거부하고, 그 배우자는 약혼하지 않은 상태가 된다). 약혼의 잠정적 특성은 이미 약혼한 여성이 "더 나은 상대로 갈아탈" (그리고 그 과정에서 그때까지의 배우자를 "저버릴") 권리를 보존한다.
이 알고리즘은 남성 또는 여성의 수가 일 때 시간  내에 모든 참가자에 대해 안정적인 결혼을 생성함을 보장한다.
가능한 모든 안정 매칭 중에서 이 알고리즘은 항상 모든 남성에게 가장 좋고 모든 여성에게는 가장 나쁜 매칭을 생성한다.
이것은 남성(청혼하는 측)의 관점에서 진실된 메커니즘이다. 즉, 어떤 남성도 자신의 선호도를 잘못 보고하여 자신에게 더 나은 매칭을 얻을 수 없다. 또한 GS 알고리즘은 남성에 대한 그룹 전략 증명(group-strategy proof)이다. 즉, 남성 연합이 자신들의 선호도를 왜곡하여 연합 내 모든 남성이 더 나은 상태가 되도록 조정할 수 없다. 그러나 일부 연합이 자신들의 선호도를 왜곡하여 일부 남성은 더 나은 상태가 되고 다른 남성은 같은 배우자를 유지하는 것이 가능하다.
GS 알고리즘은 여성(검토하는 측)에게는 진실되지 않다. 각 여성은 자신의 선호도를 잘못 보고하여 더 나은 매칭을 얻을 수 있다.
안정 매칭 문제 농촌 병원 정리
농촌 병원 정리는 안정 매칭 문제의 더 일반적인 변형에 관한 것으로, 병원에 의사를 배치하는 문제에 적용되는 경우 기본 n-대-n 형태의 안정 결혼 문제와 다음과 같은 방식으로 다르다.
이 경우 안정성 조건은 매칭되지 않은 어떤 쌍도 매칭에서의 자신의 상황(다른 배우자이든 매칭되지 않은 상태이든)보다 서로를 선호하지 않는 것이다. 이 조건에서도 안정 매칭은 여전히 존재하며, 게일-섀플리 알고리즘으로 찾을 수 있다.
이러한 종류의 안정 매칭 문제에 대해 농촌 병원 정리는 다음과 같이 설명한다.
안정 매칭 문제 관련 문제
무차별성을 포함한 안정 매칭에서는 일부 남성이 두 명 이상의 여성에게 무관심할 수 있으며 그 반대도 마찬가지이다.
안정 룸메이트 문제는 안정 결혼 문제와 유사하지만, 모든 참가자가 단일 풀에 속한다는 점(동일한 수의 "남성"과 "여성"으로 나뉘는 대신)에서 다르다.
병원 레지던트 문제 – 또한 대학 입학 문제로 알려짐 –는 병원이 여러 레지던트를 받을 수 있거나 대학이 한 명 이상의 학생으로 구성된 신입생을 받을 수 있다는 점에서 안정 결혼 문제와 다르다. 병원/레지던트 문제를 해결하는 알고리즘은 병원 중심적일 수 있다(1995년 이전 NRMP가 그랬던 것처럼). 또는 레지던트 중심적일 수 있다. 이 문제는 안정 결혼 문제가 해결된 동일한 게일과 섀플리의 원본 논문에서 알고리즘과 함께 해결되었다.
안정 매칭 문제 관련 문제
커플을 포함한 병원/레지던트 문제는 레지던트 집합에 커플을 포함할 수 있으며, 이들은 함께 배정되어야 한다. 동일한 병원이거나 커플이 선택한 특정 병원 쌍(예: 결혼한 커플이 함께 지내며 서로 멀리 떨어진 프로그램에 갇히지 않도록 보장하기를 원함)에 배정될 수 있다. 병원/레지던트 문제에 커플을 추가하면 이 문제는 NP-완전이 된다.
할당 문제는 최대 가중치를 갖는 가중 이분 그래프에서 매칭을 찾는 것을 목표로 한다. 최대 가중치 매칭은 안정적일 필요는 없지만, 일부 응용에서는 안정적인 매칭보다 최대 가중치 매칭이 더 좋다.
계약을 포함한 매칭 문제는 참가자들이 다른 계약 조건으로 매칭될 수 있는 매칭 문제의 일반화이다. 계약의 중요한 특별한 경우는 유연한 임금을 포함한 매칭이다.
안정 매칭 문제 추가 자료
[[Donald Knuth|Knuth, D. E.]] (1996). 《Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms》. English translation. CRM Proceedings and Lecture Notes. American Mathematical Society.  |author-link1= 값 확인 필요 (도움말)
Roth, A. E. (1984). 《The evolution of the labor market for medical interns and residents: A case study in game theory》 (PDF). 《Journal of Political Economy》 92. 991–1016쪽. doi:10.1086/261272. S2CID 1360205.
안정 매칭 문제 추가 자료
Shoham, Yoav; Leyton-Brown, Kevin (2009). 《Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations》. New York: Cambridge University Press. ISBN 978-0-521-89943-7.  See Section 10.6.4; downloadable free online.
Schummer, J.; Vohra, R. V. (2007). 〈Mechanism design without money〉 (PDF).   Nisan, Noam; Roughgarden, Tim; Tardos, Eva; Vazirani, Vijay (편집). 《Algorithmic Game Theory》. 255–262쪽. ISBN 978-0521872829.
저작자표시
저작자표시(attribution)는 저작권법에서 저작권자 또는 저작물 작성자에게 크레디트를 부여하여 인정하는 것을 말한다. 저작물이 저작권의 보호를 받는 경우, 저작자가 작성한 저작물의 일부를 직접 인용할 때 저작자표시를 요구하는 오랜 전통이 있다.
저작자는 라이선스를 통해 저작자표시를 공식적으로 요구할 수 있으며, 이는 타인이 저작물을 작성했다고 주장하는 것을 법적으로 방지하고 저작권자가 저작물 작성으로 인한 명예 이익을 유지할 수 있도록 한다. 저작권자가 저작자 자신인 경우, 이러한 행위는 저작물에 대한 크레디트를 제공함으로써 창작자를 인정하는 예의와 존경의 표시로 종종 도덕적으로 여겨진다.
그러나 저작권의 보호를 받지 않는 퍼블릭 도메인 저작물은 세계 대부분의 지역에서 그러한 저작자표시 요구사항이 없다. 이것이 범죄는 아니지만 비윤리적인 행위인 표절과 저작자의 법적 조치 원인이 될 수 있는 저작권 침해를 구별하는 요소이다.
저작자표시 저작권자표시
세계 대부분의 국가에서는 베른 협약으로 인해 원본 자료에 저작권자표시가 필수는 아니다. 가장 기본적인 형태의 저작자표시는 종종 Copyright © [연도] [저작권자 이름]의 형태로 저작권자의 신원을 명시하는 것이다. 미국에서는 이러한 표시의 보존이 과거에는 저작물이 퍼블릭 도메인으로 들어가는 것을 막기 위한 필수 요건이었다. 이것은 1988년 베른 협약 이행법에 의해 저작권 등록 및 저작권 기명 요구사항이 종료된 1989년 3월 1일에 변경되었다.
류하오판
류하오판(중국어: 刘浩帆, 2003년 10월 23일 ~ )는 중화인민공화국의 축구 선수로 포지션은 센터백이며 현재 중국 슈퍼리그 저장 FC 소속이다.
컴퓨터 예약 시스템
컴퓨터 예약 시스템(computer reservation system), 컴퓨터 좌석 예약 시스템 또는 중앙 예약 시스템(central reservation systems, CRS)은 항공 여행, 호텔, 렌터카 또는 기타 활동과 관련된 정보를 저장하고 검색하며 거래를 수행하는 데 사용되는 컴퓨터화된 시스템이다. 원래 항공사에서 설계하고 운영했지만, CRS는 나중에 여행사와 글로벌 유통 시스템(GDS)에서 여러 항공사의 티켓을 예약하고 판매하는 데 사용하도록 확장되었다. 대부분의 항공사는 CRS를 GDS 회사에 아웃소싱했으며, 이들 회사는 인터넷 게이트웨이를 통해 소비자에게도 접근을 가능하게 한다.
컴퓨터 예약 시스템
현대 GDS는 일반적으로 호텔 객실, 렌터카, 항공권뿐만 아니라 기타 활동 및 투어를 예약할 수 있게 한다. 또한 일부 시장에서는 철도 예약 및 버스 예약에 대한 접근을 제공하지만, 이들이 항상 주 시스템과 통합되는 것은 아니다. 이들은 호텔 산업의 사용자에게 컴퓨터화된 정보를 전달하는 데 사용되어 예약을 하고 호텔이 초과 예약되지 않도록 보장한다.
항공사 예약 시스템은 더 큰 승객 서비스 시스템에 통합될 수 있으며, 여기에는 항공사 재고 시스템과 출발 통제 시스템도 포함된다. 현재의 중앙 집중식 예약 시스템은 네트워크 전체의 시스템 중단에 취약하다.
컴퓨터 예약 시스템 역사
MARS-1 기차표 예약 시스템은 1950년대에 일본국유철도 연구개발원(현재의 철도종합기술연구소)에 의해 설계 및 계획되었으며, 이 시스템은 결국 1958년에 히타치 제작소에 의해 생산되었다. 이는 세계 최초의 기차 좌석 예약 시스템이었다. MARS-1은 좌석 위치를 예약할 수 있었으며, 중앙 처리 장치와 40만 비트의 자기 드럼 메모리 장치로 좌석 파일을 보관하는 트랜지스터 컴퓨터로 제어되었다. 이 시스템은 많은 프로세서 레지스터를 사용하여 기차의 좌석이 비어 있는지 예약되어 있는지를 나타내어 좌석 패턴 검색 및 업데이트, 터미널과의 통신, 예약 통지 인쇄, CRT 디스플레이를 가속화했다.
컴퓨터 예약 시스템 역사
1953년 트랜스 캐나다 항공 (TCA)은 원격 단말기를 갖춘 컴퓨터 기반 시스템을 조사하기 시작했으며, 그해 여름 토론토 대학교의 페란티 마크 1 기계에서 한 가지 설계를 시험했다. 성공적이었지만, 연구원들은 입출력이 큰 문제임을 발견했다. 페란티 캐나다는 이 프로젝트에 참여하여 신뢰할 수 없는 진공관 기반 마크 1 대신 천공 카드와 트랜지스터화된 컴퓨터를 사용하는 새로운 시스템을 제안했다. 그 결과물인 ReserVec 시스템은 1962년에 작동을 시작하여 1963년 1월에 모든 예약 업무를 인계했다. 터미널은 TCA의 모든 티켓 판매 사무실에 설치되어 원격 운영자가 필요 없이 약 1초 만에 모든 조회 및 예약이 완료될 수 있었다.
컴퓨터 예약 시스템 역사
1953년 아메리칸 항공의 CEO C. R. 스미스는 로스앤젤레스에서 뉴욕으로 가는 비행기에서 우연히 IBM의 고위 영업 대표인 R. 블레어 스미스 옆에 앉게 되었다. C.R.은 블레어를 초대하여 그들의 Reservisor 시스템을 방문하고 IBM이 시스템을 개선할 방법을 찾아보라고 요청했다. 블레어는 토마스 왓슨 주니어에게 아메리칸 항공이 대규모 협력에 관심이 있다고 알렸고, 일련의 저수준 연구가 시작되었다. 이들의 자동화된 항공사 예약 시스템 (ARS) 아이디어는 1959년 반자동 비즈니스 연구 환경(SABRE)으로 알려진 벤처로 이어졌고, 이듬해에 출시되었다. 1964년 12월 SABRE가 완전히 완성되었을 때, 이는 세계 최초의 온라인 트랜잭션 처리 시스템이었으며, 당시 "세계에서 가장 큰 민간 실시간 상업 전자 정보 처리 시스템"이었다.
컴퓨터 예약 시스템 역사
다른 항공사들도 자체 시스템을 구축했다. 팬아메리칸 월드 항공은 1965년에 PANAMAC 시스템을 출시했고 델타 항공은 1965년에 DELTAMATIC을 출시했는데, 이들 모두 IBM이 SABRE와 함께 SABER 공동 프로젝트의 일환으로 개발했다 (이후 아메리칸 항공은 프로젝트에 다른 이름을 고집하여 SABRE라는 이름이 붙었다). DELTAMATIC에 이어 1968년에는 델타 자동 여행 계정 시스템(DATAS)이 나왔다.
1965년 IBM은 SABER 공동 프로젝트에 대한 작업을 PARS로 일반화했으며, 이는 1971년까지 산업 표준이 되었다. 1971년부터 1973년까지 아메리칸 항공은 SABRE를 PARS 기반 시스템으로 전환했다.
곧 여행사들은 다양한 ARS에 직접 접속하여 예약을 함으로써 자신들의 업무를 자동화할 수 있는 시스템을 추진하기 시작했다. 이것이 에이전트들에게 너무 많은 권한을 부여할 것을 우려한 아메리칸 항공의 경영진 로버트 크랜달은 미국 여행의 중앙 정보 처리 기관이 될 산업 전체의 컴퓨터 예약 시스템을 만들 것을 제안했다. 다른 항공사들은 이것이 미국의 반독점법을 위반할 수 있다는 이유로 반대했다.
컴퓨터 예약 시스템 역사
1976년, 유나이티드 항공은 아폴로 시스템을 여행사들에게 제공하기 시작했다. 비록 에이전트들이 유나이티드의 경쟁사 항공권을 예약할 수는 없었지만, 편리한 터미널의 마케팅 가치는 필수불가결한 것으로 입증되었다. SABRE, PARS, DATAS도 곧 여행사들에게 공개되었다. 1978년 항공사 규제 완화법 이후, 효율적인 CRS는 특히 중요하게 입증되었다. 일부 집계에 따르면, 텍사스 에어의 임원 프랭크 로렌조는 SystemOne CRS에 대한 통제권을 얻기 위해 적자를 보고 있던 이스턴 항공을 특별히 인수했다.
컴퓨터 예약 시스템 역사
또한 1976년 비데콤 인터내셔널은 영국항공, 브리티시 칼레도니안, CCL과 함께 세계 최초의 다중 접속 예약 시스템인 트래비콤을 출시했으며(전적으로 비데콤 기술 기반), 처음에는 2개, 이후 49개 국제 항공사(영국항공, 브리티시 칼레도니안, 트랜스월드 항공, 팬아메리칸 월드 항공, 콴타스 항공, 싱가포르 항공, 에어 프랑스, 루프트한자, 스칸디나비아 항공, 에어 캐나다, KLM, 알리탈리아, 캐세이퍼시픽 항공, 일본항공 포함)에 영국 내 수천 개의 여행사로 분배하는 네트워크를 형성했다. 이를 통해 에이전트와 항공사는 공통 분배 언어 및 네트워크를 통해 통신할 수 있었으며, 1987년까지 영국 항공 비즈니스 거래 예약의 97%를 처리했다. 이 시스템은 비데콤에 의해 중동(DMARS), 뉴질랜드, 쿠웨이트(KMARS), 아일랜드, 카리브해, 미국, 홍콩 등 세계 다른 지역에서도 복제되었다. 트래비콤은 트래블 오토메이션 서비스(Travel Automation Services Ltd)의 상호였다. 영국항공(당시 트래블 오토메이션 서비스의 100%를 소유)이 갈릴레오 시스템 개발에 참여하기로 결정하자 트래비콤은 상호를 갈릴레오 UK로 변경하고 트래비콤에서 갈릴레오로 에이전시를 이전하는 과정이 시작되었다.
유럽 항공사들도 1980년대에 여행 수요 증가와 GDS가 ever-increasing 서비스와 검색 기능을 제공할 수 있도록 하는 기술 발전의 힘을 받아 자국 내에 자체 예약 시스템을 배포하며 이 분야에 투자하기 시작했다. 1987년, 에어 프랑스와 서독의 루프트한자가 이끄는 컨소시엄은 SystemOne을 모델로 한 아마데우스를 개발했다. 아마데우스 글로벌 트래블 디스트리뷰션은 1992년에 출시되었다. 1990년, 델타 항공, 노스웨스트 항공, 트랜스월드 항공은 월드스팬을 결성했고, 1993년에는 또 다른 컨소시엄(영국항공, KLM, 유나이티드 항공 등을 포함)이 아폴로를 기반으로 경쟁사 갈릴레오 GDS를 결성했다. 저비용 항공사 부문 및 중소규모 국내 및 지역 항공사를 포함하여 4대 네트워크가 다루지 않는 틈새 시장을 겨냥한 KIU와 같은 수많은 소규모 회사들도 형성되었다.
컴퓨터 예약 시스템 경향
처음에 항공사의 예약 시스템은 자사 항공편을 다른 항공편보다 선호했다. 1987년까지 미국 정부 규정에 따라 SABRE와 다른 미국 시스템은 중립적이어야 했으며, 항공사는 대신 이 시스템에 대한 접근권을 이윤을 위해 판매했다. 유럽 항공사의 시스템은 여전히 소유주의 항공편에 편향되어 있었지만, 플라이트 인터내셔널은 이들도 필연적으로 중립적이 될 것이라고 보도했다.
수년간 글로벌 유통 시스템 (GDS)은 여행 산업에서 지배적인 위치를 차지해 왔다. GDS를 우회하고 높은 GDS 수수료를 피하기 위해 항공사들은 웹사이트를 통해 직접 항공편을 판매하기 시작했다. GDS를 우회하는 또 다른 방법은 아메리칸 항공과 같은 여행사와의 직접 연결이다.
구원자
《구원자》는 2025년에 개봉한 대한민국의 영화이다.
디지털 자산 관리
디지털 자산 관리(Digital asset management, DAM) 및 컴퓨터 응용 프로그램으로서의 사용 구현은 소유자 및 대리인이 데이터 파일에 대한 작업을 수행할 수 있도록 디지털 자산 수집에 필요하다.
디지털 자산 관리 용어
미디어 자산 관리 (MAM)라는 용어는 일반적으로 오디오 녹음, 사진, 비디오와 같이 "미디어"로 간주되는 디지털 객체의 하위 집합에 적용될 때 디지털 자산 관리를 지칭하는 데 사용될 수 있다. 미디어, 특히 비디오를 포함하는 모든 편집 과정은 MAM을 사용하여 미디어 구성 요소에 접근하여 유연하게 함께 편집하거나 라이브 피드와 결합할 수 있다. MAM은 일반적으로 이미지에서 패턴 인식을 사용하여 수집하거나 수동으로 입력한 메타데이터로 구성된 검색 가능한 이미지, 오디오 및 비디오 인덱스를 하나 이상 제공한다.
디지털 자산 관리(DAM)는 디지털 방식으로 저장된 모든 형태의 정보 조각을 전자적으로 관리하는 데 초점을 맞출 수 있다. DAM은 분명히 전략적인 반면 MAM은 거의 항상 전술적이다. 두 자산 관리 모두 주로 보관, 보존 및 특히 재사용에 사용되는 장기 저장 콘텐츠를 반영한다.
디지털 자산 관리 관리
응용 프로그램은 아날로그 녹음 및 디지털 데이터 도메인에서 (인코딩, 이미지 스캐닝, 광학 문자 인식 등을 통해) 디지털 자산 관리를 가져오거나 새 개체로 작성하여 구현한다.
DAM 시스템의 주요 기능은 자산의 내용과 메타데이터를 통해 자산의 정보 검색을 지원하는 검색 가능한 인덱스를 제공하여 사용자가 자산을 쉽게 이용할 수 있도록 하는 것이다. 카탈로그 기능은 일반적으로 새 자산에 대한 수집 프로세스의 일부이다.
디지털 자산에는 일반적으로 생성, 승인, 라이브, 보관, 삭제와 같은 다양한 상태를 포함할 수 있는 수명 주기가 있다.
종종 DAM 시스템은 디지털 자산의 이전 버전을 저장하고 해당 버전을 다운로드하거나 되돌릴 수 있도록 한다. 따라서 DAM 시스템은 고급 유형의 버전 관리 시스템으로 작동할 수 있다.
디지털 자산 관리 관리
DAM 시스템에는 일반적으로 데이터 보호 동의 및 자산을 승인하고 분류하는 기능과 같은 컴플라이언스 조치가 포함되어 산업 또는 지역 컴플라이언스가 충족되도록 보장하며 사용자가 자신의 위치에 대해 법률을 준수하는 자산에만 접근할 수 있도록 한다.
마지막으로, DAM 시스템은 일반적으로 관련 사람들이 자산에 접근할 수 있도록 보안 제어를 포함한다. 이는 종종 통합 인증과 같은 기술을 통해 기존 디렉터리 서비스와 통합하는 것을 포함한다.
디지털 자산 관리 분류
소규모 DAM 시스템은 예를 들어 비디오 제작 시스템과 같은 특정 운영 환경에서 사용된다. 이들 간의 주요 차이점은 자산을 관리하기 위해 디지털 사본을 만드는 데 사용되는 입력 인코더 유형과 문 및 온라인 리소스로 사용 가능하게 만드는 데 사용되는 출력 디코더 및 포맷터 유형이다. 콘텐츠 항목의 메타데이터는 처리 중 콘텐츠를 처리하는 데 필요한 코덱 선택에 대한 가이드 역할을 할 수 있으며 접근 제어 규칙을 적용하여 승인 정책을 시행할 때 유용할 수 있다.
워크플로우에서 특정 기술이 필요한 자산은 해당 자산을 생성하거나 저장하는 도구 설계뿐만 아니라 해당 자산을 배포하고 보관하는 시스템 아키텍처에서 대역폭, 대기 시간 및 접근 제어 요구 사항을 고려해야 한다.
자산이 활발하게 작업되지 않을 때, 이들은 운영 중 필요한 형식보다 저장 비용이 "더 저렴한" 데이터베이스의 바이너리 라지 오브젝트(바이너리 라지 오브젝트) 또는 표준 파일 시스템의 파일 등 다양한 형식으로 DAM에 저장될 수 있다. 이를 통해 고성능 처리 시스템의 집합체가 중앙에 고밀도 저장 솔루션을 갖춘 네트워크 내에서 대규모 DAM을 구현할 수 있다.
디지털 자산 관리 시스템 유형
디지털 자산 관리 시스템은 다음 분류에 속한다.
이러한 모든 유형에는 워크플로우 관리, 협업, 프로젝트 관리 및 개정 관리 기능이 포함된다.
디지털 자산 관리 미디어 자산 문제
자산은 여러 형식과 일련의 버전으로 존재할 수 있다. 원본 자산의 디지털 버전은 일반적으로 최종 사용에 허용 가능한 품질을 보장하는 데 필요한 최고 해상도, 색 농도 및 (해당하는 경우) 프레임 속도로 캡처된다. 시각적 인덱싱에 사용하기 위한 저품질 섬네일 사본도 있을 수 있다.
자산의 메타데이터에는 패키징, 인코딩, 출처, 소유권 및 접근 권한, 원본 생성 위치가 포함될 수 있다. 이는 자산에 대해 작업하거나 자산과 함께 사용되는 도구 및 시스템에 자산이 어떻게 처리되고 표시되어야 하는지에 대한 힌트를 제공하는 데 사용된다.
디지털 자산 관리 추가 자료
Jacobsen, Jens; Schlenker, Tilman; Edwards, Lisa (2005). 《Implementing a Digital Asset Management System: For Animation, Computer Games, and Web Development》. Focal Press. ISBN 0-240-80665-4.