基于Matlab实现深度优先搜索求解八数码问题

核心改动说明 #

BFS采用队列（先进先出）管理待探索节点，而DFS需要采用栈（后进先出）。仅需修改节点取出和栈维护的逻辑，其余生成邻节点、路径回溯的逻辑无需调整：

• 原BFS取队列第一个元素，DFS改为取栈的最后一个元素
• 原BFS删除队列第一个元素，DFS改为删除栈的最后一个元素

修改后的DFS完整代码 #

% 八数码问题DFS求解
I = [4, 1, 2; 7, 5, 3; 0, 8, 6]; % 初始状态
G = [1, 2, 3; 4, 5, 6; 7, 8, 0]; % 目标状态

F = {};          % 栈：存储待探索的节点
Fparent = {};    % 栈：存储对应节点的父节点索引

P = I;           % 当前探索节点
i = 1;

S(i,:,:) = P(:,:);    % 记录所有已探索节点
Sparent(i) = 0;       % 记录已探索节点的父节点索引

while ~isequal(P, G)
    % 找到空格0的位置
    [x,y] = find(P == 0);
    
    % 生成所有可能的邻节点（上下左右移动空格）
    if x > 1
        C = P;
        C(x,y) = P(x-1,y);
        C(x-1,y) = 0;
        F{end+1} = C;
        Fparent{end+1} = i;
    end
    if x < 3
        C = P;
        C(x,y) = P(x+1,y);
        C(x+1,y) = 0;
        F{end+1} = C;
        Fparent{end+1} = i;
    end
    if y > 1
        C = P;
        C(x,y) = P(x,y-1);
        C(x,y-1) = 0;
        F{end+1} = C;
        Fparent{end+1} = i;
    end
    if y < 3
        C = P;
        C(x,y) = P(x,y+1);
        C(x,y+1) = 0;
        F{end+1} = C;
        Fparent{end+1} = i;
    end
    
    % DFS核心：取出栈的最后一个元素（后进先出）
    P = F{end};
    i = i + 1;
    S(i,:,:) = P(:,:);
    Sparent(i) = Fparent{end};
    
    % 删除栈的最后一个元素
    F = F(1:end-1);
    Fparent = Fparent(1:end-1);
end

% 回溯求解路径
P(:,:) = S(i,:,:);
idp = Sparent(i);
path = {P};

while ~isequal(P, I)
    idp = Sparent(idp);
    P(:,:) = S(idp,:,:);
    path{end+1} = P;
end
path = flip(path);
disp('求解路径：');
path{:}

关键改动点拆解 #

1. 节点取出逻辑：将P=F{1};改为P=F{end};，从队列头部取节点改为从栈尾部取节点
2. 栈维护逻辑：将F = F(2:end);改为F = F(1:end-1);，删除队列第一个元素改为删除栈最后一个元素，Fparent的维护同步调整
3. 生成邻节点、路径回溯的逻辑完全复用原BFS代码，因为这部分与搜索策略无关

内容的提问来源于stack exchange，提问作者Sanchez Julio