목록 업데이트 문제

List Update 또는 List Access 문제는 온라인 알고리즘의 경쟁 분석 연구에 사용되는 단순한 모델입니다.항목 액세스 비용이 목록 선두와의 거리에 비례하는 일련의 항목(예: Linked List 및 액세스 요청 순서)을 고려할 때, 문제는 전체 액세스 비용을 최소화하도록 목록을 재정렬하는 전략을 고안하는 것이다.재주문은 언제든지 가능하지만 비용이 발생합니다.표준 모델에는 다음 두 가지 정렬 작업이 포함됩니다.

• 현재 위치보다 이전 위치에 있는 항목에 대한 무료 이전.
• 리스트내의 인접하는 2개의 아이템을 교환하기 위한 단위 코스트의 유상 이동.알고리즘의 성능은 다양한 적대적 모델 하에서의 공격자에 의한 요청 시퀀스의 구성에 따라 달라집니다.

이 문제의 온라인 알고리즘은 이전에 요청된 항목의 지식만을 바탕으로 요소를 재정렬하고 요구를 처리해야 합니다.따라서 그 전략은 첫 번째 요구를 처리하기 전에 요구 시퀀스 전체를 확인하고 완전한 전략을 고안하는 오프라인 알고리즘에 비해 최적의 비용이 들지 않을 수 있습니다.

이 문제는 본래의 용도와 함께 Burrows에 따른 글로벌 컨텍스트 및 압축성 개선 문제와 매우 유사하다고 제안되어 왔다.휠러 트랜스폼이 변환에 따라 파일은 로컬로 높은 빈도를 갖는 큰 영역을 갖는 경향이 있으며, 자주 발생하는 문자가 0으로 이동하거나 "목록"의 앞부분으로 이동하는 기술을 통해 압축 효율이 크게 향상됩니다.따라서 압축성을 개선하기 위해 Move-to-Front 및 주파수 카운트의 방법 및 변형은 종종 BWT 알고리즘을 따릅니다.

대항 모델

상대는 알고리즘 ALG의 요구 시퀀스 $"\displaystyle \sigma"$를 선택하는 엔티티입니다.ALG의 전략에 따라 ${\(\displaystyle$ \$sigma)$를 변경할 수 있는지 여부에 따라 적에게 다양한 파워를 부여하여 ALG의 성능을 평가합니다.

무감각한 상대는 ALG를 실행하기 전에 요청 시퀀스 $전체{\displaystyle }$ $【\$${\displaystyle \mathrm{displaystyle}}$$\sigma】$를 구축해야 하며, $displaystyle$ OPT$(\sigma)$와 비교한 최적의 오프라인 가격 $sigma)$를 지불해야 합니다.

적응형 온라인 상대는 온라인 알고리즘의 이전 결과에 따라 다음 요청을 할 수 있지만, 요구에 대해 최적으로 온라인으로 지불합니다.

적응형 오프라인 상대는 온라인 알고리즘의 이전 결과에 따라 다음 요청을 할 수 있지만 최적의 오프라인 비용을 지불합니다.

오프라인 알고리즘

Optimal Offline Algorithm(OPT)의 정확한 성질에 대한 구체적인 지식 없이 많은 목록 업데이트 문제에 대한 경쟁 분석을 수행했습니다.O(n2^l(l-1)!) 시간 및 O(l!) 공간에서 실행되는 알고리즘이 있습니다.n은 요청 시퀀스의 길이, l은 ^[1]목록의 길이입니다.요청 시퀀스 길이에 따라 가장 잘 알려진 최적의 오프라인 알고리즘은 2014년 ^[2]Dr. Srikrishnan Divakaran에 의해 발표된 O(l^2(l-1)!n) 시간에 실행됩니다.

일반적으로 최적의 알고리즘을 위해 유료 전환이 필요하다.a가 목록의 선두에 있는 리스트(a, b, c)와 요구 시퀀스 c, b, c, b를 검토합니다.무료 교환만 사용하는 최적의 오프라인 알고리즘은 9(3+3+2+1)의 비용이 드는 반면 유료 교환만 사용하는 최적의 오프라인 알고리즘은 8의 비용이 듭니다.따라서 우리는 최적의 오프라인 알고리즘을 위해 무료 트랜지션을 사용하는 것만으로 벗어날 수 없습니다.

최적의 목록 업데이트 문제는 (Ambühl 2000) harv 오류: no target: CITRE FAMbühl 2000 (도움말)에 의해 NP-hard로 입증되었다.

온라인 알고리즘

온라인 알고리즘 ALG는 어떤 입력에서도 OPT보다 적어도 c배 이상 성능이 나쁘면 경쟁률 c를 $가집니다{\displaystyle }$.즉, 모든 유한길이 요구 시퀀스$display{\displaystyle }$$$\$displaystyle \sigma$${\displaystyle \mathrm{display<img\; alt="\{\backslash displaystyle\; \backslash alpha\; \backslash geq\; 0\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/d9e01f6a4360f062e662779cb235d41c7c68a557"\; style="vertical-align:\; -0.505ex;\; width:5.749ex;\; height:2.343ex;"\; papago-attr-id="39">}}$$$、 ${\displaystyle A}$ ${\displaystyle L}$ G${\displaystyle }$${\displaystyle （}$ ${\displaystyle ）}$ - ${\displaystyle C}$. ${\displaystyle P}$ $display$$$）${\displaystyle }$。OPT$(\sigma)\leq \alpha$ 온라인 알고리즘은 결정론적이거나 랜덤화할 수 있으며, 이 경우 랜덤화가 무감각한 적에 대해 진정으로 도움이 된다는 것이 $판명$되었습니다.

결정론

대부분의 결정론적 알고리즘은 다음 3가지 알고리즘의 변형입니다.

MTF(앞으로 이동)

항목에 액세스한 후 다른 항목의 순서를 변경하지 않고 목록 맨 앞으로 이동합니다.

TRANS(트랜스포즈)

항목에 액세스한 후 직전 항목으로 바꿉니다.

FC(주파수)

각 항목에 대해 해당 항목에 대한 액세스 횟수의 빈도 카운트를 유지합니다. 요소에 액세스할 때 해당 빈도 카운트를 늘리고 빈도 내림차순으로 목록을 재정렬합니다.

이 모든 것이 자유 이행만을 사용하는 것에 주의해 주세요.TRANS와 FC는 모두 경쟁력이 없는 것으로 나타났습니다.잠재력 분석(Sleator & Tarjan 1985)을 사용한 고전적인 결과에서 MTF가 2-경쟁력임을 입증했다.증명에는 OPT에 대한 명확한 지식이 필요하지 않지만, 반대로 MTF와 OPT 목록에 있는 요소의 역순으로 발생하는 역전의 수가 계산된다.

모든 결정론적 알고리즘은 길이 l의 리스트에 대해 2${\displaystyle }$- ${\displaystyle \frac{2}{}}$l +$1$의 하한을 가집니다({$displaystyle 2-{\frac {2$}{l$$$+1}}).$ MTF는 실제로 최적의 결정론적 리스트 갱신 알고리즘입니다.결정론적 알고리즘의 경우 상대방이 스스로 결정론적 알고리즘의 복사본을 실행하여 가장 비참한 시퀀스를 미리 계산할 수 있기 때문에 상대편의 유형은 중요하지 않습니다.

랜덤화

다음의 간단한 랜덤화 알고리즘을 검토합니다.

조금

목록의 모든 항목에 대해 조금씩 유지합니다.모든 비트를 0 또는 1로 균일하고 랜덤하게 초기화합니다.항목에 액세스할 때 비트를 뒤집고 1인 경우 앞으로 이동하고, 그렇지 않은 경우 앞으로 이동하지 마십시오.

이 알고리즘은 거의 랜덤하지 않습니다. 모든 랜덤 선택은 실행 중이 아니라 초반에 이루어집니다.BIT는 결정론적 경계를 깨는 것으로 판명되었습니다.- 망각한 적에 대해서는 MTF보다 낫습니다.7/4 경쟁사입니다.BIT보다 성능이 뛰어난 랜덤화 알고리즘이 COMB 등 있습니다.Boris Teia는 임의의 랜덤 리스트 갱신 ^[3]알고리즘에 대해 1.5의 하한을 증명했습니다.

관련 문제

요소가 삽입 및 삭제될 수 있는 리스트업데이트 문제를 다이내믹리스트 업데이트 문제라고 부릅니다.이 문제는 리스트 요소에 대한 접근만 허용되는 스태틱리스트 업데이트 문제와는 다릅니다.2${\displaystyle }$- ${\displaystyle \frac{2}{}}$l + $({$의 $상한$은 동적 모델에도 적용됩니다.

다른 비용 모델도 있습니다.통상적인 풀코스트 모델에서는 i 위치에 있는 요소에 대한 접근은 i 비용이 들지만, 마지막 비교는 어떤 알고리즘에서도 불가피하다.즉 i-1 요소가 i를 가로막고 있다.부분 비용 모델에서는 요청 시퀀스 내의 요소 수에 합산된 이러한 최종 비교 비용은 무시됩니다.단일성 이외의 유료 트랜지션 비용은 P^d 모델을 사용합니다.

「 」를 참조해 주세요.

• 온라인 알고리즘
• 경쟁력 분석
• 캐시 알고리즘

메모들

레퍼런스

• 를 클릭합니다Sleator, D.; Tarjan, R. (1985), "Amortized efficiency of list update and paging rules", Communications of the ACM, 28 (2): 202–208, CiteSeerX 10.1.1.367.6317, doi:10.1145/2786.2793, S2CID 2494305.
• Borodin, A.; El-Yaniv, R. (1998). Online Computation and Competitive Analysis. Cambridge University Press. ISBN 978-0-521-56392-5.

• Ambühl, C. (2000), Offline list update is np-hard, Springer, pp. 42–51