Scribd
Upload
15 views20 pages

Problem Solving and Searching Algorithm

The document outlines the basic concepts and challenges of Hill Climbing algorithms, detailing the steps involved in the process and issues such as local maximum, plateau, and ridge problems. It also describes the A* Search Algorithm, emphasizing its efficiency in pathfinding and the steps it follows, including initialization, evaluation, expansion, update, goal check, and reconstruction. Overall, it highlights the strengths and limitations of these algorithms in optimization tasks.

Uploaded by

Ch Ahtasham
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
15 views20 pages

Problem Solving and Searching Algorithm

The document outlines the basic concepts and challenges of Hill Climbing algorithms, detailing the steps involved in the process and issues such as local maximum, plateau, and ridge problems. It also describes the A* Search Algorithm, emphasizing its efficiency in pathfinding and the steps it follows, including initialization, evaluation, expansion, update, goal check, and reconstruction. Overall, it highlights the strengths and limitations of these algorithms in optimization tasks.

Uploaded by

Ch Ahtasham
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 20

Basic Concepts of Hill Climbing Algorithms

Hill climbing follows these steps:


1.Initial State: Start with an arbitrary or random solution (initial state).

2.Neighboring States: Identify neighboring states of the current


solution by making small adjustments (mutations or tweaks).

3.Move to Neighbor: If one of the neighboring states offers a better


solution (according to some evaluation function), move to this new state.

4.Termination: Repeat this process until no neighboring state is better


than the current one. At this point, you’ve reached a local maximum or
minimum (depending on whether you’re maximizing or minimizing).
Challenges in Hill Climbing Algorithm

1. Local Maximum Problem

A local maximum occurs when all neighboring states have worse


values than the current state. Since Hill Climbing uses a greedy
approach, it will not move to a worse state, causing the algorithm to
terminate even though a better solution may exist further along.

2. Plateau Problem

A plateau is a flat region in the search space where all neighboring


states have the same value. This makes it difficult for the algorithm
to choose the best direction to move forward.

3. Ridge Problem

A ridge is a region where movement in all possible directions seems


to lead downward, resembling a peak. As a result, the Hill Climbing
algorithm may stop prematurely, believing it has reached the optimal
solution when, in fact, better solutions exist.
A* Search Algorithm
The A* Search Algorithm is an optimal and efficient
method for solving pathfinding problems. When
seeking the shortest path between a starting
point and a goal, A* is often the best choice due to
its versatility and robustness.
How does the A* Algorithm work?
A step-by-step implementation of this algorithm is given below:
1.Initialization: The algorithm starts by placing the starting node in
a priority queue. This priority queue, also known as an open list,
contains all the nodes that have yet to be evaluated.

2.Evaluation: This is the selection process in which the node with


the lowest f(n) value from the queue is chosen for further operations.

3.Expansion: The chosen node is evaluated by comparing it with its


neighbours. For each neighbour, g(n) and h(n) values are calculated.

4.Update: If a neighbour has a lower f(n) value than the recorded


one, it is updated to the open list.

5.Goal Check: The algorithm continues until the goal node is


reached or the open list is empty, indicating no more path to
traverse.

6.Reconstruction: After finding the goal node, the algorithm

You might also like