• مقالات آموزشی
    • آموزش برنامه نویسی
    • آموزش الگوریتم
    • آموزش شبکه های کامپیوتری
    • آموزش های عمومی
  • ترجمه مقاله
    • لیست ترجمه کامل مقالات
    • لیست ترجمه مفهومی مقالات
  • تحقیق و پژوهش
    • لیست داکیومنت پایان‌نامه
    • لیست داکیومنت سمینار
  • پیاده سازی
    • سی پلاس پلاس ++C
    • برنامه نویسی OpenGL
    • سی شارپ #C
    • پایتون Python
    • اندروید Android
    • پی اچ پی PHP
    • متلب Matlab
  • پاورپوینت
    • پاورپوینت الگوریتم های بهینه سازی
    • پاورپوینت شبکه‌های کامپیوتری
    • پاورپوینت مهندسی کامپیوتر
    • پاورپوینت یادگیری ماشین
    • پاورپوینت درس و تحقیق
    • قالب آماده پاورپوینت
  • فیلم آموزشی
    • لیست فیلم های آموزشی
  • قالب آماده
    • لیست قالب آماده HTML
  • دانلود رایگان
  • مجله پی استور
  • ابزارهای آنلاین
    • برنامه نویسی آنلاین
    • تبدیل مبنای آنلاین
  • سفارش تدریس آنلاین
  • آموزش برنامه نویسی
  • آموزش الگوریتم
  • آموزش شبکه
  • آموزش عمومی

ورود

رمز عبور را فراموش کرده اید؟

هنوز عضو نشده اید؟ عضویت در سایت
  • درباره ما
  • تماس با ما
  • سفارش تدریس آنلاین
پی استور
0

ورود و ثبت نام

مقالات آموزشی
  • ترجمه مقاله
    • لیست ترجمه کامل مقالات
    • لیست ترجمه مفهومی مقالات
  • تحقیق و پژوهش
    • لیست داکیومنت پایان‌نامه
    • لیست داکیومنت سمینار
  • پیاده سازی
    • سی پلاس پلاس ++C
    • برنامه نویسی OpenGL
    • سی شارپ #C
    • پایتون Python
    • اندروید Android
    • پی اچ پی PHP
    • متلب Matlab
  • پاورپوینت
    • پاورپوینت الگوریتم های بهینه سازی
    • پاورپوینت شبکه‌های کامپیوتری
    • پاورپونت مهندسی کامپیوتر
    • پاورپوینت یادگیری ماشین
    • پاورپوینت درس و تحقیق
      • عمومی
      • مشاهیر و اشخاص
      • واقعیت مجازی
      • طراحی سایت
      • برنامه نویسی
      • علوم کامپیوتر
      • اینترنت اشیاء
      • سیستم عامل
      • ارز دیجیتال
      • کسب و کار
      • تکنولوژی
      • علوم
    • قالب آماده پاورپوینت
  • فیلم آموزشی
    • لیست فیلم های آموزشی
  • قالب آماده
    • قالب آماده HTML
  • مجله پی استور
  • ابزارهای آنلاین
    • برنامه نویسی آنلاین
    • تبدیل مبنای آنلاین

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

خانهفروشگاهبرنامه نویسیمتلبتعیین درخت پوشای مینیمم با الگوریتم پریم در متلب
https://dl2.programstore.ir/files/Uploades/Previews/Matlab/Minimum-Spanning-Tree-using-prim.mp4

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

cropped-fav2.png

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

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

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

الگوریتم پریم 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

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

تصویر خروجی

تصویر خروجی الگوریتم پریم در متلب

ویدئوی معرفی محصول

Your browser does not support the video tag.

درباره محصول

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

گارنتی 7 روزه بازگشت هزینه

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

  • ۱۰۰ درصد مبلغ پرداختی در حساب کاربری شما شارژ می‌شود.
  • و یا 80 درصد مبلغ پرداختی به حساب بانکی شما عودت داده می‌شود.

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

تعیین درخت پوشای مینیمم با الگوریتم پریم در پایتون Python
تعیین درخت پوشای مینیمم با الگوریتم پریم در پایتون Python
تعیین درخت پوشای مینیمم با الگوریتم پریم در سی پلاس پلاس
تعیین درخت پوشای مینیمم با الگوریتم پریم در سی پلاس پلاس
تعیین درخت پوشای مینیمم با الگوریتم پریم در سی شارپ #C
تعیین درخت پوشای مینیمم با الگوریتم پریم در سی شارپ #C
تعیین درخت پوشای مینیمم با الگوریتم کروسکال در متلب
تعیین درخت پوشای مینیمم با الگوریتم کروسکال در متلب
تعیین درخت پوشای مینیمم با الگوریتم کروسکال در سی پلاس پلاس
تعیین درخت پوشای مینیمم با الگوریتم کروسکال در سی پلاس پلاس
تعیین درخت پوشای مینیمم با الگوریتم کروسکال در Python
تعیین درخت پوشای مینیمم با الگوریتم کروسکال در Python
تعیین درخت پوشای مینیمم با الگوریتم کروسکال در سی شارپ
تعیین درخت پوشای مینیمم با الگوریتم کروسکال در سی شارپ
تعیین درخت پوشای مینیمم با الگوریتم سولین در سی پلاس پلاس
تعیین درخت پوشای مینیمم با الگوریتم سولین در سی پلاس پلاس
الگوریتم sollin در پایتون (حل درخت پوشای کمینه با الگوریتم سولین)
تعیین درخت پوشای مینیمم با الگوریتم سولین در پایتون Python

تاکنون 207 نفر این محصول را تهیه کرده اند و 1 نظر برای آن ثبت شده است.

نظرات و دیدگاه ها
  • مدیریت و پشتیبانی
    22 فروردین 1398
    امتیاز 5 از 5
    پاسخ

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

قوانین ثبت دیدگاه

  • لطفاً دیدگاه های خود را فارسی تایپ کنید.
  • دیدگاه های نامرتبط به مطلب تایید نخواهد شد.
  • از درج دیدگاه های تکراری پرهیز نمایید.
  • سوالات تخصصی خودتان را از طریق تیکت پشتیبانی مطرح کنید.

لغو پاسخ

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

دسته‌بندی موضوعی: برنامه نویسی ساختمان داده متلب

قیمت 39,000 تومان

افزودن به علاقه مندی ها
امتیاز
5.00 از 1 رأی
5.00 1 رای
39,000 تومان

تاریخ انتشار: 17 اسفند 1397
تاریخ بروزرسانی: 27 آذر 1398
حجم فایل: 6 کیلوبایت
فرمت فایل m. در قالب متلب
نسخه: 1.0
شناسه اثر: ندارد
هماهنگی با: Matlab 2009 و بالاتر
دانلود شده توسط: 207 نفر

1 بازخورد (مشاهده نظرات)

قیمت: 39,000 تومان

تماس با ما
  • دفتر پشتیبانی: 04144225175 (ساعت کاری 8:00 الی 16:00)
  • آی دی تلگرام: programerPstore
درباره پی استور

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

مجوز های اخذ شده
اینماد نشان ملی   پروانه نشر دیجیتال
  • حساب کاربری من
  • سوالات متداول
  • راهنمای خرید و دانلود
پی استور
  • همکاری با ما
  • قوانین و مقررات
  • حریم خصوصی
تمامی حقوق برای پی استور محفوظ است.
keyboard_arrow_up