EvaluateNormalVsBidirectionalBFS.m
///////////////////
upperBound = 10;
lowerBound = 3;
numberOfExperiments = 5;
x=1:upperBound;
y1=zeros(1,upperBound);
y2=zeros(1,upperBound);
for i=lowerBound:upperBound
for j=1:i*numberOfExperiments
problem = Problem(i, i);
[cost , numberOfExpandedNodes] = SolveMaze(problem, false, BFSFringe);
y1(i) = y1(i) + numberOfExpandedNodes;
[cost , numberOfExpandedNodes] = SolveMazeBidirectional(problem, false, BFSFringe, BFSFringe);
y2(i) = y2(i) + numberOfExpandedNodes;
end
y1(i) = y1(i)/(i*numberOfExperiments);
y2(i) = y2(i)/(i*numberOfExperiments);
end
figure(‘name’,’Normal vs Bidirectional BFS’);
hold on
axis([lowerBound upperBound 0 max(max(y1),max(y2))]);
plot(x,y1,’r’);
plot(x,y2,’b’);
clear;
EvaluateDFS.m
upperBound = 10;
lowerBound = 3;
numberOfExperiments = 10;
x=1:upperBound;
y=zeros(1,upperBound);
for i=lowerBound:upperBound
for j=1:i*numberOfExperiments
problem = Problem(i, i);
[cost , numberOfExpandedNodes] = SolveMaz(problem, false, DFSFringe, SLHeuristic);
y(i) = y(i) + numberOfExpandedNodes;
end
y(i) = y(i)/(i*numberOfExperiments;
end
figure(‘name’,’DFS Evaluation’)
hold on
axis([lowerBound upperBound 0 max(y)]);
plot(x,y,’r’);
clear;
EvaluateBestFirst.m
upperBound = 10;
lowerBound = 3;
numberOfExperiments = 10;
x=1:upperBound;
y=zeros(1,upperBound
for i=lowerBound:upperBound
for j=1:i*numberOfExperiments
problem = Problem(i, i);
[cost , numberOfExpandedNodes] = SolveMaze(problem, false, BestFirstFringe, SLHeuristic);
y(i) = y(i) + numberOfExpandedNodes;
end
y(i) = y(i)/(i*numberOfExperiments);
end
figure(‘name’,’Best First Evaluation’);
hold on
axis([lowerBound upperBound 0 max(y)]);
plot(x,y,’g’);
clear;
EvaluateAStar.m
upperBound = 10;
lowerBound = 3;
numberOfExperiments = 10;
x=1:upperBound;
y=zeros(1,upperBound);
for i=lowerBound:upperBound
for j=1:i*numberOfExperiments
problem = Problem(i, i);
[cost , numberOfExpandedNodes] = SolveMaze(problem, false, AStarFringe, SLHeuristic);
y(i) = y(i) + numberOfExpandedNodes;
end
y(i) = y(i)/(i*numberOfExperiments);
end
figure(‘name’,’A* Evaluation’);
hold on
axis([lowerBound upperBound 0 max(y)]);
plot(x,y,’b’);
clear;
ExampleNormalVsBidirectional.m
function ExampleNormalVsBidirectional(numberOfRows, numberOfColumns)
problem = Problem(numberOfRows, numberOfColumns);
close all;
[cost , numberOfExpandedNodes] = SolveMaze(problem, true, BFSFringe);
disp(‘Solution cost with normal BFS:’);
disp(cost);
disp(‘Number of expanded nodes with normal BFS’);
disp(numberOfExpandedNodes);
[cost , numberOfExpandedNodes] = SolveMazeBidirectional(problem, true, BFSFringe,BFSFringe);
disp(‘Solution cost with bidirectional BFS:’);
disp(cost);
disp(‘Number of expanded nodes with bidirectional BFS:’);
disp(numberOfExpandedNodes);
end
ExampleDFS.m
function ExampleDFS(numberOfRows, numberOfColumns)
disp(‘Depth First Search’);
problem = Problem(numberOfRows, numberOfColumns);
close all;
[cost , numberOfExpandedNodes] = SolveMaze(problem, true, DFSFringe);
disp(‘Solution cost:’);
disp(cost);
disp(‘Number of expanded nodes:’);
disp(numberOfExpandedNodes);
end
ExampleBFS.m
function ExampleBFS(numberOfRows, numberOfColumns)
disp(‘Breadth First Search’);
problem = Problem(numberOfRows, numberOfColumns);
close all;
[cost , numberOfExpandedNodes] = SolveMaze(problem, true, BFSFringe);
disp(‘Solution cost:’);
disp(cost);
disp(‘Number of expanded nodes:’);
disp(numberOfExpandedNodes);
end
ExampleBestFirst.m
function ExampleBestFirst(numberOfRows, numberOfColumns)
disp(‘Best First Search, Straight Line Distance Heuristic’);
problem = Problem(numberOfRows, numberOfColumns);
close all;
[cost , numberOfExpandedNodes] = SolveMaze(problem, true, BestFirstFringe, SLHeuristic);
disp(‘Solution cost:’);
disp(cost);
disp(‘Number of expanded nodes:’);
disp(numberOfExpandedNodes);
end
ExampleAStar.m
function ExampleAStar(numberOfRows, numberOfColumns)
disp(‘A* Search, Straight Line Distance Heuristic’);
problem = Problem(numberOfRows, numberOfColumns);
close all;
[cost , numberOfExpandedNodes] = SolveMaze(problem, true, AStarFringe, SLHeuristic);
disp(‘Solution cost:’);
disp(cost);
disp(‘Number of expanded nodes:’);
disp(numberOfExpandedNodes);
end
for i=1:numberOfColumns
x=zeros(0);
y=zeros(0);
for j=1:numberOfRows
if(arrayVersion(j,i) == 1)
x = [x i];
y = [y j];
else
plot(x,y,’-ks’,’LineWidth’,3,…
‘MarkerEdgeColor’,’k’,…
‘MarkerFaceColor’,’g’,…
‘MarkerSize’,5)
x=zeros(0);
y=zeros(0);
end
end
plot(x,y,’-ks’,’LineWidth’,3,…
‘MarkerEdgeColor’,’k’,…
‘MarkerFaceColor’,’g’,…
‘MarkerSize’,5)
end
if isempty(solution) == false
[x, y] = ConvertToArray(solution);
plot(x,y,’:r’, ‘LineWidth’,2);
else
text(numberOfColumns/2,0,’FAILURE’);
end
text(problem.InitialState.Column, problem.InitialState.Row, ‘S’);
text(problem.GoalState.Column, problem.GoalState.Row, ‘G’);
hold off
end
function [x, y] = ConvertToArray(path)
x=zeros(0);
y=zeros(0);
for node = path
x = [x node.State.Column];
y = [y node.State.Row];
end
end
DrawMaze.m
function DrawMaze(problem, solution)
arrayVersion = problem.ArrayVersion;
[numberOfRows, numberOfColumns] = size(problem.States);
figure;
hold on;
axis ij
axis([0.5 numberOfColumns+0.5 0.5 numberOfRows+0.5]);
for i=1:numberOfRows
x=zeros(0);
y=zeros(0);
for j=1:numberOfColumns
if(arrayVersion(i,j) == 1)
x = [x j];
y = [y i];
else
plot(x,y,’-ks’,’LineWidth’,3,…
‘MarkerEdgeColor’,’k’,…
‘MarkerFaceColor’,’g’,…
‘MarkerSize’,5)
x=zeros(0);
y=zeros(0);
end
end
plot(x,y,’-ks’,’LineWidth’,3,…
‘MarkerEdgeColor’,’k’,…
‘MarkerFaceColor’,’g’,…
‘MarkerSize’,5)
end
SolveMazeBidirectional.m
function [cost , numberOfExpandedNodes] = SolveMazeBidirectional(problem, drawMaze, fringe1, fringe2, heuristic1, heuristic2)
if isa(fringe1,’HeuristicFringe’)
fringe1.Set(problem,heuristic1);
end
if isa(fringe2,’HeuristicFringe’)
if nargin == 5
fringe2.Set(problem,heuristic1);
else
fringe2.Set(problem,heuristic2);
end
end
[solution, cost] = BidirectionalSearch(problem, fringe1, fringe2);
numberOfExpandedNodes = fringe1.NumberOfExpandedNodes + fringe2.NumberOfExpandedNodes;
if drawMaze
DrawMaze (problem, solution);
end
end
SolveMaze.m
function [cost , numberOfExpandedNodes] = SolveMaze(problem, drawMaze, fringe, heuristic)
if isa(fringe,’HeuristicFringe’)
fringe.Set(problem,heuristic);
end
[solution, cost] = GraphSearch(problem,fringe);
numberOfExpandedNodes = fringe.NumberOfExpandedNodes;
if drawMaze
DrawMaze(problem, solution);
end
end
Problem.m
classdef Problem < handle
properties
InitialState
GoalState
States = State.empty;
ArrayVersion
end
methods
function problem = Problem(numberOfRows, numberOfColumns)
problem.States(1:numberOfRows, 1: numberOfColumns) = State;
for i = 1:numberOfRows
for j = 1:numberOfColumns
if rand < 0.4
blocked = true;
else
blocked = false;
end
problem.States(i,j) = State(i,j,blocked);
problem.ArrayVersion(i,j) = blocked;
end
end
index = round(rand*(i*j-1))+1;
problem.InitialState = problem.States(index);
problem.InitialState.Blocked = false;
problem.ArrayVersion(index) = 0;
index = round(rand*(i*j-1))+1;
problem.GoalState = problem.States(index);
problem.GoalState.Blocked = false;
problem.ArrayVersion(index) = 0;
end
function result = GoalTest(problem, state)
if state == problem.GoalState
result = true;
else
result = false;
end
end
function [actions, results] = SuccessorFunction(problem, state)
[numberOfRows, numberOfColumns] = size(problem.States);
row = state.Row;
column = state.Column;
actions = double.empty;
results = State.empty;
index = 0;
if(column>1 && problem.States(row,column-1).Blocked == false)
index = index + 1;
actions(index) = 4; % left (according to keyboard’s numeric keypad!)
results(index) = problem.States(row,column-1);
end
if(column<numberOfColumns && problem.States(row,column+1).Blocked == false)
index = index + 1;
actions(index) = 6; % right
results(index) = problem.States(row,column+1);
end
if(row>1 && problem.States(row-1,column).Blocked == false)
index = index + 1;
actions(index) = 8; % up
results(index) = problem.States(row-1,column);
end
if(row<numberOfRows && problem.States(row+1,column).Blocked == false)
index = index + 1;
actions(index) = 2; % down
results(index) = problem.States(row+1,column);
end
if(column>1 && row>1 && problem.States(row-1,column-1).Blocked == false)
index = index + 1;
actions(index) = 7; % upper left
results(index) = problem.States(row-1,column-1);
end
if(column<numberOfColumns && row>1 && problem.States(row-1,column+1).Blocked == false)
index = index + 1;
actions(index) = 9; % upperRight
results(index) = problem.States(row-1,column+1);
end
if(column>1 && row<numberOfRows && problem.States(row+1,column-1).Blocked == false)
index = index + 1;
actions(index) = 1; % bottomLeft
results(index) = problem.States(row+1,column-1);
end
if(column<numberOfColumns && row<numberOfRows && problem.States(row+1,column+1).Blocked == false)
index = index + 1;
actions(index) = 3; % bottomRight
results(index) = problem.States(row+1,column+1);
end
end
end
end
BidirectionalSearch.m
function [solution, cost] = BidirectionalSearch(problem, fringe1, fringe2)
closed = State.empty;
fringe1.Insert(MakeNode(problem.InitialState));
fringe2.Insert(MakeNode(problem.GoalState));
while(true)
if fringe1.IsEmpty || fringe2.IsEmpty
solution = Node.empty; % Failure
cost = 0;
break;
end
[intersectingNodeFromFring1, intersectingNodeFromFring2] = FindIntersection(fringe1,fringe2);
if isempty(intersectingNodeFromFring1) == false
[solution, cost] = Solution(intersectingNodeFromFring1, intersectingNodeFromFring2);
break;
end
node1 = fringe1.RemoveFront();
node2 = fringe2.RemoveFront();
if Contains(closed, node1.State) == false
closed = [node1.State closed];
fringe1.InsertAll(Expand(node1, problem));
end
if Contains(closed, node2.State) == false
closed = [node2.State closed];
fringe2.InsertAll(Expand(node2, problem));
end
end
end
function [intersectingNodeFromFring1, intersectingNodeFromFring2] = FindIntersection(fringe1,fringe2)
intersectingNodeFromFring1 = Node.empty;
intersectingNodeFromFring2 = Node.empty;
for node1 = fringe1.Nodes
for node2 = fringe2.Nodes
if node1 == node2
intersectingNodeFromFring1 = node1;
intersectingNodeFromFring2 = node2;
break;
end
end
end
end
function [solution, cost] = Solution(node1,node2)
solution = node1;
currentNode = node1;
rootReached = false;
while(rootReached == false)
currentNode = currentNode.ParentNode;
solution = [currentNode solution];
if isempty(currentNode) || isempty(currentNode.ParentNode)
rootReached = true;
end
end
currentNode = node2;
rootReached = false;
while(rootReached == false)
currentNode = currentNode.ParentNode;
solution = [solution currentNode];
if isempty(currentNode) || isempty(currentNode.ParentNode)
rootReached = true;
end
end
cost = node1.PathCost + node2.PathCost;
end
5.16. Problem.m
classdef Problem < handle
properties
InitialState
GoalState
States = State.empty;
ArrayVersion
end
methods
function problem = Problem(numberOfRows, numberOfColumns)
problem.States(1:numberOfRows, 1: numberOfColumns) = State;
for i = 1:numberOfRows
for j = 1:numberOfColumns
if rand < 0.4
blocked = true;
else
blocked = false;
end
problem.States(i,j) = State(i,j,blocked);
problem.ArrayVersion(i,j) = blocked;
end
end
index = round(rand*(i*j-1))+1;
problem.InitialState = problem.States(index);
problem.InitialState.Blocked = false;
problem.ArrayVersion(index) = 0;
index = round(rand*(i*j-1))+1;
problem.GoalState = problem.States(index);
problem.GoalState.Blocked = false;
problem.ArrayVersion(index) = 0;
end
function result = GoalTest(problem, state)
if state == problem.GoalState
result = true;
else
result = false;
end
end
function [actions, results] = SuccessorFunction(problem, state)
[numberOfRows, numberOfColumns] = size(problem.States);
row = state.Row;
column = state.Column;
actions = double.empty;
results = State.empty;
index = 0;
if(column>1 && problem.States(row,column-1).Blocked == false)
index = index + 1;
actions(index) = 4; % left (according to keyboard’s numeric keypad!)
results(index) = problem.States(row,column-1);
end
if(column<numberOfColumns && problem.States(row,column+1).Blocked == false)
index = index + 1;
actions(index) = 6; % right
results(index) = problem.States(row,column+1);
end
if(row>1 && problem.States(row-1,column).Blocked == false)
index = index + 1;
actions(index) = 8; % up
results(index) = problem.States(row-1,column);
end
if(row<numberOfRows && problem.States(row+1,column).Blocked == false)
index = index + 1;
actions(index) = 2; % down
results(index) = problem.States(row+1,column);
end
if(column>1 && row>1 && problem.States(row-1,column-1).Blocked == false)
index = index + 1;
actions(index) = 7; % upper left
results(index) = problem.States(row-1,column-1);
end
if(column<numberOfColumns && row>1 && problem.States(row-1,column+1).Blocked == false)
index = index + 1;
actions(index) = 9; % upperRight
results(index) = problem.States(row-1,column+1);
end
if(column>1 && row<numberOfRows && problem.States(row+1,column-1).Blocked == false)
index = index + 1;
actions(index) = 1; % bottomLeft
results(index) = problem.States(row+1,column-1);
end
if(column<numberOfColumns && row<numberOfRows && problem.States(row+1,column+1).Blocked == false)
index = index + 1;
actions(index) = 3; % bottomRight
results(index) = problem.States(row+1,column+1);
end
end
end
end