온라인 알고리즘
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
온라인 알고리즘은 전체 입력을 미리 알 수 없는 상황에서 결정을 내려야 하는 알고리즘을 의미하며, 이러한 상황에서 의사 결정의 질을 연구한다. 온라인 알고리즘의 성능을 평가하기 위해 경쟁 분석을 사용하며, 이는 온라인 알고리즘과 오프라인 알고리즘의 성능을 비교한다. 온라인 알고리즘은 삽입 정렬, 퍼셉트론, 저수지 샘플링 등 다양한 예시가 있으며, 최단 경로 탐색 문제와 같이 전체 정보를 알 수 없는 상황에서 유용하게 사용된다. 캐나다 여행자 문제와 같은 온라인 문제를 해결하기 위해 다양한 온라인 알고리즘이 활용되며, k-서버 문제, 작업장 스케줄링 문제 등 다양한 문제들이 존재한다.
더 읽어볼만한 페이지
- 온라인 알고리즘 - 경쟁성 분석
경쟁성 분석은 위키백과 내에서 문서 분석, 주제 통합, 목차 설계가 예정된 상태로, 아직 내용이 채워지지 않아 내용 추가가 필요한 문서이다. - 온라인 알고리즘 - 페이지 교체 알고리즘
페이지 교체 알고리즘은 메모리 부족 시 메모리 페이지를 교체하는 방법으로, 다양한 종류와 고려 사항이 존재하며 여러 환경에 적용된다.
| 온라인 알고리즘 | |
|---|---|
| 개요 | |
| 유형 | 알고리즘 |
| 분야 | 컴퓨터 과학, 알고리즘 분석 |
| 특징 | 입력 전체를 미리 알 수 없는 상황에서 동작 |
| 관련 분야 | 스트리밍 알고리즘, 경쟁 분석 |
| 상세 내용 | |
| 정의 | 알고리즘이 입력의 일부만을 읽은 상태에서 결정을 내려야 하는 알고리즘 |
| 예시 | 삽입 정렬 온라인 쇼핑 추천 시스템 캐시 관리 |
| 경쟁 분석 | 온라인 알고리즘의 성능을 분석하는 방법론 |
| 온라인 알고리즘의 한계 | 최적의 해를 보장할 수 없음 |
| 목표 | 가능한 한 최적의 해에 가까운 해를 찾는 것 |
| 오프라인 알고리즘과의 비교 | |
| 오프라인 알고리즘 | 입력 전체를 미리 알고 있는 상태에서 동작하는 알고리즘 |
| 온라인 알고리즘 | 입력의 일부만을 읽은 상태에서 동작하는 알고리즘 |
| 장단점 | 온라인 알고리즘은 실시간 처리 가능, 오프라인 알고리즘은 최적의 해 보장 가능 |
| 활용 | |
| 활용 분야 | 운영 체제 데이터베이스 시스템 네트워크 게임 이론 |
2. 정의
온라인 알고리즘은 전체 입력을 처음부터 알 수 없는 상황에서 작동하며, 이 때문에 나중에 최적이 아닌 결정을 내릴 수도 있다. 온라인 알고리즘 연구는 이러한 상황에서 가능한 최선의 결정을 내리는 데 초점을 맞춘다.
2. 1. 경쟁 분석
온라인 알고리즘은 전체 입력을 알지 못하기 때문에, 나중에 최적이 아닌 결정들을 내려야만 하며, 온라인 알고리즘 연구는 이러한 상황에서 가능한 의사 결정의 질에 초점을 맞춰왔다. 경쟁 분석은 동일한 문제 인스턴스에 대해 온라인 알고리즘과 오프라인 알고리즘의 상대적 성능을 비교함으로써 이러한 아이디어를 공식화한다. 구체적으로, 알고리즘의 경쟁 비율은 모든 가능한 입력에 대해 알고리즘의 비용을 최적 비용으로 나눈 최악의 경우의 비율로 정의된다. 온라인 문제의 경쟁 비율은 온라인 알고리즘이 달성한 최상의 경쟁 비율이다. 직관적으로, 알고리즘의 경쟁 비율은 이 알고리즘이 생성한 솔루션의 품질에 대한 척도를 제공하는 반면, 문제의 경쟁 비율은 이 문제를 위해 미래를 아는 것이 얼마나 중요한지를 보여준다.2. 2. 다른 관점
- 스트리밍 알고리즘: 과거 입력값을 정확하게 표현하는 데 필요한 메모리 양에 중점을 둔다.
- 동적 알고리즘: 온라인 입력이 있는 문제에 대한 솔루션을 유지 관리하는 시간 복잡도에 중점을 둔다.
3. 예제
- 삽입 정렬
- 퍼셉트론
- 저수지 샘플링
- 탐욕 알고리즘
- 적대적 모델
- 메트릭 작업 시스템
- 오즈 알고리즘
- 페이지 교체 알고리즘
- 분산 계산 알고리즘
- 우코넨 알고리즘
- 입자 필터
- 데이터 압축 알고리즘의 상당수는 스트림 알고리즘임. LZSS, LZ77
4. 온라인 문제
온라인 알고리즘은 모든 입력값이 미리 주어지지 않고, 시간이 지남에 따라 순차적으로 입력되는 상황에서 작동하는 알고리즘이다. 이러한 특성 때문에 온라인 알고리즘은 기존 알고리즘과는 다른 접근 방식과 성능 측정 방법이 필요하다.
최단거리탐색 문제를 예로 들어보자. 탐색할 그래프가 유한 개의 노드로 이루어진 것은 알지만, 모든 연결 상태를 미리 알 수는 없다. 특정 노드에 도착해야만 주변 이웃 노드를 알 수 있다. 이런 경우 모든 가능성을 나열하여 최단거리를 찾는 것은 불가능하므로, 경쟁성 분석과 같은 새로운 성능 측정 방법이 필요하다.
캐나다 여행자 문제는 온라인 알고리즘의 개념을 잘 보여주는 또 다른 예시이다. 가중치 그래프에서 일부 간선이 제거될 수 있는 상황에서, 대상에 도달하는 비용을 최소화해야 한다. 간선 제거 여부는 여행자가 간선의 한쪽 끝점에 도달해야만 알 수 있다. 최악의 경우 모든 간선이 제거되어 최단 경로 문제로 축소될 수 있다. 이 문제는 경쟁성 분석으로 분석할 수 있으며, PSPACE-완전이다.[1]
이 외에도 다음과 같은 다양한 온라인 문제들이 존재한다.
- k-서버 문제
- 작업장 스케줄링 문제
- 리스트 갱신 문제
- 밴딧 문제
- 비서 문제
- 탐색 게임
- 스키 대여 문제
- 선형 탐색 문제
- 포트폴리오 선택 문제
- 입자 필터 (Particle filter)
- 데이터 압축 알고리즘 (예: LZSS, LZ77)
4. 1. 최단 경로 탐색 문제
탐색하고자 하는 그래프가 유한 개의 노드로 이루어졌다는 것은 알고 있으나, 그 모든 연결 상태는 아직 알 수 없다고 가정한다. 알고리즘이 어떤 특정 노드에 도착했을 때만 그 주위에 연결된 이웃 노드를 알게 된다. 이러한 조건에서는 전체 상황을 알 수 없기 때문에, 모든 가능한 경우를 나열하고 그중 최단거리를 얻어내는 것과 같은 간단한 방법은 사용할 수 없다. 따라서 이러한 경우를 위해 경쟁성 분석(competitive analysis)과 같은 새로운 알고리즘 성능 측정 방법이 필요하다.온라인 알고리즘의 개념을 잘 보여주는 문제 중 하나는 캐나다 여행자 문제이다. 이 문제의 목표는 가중치 그래프에서 일부 간선이 신뢰할 수 없고 그래프에서 제거되었을 수 있는 경우, 대상에 도달하는 비용을 최소화하는 것이다. 그러나 간선이 제거(''실패'')되었다는 사실은 ''여행자''가 간선의 한쪽 끝점에 도달했을 때만 밝혀진다. 이 문제의 최악의 경우는 신뢰할 수 없는 모든 간선이 실패하여 문제가 일반적인 최단 경로 문제로 축소되는 것이다. 이 문제에 대한 대안적인 분석은 경쟁 분석을 통해 수행할 수 있다. 이 분석 방법에서 오프라인 알고리즘은 어떤 간선이 실패할지 미리 알고 있으며, 목표는 온라인 알고리즘과 오프라인 알고리즘의 성능 비율을 최소화하는 것이다. 이 문제는 PSPACE-완전이다.[1]
참조
[1]
학술지
On-line algorithms versus off-line algorithms: How much is it worth to know the future?
http://www.icsi.berk[...]
1992
[2]
서적
Online Algorithms for the Portfolio Selection Problem
https://www.springer[...]
Springer Gabler
2016
[3]
웹사이트
オンラインアルゴリズムで平均値の逐次計算
http://qiita.com/awa[...]
2014-10-05
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com