Breadth-first-search in AI Mini Project

In this post, you will learn the use of the breadth-first-search algorithm. This algorithm is pretty good to resolve the shortest route problem. You may create a small mini-project on the finding of the shortest route in your area. Here is a guide on how to solve problems with AI.

Project: To find the Shortest Route Between Boston and Newyork.

Consider a road trip between Boston and New York City. There are a variety of ways to make this trip. There are many paths between Boston and New York because it is a heavily populated corridor with many towns and cities between the two locations.

Some common-sense guidelines may be applied, including that any town or city on the path may be visited only once on a trip. It would not make much sense to repeatedly loop through a specific town or city during a trip.

“Artificial intelligence will reach human levels by around 2029. Follow that out further to, say, 2045, and we will have multiplied the intelligence – the human biological machine intelligence of our civilization – a billion-fold.

”Ray Kurzweil, American inventor, and futurist.

The key realistic points to consider in making the trip’s path selections are the costs that are manifested: travel time, path length, fuel costs, tolls, and traffic density, which are actual or anticipated delays. Here is the best Breadth-first search example

These costs are often dependent because a longer path will increase fuel expenses, but not necessarily travel time because an alternate path could use a superhighway, on which the car maintains a higher consistent speed, as compared to traveling through backroads and going through many small towns.

But, a superhighway can be congested, reducing overall speed, and there may even be tolls to add to the misery.

The above approach is called breadth-first approach.

Quick Video Presentation on the breadth-first-search (BFS).

The breadth-first approach starts by considering all possible paths between Boston and New York City, and computing and accumulating the total costs incurred while progressing through the various paths.

References

  1. Breadth-first search
  2. Detailed Explanation of breadth-first-search

Author: Srini

Experienced software developer. Skills in Development, Coding, Testing and Debugging. Good Data analytic skills (Data Warehousing and BI). Also skills in Mainframe.