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.

Read full article: http://bp.bookpi.org/index.php/bpi/catalog/view/69/823/628-1
View Volume: https://doi.org/10.9734/bpi/amacs/v2
Labels:

Comments

Post a Comment

Popular posts from this blog

Risk Factors for Postpartum Psychiatric Disorders. A Review of the Literature | Chapter 8 | New Visions in Medicine and Medical Science Vol. 4

  Objective: The aim of this study was to explore the risk factors for the development of postpartum psychiatric disorders through international literature. Materials and Methods: Throughout many articles in PubMed, Google scholar and PsycInfo, a great amount of recent data was gathered to identify the disorders that are most common as well as their risk factors. Results: After childbirth, most commonly women experience postpartum depression, anxiety disorders, post-traumatic stress disorder and postpartum psychosis. All the disorders have many similar risk-factors with the main one being preexisting psychiatric disorder and many similar symptoms too. Conclusions: Women after childbirth are at risk of experience many psychiatric disorders, such as postpartum distress, postpartum post traumatic stress disorder and even more rarely postpartum psychosis. It is important to provide comprehensive support to ensure the well-being of both the mother and the infant and this will b...
Post a Comment
Read more

Greening Regional Airports: A Vision for Carbon Neutral Infrastructure | Chapter 12 | Contemporary Perspective on Science, Technology and Research Vol. 3

 This study provides an overview of the energy demand of a regional airport, divided into individual time horizons. The electrification of aircraft systems raises the question of whether airports will be among the largest electricity consumers in our infrastructure in the future. Sustainability and especially emission reductions are significant challenges for airports that are currently being addressed. The Clean Sky 2 project GENESIS addresses the environmental sustainability of hybrid-electric 50-passenger aircraft systems in a life cycle perspective to support the development of a technology roadmap for the transition to sustainable and competitive electric aircraft systems. This article originates from the GENESIS research and describes various options for ground power supply at a regional airport. Potential solutions for airport infrastructure with a short (2030), medium (2040), and long (2050) time horizon are proposed. In addition to the environmental and conservation benefi...
Post a Comment
Read more

Alkali Element Modification of Glucose Molecules as a Method to Dissolve Cancer Cells | Chapter 12 | New Visions in Medicine and Medical Science Vol. 4

  The present study highlights about alkali element modification of glucose molecules as a method to dissolve cancer cells. The central regulation of the mechanisms governing cell proliferation has little effect on cancer cells. Cancer cells are entirely independent of the central command and divide and proliferate on their own, making it challenging to activate their response mechanism. Precisely, this is the reason why they are at risk to the health of humans and/or any biological entities. Instead of trying to reconnect the central command of the growth control mechanism to cancer cells that are already out of the range, we present a method of using the cancer cell’s own irresponsive and uncontrolled growth mechanism to their disadvantage and destroy the cancer cells. We found that this is achievable in an atomic/molecular level study of the glucose molecule, which is the primary food source used for growth and energy generation by all cells in the body, including the cancer cel...
Post a Comment
Read more