تخفیف نوروزی پی استور

کد تخفیف: PR1404

شامل تمامی آثار
روز
ساعت
دقیقه
ثانیه

با خرید اشتراک ویژه ، با هزینه بسیار کمتر به فایل های پاورپوینت دسترسی داشته باشید!

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

هزینه سفارش:

۹۹,۰۰۰ تومان

روز
ساعت
دقیقه
ثانیه
دریافت کد تخفیف با گردونه شانس %
تعداد فراگیر
319 نفر
امتیاز کاربران
امتیاز 5.00 از 5

الگوریتم پریم در متلب برای حل مسئله درخت پوشای کمینه عنوان محصولی است که در این پست به آن پرداخته شده است. الگوریتم پریم یک روش حریصانه Heuristic در علوم کامپیوتر می‌باشد. از این الگوریتم برای حل مسئله درخت پوشا مینیمم استفاده می‌شود.

الگوریتم پریم در متلب برای حل مسئله درخت پوشای کمینه عنوان محصولی است که در این پست به آن پرداخته شده است. الگوریتم پریم یک روش حریصانه 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 است. این برنامه مناسب برای دانشجویان و علاقه مندان به درس ساختمان داده و طراحی الگوریتم می‌باشد چرا که دارای کدهای روان و قابل فهم و آسان برای یادگیری می‌باشد. خرید فایل توسط کلیه کارت‌های شتاب امکان پذیر است و بلافاصله پس از خرید، لینک دانلود اثر در اختیار شما قرار خواهد گرفت. کیفیت فایل توسط کارشناسان پی استور تضمین می‌شود.

ویدئوی معرفی

نحوه اجرای سورس کد


برنامه‌نویس:  تیم برنامه‌نویسی پی‌استور

متشکل از اساتید و فارغ التحصیلان رشته‌های فنی - مهندسی

تیم برنامه نویسی پی استور یکی از اولین گروه‌های تشکیل شده در مجموعه آموزشی پی استور می‌باشد. این تیم از اساتید مجرب و فارغ التحصیلان رشته‌های فنی و مهندسی تشکیل شده که در زمینه‌های مختلف برنامه‌نویسی و تهیه سورس کد فعال هستند.

مشخصات تکمیلی سورس کد

نام اثر: تعیین درخت پوشای مینیمم با الگوریتم پریم در متلب
نوع اثر: سورس کد
برنامه‌نویس: تیم برنامه‌نویسی پی‌استور
زبان برنامه نویسی: Matlab
ویژگی: قابلیت دانلود و ویرایش

راهنمای خرید و ثبت سفارش

تصویر مراحل خرید از پی استور

اگر در مورد این اثر یا نحوه تهیه آن سوالی دارید؟
  • با شماره تلفن واحد مخاطبین 44225175 (پیش شماره 041) تماس بگیرید. – تمام ساعات اداری
  • با ما مکاتبه ایمیلی داشته باشید (این لینک). – تمام ساعات

توجه: کیفیت این محصول توسط پی استور تضمین شده و در صورت عدم رضایت از محصول، به انتخاب شما:

تصویر و لوگوی گارانتی

نظرات

1 نظر|5.00 (میانگین امتیاز کاربران)

  1. آواتار مدیریت و پشتیبانی

    مدیریت و پشتیبانی

    نظرات و دیدگاه های خود را با ما درمیان بگذارید.

دیدگاه خود را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

سه × دو =

شناسه اثر: 5121 دسته‌بندی موضوعی: برچسب , ,

هزینه سفارش:

۹۹,۰۰۰ تومان

دریافت کد تخفیف %