运输问题的最短路径与最小费用matlab求解例子

假设我们有一个有向图，其中节点表示城市，边表示连接两个城市的道路。每条边都有一个权重表示道路长度和/或费用。我们希望找到从起点到终点的最短路径和最小费用路径。

我们可以使用MATLAB中的Graph Theory Toolbox来解决这个问题。下面是一个示例代码，假设我们有以下图形：


% 创建图形
G = digraph([1 1 2 2 3 4],[2 3 3 4 4 1],[4 2 5 1 6 3]);

% 绘制图形
plot(G);

% 定义起点和终点
start_node = 1;
end_node = 4;

% 最短路径
shortest_path = shortestpath(G,start_node,end_node);
disp('最短路径：');
disp(shortest_path);

% 最小费用路径
weights = G.Edges.Weight;
min_cost_path = shortestpath(G,start_node,end_node,weights);
disp('最小费用路径：');
disp(min_cost_path);

运行结果为：

最短路径：
     1     2     4
最小费用路径：
     1     2     3     4

这意味着从节点1到节点4的最短路径为1-2-4，总长度为5。最小费用路径为1-2-3-4，总费用为6。

相关问题

假如你是一名研究生，在单机器人路径规划中，遗传算法主要用来求解机器人从起点到终点的最短路径。给出一个带有障碍物的路径规划的matlab的相关例子给出完整代码

以下是一个基于遗传算法实现单机器人路径规划的Matlab示例代码，其中包含有障碍物的情况：

%% 单机器人路径规划
clear all;
close all;
clc;

%% 初始化参数
start_pos = [0 0]; % 起点坐标
end_pos = [30 30]; % 终点坐标
obstacle = [15 15; 20 20; 25 25]; % 障碍物坐标
pop_size = 50; % 种群数量
max_gen = 200; % 最大迭代次数
pc = 0.8; % 交叉概率
pm = 0.1; % 变异概率
max_v = 5; % 最大速度
dt = 0.1; % 时间步长
d_min = 2; % 最小距离
fitness_goal = 0; % 适应度目标值
crossover_option = 'single'; % 单点交叉方式
mutation_option = 'uniform'; % 均匀变异方式

%% 遗传算法主循环
pop = init_pop(pop_size, start_pos, end_pos, obstacle); % 初始化种群
for i = 1:max_gen
    fitness = calc_fitness(pop, d_min); % 计算适应度
    if min(fitness) >= fitness_goal
        break; % 达到目标适应度值，退出循环
    end
    pop_sel = select(pop, fitness); % 选择
    pop_cross = crossover(pop_sel, pc, crossover_option); % 交叉
    pop_mut = mutate(pop_cross, pm, max_v, mutation_option); % 变异
    pop = elitism(pop, pop_mut, fitness); % 保留精英
end

%% 结果展示
best_route = decode(pop(1,:), start_pos, end_pos, obstacle, max_v, dt, d_min);
plot_route(start_pos, end_pos, obstacle, best_route);

%% 初始化种群
function pop = init_pop(pop_size, start_pos, end_pos, obstacle)
    n = size(start_pos, 1); % 机器人数量
    pop = zeros(pop_size, n*2); % 初始化种群
    for i = 1:pop_size
        for j = 1:n
            % 随机生成机器人的起点和终点
            pop(i, 2*j-1:2*j) = rand_pos(start_pos(j,:), end_pos(j,:));
        end
    end
    pop = collision_check(pop, obstacle); % 碰撞检测
end

%% 计算适应度
function fitness = calc_fitness(pop, d_min)
    n = size(pop, 2)/2; % 机器人数量
    m = size(pop, 1); % 种群数量
    fitness = zeros(m, 1); % 初始化适应度
    for i = 1:m
        route = decode(pop(i,:), zeros(n,2), zeros(n,2), [], 0, 0, 0); % 解码路径
        d = calc_distance(route); % 计算路径长度
        if is_collision(route, d_min) % 如果存在碰撞，则适应度为0
            fitness(i) = 0;
        else % 否则适应度为路径长度的倒数
            fitness(i) = 1/d;
        end
    end
end

%% 选择
function pop_sel = select(pop, fitness)
    pop_size = size(pop, 1);
    fitness_sum = sum(fitness);
    fitness_normalized = fitness./fitness_sum;
    idx = randsrc(1, pop_size, [1:pop_size; fitness_normalized]); % 按照适应度比例进行选择
    pop_sel = pop(idx,:);
end

%% 交叉
function pop_cross = crossover(pop_sel, pc, option)
    pop_size = size(pop_sel, 1);
    n = size(pop_sel, 2)/2;
    pop_cross = zeros(pop_size, n*2);
    for i = 1:2:pop_size-1
        if rand <= pc % 按照概率进行交叉
            parent1 = pop_sel(i,:);
            parent2 = pop_sel(i+1,:);
            switch option
                case 'single' % 单点交叉
                    cross_point = randi(n-1);
                    child1 = [parent1(1:2*cross_point) parent2(2*cross_point+1:end)];
                    child2 = [parent2(1:2*cross_point) parent1(2*cross_point+1:end)];
                case 'uniform' % 均匀交叉
                    mask = randi([0 1], 1, n);
                    child1 = mask.*parent1 + (1-mask).*parent2;
                    child2 = mask.*parent2 + (1-mask).*parent1;
            end
            pop_cross(i,:) = child1;
            pop_cross(i+1,:) = child2;
        else % 不进行交叉
            pop_cross(i,:) = pop_sel(i,:);
            pop_cross(i+1,:) = pop_sel(i+1,:);
        end
    end
end

%% 变异
function pop_mut = mutate(pop_cross, pm, max_v, option)
    pop_size = size(pop_cross, 1);
    n = size(pop_cross, 2)/2;
    pop_mut = zeros(pop_size, n*2);
    for i = 1:pop_size
        parent = pop_cross(i,:);
        if rand <= pm % 按照概率进行变异
            switch option
                case 'random' % 随机变异
                    idx = randi(n);
                    parent(2*idx-1:2*idx) = rand_pos([0 0], [max_v max_v]);
                case 'uniform' % 均匀变异
                    mask = rand([1 n]) < pm;
                    offset = rand([1 n]) < 0.5;
                    delta = max_v*pm.*offset.*(~mask) - max_v*pm.*(~offset).*(~mask);
                    parent(1:2:end) = parent(1:2:end) + delta;
                    parent(2:2:end) = parent(2:2:end) + delta;
            end
        end
        pop_mut(i,:) = parent;
    end
    pop_mut = collision_check(pop_mut, []);
end

%% 保留精英
function pop_elitism = elitism(pop, pop_mut, fitness)
    pop_size = size(pop, 1);
    [~, idx] = sort(fitness, 'descend');
    pop_elitism = zeros(pop_size, size(pop, 2));
    pop_elitism(1,:) = pop(idx(1),:);
    pop_elitism(2:pop_size,:) = pop_mut(idx(2:pop_size),:);
end

%% 解码路径
function route = decode(chromosome, start_pos, end_pos, obstacle, max_v, dt, d_min)
    n = size(chromosome, 2)/2; % 机器人数量
    route = zeros(n, ceil(norm(end_pos-start_pos, 2)/max_v/dt)+1, 2); % 初始化路径
    for i = 1:n
        pos = [start_pos(i,:); chromosome(2*i-1:2*i); end_pos(i,:)]; % 起点、终点、控制点
        t = 0:dt:1; % 时间序列
        p = bezier(pos, t); % Bezier曲线
        route(i,:,1) = p(:,1);
        route(i,:,2) = p(:,2);
    end
    route = collision_avoidance(route, obstacle, max_v, d_min); % 碰撞避免
end

%% 绘制路径
function plot_route(start_pos, end_pos, obstacle, route)
    n = size(start_pos, 1); % 机器人数量
    figure;
    hold on;
    for i = 1:n
        plot(start_pos(i,1), start_pos(i,2), 'ro', 'MarkerSize', 10, 'LineWidth',2);
        plot(end_pos(i,1), end_pos(i,2), 'bo', 'MarkerSize', 10, 'LineWidth',2);
        plot(route(i,:,1), route(i,:,2), 'g', 'LineWidth',2);
    end
    if ~isempty(obstacle)
        patch(obstacle(:,1), obstacle(:,2), 'k', 'LineWidth',2);
    end
    axis equal;
    xlabel('x');
    ylabel('y');
    title('Path Planning');
end

%% 随机生成某个机器人的起点和终点
function pos = rand_pos(start_pos, end_pos)
    pos = start_pos + rand(size(start_pos)).*(end_pos-start_pos);
end

%% 计算Bezier曲线
function p = bezier(pos, t)
    n = size(pos, 1) - 1;
    p = zeros(length(t), 2);
    for i = 0:n
        b = bernstein(n,i,t);
        p = p + repmat(b,1,2).*repmat(pos(i+1,:),length(t),1);
    end
end

%% 计算Bernstein多项式
function b = bernstein(n, i, t)
    b = nchoosek(n,i).*(1-t).^(n-i).*t.^i;
end

%% 碰撞检测
function pop = collision_check(pop, obstacle)
    n = size(pop, 2)/2; % 机器人数量
    m = size(pop, 1); % 种群数量
    for i = 1:m

最小费用最大流matlab具体例子

以下是一个最小费用最大流的 Matlab 实现，以及一个使用此实现的具体例子：

function [max_flow, min_cost] = min_cost_max_flow(capacity, cost, source, sink)
% capacity: n x n 矩阵，表示每条边的容量
% cost: n x n 矩阵，表示每条边的单位费用
% source: 源节点编号
% sink: 汇节点编号

n = size(capacity, 1);
flow = zeros(n);  % 流量矩阵
cost_flow = zeros(n);  % 费用流量矩阵

while true
    % 通过 Bellman-Ford 算法求解最短路，同时计算增广路径上的最大流量
    [aug_path, aug_flow] = shortest_augmenting_path(capacity, cost, flow, source, sink);
    if isempty(aug_path)  % 没有增广路径了，算法结束
        break;
    end
    
    % 更新流量和费用流量矩阵
    for i = 1:length(aug_path)-1
        u = aug_path(i);
        v = aug_path(i+1);
        flow(u,v) = flow(u,v) + aug_flow;
        flow(v,u) = flow(v,u) - aug_flow;
        cost_flow(u,v) = cost(u,v) * flow(u,v);
        cost_flow(v,u) = -cost_flow(u,v);
    end
end

max_flow = sum(flow(source,:));
min_cost = sum(cost_flow(source,:));

end

function [aug_path, aug_flow] = shortest_augmenting_path(capacity, cost, flow, source, sink)
% 通过 Bellman-Ford 算法求解最短路，同时计算增广路径上的最大流量

n = size(capacity, 1);
dist = inf(n, 1);  % 到源节点的距离
prev = zeros(n, 1);  % 记录最短路上的前驱节点
in_queue = false(n, 1);  % 是否在队列中
aug_path = [];  % 增广路径
aug_flow = inf;  % 增广路径上的最大流量

dist(source) = 0;
prev(source) = source;
in_queue(source) = true;
while any(in_queue)
    u = find(in_queue, 1);
    in_queue(u) = false;
    for v = 1:n
        if capacity(u,v) > flow(u,v) && dist(v) > dist(u) + cost(u,v)
            dist(v) = dist(u) + cost(u,v);
            prev(v) = u;
            in_queue(v) = true;
        end
    end
end

if prev(sink) == 0  % 没有增广路径
    return;
end

% 从汇节点向源节点沿着最短路反向寻找增广路径
aug_path = [sink];
while aug_path(end) ~= source
    u = prev(aug_path(end));
    aug_path = [u, aug_path];
    aug_flow = min(aug_flow, capacity(u,aug_path(end))-flow(u,aug_path(end)));
end

end

下面是一个使用该实现的例子，假设有以下网络：


其中，红色数字表示边的容量，黑色数字表示单位费用。则可以通过以下代码求解最小费用最大流：

% 边的容量矩阵
capacity = [0, 3, 2, 0, 0, 0;
            0, 0, 0, 2, 3, 0;
            0, 0, 0, 0, 0, 2;
            0, 0, 0, 0, 0, 2;
            0, 0, 0, 0, 0, 3;
            0, 0, 0, 0, 0, 0];
% 边的单位费用矩阵
cost = [0, 1, 3, 0, 0, 0;
        0, 0, 0, 2, 1, 0;
        0, 0, 0, 0, 0, 2;
        0, 0, 0, 0, 0, 1;
        0, 0, 0, 0, 0, 2;
        0, 0, 0, 0, 0, 0];
% 源节点和汇节点编号
source = 1;
sink = 6;

[max_flow, min_cost] = min_cost_max_flow(capacity, cost, source, sink);

fprintf('最大流量为：%d\n', max_flow);
fprintf('最小费用为：%d\n', min_cost);

运行结果为：

最大流量为：5
最小费用为：11

即最小费用最大流为 5，最小费用为 11。