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

A Prospective Study about Safety and Efficacy of Perioperative Lidocaine Infusion | Chapter 09 | New Horizons in Medicine and Medical Research Vol. 8

 Opioids cause clinically significant side effects such as respiratory depression, immunosuppression, muscle rigidity, negative inotropism, nausea, vomiting, hyperalgesia, urine retention, postoperative ileus, and drowsiness. Perioperative opioids are a major contributor to the United States' and other countries' opioid epidemics. Non-opioid analgesics, particularly lidocaine, are becoming more common for perioperative use as a result of this. A total of 185 adult patients were randomly assigned to one of two groups: control group I (105 patients) [fentanyl group] or group ii (80 patients) [opioid-free anaesthesia group]. Lidocaine 1.5 mg/kg bolus followed by 1.5 mg/kg/h infusion intraoperatively, and 1.5-2 mg/kg/h infusion for 2-8 hours postoperatively were given to patients in both groups at anaesthetic induction. Intraoperatively, both groups received analgesic adjuvants such as diclofenac 75 mg, paracetamol 1 gm, and mgso4 30-50 mg/kg. If the mean arterial pressure (map)
Post a Comment
Read more

A Brief Study of Middleware Technologies: Programming Applications and Management Systems | Chapter 15 | Novel Research Aspects in Mathematical and Computer Science Vol. 1

  Many platforms, services, applications, hardware, and operating systems are connected through the middleware layer. Because the middleware layer abstracts much low-level complexity and makes applications and software systems portable, it allows disparate systems to interface and function together in harmony. Middleware technologies enable software engineers to swiftly construct software systems and applications, allowing developers to focus on more important tasks. This chapter examines several types of middleware systems and discusses middleware capabilities, middleware operation, middleware's function in cloud-based systems, and the best middleware platforms to use. Middleware systems are widely utilised and can be found in practically any software system or application. Middleware programmes provide as a link between many sorts of systems and protocols. They serve as a mechanism for various systems. To successfully exchange information, it runs on a variety of operating system
Post a Comment
Read more

Patients’ Perspective of Acute Post-operative Pain Management: A Multicentre Survey of Tertiary Hospitals in Maharashtra, India | Chapter 08 | New Horizons in Medicine and Medical Research Vol. 8

 When postoperative pain is adequately controlled, patients' satisfaction and patient-related outcomes (PROs) increase. Understanding the patients' perspective is crucial since it supports in the formulation of improvement strategies. Because wrong attitudes and assumptions might block pain alleviation, patients' attitudes and beliefs are critical. As a result, a multicenter study of patients' attitudes, beliefs, experiences, and satisfaction levels with acute postoperative pain management was done in Maharashtra's tertiary hospitals. In addition, the responses were examined to evaluate if the Acute Pain Service (APS) resulted in improved patient outcomes and satisfaction. A 13-item questionnaire adapted from previous studies was used to capture patients' experiences with postoperative pain treatment. The responses of 179 patients are included in the study. The findings revealed that 91.6 percent of patients experienced postoperative pain, with 75.5 percent
Post a Comment
Read more