온라인 알고리즘

Online algorithm

컴퓨터 과학에서 온라인 알고리즘은[1] 처음부터 전체 입력을 이용할 수 없는 상태에서 입력을 알고리즘에 공급되는 순서, 즉 입력을 연속적으로 처리할 수 있는 알고리즘이다.

이와는 대조적으로 오프라인 알고리즘은 처음부터 전체 문제 데이터가 주어지고 당면한 문제를 해결하는 답을 출력해야 한다. 운영 연구에서는 온라인 알고리즘이 개발되는 영역을 온라인 최적화라고 한다.

예를 들어 정렬 알고리즘 선택 정렬 및 삽입 정렬을 고려하십시오. 선택 정렬 정렬은 정렬되지 않은 나머지 요소에서 최소 요소를 반복적으로 선택하여 앞쪽에 배치하므로 전체 입력에 대한 액세스가 필요하므로 오프라인 알고리즘이 된다. 반면에 삽입 분류는 반복당 하나의 입력 요소를 고려하며 미래 요소를 고려하지 않고 부분적인 솔루션을 생성한다. 따라서 삽입 정렬은 온라인 알고리즘이다.

삽입 정렬의 최종 결과, 즉 올바르게 정렬된 목록이 최적이라는 점에 유의하십시오. 많은 문제에서 온라인 알고리즘은 오프라인 알고리즘의 성능을 따라올 수 없다. 온라인 알고리즘의 성능과 최적의 오프라인 알고리즘 사이의 비율이 경계되면 온라인 알고리즘을 경쟁이라고 한다.[1]

모든 오프라인 알고리즘이 효율적인 온라인 상대는 아니다.

정의

입력 전체를 모르기 때문에 온라인 알고리즘은 나중에 최적이 아닌 것으로 판명될 수 있는 결정을 내릴 수밖에 없고, 온라인 알고리즘의 연구는 이 환경에서 가능한 의사 결정의 품질에 초점을 맞추었다. 경쟁 분석은 동일한 문제 사례에 대해 온라인과 오프라인 알고리즘의 상대적 성능을 비교함으로써 이 아이디어를 공식화한다. 특히, 알고리즘의 경쟁률은 가능한 모든 입력에 대해 최적의 비용으로 나눈 최악의 경우 비율로 정의된다. 온라인 문제의 경쟁률은 온라인 알고리즘이 달성한 최고의 경쟁률이다. 직관적으로 알고리즘의 경쟁률은 이 알고리즘이 생산하는 솔루션의 품질에 대한 측정치를 제공하는 반면, 문제의 경쟁률은 이 문제에 대한 미래를 아는 것의 중요성을 보여준다.

기타 해석

알고리즘에 대한 온라인 입력에 대한 기타 관점은 을 참조하십시오.

  • 스트리밍 알고리즘: 과거의 입력을 정확하게 나타내기 위해 필요한 메모리 양에 초점을 맞춘다.
  • 동적 알고리즘: 온라인 입력 문제에 대한 해결책 유지의 시간 복잡성에 초점을 맞춘다.

예

일부 온라인 알고리즘:

온라인 문제

온라인 알고리즘의 개념을 예시하는 문제는 캐나다 여행자 문제다. 이 문제의 목적은 일부 가장자리가 신뢰할 수 없고 그래프에서 제거되었을 수 있는 가중 그래프에서 목표값에 도달하는 비용을 최소화하는 것이다. 단, 가장자리가 제거(실패)되었다는 것은 여행자가 가장자리의 끝점 중 하나에 도달했을 때에만 나타난다. 이 문제의 가장 나쁜 경우는 단순히 모든 신뢰할 수 없는 가장자리가 실패하고 문제가 일반적인 최단 경로 문제로 줄어든다는 것이다. 경쟁 분석의 도움을 받아 문제에 대한 대체 분석을 할 수 있다. 이 분석 방법을 위해 오프라인 알고리즘은 어떤 에지가 고장날지 미리 알고 있으며, 목표는 온라인과 오프라인 알고리즘의 성능 비율을 최소화하는 것이다. 이 문제는 PSPACE-완전이다.

솔루션으로 두 개 이상의 온라인 알고리즘을 제공하는 많은 공식적 문제가 있다.

참고 항목

참조

  1. ^ a b Karp, Richard M. (1992). "On-line algorithms versus off-line algorithms: How much is it worth to know the future?" (PDF). IFIP Congress (1). 12: 416–429. Retrieved 17 August 2015.
  2. ^ Dochow, Robert (2016). Online Algorithms for the Portfolio Selection Problem. Springer Gabler.

외부 링크