الگوریتم حریصانه: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Haniyeh120 (بحث | مشارکت‌ها) |
Haniyeh120 (بحث | مشارکت‌ها) |
||
خط ۲۵۰:
روش‌های [[الگوریتم پریم|پریم]] و [[الگوریتم کراسکال|کروسکال]] دو روش مشهور تولید درخت پوشای کمینه از یک [[گراف وزن‌دار]] هستند که از روش حریصانه بهره می‌برند. منظور از درخت پوشای کمینه، [[درخت پوشا]]<nowiki/>یی از گراف است که مجموع وزن یال‌های آن کمتر یا مساوی مجموع وزن یال‌های سایر درخت‌های پوشای آن گراف است.<ref>{{پک|ابراهیم علایی فرادنبه - محمدرضا علایی|۱۳۹۲|ک=طراحی الگوریتم ایران|ص=265}}</ref>
[[پرونده:Huffman tree 2.svg|left|thumb|350px|درخت هافمن، ایجاد شده از تعداد تکرار حرف‌های جملهٔ «this is an example of a huffman tree». تعداد تکرارها و کد هر حرف، به همراه همان حرف در جدول زیر آمده‌است. رمز کردن این جمله به کمک این کد، به 135 بیت نیاز دارد.]]
==== '''[[کدگذاری هافمن]]:''' ====
کدگذاری هافمن یک الگوریتم [[مقایسه داده‌ها|مقایسهٔ داده]] است که از الگوریتم حریصانه برای پیاده‌سازی استفاده می‌کند و بر اساس تعداد تکرارهای یک [[نویسه (رایانه)|کاراکتر]] در یک [[پرونده (رایانه)|فایل]] است. این کدگذاری در فشرده‌سازی اطلاعات به کار می‌رود و با کدگذاری مجدد کاراکترهای موجود در اطلاعات بر اساس میزان استفاده‌ی آن‌ها، سعی در کم کردن حجم فایل می‌کند. بر اساس این روش، کاراکتری با استفاده‌ی بالا با کد کوتاهتر و کاراکتری با استفاده‌ی کم با کد طولانی‌تر جایگزین می‌شود. <ref>{{پک|Richard E. Neapolitan, Kumarss Naimipour|2004|ک=Foundations of Algorithms Using Java Pseudocode|ص=169}}</ref>
==== '''[[الگوریتم_دکسترا|الگوریتم دایسترا (دکسترا)]]:''' ====
| |||