<div class="notebook">

<div class="nb-cell markdown" name="md1">
# Tutorial III: Tree Search

Explain Breadth first Search algorithm?

- Expands unexpanded nodes from a firnge.
- Nodes: from a tree
- Trees may be infinite.


How do we expand the finge in BFS?

- Take children of current node and add them to the nend of the fringe?
-First-in-first-out.

## Implementation

### Trees
</div>

<div class="nb-cell program" name="p1">
subtrees([]). %Empty list is a list of subtrees.
subtrees([(Cost,T)|Rest]):- number(Cost), isTree(T), subtrees(Rest).
%A tree consists of a value (root) and a list of its subtrees.
isTree(tree(Value,Children)):- string(Value), subtrees(Children).
%Subtrees record tree structure as well as step costs.
%subtrees([Cost,T|Rest]):- number(Cost), isTree(T), substrees(Rest).

testTree(tree("X",[])).
testTree2(tree("A",[(2,tree("B",[(5,tree("C",[]))])),(3,tree("B",[(10,tree("D",[]))]))])).
testTree3(tree("A",[(2,tree("B",[(5,tree("C",[])),(60,tree("D",[])),(42,tree("H",[]))])),(3,tree("C",[(10,tree("E",[(60,tree("J",[(60,tree("D",[(60,tree("I",[]))]))]))]))]))])).
testTree4(tree("A",[(2,tree("B",[(5,tree("C",[]))])),(3,tree("C",[(10,tree("D",[]))]))])).
</div>

<div class="nb-cell query" name="q1">
testTree(A), isTree(A), testTree2(B), isTree(B).
</div>

<div class="nb-cell markdown" name="md2">
Now we get to the actual implementation. Let's begin with the parameters of the predicates, i.e. when is BFS applicable?
</div>

<div class="nb-cell program" name="p3">
% Takes children of a tree, inserts path to parent and adds up cost.
fringehelper( _, _, [], []).
fringehelper(NewPath, Cost, Children, NewChildren):-.

bfs(Goal, Tree, Solution, Cost):- isTree(Tree), Fringe=[(Tree, "", 0)], bfs(Goal,Fringe,Solution,Cost).
bfs(Goal, [(tree(Goal,_),ParentPath,SolutionCost)|_],FinalPath,SolutionCost):- string_concat(ParentPath,Goal,FinalPath),write(Goal).
bfs(GoalValue,[(tree(Value,Children),Path,Cost)|Rest],NewPath, NewCost) :- string_concat(Path, Value, NewPath), write(Value),
    fringehelper(NewPath, Cost, Children, NewChildren),
    append(Rest, NewChildren, NewFringe),
    bfs(GoalValue, NewFringe, NewPath, NewCost).
</div>

</div>