Problems with making Puzzle 8 with A* Search in Matlab
2 次查看(过去 30 天)
显示 更早的评论
Hi i am trying to make a program that solve puzzle 8 with A* Search in Matlab. I have done this code but i don't know how to make it work. It doesn`t order it correctly and ignores previous expanded nodes. The initial state is choose by the user and the final state must be always [1,2,3;4,5,6;7,8,0]. Could anyone help me? Thanks!
clc;
clear all;
fprintf('Starting...\n\n');
%% Declaration of variables
vi=[]; %Creating de Initial Vector
r=0;
vgoal = [1 2 3;4 5 6;7 8 0];
MaxC = 3;
MaxR = 3;
while (r~=1)
% Loop to ask for the components of the Matrix to be introduce
for aux1=1 : MaxR %For 1 to Max number of Rows
for aux2=1 : MaxC
vi(aux1,aux2)= input('Enter the number in the matrix (from 1 to 8). Type "0" for the Empty one :\n');
end
end
% Show the Start State of the Matrix
fprintf('\nStart State: \n');
for aux1=1 : MaxR
for aux2=1 : MaxC
fprintf('\t %d\t',vi(aux1,aux2));
end
fprintf('\n');
end
% If you type 0, the program will ask you again for all the data
r=input('Is that the Matrix you wanted to create? Type "1" for YES or "0" for NO :\n');
end
vf=vi;
%% A* Search
g=0;
res=0;
while ((sum(sum(vf==vgoal)))~=res)
for aux1=1 : MaxR
for aux2=1 : MaxC
if (vf(aux1,aux2)==0)
g= g+1;
lf=0;
rf=0;
uf=0;
df=0;
if(aux2~=1)
lv=vf;
lv(aux1,aux2)= lv(aux1,aux2-1);
lv(aux1,aux2-1)=0;
lh = getH(lv,vgoal);
lf = getF(lh,g);
else
lf=1000;
end
if (aux2~=3)
rv=vf ;
rv(aux1,aux2)= rv(aux1,aux2+1);
rv(aux1,aux2+1)=0;
rf = getF(getH(rv,vgoal),g);
else
rf=1000;
end
if(aux1~=1)
uv=vf;
uv(aux1,aux2)= uv(aux1-1,aux2);
uv(aux1-1,aux2)=0;
uf = getF(getH(uv,vgoal),g);
else
df=1000;
end
if (aux1~=3)
dv=vf;
dv(aux1,aux2)= dv(aux1+1,aux2);
dv(aux1+1,aux2)=0;
df = getF(getH(dv,vgoal),g);
else
uf=1000;
end
if ((lf<=rf) && (lf<=uf) && (lf<=df) && (lf~=0))
fprintf('\nLeft: \n');
vf=lv;
end
if ((rf<lf) && (rf<uf) && (rf<df) && (rf~=0))
fprintf('\nRight: \n');
vf=rv;
end
if ((uf<lf) && (uf<rf) && (uf<df) && (uf~=0))
fprintf('\nUp: \n');
vf=uv;
end
if ((df<lf) && (df<uf) && (df<rf) && (df~=0))
fprintf('\nDown: \n');
vf=dv;
end
for aux5=1 : MaxR
for aux6=1 : MaxC
fprintf('\t %d\t',vf(aux5,aux6));
end
fprintf('\n');
end
fprintf('\n');
end
end
end
c=[vf==vgoal];
res=sum(sum(c));
fprintf('Resultado %d\n',res);
end
%% Final Outputs
% Show the final State of the Matrix
fprintf('\nGoal State: \n');
for aux1=1 : MaxR
for aux2=1 : MaxC
fprintf('\t %d\t',vf(aux1,aux2));
end
fprintf('\n');
end
%% Functions
function H = getH(vm,vgoal)
H=0;
MaxR=3;
MaxC=3;
for aux1=1 : MaxR
for aux2=1 : MaxC
if (vm(aux1,aux2)~=vgoal(aux1,aux2))
H = H+1;
end
end
end
end
function getF = getF(h_score,g_score)
getF=h_score+g_score;
end
2 个评论
Geoff Hayes
2021-10-15
编辑:Geoff Hayes
2021-10-15
@Sergio Álvarez Varela - can you clarify what the rules for this game are? Why should the output always be
vgoal = [1 2 3;4 5 6;7 8 0];
?
回答(1 个)
Nipun
2024-4-16
Hi Sergio,
I understand that you want to implement a 8-Puzzle solver with A* heuristic search. As mentioned by you, the shared code does not work as intended and you want to mend it accordingly.
Upon in-depth investigation of the shared code, I can confirm there are a few areas of improvement that might help get the desired result. They are as follows:
- Main Loop Condition: The condition in your main while loop seems to be intended to continue until the current state (vf) matches the goal state (vgoal). However, the way res is used and updated might not correctly reflect when the goal state is reached. Consider simplifying this condition to directly check if vf equals vgoal.
- Your method of checking if the current state matches the goal state (sum(sum(vf==vgoal))) is correct, but the way you're using res to track this is a bit convoluted. It's more straightforward to directly compare matrices using isequal(vf, vgoal).
Here's a simplified and corrected approach for the main loop and condition checks, addressing points 1 and 2:
% Correcting the misplaced 'else' conditions and simplifying the main loop condition
while ~isequal(vf, vgoal)
for aux1 = 1:MaxR
for aux2 = 1:MaxC
if vf(aux1, aux2) == 0 % Found the empty tile
% Increment g for each move
g = g + 1;
% Initialize variables for holding F scores of possible moves
lf = rf = uf = df = 1000; % Default to high value to represent 'impossible' moves
% Check and perform moves, calculating F scores
if aux2 ~= 1 % Can move left
% Calculate left move F score
end
% Similar checks for right, up, down with corrected 'else' placement
% Choose move with lowest F score
% Update vf to new state after chosen move
% Print current state vf
end
end
end
end
Hope this helps.
Regards,
Nipun
0 个评论
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Logical 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!