bredth_first_sg.zip_Breadth-First_city_sg

function [solutionpath,visiting_path]=bredth_first_sg(instate, goalstate) % From S to G % we use five number to represent the five destinations: % S A B C G [1 1] [2 2] [3 3] [4 4] [5 5] % instate=[1 1]; % goalstate=[5 5]; % This function is to solve the city block problem by bredth-first search % The usage of this code is: % [solutionpath,visiting_path]=bredth_first_sg([1 1], [5 5]) %show the initial state and goal state state{1}='S'; state{2}='A'; state{3}='B'; state{4}='C'; state{5}='G'; display(['The initial state is ' state{instate(1)}]) display(['The goal state is ' state{goalstate(1)}]) open=instate; % initialize the open set closed=[]; % initialize the closed set iternnum=0; % record the interation number %% get closed and open set while ~isempty(open) iternnum=iternnum+1; X=open(1,:); %got the leftmost state from open open(1,:)=[]; %remove leftmost state from open eva=sum(abs(X-goalstate)); %if x is goal then return success if eva==0 display('Find the goalstate successfully') break; end children=getchilidrenSG(X); % get the clidren of X k = ismember(children,[open;closed],'rows'); % remove the repeated state children(k,:)=[]; closed=[X;closed]; % put the leftmoset to the closed open=[open;children]; % put the children on right end of open end %% get the visiting path and solution path if isempty(open) && eva~=0 display('Fail to find the goalstate successfully') else %show the visiting path visitingpath=[]; for i=1:size(closed,1) visitingpath=[state(closed(i,1)) visitingpath]; end visiting_path=[visitingpath state(goalstate(1))]; display('The visiting path is ') display(visiting_path) visitingpath=[goalstate;closed]; %prune the visiting path to get solution path k=1; while k<size(visitingpath,1) % find the father mode of the visiting path father_mode=getchilidrenSG(visitingpath(k,:)); same_mode=ismember(visitingpath(k+1:end,:),father_mode,'rows'); % find the father node(s) of the visiting node, delete % the nodes between the current node and fathest father. (e.g., G-C-B-A-S, % G is the child of B and C, then delete C and keep B index= find(same_mode==1)+k; visitingpath=visitingpath([1:k,index(end):end],:); k=k+1; end solutionpath=state(flipud(visitingpath(:,1))); display('The solution path is ') display(solutionpath) end