Skip to main content

Comparative Analysis of Four Heuristic Functions that Optimizes the A* Search Algorithm | Chapter 02 | Advances in Mathematics and Computer Science Vol. 2

In  this  chapter are compared  four  heuristic  functions  with  high  efficiency  for an optimum solving  of  8-puzzle. The analysis is realized among Chebyshev distance, Hamming distance and Manhattan distance using A* search algorithm  implemented in  Java.  The  two  heuristic  functions defined  using  Chebyshev  distance  are  more informed than Hamming and Manhattan heuristics. This chapter also presents necessary stages in object oriented development  of  an  interactive  software dedicated to  simulate  the  A*  search  algorithm  for  8-puzzle.  The modelling  of  software  is achieved through  specific  UML  diagrams representing phases  of analysis,  design and implementation, the system thus being described in a clear and practical manner. In order to confirm that second Chebyshev  heuristic  is  more  efficient  was  used space  complexity  performance  criteria.  The  space  complexity was measured  by number  of generated  nodes from search tree, by  number  of  expanded  nodes  and by effective branching factor. From experimental results obtained by using second Chebyshev heuristic, improvements were observed  regarding  space  complexity  of  A* algorithm  versus  Hamming,  Manhattan  and  first  Chebyshev heuristics. Analysing the results presented in graphics, it can be asserted that number of steps made for obtaining the  solution  is  the  same  for  similar  configurations,  determining  the optimal  solutions  for  all  four  examined heuristics. But, investigating generated nodes number in the search tree associated with the A* algorithm using second Chebyshev  heuristic,  it  can  be  observed  that  this  number is  strictly  less  than number  obtain  by  using other  three  heuristics.  Calculating  approximately  effective branching  factor  for  all  four  heuristics,  there  were obtained values illustrated in figures. The values of b* appropriate to function hC2 are more appropriate to value 1 than values of b* appropriate to functions hM, hH, and hC1, so the A* algorithm using hC2 heuristic drives to an optimal  solution  in  a  way  that  appears  to  be  linear. According  to  these  experimental  values,  results  the superiority  of  second Chebyshev  heuristic  from  Manhattan,  Hamming  and  first  Chebyshev  heuristics.  In this case we can say that hC2 heuristic dominates hM, hH, and hC1 heuristics, from space complexity point of view.

Author(s) Details

Anca-Elena Iordan
Department of Electrical Engineering and Industrial Informatics, Engineering Faculty of Hunedoara, Polytechnic University Timisoara, Romania.

View Volume:


Popular posts from this blog

Consensus Summit: Lipids and Cardiovascular Health in the Nigerian Population | Chapter 09 | Current Trends in Food Science Vol. 1

Aims: To issue a consensus statement on Lipids and Cardiovascular Health and the impact of their interrelationship in Nigerian Population. Study Design: Experts from a range of relevant disciplines, deliberated on different aspects of Lipids and Cardiovascular Health in the Nigerian Population at a Summit. Place and Duration of Study: The Summit was held in April 2016 at the Nigerian Institute of Medical Research. Methodology: Presentations were made on central themes after which expert participants split into four different groups to consider the questions relevant to different sub themes of the title. Consensus was arrived at, from presentations of groups at plenary. Conclusion: With the increase in the prevalence of NCDs, especially Cardiovascular Disease in Nigeria, and the documented evidence of deleterious effects of lipids, the expert panel called for an urgent need to advocate for the general public and health professionals to make heart-friendly

A Review on Gongronema latifolium, an Extremely Useful Plant with Great Prospects | Chapter 11 | Recent Advances in Biological Research Vol. 3

Gongronema latifolium is a plant that has a wide range of nutritional and ethnomedical uses in different tropical African communities. Scientific reports on the chemical composition and bioactivity (anti-inflammatory, antimicrobial, antidiabetic, antioxidant, anticancer and allelopathic properties) of the plant material by different authors are discussed in this review. Future prospects of the plant extracts in the areas of herbal formulations, food preservation, alcoholic fermentation and beer production, drug discovery and allelopathy are also highlighted. Author   Details: Olugbenga Morebise Faculty of Basic Medical Sciences, All Saints University School of Medicine, Roseau, Commonwealth of Dominica. Read full article: View Volume:

An Overview of Ultrasonic Technology and Its Applications in Food Processing, Preservation and Quality Control | Chapter 03 | Current Research in Science and Technology Vol. 3

Ultrasound is one of the emerging technologies that were developed to minimize processing, maximize quality and ensure the safety of food products. In recent years, ultrasound technology has been used as an alternative processing option to conventional thermal approaches. Although Ultrasonication methods have been used for years in research and diagnostics, major advances have been made in the last decade. The applications for which high power ultrasound can be used range from existing processes that are enhanced by the retrofitting of high power ultrasonic technology, to the development of processes up to now not possible with conventional energy sources. The present paper reviews the generation, principle mechanism, properties, process parameters, applications, merits and demerits and future trends of the ultrasound technology in the food processing. Author(s) Details Er. Bogala Madhu Department of Processing and Food Engineering, College of Technology and Engineering, MP