[논문]Iterative state-space reduction for flexible computation

Zhang, Weixiong

doi:10.1016/S0004-3702(00)00066-7

[해외논문] Iterative state-space reduction for flexible computation 원문보기

Artificial intelligence, v.126 no.1/2, 2001년, pp.109 - 138

Zhang, Weixiong (Department of Computer Science, Washington University, St. Louis, MO 63130-4899, USA)

Abstract ▼ AI-Helper

AbstractFlexible computation is a general framework for decision making under limited computational resources. It enables an agent to allocate limited computational resources to maximize its overall performance or utility. In this paper, we present a strategy for flexible computation, which we call iterative state-space reduction. The main ideas are to reduce a problem space that is difficult to search to one that is relatively easy to explore, to use the optimal solution from the reduced space as an approximate solution to the original problem, and to iteratively apply multiple reductions to progressively find better solutions. The basic operation for state-space reduction is heuristic node pruning, which excludes the nodes that do not seem to lead to high-quality solutions from further examination. Iterative state-space reduction can be combined with a state-space search, such as best-first search or depth-first branch-and-bound (DFBnB). The resulting algorithm can run as an anytime algorithm, which provides a tradeoff between solution quality and computation. Based on an analytical modal, we analyze the probability that one iteration of the iterative process finds a solution. Furthermore, by combining it within DFBnB we apply iterative state-space reduction to three combinatorial problems, the maximum Boolean satisfiability, the symmetric TSP and asymmetric TSP. Our experimental results show that iterative state-space reduction is effective and efficient, making DFBnB find better solutions with less computation.

Keyword

참고문헌 (52)

Balas 361 1985 The Traveling Salesman Problem Branch and bound methods
Bisiani 1467 1992 Encyclopedia of Artificial Intelligence Search, beam
Artificial Intelligence Boddy Vol. 67 245 1994 10.1016/0004-3702(94)90054-X Deliberation scheduling for problem solving in time-constrained environments

상세보기
Management Science Carpaneto Vol. 26 736 1980 10.1287/mnsc.26.7.736 Some new branching and bounding criteria for the asymmetric traveling salesman problem

상세보기
Cheeseman 331 1991 Proc. IJCAI-91, Sydney, Australia Where the really hard problems are
Artificial Intelligence Dagum Vol. 60 141 1993 10.1016/0004-3702(93)90036-B Approximating probabilistic inference in bayesian belief networks is NP-hard

상세보기
J. ACM Davis Vol. 7 201 1960 10.1145/321033.321034 A computing procedure for quantification theory

상세보기
Dean 49 1988 Proc. AAAI-88, St. Paul, MN An analysis of time-dependent planning
Artificial Intelligence Dietterich Vol. 16 257 1981 10.1016/0004-3702(81)90002-3 Inductive learning of structural descriptions: Evaluation criteria and comparative review of selected methods

상세보기
Fox 1983 Constraint directed search: A case study of job-shop scheduling, Ph.D. Thesis
Artificial Intelligence Freuder Vol. 58 21 1992 10.1016/0004-3702(92)90004-H Partial constraint satisfaction

상세보기
Garey 1979 Computers and Intractability: A Guide to the Theory of NP-Completeness
Artificial Intelligence Ginsberg Vol. 55 367 1992 10.1016/0004-3702(92)90059-7 Iterative broadening

상세보기
Hansen 1997 Anytime heuristic search: First results
Harris 1963 The Theory of Branching Processes
Mathematical Programming Held Vol. 1 6 1971 10.1007/BF01584070 The traveling salesman problem and minimum spanning trees: Part II

상세보기
1996 Proceedings of the AAAI Fall Symposium on Flexible Computation in Intelligent Systems: Results, Issues and Opportunities, Cambridge, MA
Horvitz 1987 Proc. 3rd Workshop on Uncertainty in Artificial Intelligence Reasoning about beliefs and actions under computational resource constraints
Zeitschrift fur Operations Research Ibaraki Vol. 27 177 1983 Using branch-and-bound algorithms to obtain suboptimal solutions
Johnson 341 1996 Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms Asymptotic experimental analysis for the Held-Karp Traveling Salesman bound
Artificial Intelligence Karp Vol. 21 99 1983 10.1016/S0004-3702(83)80006-X Searching for an optimal path in a tree with random costs

상세보기
Artificial Intelligence Korf Vol. 27 97 1985 10.1016/0004-3702(85)90084-0 Depth-first iterative-deepening: An optimal admissible tree search

상세보기
Artificial Intelligence Korf Vol. 42 189 1990 10.1016/0004-3702(90)90054-4 Real-time heuristic search

상세보기
Korf 1994 Proc. AAAI 1994 Workshop on Experimental Evaluation of Reasoning and Search Methods, Seattle, WA Incremental random search trees
Langley 145 1992 Proc. 1st International Conference on AI Planning Systems, College Park, MD Systematic and nonsystematic search strategies
Lawler 1985 The Traveling Salesman Problem
Lee 1988 Large-vocabulary speaker-dependent continuous recognition: The sphinx system, Ph.D. Thesis
Ann. Discrete Math. Martello Vol. 31 259 1987 Linear assignment problems
McDiarmid 249 1990 Disorder in Physical Systems Probabilistic analysis of tree search
McDiarmid 172 1991 Proc. IJCAI-91, Sydney, Australia An expected-cost analysis of backtracking and non-backtracking algorithms
Mitchell 459 1992 Proc. AAAI-92, San Jose, CA Hard and easy distributions of SAT problems
Motwani 1992 Lecture notes on approximation algorithms
Muscettola 1989 Generating space telescope observation schedules
Papadimitriou 1982 Combinatorial Optimization: Algorithms and Complexity
Ann. Math. Artificial Intelligence Patrick Vol. 5 265 1992 10.1007/BF01543478 An upper bound on the complexity of iterative-deepening-A？

상세보기
Artificial Intelligence Pemberton Vol. 81 297 1996 10.1016/0004-3702(95)00057-7 Epsilon-transformation: Exploiting phase transitions to solve combinatorial optimization problems

상세보기
1995 Proceedings of the AAAI Fall Symposium on Rational Agency, Cambridge, MA
1995 Proceedings of the IJCAI-95 Workshop on Anytime Algorithms and Deliberation Scheduling, Montreal, Canada
Provost 769 1993 Proc. AAAI-93, Washington, DC Iterative weakening: Optimal and near-optimal policies for the selection of search bias
Rubin 1978 The ARGOS image understanding system, Ph.D. Thesis
Russell 1991 Do the Right Thing: Studies in Limited Rationality
European J. Oper. Res. Volgenant Vol. 9 83 1982 10.1016/0377-2217(82)90015-7 A branch and bound algorithm for the symmetric Traveling Salesman Problem based on the 1-tree relaxation

상세보기
Winston 1992 Artificial Intelligence
Zhang 160 1993 Proc. AAAI 1993 Spring Symposium on AI and NP-Hard Problems, Stanford, CA Truncated branch-and-bound: A case study on the asymmetric TSP
Zhang 425 1998 Proc. AAAI-98, Madison, WI Complete anytime beam search
Zhang 531 1998 Proc. 14th Annual Conference on Uncertainty in Artificial Intelligence (UAI-98), Madison, WI Flexible and approximate computation through state-space reduction
Zhang 148 1999 Proc. AAAI 1999 Spring Symposium on Search Techniques for Problem Solving under Uncertainty and Incomplete Information, Stanford, CA Truncated and anytime depth-first branch-and-bound: A case study on the asymmetric Traveling Salesman Problem
Zhang 545 1992 Proc. AAAI-92, San Jose, CA An average-case analysis of branch-and-bound with applications: Summary of results
Zhang 769 1993 Proc. AAAI-93, Washington, DC Depth-first vs. best-first search: New results
Artificial Intelligence Zhang Vol. 79 241 1995 10.1016/0004-3702(94)00047-6 Performance of linear-space search algorithms

상세보기
Zhang 895 1994 Proc. AAAI-94, Seattle, WA Epsilon-transformation: Exploiting phase transitions to solve combinatorial optimization problems-Initial results
Artificial Intelligence Zilberstein Vol. 82 181 1996 10.1016/0004-3702(94)00074-3 Optimal composition of real-time systems

상세보기

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

원문 보기

AccessON 원문보기

원문 URL 링크

DOI : 10.1016/S0004-3702(00)00066-7 [무료]
Elsevier : 저널 > 논문 [무료]
AccessON : 저널

*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.

ScienceON TREND 양자컴퓨터

오픈액세스(OA) 유형

BRONZE

출판사/학술단체 등이 한시적으로 특별한 프로모션 또는 일정기간 경과 후 접근을 허용하여, 출판사/학술단체 등의 사이트에서 이용 가능한 논문

저작권 관리 안내

내보내기 메뉴

내보내기 구분

파일저장
인쇄
메일전송

구성항목

기본정보
상세정보

관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관

저장형식

Text(ASCII format)
Excel format
RefWorks Direct Export
RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley

메일정보

받는사람 (필수): @
보내는사람 (선택): @
제목
내용: KISTI 검색결과 이메일 서비스

안내

총 건의 자료가 검색되었습니다.

다운받으실 자료의 인덱스를 입력하세요. (1-10,000)

검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다.

데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요)

다운로드 파일은 UTF-8 형태로 저장됩니다.
파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오.

Text(ASCII format)
Excel format

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

AI-Helper ※ AI-Helper는 을 사용합니다.

AI-Helper

안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

연합인증