الگوریتم حریصانه: تفاوت میان نسخه‌ها

محتوای حذف‌شده محتوای افزوده‌شده
Zyousefi (بحث | مشارکت‌ها)
Zyousefi (بحث | مشارکت‌ها)
خط ۲۴۵:
 
[[File:16597fe.jpg|thumb|نمونه مثال الگوریتم پریم]]
 
 
 
 
 
سطر ۲۵۵ ⟵ ۲۵۲:
روش‌های [[الگوریتم پریم|پریم]] و [[الگوریتم کراسکال|کروسکال]] دو روش مشهور تولید درخت پوشای کمینه از یک [[گراف وزن‌دار]] هستند که از روش حریصانه بهره می‌برند. منظور از درخت پوشای کمینه، [[درخت پوشا]]<nowiki/>یی از گراف است که مجموع وزن یال‌های آن کمتر یا مساوی مجموع وزن یال‌های سایر درخت‌های پوشای آن گراف است.<ref>{{پک|ابراهیم علایی فرادنبه - محمدرضا علایی|۱۳۹۲|ک=طراحی الگوریتم ایران|ص=265}}</ref>
 
[[پرونده:Huffman tree 2.svg|left|thumb|350px|درخت هافمن، ایجاد شده از تعداد تکرار حرف‌های جملهٔ «this is an example of a ‌Huffman tree». تعداد تکرارها و کد هر حرف، به همراه همان حرف در جدول زیر آمده‌است. رمز کردن این جمله به کمک این کد، به 135 بیت نیاز دارد.]]
 
 
 
[[پرونده:Huffman tree 2.svg|left|thumb|350px|درخت هافمن، ایجاد شده از تعداد تکرار حرف‌های جملهٔ «this is an example of a ‌Huffman tree». تعداد تکرارها و کد هر حرف، به همراه همان حرف در جدول زیر آمده‌است. رمز کردن این جمله به کمک این کد، به 135 بیت نیاز دارد.]]
 
==== '''[[کدگذاری هافمن]]:''' ====
سطر ۲۷۸ ⟵ ۲۷۵:
==== '''[[الگوریتم_دکسترا|الگوریتم دایسترا (دکسترا)]]:''' ====
این الگوریتم در سال 1956 توسط [[ادسخر_دیکسترا|ادسخر دکسترا]] (Edsger Dijkstra) اثبات شد؛ که جزو الگوریتم‌های [[پیمایش گراف|جستجوی گراف]] است، و سؤالاتی چون [[مسئله یافتن کوتاه‌ترین مسیر|کوتاه‌ترین مسیر از یک رأس]] در [[گراف وزن‌دار|گراف‌های بدون وزن منفی]] را حل می‌کند. همچنین در [[مسیریابی (شبکه)|مسیریابی]] (routing) و به عنوان یک [[رویه (علوم رایانه)|زیرروال]] (subroutine) در الگوریتم‌های دیگر [[گراف (ریاضی)|گراف]] استفاده می‌شود. <ref>{{پک| Jesse Russell- Ronald Cohn|2012|ک=Dijkstra's Algorithm}}</ref>
 
 
 
 
 
 
 
 
<br /><syntaxhighlight lang="python" line="1">
def dijkstra(Adj, w, s):