Branch and bound and A search using fuzzy underestimates
Other Title(s)
استعمال أقل تقديرضبابي في تقنيتي البحث، التفرع و الحد و (A *)
Dissertant
al-Rababiah, Bilal Muhammad Badr al-Din Ahmad
Thesis advisor
Comitee Members
Kaabneh, Khalid
al-Utaybi, Ghassan
Dutta, Ashit Kumar
University
Amman Arab University
Faculty
Collage of Computer Sciences and Informatics
Department
Department of Computer Science
University Country
Jordan
Degree
Ph.D.
Degree Date
2007
English Abstract
Search in Artificial Intelligence is a problem-solving technique that systematically explores a space of problem states.
Branch and Bound (B&B) and A* searching techniques are effective heuristic principle guided Artificial Intelligence Problem-Solving Techniques.
Fuzzy Logic is related to Expert Systems, as an effective Expert systems tool which can deal with imprecise and uncertain data and permit inexact reasoning.
A search problem and its solution by the existing crisp methods of “Branch and Bound” and A* search have been considered in this work.
We have observed that these methods can be improved by using fuzzy theory.
In this dissertation, new methods of B&B and A* searching techniques with fuzzy underestimation to the available Fuzzy information have been proposed by applying the Triangular Fuzzy Number Model in order to add Fuzzy Underestimation to the existing algorithms.
A new improved version of searching techniques under uncertainty has been suggested.
The corresponding algorithms have been given, and each of the two algorithms have been explained in details using two applications.
A simulation program has been introduced to evaluate the performance of the proposed algorithms.
Six Searching techniques were analyzed and compared by computing Number of Iterations, Time Complexity, Space Complexity, and Effective Branching Factor for each algorithm.
The proposed algorithms have been implemented and tested; The analysis and simulation results showed that Fuzzy Underestimated A* and Fuzzy Underestimated “Branch and Bound” search techniques have achieved better efficiency, time complexity, and effective branching factor than all other compared searching techniques.
Fuzzy underestimation increases the efficiency of A* and B&B Augmented by Crisp Underestimation, enabling it to be more informed.
Space complexity for Fuzzy A* and Fuzzy Underestimated B&B is always less than that for crisp algorithms.
The analysis also proved that Time complexity for Fuzzy A* is better than that for Fuzzy Underestimated B&B, but with more Space complexity.
This is because Fuzzy A* has more memory requirements compared to Fuzzy B&B due to A* maintaining all the generated nodes in memory.
Main Subjects
Topics
No. of Pages
225
Table of Contents
Table of contents.
Abstract.
Abstract in Arabic.
Chapter One : Introduction.
Chapter Two : Preliminaries.
Chapter Three : Branch and bound search using fuzzy underestimates.
Chapter Four : A searching technique using fuzzy underestimates.
Chapter Five : Performance evaluation and simulation.
Chapter Six : Conclusions and future work.
References.
American Psychological Association (APA)
al-Rababiah, Bilal Muhammad Badr al-Din Ahmad. (2007). Branch and bound and A search using fuzzy underestimates. (Doctoral dissertations Theses and Dissertations Master). Amman Arab University, Jordan
https://search.emarefa.net/detail/BIM-528249
Modern Language Association (MLA)
al-Rababiah, Bilal Muhammad Badr al-Din Ahmad. Branch and bound and A search using fuzzy underestimates. (Doctoral dissertations Theses and Dissertations Master). Amman Arab University. (2007).
https://search.emarefa.net/detail/BIM-528249
American Medical Association (AMA)
al-Rababiah, Bilal Muhammad Badr al-Din Ahmad. (2007). Branch and bound and A search using fuzzy underestimates. (Doctoral dissertations Theses and Dissertations Master). Amman Arab University, Jordan
https://search.emarefa.net/detail/BIM-528249
Language
English
Data Type
Arab Theses
Record ID
BIM-528249
