A star算法的MATLAB程序

A*搜索算法（A-star Algorithm），也被称为启发式搜索算法，是一种用于解决图形搜索问题的有效方法，特别适用于寻找两点之间的最短路径。在MATLAB中编写A*算法，你需要创建一些关键函数，包括计算节点的F值、G值和H值（启发式估计）、开放列表操作以及关闭列表检查。

以下是一个简单的MATLAB程序示例，它使用了cell数组来表示图的邻接矩阵：

% 定义函数来计算F值（总成本）
function f = calculate_F(g, h)
    f = g + h;
end

% 定义A*搜索函数
function [path, cost] = a_star_search(graph, start, goal)
    % 初始化
    open_list = {start};
    closed_list = {};
    came_from = containers.Map('KeyType', 'char', 'ValueType', 'char'); % 路径记录
    g_score = containers.Map('KeyType', 'char', 'ValueType', 'double'); % G值
    g_score(start) = 0; % 初始节点的g值为0
    h_score = containers.Map('KeyType', 'char', 'ValueType', 'double'); % H值
    for node in open_list
        if isequal(node, goal)
            break;
        end
        
        % 计算当前节点的所有邻居
        neighbors = graph[node];
        for neighbor in neighbors.keys()
            tentative_g_score = g_score(node) + graph(node, neighbor);
            
            % 如果邻居不在open_list，或者找到更优路径
            if ~isKey(g_score, neighbor) || tentative_g_score < g_score(neighbor)
                came_from(neighbor) = node;
                g_score(neighbor) = tentative_g_score;
                h_score(neighbor) = heuristic_function(neighbor, goal); % 递归地计算每个邻居的H值
                
                % 将邻居加入open_list
                if ~ismember(neighbor, open_list)
                    open_list{end+1} = neighbor;
                end
            end
        end
        delete(open_list, find(strcmp(open_list, node))); % 移除已处理节点
    end
    
    path = [];
    current = goal;
    while ~isempty(came_from(current))
        path = [came_from(current), path];
        current = came_from(current);
    end
    path = reverse(path); % 因为路径是从终点开始的
    cost = g_score(goal);
end

% 启发式函数（这里假设曼哈顿距离作为例子）
heuristic_function = @(node, goal) abs(node(1)-goal(1)) + abs(node(2)-goal(2));

% 示例：使用4x4网格地图
grid = {'S', '.', '.', '.',
       '.', '#', '.', '.',
       '.', '.', '.', 'G'};
[~, path] = a_star_search(grid, 'S', 'G');
disp(['Shortest path from S to G: ', char(path), ' (Cost: ', num2str(cost), ')']);