Heuristic search techniques in problem reduction method

Abstract

ÖZET PROBLEM İNDİRGEME YÖNTEMLERİ İÇİN BULUŞSAL ARAMA TEKNİKLERİ MOHAMMED A. ARTEIMI Yüksek Lisans Tezi, Bilgisayar Müh» Bölümü Tez Danışnıanı: Doç: »Dr. Müren Bökeri Nisan, İ9S8, 207 sayfa Sorun Çözen tarama algoritmaları, bilgisayar bilim ve mühen- dislignin pek çok alanında yaygın olarak kullanılmıştır. Uygulamalar j oyun programları, biçim algılama, karar analizi, Robotik, ve teorem kanıtlama gibi çok değişik alanlardan olmuştur. Arama algoritmalarının kullanıldığı değişik prob lemlerin değişen gereksinmelerine bağlı olarak, değişik tarama algoritmaları geliştirilmiştir. örneğin ş Minima;-; tarama için Alfa Beta, SSS ve B, durum aramase için A ve diğer Heuris- tic arama yordamları, problem indirgeme için A, A, AO, A. ve C, Kombinaterial optimizasyon sorunları içinde Branch-and- Bound ve Dinamik programlama yordamları geliştirilmiştir. Bu yordamların çoğunun da diğerleriyle ilişkili olduğu sanılmak tadır. Bu tezde, sorun indirgeme için kullanılan çeşitli algorit malar tartışılmıştır. iki genel teknik (Yukarıdan aşaye ve -s Vaşağıdan yukarı) incelenmiştir. Problem indirgeme yöntemini kullanan problem çözme teknikleri-ki bu kez de AO* kullanıl- nııştır- üzerinde bazı düşünceler, temel sembolik entegral alma problemlerine uygulanmıştır. Simgesel deyimlerin düzen lenmesi ı matematik, mantık ve örneğin teorem kanıtlama ve matematiksel deyimlerin basitleştirilmesi gibi tüm sözsel çıkarımlarda ortaya çıkmaktadır. Bu yüzden, gerçekten zor olan sorunların çözümü için iyi sembolik programlama dilleri, LISP( liste işleme) dili gibi, gerekmektedir. Bu amaçla, North Star genel amaçlı mini bilgisayarında bazı sembolik entegral alma problemleri çözmek için Automatic Symbolic Integrator (ASI) yazılımı geliştirilmiştir. Kullanılan dil güçlü bir LISP derleyicisi bulunamadığı için genel amaçlı bir dil olan PASCAL olmuştur. ASI'nın sembolik integral alması tezin 4. bölümde veril miştir. ASI'nın insanlar tarafından kullanılması Sezgisel yöntemler gibi bazı yöntemleri kullanmaktadır. Anahtar sözcükler s Segzisel Arama, Sorun Çözme, Problem indirgeme, Simgesel entegral. vı

ABSTRACT HEURISTIC SEARCH TECHNIQUES IN PROBLEM REDUCTION METHOD MOHAMED A.ARTEIMI M.S thesis in Computer Engineering supervisor! Assoc. Prof.Dr. Müren Gökeri April, 1988, 207 pages Problem solving search algorithms have found wide use in many areas of computer science and engineering. Applications abound in such diverse areas as game playing, pattern recog nition, decision analysis, robotics and theorem proving. Because of the different requirements of the various problems in which search algorithms are used, different search proced- ures have evolved. For example, Alpha Beta, SSS, and B for minimax search? A and other heuristic search procedures for state space search; A, A, A0,A, and C for problem red uction search; and various Branch- and- Bound and Dynamic prog ramming procedures for combinatorial optimization problems. And many of these procedures are thought to be related to each other. This thesis presents several algorithms used for problem reduction search. Two general classes of techniques ( top- 111down- and bottom-up) are discussed. Some ideas on problem solving techniques utilising problem reduction method namely AO algorithm, are tried on the elementary symbolic integra tion problem. The manipulation of symbolic expressions occurs throughout mathematics, logic and, in fact, all of verbal reasoning, for e.g., proving theorems and simplifying mathematical expres sions. Hence, we must have good symbolic manipulating lan guage, like LISPdist processing) language, to solve really difficult problems. To this end, a software package called `Automatic Symbolic Integrator ( ASD` has been developed using Northstar, general purpose mini computer, to solve some symbolic integration problems. The language used in the implementation is the general purpose language (PASCAL), since there is no powerful LISP compiler available. A full description of how ASI solves symbolic integration problems is found in chapter 4. For now, suffice it to say that ASI employs some of the same methods used by humans, including heuristic methods. Key Words: Heuristic Search, Problem Solving »Problem Reduction, Symbolic integration. IV