EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login

Informed Search

By Priya PedamkarPriya Pedamkar

Home » Data Science » Data Science Tutorials » Artificial Intelligence Tutorial » Informed Search

Informed Search

Introduction to Informed Search

Informed Search refers to search algorithms which help in navigating large databases with certain available information about the end goal in search and most widely used in large databases where uninformed search algorithms can’t accurately curate precise results.

For example, when searching on google maps you give the search algorithm information like a place you plan to visit from your current location for it to accurately navigate the distance, the time taken and real-time traffic updates on that particular route. This is all driven by complex Informed search algorithms powering google maps search functionality.

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

Types of Informed Search Algorithms

Before getting started with different types of Informed search Algorithms, it’s important to understand some basic concepts like Search Space which refers to space or the database in which the search is to be performed, the Initial State or Start State from where the search begins and the goal state which is the result of the search like our destination in the earlier example of google maps and goal test to check whether the current state is the destination or goal state. Path cost is a numerical term assigned to measure the numeric cost of the path taken to achieve the goal. Heuristic function, which is a function used to measure how close our current state is to the goal state and uses heuristic properties to find out the best possible path with respect to path cost to achieve the goal state.

In informed search algorithms as discussed, we have information on the goal state which narrows down our results precisely. There may be many possible ways to get to the goal state, but we need to get the best possible outcome or path for our search; this is where informed search shines.

Types of Informed Search Algorithms

1. Pure Heuristic search

A pure heuristic search algorithm is a simple search performed on the basis of heuristic value denoted y h(n) to a node. In a heuristic search, there are two lost created, open for new but unexpanded nodes and closed for expanded nodes, where for every iteration the node with smallest heuristic value is expanded, and all its ‘child’ nodes are expanded and added to close it. A Heuristic function is then applied to that closed list, and the node with the shortest path is saved, and rest are dispersed.

2. Best First or ‘Greedy’ Search

In order to understand the Greedy search, we need to briefly understand the concept of DFS and FS. They’re both vertex-based techniques to find the shortest path. While DFS uses a stack data structure, BFS uses a queue data structure to find out the shortest route.

Popular Course in this category
All in One Data Science Bundle (360+ Courses, 50+ projects)360+ Online Courses | 1500+ Hours | Verifiable Certificates | Lifetime Access
4.7 (3,220 ratings)
Course Price

View Course

Related Courses
Artificial Intelligence Training (3 Courses, 2 Project)Machine Learning Training (17 Courses, 27+ Projects)

Greedy search at its core uses the best path from the current state using a combination of both DFS and FS techniques to find the shortest path. The node that is closest to the goal is expanded in that current state and the closest cost to that point. It’s called the greedy search because it may not find the best solution at a given point of time, but it surely does give you an optimal one within a reasonable amount of time. It can be best explained by the example of the Travelling Salesman problem. A salesman is given a list of places to visit in a city and has to find his optimum route to travel in order to be productive to reduce his travelling time as much as possible. Here he’ll be given a choice of choosing between 2 or more places from his current position to go to, and he’ll choose the one with least distance thereby reducing his travel time albeit not being his best destination but that is a roader optimal solution.

3. A* Tree Search

Simply put, A* search combines elements and strengths from a greedy search and a Uniform cost search. The heuristic of A*search is the summation of Heuristic cost in greedy search and that in uniform cost search denoted here,

F(x)= h(x)+g(x)

Where,

  • h(x): Forward cost referring cost of a node from the current state to the goal state.
  • g(x): Backward cost which is the cost of a node from the root state or initial state.

Here, as represented, the idea is to select a node with the shortest f(x).

One of the biggest advantages of A* search algorithm is that it’s a complete search algorithm as when compared to a simple heuristic approach which only gives the shortest paths, it also takes into account the optimality of the operation overall and therefore is the most widely used search algorithm and can solve complex functions with complex search space. However, as discussed, it keeps into its memory all of the expansion and generation of nodes, is resource constraint and can’t be used for very large scale operations.

4. A*Graph Search

In Tree search, the branches or nodes are expanded again to newer iterations and thus wasting time in the process whereas in graph search same nodes which are expanded before aren’t expanded. Here the heuristic is represented by consistency, where the graph search is optimal when the forward cost as represented in A*tree search is equal to or less than backward cost between the two nodes.

One of the advantages of graph search over A* search is that it doesn’t store all the nodes and therefore isn’t resource-constrained and can be used for very large-scale operations.

Conclusion

‘Search’ is a very important aspect of getting the desired result out of a very large, complex and ever-growing database of any organization or institution around the world. It is imperative to have a working knowledge of different types of search, be it uninformed and especially informed search in the study of Data Science in general and Database Management Systems in particular. With the advent of AI and ML, there are astounding opportunities to develop and create new ways to search databases and provide users with answers that help them solve their problems.

Recommended Articles

This is a guide to Informed Search. Here we discuss the introduction and various types of informed search algorithms in depth. You can also go through our other suggested articles to learn more –

  1. Linear Search in Data Structure
  2. Searching in Data Structure
  3. Data Modelling Tools
  4. Search Algorithms in AI

All in One Data Science Bundle (360+ Courses, 50+ projects)

360+ Online Courses

1500+ Hours

Verifiable Certificates

Lifetime Access

Learn More

0 Shares
Share
Tweet
Share
Primary Sidebar
Artificial Intelligence Tutorial
  • Basics
    • Introduction to Artificial Intelligence
    • What is Artificial Intelligence
    • Careers in Artificial Intelligence
    • Future of Artificial Intelligence
    • Uses of Artificial Intelligence
    • Artificial Intelligence Ethics
    • Types of Artificial Intelligence
    • Artificial Intelligence Tools & Applications
    • Artificial Intelligence Applications
    • Advantages of Artificial Intelligence
    • Artificial Intelligence Tools
    • Benefits of Artificial Intelligence
    • Artificial Intelligence Companies
    • Artificial Intelligence Techniques
    • Artificial Intelligence Software
    • How Artificial Intelligence Works
    • Importance of Artificial Intelligence
    • Subsets of Artificial Intelligence
    • Artificial Intelligence Problems
    • Artificial Intelligence Technology
    • Application of Neural Network
    • Applications of NLP
    • Global Positioning Systems
    • Production System in AI
    • Agents in Artificial Intelligence
    • Intelligent Agent in AI
    • Artificial Intelligence Algorithm
    • Search Algorithms in AI
    • Informed Search
    • Bidirectional Search
    • Adversarial Search
    • Uninformed Search
    • Uniform Cost Search
    • Hill Climbing in Artificial Intelligence
    • Propositional Logic in AI
    • Minimax Algorithm
    • Applications of Fuzzy Logic
    • Fuzzy Logic System
    • Implementation of Neural Networks
    • Turing Test in AI
    • Recurrent Neural Networks (RNN)
    • Spiking Neural Network
    • Feedforward Neural Networks
    • Probabilistic Neural Network
    • Overfitting Neural Network
    • Means-Ends Analysis
    • DNN Neural Network
    • Principal Component Analysis
    • Artificial Intelligence Interview
  • Pattern Recognition
    • Pattern Recognition
    • Pattern Recognition Algorithms
    • Forensic Tools
    • PRTools
    • Pattern Recognition Applications

Related Courses

Artificial Intelligence Training Courses

All One Data Science Training Courses

Machine Learning Course

Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

© 2020 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA Login

Forgot Password?

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you
Book Your One Instructor : One Learner Free Class

Let’s Get Started

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

Special Offer - All in One Data Science Bundle (360+ Courses, 50+ projects) Learn More