贪婪算法matlab程序

以下是一个简单的贪婪算法的 MATLAB 程序示例：

function [best_path, best_cost] = greedy_tsp(distance_matrix)
% 贪婪算法求解 TSP 问题

n = size(distance_matrix, 1); % 城市数量
visited = zeros(1, n); % 标记城市是否已访问
best_path = zeros(1, n); % 最佳路径
best_cost = Inf; % 最小路径长度

% 从第一个城市出发
current_city = 1;
visited(current_city) = 1;
best_path(1) = current_city;

for i = 2:n
    % 选择距离当前城市最近的未访问城市
    [~, nearest_city] = min(distance_matrix(current_city, :) + visited * Inf);
    % 更新当前城市和路径长度
    current_city = nearest_city;
    visited(current_city) = 1;
    best_path(i) = current_city;
end

% 计算最终路径长度
for i = 1:n-1
    best_cost = best_cost + distance_matrix(best_path(i), best_path(i+1));
end
best_cost = best_cost + distance_matrix(best_path(n), best_path(1));
end

该程序输入一个距离矩阵，输出一个最优路径和对应的路径长度。该算法的时间复杂度为 $O(n^2)$，适用于小规模问题。