임의의 알고리즘

Anytime algorithm

컴퓨터 공학에서 언제든지 알고리즘은 문제가 끝나기 전에 중단되더라도 유효한 해결책을 반환할 수 있는 알고리즘입니다.이 알고리즘은 계속 실행될수록 더 나은 솔루션을 찾을 수 있을 것으로 기대됩니다.

대부분의 알고리즘은 완료까지 실행되며 일정한 양의 계산을 수행한 후 하나의 답을 제공합니다.다만, 경우에 따라서는, 유저가 완료하기 전에 알고리즘을 종료하고 싶은 경우가 있습니다.예를 들어, 필요한 계산량이 상당할 수 있으며 계산 리소스를 재할당해야 할 수 있습니다.대부분의 알고리즘은 완료까지 실행되거나 유용한 솔루션 정보를 제공하지 않습니다.그러나 언제든지 알고리즘은 부분 응답을 반환할 수 있으며, 그 품질은 실행할 수 있는 계산의 양에 따라 달라집니다.임의의 알고리즘에 의해 생성되는 답은 정답의 근사치입니다.

이름

임의의 알고리즘은, 「인터럽트 알고리즘」이라고도 불립니다.이러한 알고리즘은 사전에 시간을 선언해야 하는 계약 알고리즘과는 다릅니다.임의의 알고리즘에서는, 프로세스가 [1]종료하고 있는 것을 통지할 수 있습니다.

목표들

언제든지 알고리즘의 목표는 인텔리전트 시스템에 턴어라운드 [2]시간의 대가로 더 나은 품질의 결과를 낼 수 있는 능력을 부여하는 것입니다.시간과 [3]자원도 유연해야 합니다.인공지능이나 인공지능 알고리즘은 결과를 완성하는 데 오랜 시간이 걸릴 수 있기 때문에 그것들은 중요하다.이 알고리즘은 [3]단시간에 완료되도록 설계되어 있습니다.또, 이러한 기능은, 시스템이 에이전트에 의존해, 그 에이전트에 한정되어 있는 것, 및 그것들이 어떻게 [3]협력해 동작하는지를 보다 잘 이해하기 위한 것입니다.예를 들어,[4] 숫자의 제곱근을 구하는 데 적용되는 뉴턴-라프슨 반복이 있습니다.언제든지 알고리즘을 사용하는 또 다른 예로는 목표물을 목표로 할 때 발생하는 궤도 문제입니다.물체는 알고리즘이 완료되기를 기다리는 동안 공간을 이동하며,[3] 심지어 대략적인 답변이라도 조기에 주어진다면 그 정확도가 크게 향상될 수 있습니다.

알고리즘이 항상 고유한 이유는 어떤 [2]입력에 대해서도 가능한 많은 결과를 반환할 수 있기 때문입니다.Anytime Algorithm은 문제 해결 및 분산 컴퓨팅 [2]자원의 진척 상황을 감시하기 위해 잘 정의된 많은 품질 측정 기준을 사용합니다.주어진 [5]시간에 가장 적합한 답을 계속 찾습니다.완료될 때까지 실행되지 않을 수 있으며 더 오래 [6]실행되도록 허용하면 답변이 개선될 수 있습니다.이것은 대규모 의사결정 세트의 [7]문제에 자주 사용됩니다.종료가 [8]허가되지 않는 한 일반적으로 유용한 정보를 제공하지 않습니다.이것은 동적 프로그래밍과 비슷하게 들릴 수 있지만, 차이점은 순차적인 것이 아니라 무작위 조정을 통해 미세 조정된다는 것입니다.

알고리즘은 언제든지 정지하도록 설계되어 지금까지 [3]발견된 최상의 결과를 반환합니다.이것이 인터럽트 알고리즘이라고 불리는 이유입니다.특정 시간 알고리즘도 마지막 결과를 유지하므로 시간이 더 주어지면 중단한 부분부터 계속하여 더 나은 [3]결과를 얻을 수 있습니다.

의사결정 트리

결정자가 행동해야 할 때는 분명 애매모호함이 있을 것이다.또한, 이 모호함을 어떻게 해결할 것인가에 대한 아이디어가 있을 것이다.이 아이디어는 상태-행동 [7]다이어그램으로 변환할 수 있어야 합니다.

퍼포먼스 프로파일

퍼포먼스 프로파일은 [3]입력과 알고리즘에 할당된 시간을 바탕으로 결과의 품질을 추정합니다.견적이 좋을수록 결과를 빨리 찾을 [3]수 있을 것이다.일부 시스템에는 출력이 예상 [3]출력일 가능성을 제공하는 더 큰 데이터베이스가 있습니다.1개의 알고리즘에 복수의 퍼포먼스프로파일을 [9]설정할 수 있다는 점에 주의해 주십시오.대부분의 시간 성과 프로파일은 대표적인 사례를 사용하여 수학적 통계를 사용하여 구성됩니다.예를 들어 출장 세일즈맨 문제에서는 필요한 [1]통계를 생성하기 위해 사용자 정의 특수 프로그램을 사용하여 성과 프로파일을 생성했습니다.이 예에서 성능 프로파일은 예상 [1]결과에 대한 시간 매핑입니다.이 품질은 여러 가지 방법으로 측정할 수 있습니다.

  • 확실성: 정확성의 확률이 품질을 결정하는[1] 경우
  • 정확도: 오차한계는 품질을 결정합니다[1].
  • 특수성: 세부사항의 양이 품질을 결정하는[1] 경우

알고리즘의 전제 조건

초기 동작:즉석에서 추측하는 알고리즘이 있는 반면,[9] 다른 알고리즘은 보다 계산적인 접근방식을 취하고 추측을 하기 전에 시작 기간을 갖습니다.

  • 성장 방향:프로그램의 "출력" 또는 결과의 품질이 시간의 함수에 따라 어떻게 달라지는지("[9]실행 시간")
  • 증가율:각 스텝에 따른 증가량.버블 정렬 등 끊임없이 변화하거나 예측할 수 없는 변화가 있습니까?
  • 종료 조건:필요한 런타임[9] 양

레퍼런스

  1. ^ a b c d e f Hendler, James A., 인공지능 플래닝 시스템즈, 1992년
  2. ^ a b c 질베르슈타인, 쉬로모"인텔리전트 시스템에서 언제든지 알고리즘 사용", 1996.http://rbr.cs.umass.edu/shlomo/papers/Zaimag96.pdf
  3. ^ a b c d e f g h i 잔디, 조슈아「계산 자원의 할당에 관한 논거."http://www.acm.org/crossroads/xrds3-1/racra.html 웨이백 머신에서 2007-12-12 아카이브 완료
  4. ^ 무료 온라인 컴퓨팅 사전(FOLDOC)에서 제공하는 임의의 알고리즘
  5. ^ "Anytime algorithms". Cognitive architectures. University of Michigan Artificial Intelligence Laboratory. Archived from the original on 13 December 2013.
  6. ^ "Anytime algorithm - Computing Reference". eLook.org. Archived from the original on 12 December 2013.
  7. ^ a b Horsch, Michael C., Pool, David "불확실성 하에서의 의사결정을 위한 임의의 알고리즘", 2013, http://www.cs.ubc.ca/spider/poole/papers/randaccref.pdf
  8. ^ 벤더, 에드워드 AIEEE 컴퓨터 학회 대표, 1996년 인공지능의 수학적 방법
  9. ^ a b c d 테이제, 아네트 텐, 하멜렌, 프랭크"Anytime Performance Profile을 사용한 문제 해결 방법 설명", 2000.

추가 정보

  • 보디, M, 딘, T. 1989시간 의존형 계획 문제 해결.테크니컬 리포트: CS-89-03, 브라운 대학교
  • 글라스, J. 및 질버스타인, S. 1996.언제든지 알고리즘 개발 도구.SIGART Bulletin (언제든지 알고리즘과 숙고 스케줄에 관한 특집호)7 (2)
  • 마이클 C.불확실성 하에서의 의사결정을 위한 An Anytime Algorithm for Decision Foole, Proc. 제14회 인공지능 불확실성에 관한 컨퍼런스(UAI-98), 미국 위스콘신주 매디슨, 1998년 7월, 246-255페이지.
  • E.J. 호비츠한정된 자원의 세계에서의 추론 트레이드오프에 대한 추론.테크니컬 리포트 KSL-86-55, 의료정보학부, 스탠포드 대학, 캘리포니아 스탠퍼드 대학, 1986년 3월
  • 월리스, R.와 프로이트, E. 1995.제약 만족도와 SAT 문제를 위한 임의의 알고리즘.논문은 8월 20일 캐나다 몬트리올에서 열린 IJCAI-95 Anytime Algorithms and Advestion Scheduling 워크숍에서 발표되었습니다.
  • 질베르슈타인, 1993년 산.Anytime Algorithm 컴파일을 통한 운영 합리성캘리포니아 대학교 버클리 컴퓨터 과학부 박사 학위
  • Shlomo Zilberstein, AI Magazine, Anytime Algorithm in Intelligent Systems, 17(3): 73-83, 1996