تعیین درخت پوشای مینیمم با الگوریتم پریم در متلب

الگوریتم پریم در متلب برای حل مسئله درخت پوشای کمینه عنوان محصولی است که در این پست به آن پرداخته شده است. الگوریتم پریم یک روش حریصانه Heuristic در علوم کامپیوتر می‌باشد. از این الگوریتم برای حل مسئله درخت پوشا مینیمم استفاده می‌شود. درخت پوشای کمینه یا همان مینیمم که به اصطلاح (MST (Minimum Spanning Tree  نیز گفته می‌شود درختی است که در آن مجموع وزن لبه به حداقل برسد و تمامی گره‌ها یا راس‌ها شامل شود. در ادامه به توضیح کامل الگوریتم پریم در متلب اشاره خواهد شد.

الگوریتم پریم PRIM’S ALGORITHM

الگوریتم پریم، الگوریتمی در نظریه گراف‌ها است که درخت پوشای مینیمم را برای یک گراف همبند وزن دار ( همبندی یعنی حداقل تعداد رأس‌ها یا یال‌هایی است که با حذفشان، ارتباط رأس‌های باقی‌مانده از بین نرود) پیدا می‌کند. یعنی زیرمجموعه‌ای از یال‌ها را در آن گراف می‌یابد که درختی را تشکیل می‌دهند که همه راس ها را شامل شود و دارای حداقل هزینه یال ها باشد. این الگوریتم  در سال ۱۹۵۷ توسط آقای پریم Prim، مطرح شد از این نوع دسته الگوریتم ها می توان به الگوریتم کروسکال و سولین نیز اشاره کرد.

ایده اصلی الگوریتم پریم این است که دو مجموعه ای از رأس‌ها را نگه می‌دارد. مجموعه اول شامل رأس‌هایی است که قبلا در MST موجود است، مجموعه دیگری حاوی رأس‌هایی است که هنوز موجود نیستند. در هر مرحله همه لبه‌هایی که دو مجموعه را متصل می‌کنند را بررسی می‌کند و لبه‌ها با حداقل وزن انتخاب می‌شوند. پس از برداشتن لبه، نقطه انتهایی دیگر لبه را به مجموعه حاوی MST منتقل می‌کند. روند کلی الگوریتم برای یک مثال بصورت زیر است.

الگوریتم پریم در متلب

پیاده سازی الگوریتم prim در متلب شامل توابعی است که مراحل بالا را انجام می‌دهد که بصورت گرافیکی روند انتخاب لبه‌ها انجام می‌شود. این الگوریتم به سه صورت معمولی، بازگشتی و روش Heap پیاده سازی شده است. قسمتی از سورس کد الگوریتم پریم در Matlab به صورت زیر است.

روش معمولی (تکراری) Iterative prim

[n,n] = size(A);                                             % The matrix is n by n, where n = # nodes.
    intree = 1; nintree=1;                                       % intree = nodes selected. nintree= #intree
    k = 0;                                                       % k is the number of edges selected
    notintree = [2:n]'; nnotintree=n-1;                          % notintree = nodes not selected. nnotintree=#notintree
    while nintree < n
        mincost = Inf;
        for i=1:nintree
            for j=1:nnotintree
                ni = intree(i); nj= notintree(j);
                if A(ni,nj) < mincost && A(ni,nj)~=0,
                    mincost = A(ni,nj); ei = ni; ej = nj;        % Save nodes and edge selected
                end
            end
        end
        k = k + 1;                                               % Increment number of edges in tree.
        mst(k,:) = [ei,ej]; 
        
        sol=ConverMatrix( model,mst );

        PlotSolution(sol,model);
        pause(0.2);
        % Add this edge to tree.
        costs(k,1) = mincost;                                    % Add the cost of this edge
        nintree = nintree+ 1;                                    % Increment number of nodes that tree connects.
        nnotintree = nnotintree-1;                               % Decrement number of nodes that tree connects.
        intree = [intree; ej];                                   % Add this node to tree.
        notintree = setdiff(notintree,ej);                       % Delete node to the notintree list
    end;

روش بازگشتی recursive prim

% Recursive prim algorithm
    if nargin < 5; cost=0;    
        if nargin < 4; mst = [];
            if nargin < 3; edges = [];
                if nargin<2; visited = 1;end
            end
        end
    end
    
    % Get current node (endpoint of last added edge)
    current_node = visited(end);
    % Get the costs of its edges
    potential_edges = A(:, current_node);
    % Filter 0 or Inf edges and return endpoint (index) of each feasible potential edge
    new_edges = find(potential_edges~=Inf & potential_edges~=0);
    % Check if endpoint of new potential edge is already in the mst
    new_edges = new_edges.*~ismember(new_edges,visited);
    % Delete all new edges whose endpoint is already in the mst
    new_edges = new_edges(new_edges~=0);
    
    % Add the new edges to the feasible edge list, where the feasible edges
    % satisfy that: startnode is in mst, endnode is not in mst
    for i=1:length(new_edges); edges = [edges; current_node, new_edges(i)];end
    
    % For the updated list of possible edges get their costs 
    costs = diag(A(edges(:,1)',edges(:,2)'));
    % Find the edge with minimum cost
    i = costs == min(costs);
    % Select that edge as the edge to add to the mst
    selected_edge = edges(i,:);
    
    % If there is more than one edge that satisfy that its cost is minimum
    % select the first of them
    if length(selected_edge(1,:))>1; selected_edge = selected_edge(1,:); end
    
    % Get the end node of the edge added to the mst
    next_node = selected_edge(1,2);
    % Delete from possible edges any edge whose endpoint whas the endpoint
    % of the selected edge
    i = edges(:,2)==next_node;
    edges(i,:)=[];
    
    % Update total cost and mst with new edge
    cost = cost+min(costs);
    mst = [mst;selected_edge];
    visited = [visited, next_node];
    sol=ConverMatrix( model,mst );

روش هیپ prim heap

n           = length(A(:,1));
    z           = 1:n;
    adj         = A;
    adj(adj>0)  = 1;
    edges       = zeros(n-1,2);
    n_in_tree   = [1,zeros(1,n-1)];
    c_node      = n_in_tree(1);
    heap        = [];
    % Build initial min heap starting on node 1
    for i=2:n
        if adj(c_node,i)==1
            cost = A(c_node,i);
        else cost = Inf; 
        end
        heap = insert_heap(heap,struct('v',i,'e',[c_node i],'c',cost));
    end
    % Obtain MST
    cost = 0; 
    while ~isempty(heap)
        % Extract edge with minimum cost
        min = heap(1); heap(1)=heap(end);
        heap = heap(1:length(heap)-1);
        heap = heapify_root(heap);
        % Add node to nodes already in the MST and edge to MST edges
        i = z(n_in_tree==0);  
        n_in_tree(i(1)) = min.v;
        i = z(edges(:,1)==0); 
        edges(i(1),:) = min.e;
                            sol=ConverMatrix( model,edges );
                    PlotSolution(sol,model);
                    pause(0.2);

        % Update cost
        cost = cost + min.c;
        p=[heap.v];
        
        % For the nodes not in the MST that are connected with the last
        % node added to the MST, update if necessary the min cost edge
        % that connects them to the MST 
        
        % Iterate through nodes connected with the last node added to MST
        for i=z(adj(min.v,:)==1)
            % Check if node is already in MST
            if ~isempty(p(p-i==0))
                j=z(p==i); % if not, get min heap index of node
                if A(i,min.v) < heap(j).c && A(i,min.v)~=0
                    % Update min cost edge
                    heap(j).e = [min.v i]; heap(j).c = A(i,min.v);
                    % Update heap
                    heap = decrease_heap_key(heap,j);
                    p=[heap.v];

                end
            end
        end
    end

برای دریافت سورس کامل محصول را خریداری کنید.

تصویر خروجی

درباره محصول

این اثر تحت عنوان سورس کد تعیین درخت پوشای مینیمم با الگوریتم پریم در متلب Matlab است. این برنامه مناسب برای دانشجویان و علاقه مندان به درس ساختمان داده و طراحی الگوریتم می‌باشد چرا که دارای کدهای روان و قابل فهم و آسان برای یادگیری می‌باشد. خرید فایل توسط کلیه کارت‌های شتاب امکان پذیر است و بلافاصله پس از خرید، لینک دانلود اثر در اختیار شما قرار خواهد گرفت. کیفیت فایل توسط کارشناسان پی استور تضمین می‌شود.