الگوریتم پریم در متلب برای حل مسئله درخت پوشای کمینه عنوان محصولی است که در این پست به آن پرداخته شده است. الگوریتم پریم یک روش حریصانه 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 است. این برنامه مناسب برای دانشجویان و علاقه مندان به درس ساختمان داده و طراحی الگوریتم می باشد چرا که دارای کد های روان و قابل فهم و آسان برای یادگیری می باشد. خرید محصول توسط کلیه کارت های شتاب امکان پذیر است و بلافاصله پس از خرید، لینک دانلود محصول در اختیار شما قرار خواهد گرفت. کیفیت محصول توسط کارشناسان پی استور تضمین می شود.
مطالب مرتبط با تعیین درخت پوشای مینیمم
تاریخ انتشار: | 17 اسفند 1397 |
---|---|
تاریخ بروزرسانی: | 27 آذر 1398 |
حجم فایل: | 6 کیلوبایت |
فرمت فایل | m. در قالب متلب |
نسخه: | 1.0 |
شناسه اثر: | ندارد |
هماهنگی با: | Matlab 2009 و بالاتر |
تاکنون 304 نفر این محصول را تهیه کرده اند و 1 نظر برای آن ثبت شده است.
نظرات و دیدگاه ها
قوانین ثبت دیدگاه
- لطفاً دیدگاه های خود را فارسی تایپ کنید.
- دیدگاه های نامرتبط به مطلب تایید نخواهد شد.
- از درج دیدگاه های تکراری پرهیز نمایید.
- سوالات تخصصی خودتان را از طریق تیکت پشتیبانی مطرح کنید.
قیمت 49,000 تومان
تاریخ انتشار: | 17 اسفند 1397 |
---|---|
تاریخ بروزرسانی: | 27 آذر 1398 |
حجم فایل: | 6 کیلوبایت |
فرمت فایل | m. در قالب متلب |
نسخه: | 1.0 |
شناسه اثر: | ندارد |
هماهنگی با: | Matlab 2009 و بالاتر |
1 بازخورد (مشاهده نظرات)
قیمت: 49,000 تومان
مدیریت و پشتیبانی
نظرات و دیدگاه های خود را با ما درمیان بگذارید.