Search Engines
|
E-Mail
|
Online Shopping
|
Rental Sites
|
Downloads
|
Coding Tutorials
|
Various
|
Funny Stuff
|
Job Services
|
|
Back Home
Back to the Programming Page
Artificial Intelligence Project
The Problem
Using 4 different search algorithms, find the shortest path from Arad to Bucharest (cities in Romania).
As you can see from Figure 1, there are multiple routes one could take
Figure 1: A map of Romania
The Data Structures
Each city is represented by a node which is detailed in Figure 2
A Linked List is used to join all the nodes together
Each node contains information vital to the search algorithm
|
|
struct node
{
// total cost acrued up to this point
int totCost;
// the depth of the search up to this point
int depth;
// the neighbor city with the shortest distance
int lowerNeighbor;
// previous node (travelled from node)
node* back;
// cities bordering the node and their respective distance
node* border1;
int border1dist;
node* border2;
int border2dist;
node* border3;
int border3dist;
node* border4;
int border4dist;
// determines whether or not the city has already been visited
bool visited;
// the name of the city (current node)
char city;
};
|
|
Figure 2: Details of the nodes
The Search Algorithms (with screenshots)
Breadth-First Search
Selects the shallowest unexpanded node in the search tree for expansion
Figure 3: Running the breadth-first search
Depth-First Search
Selects the deepest unexpanded node in the search tree for expansion
Figure 4: Running the depth-first search
Iterative Deepening Search
Calls a depth-first search with a fixed limit on the depth
The limit keeps increasing until a goal is found
Figure 5: Running the iterative-deepening search
Uniform-Cost Search
Similar to the breadth-first search but expands the node with the lowest path cost.
Figure 6: Running the uniform-cost search
|
|
