الگوریتم مسیریابی:

در شبکه‌هاي کوچک، و در نقاطي که انتقال اطلاعات معمولا مستقيم است، مسيريابي چندان جدي گرفته نمي‌شود. اما هنگامي که شبکه‌ها از حالت‌هاي ايستگاه‌هاي کاري خارج مي‌شوند و کمي پيچيده‌تر مي‌شوند، در اين حالت، مسيريابي و انتخاب مسير بهينه براي ارسال بسته‌هاي اطلاعاتي، به يک امر مهم بدل مي‌شود. در شبکه‌هاي بزرگ، دستگاه‌هايي به‌عنوان مسيرياب1 وجود دارند که عمل مسيريابي را انجام مي‌دهند.

الگوريتم مسيريابي‌اي مناسب است که 6 ويژگي زير را داشته باشد: صحت عملکرد2، سادگي3، قابليت اطمينان4، پايداري5، عدالت6 و بهينگي7.

بديهي است که الگوريتمي بهتر است که صحت عملکرد بالايي داشته باشد و در عين حال ساده باشد، اما چه الگوريتمي قابليت اتکاي خوبي دارد؟ الگوريتمي مناسب است که در گذشت زمان، با تغيير نرم‌افزارها و سخت‌افزارهاي شبکه و تغيير پروتکل‌ها، همچنان مسيريابي درستي ارائه دهد. همچنين مهم است که بعد از يک مدت زمان خاص، الگوريتم مسيريابي به حالتي پايدار برسد و همزمان با آن، مسيريابي بهينه‌اي داشته باشد و در ارسال بسته‌ها عدالت را رعايت کند.

الگوریتمهای LS :

در الگوریتمهای LS ،هر روتر میبایست مراحل ذیل را به انجام رساند:

روترهای را كه به لحاظ فیزیكی به آنها متصل میباشد را شناسایی نموده و هنگامی كه شروع به كار میكند آدرسهایIP آنها بدست آورد. این روتر ابتدا یك بسته HELLO را روی شبكه ارسال میكند. هر روتری كه این بسته را دریافت میكند از طریق یك پیام كه دارای آدرس IP خود این روتر میباشد به پیام HELLO پاسخ میدهد.

زمان تاخیر مربوط به روترهای مجاور را اندازه گیری نماید(یا هر پارامتر مهم دیگری از شبكه همانند ترافیك متوسط)

برای انجام این كار ،روترها بسته های echo را روی شبكه ارسال میكنند. هر روتری كه این بسته ها را دریافت میكند با یك بسته echo reply به آن پاسخ میدهد.با تقسیم زمان مسیر رفت و برگشت به دو،روترها میتوانند زمان تاخیر را محاسبه كنند.(زمان مسیر رفت و برگشت،سنجشی از تاخیر فعلی روی یك شبكه میباشد)توجه داشته باشید كه این زمان شامل زمانهای ارسال و پردازش میباشد.

اطلاعات خود را در مورد شبكه،برای استفاده سایر روترها منتشر نموده و اطلاعات روترهای دیگر را دریافت كند.

در این مرحله همه روترها دانش خود را با روتر های دیگر به اشتراك گذاشته و اطلاعات مربوط به شبكه را با یكدیگر مبادله میكنند.با این روش هر روتر میتواند در مورد ساختار و وضعیت شبكه اطلاعات كافی بدست آورد.

با استفاده از این الگوریتم مناسب،بهترین مسیر بین هر دو گره از شبكه راشناسایی كند.

در این مرحله،روترها بهترین مسیر تا هر گره را انتخاب میكنند.آنها این كار را با استفاده از یك الگوریتم همانند الگوریتم كوتاهترین مسیر Dijkstra انجام میدهند.در این الگوریتم،یك روتر مبتنی بر اطلاعاتی كه از سایر روترها جمع آوری نموده است،گرافی از شبكه را ایجاد مینماید.این گراف مكان روترهای موجود در شبكه و نقاط پیوند آنها را به یكدیگر نشان میدهد.هر پیوند با یك شماره به نام Costیاweight مشخص میشود.این شماره تابعی از زمان تاخیر،متوسط ترافیك و گاهی اوقات تعداد hopهای بین گره ها میباشد.برای مثال اگر دو پیوند بین یك گره و مقصد وجود داشته باشد،روتر پیوندی با كمترین Weight را انتخاب میكند.

 الگوریتم شاخه وقید:

روش شاخه و قید با ایجاد درختی از زیرمسأله ها با توجه به مسأله اولیه و پیمایش درخت بدون قاعده خاصی، دنبال جواب های مسأله می گردد. این روش شكل بهبود یافته ای از الگوریتم عقبگرد است كه در آن شیوه خاصی را برای ملاقات گره ها اعمال نمی كند و در هر گره برای امیدبخش بودن آن گره، قید یا عددی را محاسبه می كند و فقط برای مسائل بهینه سازی استفاده می شود. به عنوان مثال مسأله كوله پشتی صفر و یك، بهترین جست وجو با هرس كردن، ایجاد یك تور بهینه و محاسبه طول آن، مسأله فروشنده دوره گرد و استنباط با عكس العمل استفاده از روش شاخه و قید اجرا می شود.

الگوریتم جست وجو و پیمایش :

این روش روی دو گروه از مسائل قابل اعمال هستند:

۱) روش های پیمایش

در روش های پیمایش، باید تك تك گره های یك درخت دودویی برای بررسی مقادیر عددی آنها ملاقات و بررسی جست وجو شوند.

۲) روش های جست وجو

روش های جست وجو كه حالت عمومی تری نسبت به روش های پیمایش هستند، می توانند روی رئوس یك گراف اعمال شوند.

جست وجو و پیمایش در درخت های دودویی و جست وجو و پیمایش گراف ها به صورت عرضی یا عمقی به وسیله این الگوریتم ها قابل حل هستند.

الگوریتم عقبگرد:

 الگوریتم عقبگرد، برای یافتن جواب مسأله ای با فضای جست وجو به طور گسترده ای به كار می رود و از آن به عنوان حالت اصلاح شده جست وجوی عمقی یك درخت نام می برند. در این روش، منظور از عقبگرد، پیدا كردن راه حل مسأله از طریق جست وجوی عمقی در درخت فضای حالت برای یافتن گره های امید بخش است. در صورتی كه موقع پیمایش درخت به یك گروه غیرامیدبخش برخورد كند كه منجر یه یافتن جواب مسأله نمی شود، باید به سمت ریشه درخت برگشته و عمل جست وجو را در دیگر شاخه ها ادامه داد. این فرآیند را هرس كردن درخت فضای حالت می نامند.

به عنوان مثال، مسأله n وزیر، استفاده از الگوریتم مونت كارلو برای نخستین كارآیی یك الگوریتم عقبگرد، مسأله حاصل جمع زیرمجموعه ها، مسأله رنگ آمیز گراف، مسأله مدارهای هامیلتونی، مسأله كوله پشتی صفر و یك با استفاده از راهبرد عقبگرد، قابل حل هستند.

الگوریتم های حریصانه:

الگوریتم های حریصانه مشابه برنامه نویسی پویا، بیشتر برای حل مسائل بهینه سازی به كار می روند. با این اختلاف كه در برنامه سازی پویا از یك رابطه بازگشتی برای حل زیرمسأله ها استفاده می كنند. در روش حریصانه، تقسیم مسأله ها به زیر مسأله ها انجام نمی گیرد و روش تكرارشونده را به كار می برند.

در روش حریصانه در هر لحظه، با توجه به عناصر داده ای مفروض، عنصری را كه دارای ویژگی بهترین یا بهینه است (مانند كوتاه ترین مسیر، بالاترین ارزش، كمترین سرمایه گذاری، بیشترین سود و ...) انتخاب می كنند بدون این كه انتخاب های قبلی ما بعدی را در نظر بگیرد ولی انتخاب های بهینه محلی همواره منجر به راه حل بهینه سراسری نمی شود. این روش انتخاب، منجر به ارائه یك الگوریتم ساده و كارآمد می شود.

تعیین درخت های پوشالی مینیمم با استفاده از الگوریتم های پرایم، كروسكال محاسبه كوتاه ترین مسیر تك منبع با كاربرد الگوریتم دایجسترا ، مسأله زمان بندی مانند بهینه سازی زمان انتظار و سرویس به كاربران برای دسترسی به دیسك گردان ها در یك شبكه رایانه ای، تعیین حداكثر بهره برای مشتریان در یك زمان معین و مسأله كوله پشتی (كسری، صفرو یك) با استفاده از روش حریصانه قابل اجرا هستند.

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

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

الگوریتم فلوید برای تعیین كوتاه ترین مسیر، ضرب زنجیری ماتریس ها، درخت های جست وجوی دورویی بهینه حاصل جمع بهینه لیستی از n عدد حقیقی، تعیین طولانی ترین زیر مشترك در دو رشته دلخواه و مسأله فروشنده دوره گرد (TSP) با استفاده از روش برنامه نویسی پویا قابل انجام هستند.

الگوریتم های ترتیبی:

در این گروه از الگوریتم ها، رایانه فقط از یك پردازنده برای اجرای دستورالعمل ها به صورت ترتیبی (سریال) استفاده می كند. در این نوع رایانه ها كه به نام معماری فون نیومن معروف است، برنامه و داده ها در حافظه ذخیره می شوند. ریزپردازنده هر بار یكی از دستورات برنامه را بازیابی كرده، پس از تفسیر آن را اجرا می كند. چنین رایانه هایی را SLSD (جریان تك دستوری، جریان تك داده ای) می گویند. در اینجا به ۲ روش از الگوریتم های ترتیبی اشاره می شود.

▪ روش تقسیم و حل

در این روش، با استفاده از رویه های بازگشتی، مسأله اصلی را به زیرمسأله های كوچكتری تا جایی تقسیم می كنند كه امكان تقسیم مجدد آن وجود نداشته باشد. سپس با حل ساده ترین زیرمسأله ها و تركیب آنها با یكدیگر می توان به حل مسأله اصلی نائل شد. رویه بازگشتی، الگوریتمی است كه با استفاده از فراخوانی خودرویه، دستورات تشكیل دهنده آن را تا رسیدن به شرایط اولیه و خروج از آن، مكرر اجرا كند.

روش تقسیم و حل، یك روش طراحی بالا به پائین است، یعنی الگوریتم یك مسأله از سطح بالا به زیرمسأله ها تقسیم بندی می شود. به عنوان مثال می توان الگوریتم های جست وجوی دورویی در یك بردار (آرایه یك بعدی) یا در یك جدول (آرایه دوبعدی) ، مرتب سازی تركیب و مرتب سازی سریع ، مسأله برج های هانوی ، ضرب «ماتریس به روش استراسن»، عملیات محاسباتی مانند ضرب و جمع اعداد صحیح بسیار بزرگ و جدول مسابقات تیم ها در یك جام حذفی را با استفاده از روش تقسیم و حل انجام داد.

الگوریتم مورچگان:

الگوریتم مورچه گان از آزمایشی كه توسط Goss و همكارانش (Goss et al.,1989) با استفاده از یك كلونی ازمورچه های واقعی ترتیب داده بودند، الهام گرفته شد. آمد و شد یك كلونی آزمایشگاهی از مورچه های آرژانتینی كه از طریق یک پل با دو شاخه با طولهای متفاوت كه یك منبع غذایی را به لانه متصل می كرد، مورد مشاهده قرار گرفت. شكل 1 این ارتباط را به تصویر كشیده است. شاخه ها به صورتی قرار داده شده بودند كه مورچه ها درهر جهت (از لانه به منبع غذایی و یا برعكس) می بایست یكی از این دو شاخه را برای ادامه مسیر انتخاب می كردند.
مشاهدات تجربی نشان داد كه بعد از یك مرحله گذرا كه می تواند فقط چند دقیقه ادامه داشته باشد، اغلب مورچه ها مسیر كوتاهتر را انتخاب می كنند. همچنین مشاهده شده است كه احتمال انتخاب مسیر كوتاهتر توسط كلونی با تفاوت در طول بین دو شاخه افزایش می یابد. در حقیقت، مورچه های آرژانتینی درحالیكه از لانه به سمت منبع غذایی حركت می كنند و بالعكس، یك ماده شیمیایی كه فرومون نامیده می شود، بر روی مسیر از خود بر جای می گذارند. هنگامیكه آنها به یك نقطه تصمیم می رسند (نظیر تقاطع بین شاخه كوتاهتر وشاخه بلندتر)، بر پایه احتمال یك مسیر را انتخاب می كنند كه احتمال انتخاب هر شاخه متناسب با اثر مقدار فرمونی است كه روی آن شاخه باقی مانده است. میزان فرومون هر شاخه از طریق حس بویایی مورچگان تشخیص داده می شود. این رفتار مورچه ها، یك اثر خودشتابی دارد. زیرا واقعیت انتخاب یك مسیر توسط چند مورچه، احتمال آنکه مورچه های دیگر نیز آن مسیر را انتخاب نمایند، افزایش می دهد.

شکل 1: ارتباط دو شاخه از یک لانه موچگان به یک منبع غذایی
در ابتدای آزمایش هیچ فرومونی روی دو شاخه نیست. بنابراین مورچه هایی كه از لانه به سمت منبع غذایی حركت می كنند هر یك از شاخه ها را با احتمال 50 درصد انتخاب خواهند كرد. به دلیل تفاوت در طول شاخه ها، مورچه هایی كه شاخه كوتاهتر را انتخاب می كنند، اولین مورچه هایی خواهند بود كه به منبع غذایی دست پیدا خواهند كرد. هنگامیكه این مورچه ها در مسیر بازگشت خودشان به لانه، به نقطه تصمیم (محل انشعاب دو شاخه از مسیر اصلی) می رسند، مقداری فرومون روی شاخه كوتاهتر خواهند یافت (این در حقیقت همان فرومونی است كه آنها در هنگام عزیمت از لانه به منبع غذایی از خود بر جای گذاشته اند) و بنابراین مسیر كوتاهتر را با احتمال بیشتری نسبت به مسیر بلندتر انتخاب خواهند كرد. بنابراین فرومون جدیدی روی مسیر انتخاب شده رها خواهد شد و این خود دلیلی بری جذابتر شدن این مسیر برای مورچه های بعدی خواهد بود. درحالیكه این فرآیند تكرار می شود، فرومون روی شاخه كوتاهتر نسبت به شاخه بلندتر با نرخ بیشتری ریخته می شود، لذا مسیر كوتاهتر به دفعات بیشتر و بیشتری توسط مورچه ها انتخاب خواهد شد، تا سرانجام تمام مورچه ها از این مسیر استفاده كنند. در ادامه به این بحث خواهیم پرداخت كه چگونه این ایده ساده می تواند زمینه را برای جستجوی جواب مسایل بهینه یابی پیچیده به وسیله مورچه های مصنوعی فراهم نماید.
رئوس پایه ای
در این قسمت یك الگوریتم بسیار ساده مورچه مدار ارائه می شود تا بوسیله آن رفتار پایه ای روش فراابتكاری ACO بیان گردد و مؤلفه های اصلی آن نشان داده شود.
كار اصلی هر مورچه مصنوعی (مانند مورچه های طبیعی)، جستجوی كوتاهترین مسیر بین یك جفت گره در شبكه ایست كه مساله به طور مناسبی در قالب آن شبكه بیان شده است. G=(N,A) یك شبكه همبند با n=[N] گره است. الگوریتم ساده ACO یا S-ACO می تواند برای یافتن یك راه حل برای مساله كوتاهترین مسیر كه روی شبكه G تعریف شده باشد، مورد استفاده قرار گیرد. جواب مساله مسیری خواهد بود كه گره منبع f را به گره مقصد d متصل كند. در ضمن طول مسیر بوسیله تعداد پرشها در مسیر داده شده است.

شکل 2: مورچه ها مسیر پررنگ تر را برای عبور از مبدأ به مقصد انتخاب می کنند.

به هر سویه (i,j) از شبكه یك متغیر τij مرتبط شده است كه اثر فرمون مصنوعی نامیده می شود. از این پس ما فقط از عبارت "اثر فرومون" و یا برای تلخیص بیشتر از "فرومون " به جای "اثرفرومون مصنوعی" استفاده خواهیم كرد. اثرات فرومونی بوسیله مورچه ها نوشته (برجای گذاشته) می شود و خوانده (بوئیده) می شود. مقدار (شدت) اثر فرومون متناسب با مطلوبیت استفاده از آن سویه ایست كه برای ساختن جواب به كار می رود.
هر مورچه یك سیاست تصمیم گیری با ساختار گام به گام برای ساختن جوابهای مساله به كار می برد. در هرگره از اطلاعات محلی با یك روش احتمالی جهت تصمیم گیری برای حركت به گره بعدی استفاده می شود. اطلاعات محلی یا در خود گره و یا روی سویه خروجی از آن گره نگهداری می شود.
قانون تصمیم گیری مورچه k ام كه درگره i قرار گرفته، از اثرات فرومونی τij برای محاسبه احتمالی انتخاب گره به عنوان گره بعدی، استفاده می كند. لازم به ذكر است كه در ابتدای فرآیند جستجو، یك مقدار فرومون τij به تمام سویه ها اختصاص داده شده است. Ni مجموعه گره ها همسایه گرهi است كه می توان به آنها عزیمت كرد.

مورچه ها درحالیكه یك جواب ایجاد می كنند، در همان حالت اطلاعات فرومونی را بر روی سویه هایی كه از آنها تشكیل جواب استفاده شده، برجای می گذارند. در S-ACO مورچه ها یك مقدار ثابت از فرمون Δτ بر جای می گذارند. توجه داشته باشید كه هنگامیكه یك مورچه در زمان t از گره i به گره j حركت می كند، مقدار فرومون τij سویه (i,j) را به صورت زیر تغییر خواهد داد.

به وسیله این قانون (كه مورچه های واقعی نیز بطور مشابه به همین صورت عمل
می كنند) مورچه ای كه سویه متصل كننده گره i به گره j مورداستفاده قرار می دهد، باعث افزایش احتمال انتخاب سویه (i,j) توسط مورچه های بعدی خواهد شد. در حالتیكه مورچه ها واقعی باشند، اثر خودشتابی و تفاوت بین طول مسیرها، همگرایی به سوی مسیر كوتاهتر را میسر می سازند.
به منظور اجتناب از همگرایی سریع همه مورچه ها به سمت یك مسیر بهینه جزئی، یك مكانیزم كاوش در نظر گرفته شده است. فرومون به صورت تبخیر كاهش می یابد و كاوش سویه های مختلف در طی كل فرآیند جستجو را میسر می سازد. تبخیر فرومون بصورت ساده ای انجام می شود. در ضمن كاهش اثرات فرومونی بصورت تصاعدی انجام می پذیرد. در هر تكرار الگوریتم داریم:

آزمایش های مقدماتی انجام شده بوسیله S-ACO از یك مدل شبكه ساده استفاده می كرد كه در شكل 2 نشان داده شده است. الگوریتم عملاً كوتاهترین مسیر شبیه سازی شده بین لانه و منبع غذایی را پیدا می كند. همچنین آزمایشها نشان داده كه اگر پیچیدگی شبكه جستجو شده افزایش یابد، رفتار الگوریتم ناپایدار خواهد شد و مقادیر به دست آمده نیز یكسان نخواهد بود. در این حالت مقادیر پارامترها موضوع مهمی خواهند بود. به عنوان مثال اگر بین لانه و منابع غذایی راههایی بیشتر قرارداده شود، این نوع پیچیدگی بوجود خواهد آمد. به منظور درك بهتر مطالب ذكر شده توجه داشته باشید كه اگر مقدار فرومون بر جای گاشته شده بوسیله مورچه ها را متناسب با كیفیت جوابی كه ساخته اند، قرار دهیم در این صورت اطلاعات فرومونی برای هدایت جستجوی مورچه ها بسیار مفید واقع خواهد شد. همچنین بدلیل اینكه در خیلی از مسائل، انواع مختلفی از اطلاعات قابل تحصیل در گره ها در دسترس است، مطلوب خواهد بود كه مورچه ها توانایی استفاده از آنها را داشته باشند. نكته جالب توجه دیگر این است كه سطح مسائلی كه بوسیله ACO به آنها پرداخته می شود می تواند بزرگتر شود، در حالیكه S-ACO بدون در نظر گرفتن محدودیتهای اضافی، صرفاً برای مسائل كوتاهترین مسیر می تواند مورد استفاده قرار گیرد.

الگوریتم وارشال:

الگوريتم وارشال:وریتم فلوید-وارشال یک الگوریتم تحلیل گراف برای پیدا کردن کوتاهترین مسیر در یگ گراف جهتدار و وزن دار می‌باشد .با یکبار اجرای این الگوریتم کوتاهترین مسیر بین همهٔ جفت راس‌ها پیدا خواهد شد. الگوریتم فلوید-وارشال به نام استفن وارشال ^[۱] و روبرت فلوید ^[۲] نامگذاری شده‌است. این الگوریتم یک مثال از برنامه نویسی پویا می‌باشد.

الگوریتم وارشال همهٔ مسیرهای ممکن در یک گراف , بین هر جفت از راس هارا مقایسه می‌کند. این الگوریتم قادر است این کار را تنها با V² مقایسه انجام دهد. این ملاحظه قابل توجهی می‌باشد که در یک گراف V² یال وجود داشته باشد وهر ترکیبی از یالها چک شده باشد. یک گراف G با راس‌های Vi که i از 1 تا N می‌باشد را در نظر بگیرید. علاوه بر این یک تابع به نام (shortestPath(i,j,k را در نظر بگیرید که کوتاهترین مسیر ممکن از i تا j را با استفاده از راس‌های 1 تا k که به عنوان راسهای میانی در امتداد مسیر می‌باشند را بر می‌گرداند.

هم اکنون این تابع داده شده‌است .هدف ما پیدا کردن کوتاهترین مسیر از هر i تا هر j تنها با استفاده از راسهای 1 تا 1+k می‌باشد. دو کاندیدا برای این مسیر وجود دارد :

1-کوتاهترین مسیری که فقط از راس‌های موجود در مجموعه ی(k,........,1) استفاده می‌کند.

2-تعدادی مسیر که از i تا 1+k و سپس از 1+k تا j می‌روند وجود دارد که این مسیر بهتر می‌باشد.

الگوریتم مرتب‌سازی:

 در علوم کامپیوتر و ریاضی، الگوریتمی است که لیستی از داده‌ها را به ترتیبی مشخص می‌چیند.

پر استفاده‌ترین ترتیب‌ها، ترتیب‌های عددی و لغت‌نامه‌ای هستند. مرتب‌سازی کارا در بهینه سازی الگوریتم‌هایی که به لیست‌های مرتب شده نیاز دارند (مثل جستجو و ترکیب) اهمیت زیادی دارد.

از ابتدای علم کامپیوتر مسائل مرتب‌سازی تحقیقات فراوانی را متوجه خود ساختند، شاید به این علت که در عین ساده بودن، حل آن به صورت کارا پیچیده‌است. برای مثال مرتب‌سازی حبابی در سال ۱۹۵۶ به وجود آمد. در حالی که بسیاری این را یک مسئلهٔ حل شده می‌پندارند، الگوریتم کارآمد جدیدی همچنان ابداع می‌شوند (مثلاً مرتب‌سازی کتاب خانه‌ای در سال ۲۰۰۴ مطرح شد).

مبحث مرتب‌سازی در کلاس‌های معرفی علم کامپیوتر بسیار پر کاربرد است، مبحثی که در آن وجود الگوریتم‌های فراوان به آشنایی با ایده‌های کلی و مراحل طراحی الگوریتم‌های مختلف کمک می‌کند؛ مانند تحلیل الگوریتم، داده‌ساختارها، الگوریتم‌های تصادفی، تحلیل بدترین و بهترین حالت و حالت میانگین، هزینهٔ زمان و حافظه، و حد پایین.

طبقه بندي:

در علم کامپیوتر معمولاً الگوریتم‌های مرتب‌سازی بر اساس این معیارها طبقه‌بندی می‌شوند:

• پیچیدگی (بدترین و بهترین عملکرد و عملکرد میانگین): با توجه به اندازهٔ لیست (n). در مرتب‌سازی‌های معمولی عملکرد خوب (O(n log n و عملکرد بد (O(n^۲ است. بهترین عملکرد برای مرتب‌سازی (O(n است. الگوریتم‌هایی که فقط از مقایسهٔ کلیدها استفاده می‌کنند در حالت میانگین حداقل (O(n log n مقایسه نیاز دارند.
• حافظه (و سایر منابع کامپیوتر) : بعضی از الگوریتم‌های مرتب‌سازی «در جا» هستند. یعنی به جز داده‌هایی که باید مرتب شوند، حافظهٔ کمی ((O(۱) مورد نیاز است؛ در حالی که سایر الگوریتم‌ها به ایجاد مکان‌های کمکی در حافظه برای نگه‌داری اطلاعات موقت نیاز دارند.
• پایداری: الگوریتم‌های مرتب‌سازی پایدار ترتیب را بین داده‌های دارای کلیدهای برابر حفظ می‌کنند. فرض کنید می‌خواهیم چند نفر را بر اساس سن با یک الگوریتم پایدار مرتب کنیم. اگر دو نفر با نام‌های الف و ب هم‌سن باشند و در لیست اولیه الف جلوتر از ب آمده باشد، در لیست مرتب شده هم الف جلوتر از ب است.
• مقایسه‌ای بودن یا نبودن. در یک مرتب‌سازی مقایسه‌ای داده‌ها فقط با مقایسه به وسیلهٔ یک عملگر مقایسه مرتب می‌شوند.
• روش کلی : درجی، جابجایی، گزینشی، ترکیبی و غیره. جابجایی مانند مرتب‌سازی حبابی و مرتب‌سازی سریع و گزینشی مانند مرتب‌سازی پشته‌ای.

الگوریتم مرتب سازی حبابی:

اين الگوريتم ساده ترين و معروف ترين الگوريتم براي مرتب سازي داده است.

فرض کنید می‌خواهیم n داده به صورت صعودی مرتب شوند. عنصر اول را با با عنصر دوم مقایسه کرده، و در صورتی که عنصر اول بزرگتر باشد باشد جای عنصر اول و دوم را عوض می‌کنیم. همین کار را با عناصر دوم و سوم انجام می‌دهیم و همینطور عناصر سوم و چهارم ، الی آخر. وقتی این کار تمام شد بزرگ‌ترین عنصر بین داده‌ها به آخر لیست می‌رسد . حالا یک بار دیگر از اول این کار را انجام می‌دهیم اما این بار تا عنصر (n -۱)ام ادامه می‌دهیم (عنصر nام در مرحله اول در جای خودش قرار گرفته). باز هم این کار را تا عنصر (n - ۲)ام تکرار می‌کنیم ، و بازهم .... تا اینکه بالاخره داده‌ها مرتب می‌شوند.

مثلا:

۰ - ۰)    ۵ ۶ ۴ ۲

۱ - ۱)    ۵ ۶ ۴ ۲

۱ - ۲)    ۵ ۴ ۶ ۲

۱ - ۳)    ۵ ۴ ۲ ۶

۲ - ۱)    ۴ ۵ ۲ ۶

۲ - ۲)    ۴ ۲ ۵ ۶

۳ - ۱)    ۲ ۴ ۵ ۶

مرحله اول سه مقایسه ، مرحله دوم دو مقایسه و مرحله سوم یک مقایسه داره ، که روی هم می‌شوند شش مقایسه. در کل این روش n (n - ۱) / ۲ مقایسه لازم داره. اما نه همیشه. به مثال زیر توجه کنید:

۰ - ۰)    ۰ ۷ ۱ ۳ ۵ ۴

۱ - ۱)    ۰ ۱ ۷ ۳ ۵ ۴

۱ - ۲)    ۰ ۱ ۷ ۳ ۵ ۴

۱ - ۳)    ۰ ۱ ۳ ۷ ۵ ۴

۱ - ۴)    ۰ ۱ ۳ ۵ ۷ ۴ 

۱ - ۵)    ۰ ۱ ۳ ۵ ۴ ۷ 

۲ - ۱)    ۰ ۱ ۳ ۵ ۴ ۷

۲ - ۲)    ۰ ۱ ۳ ۵ ۴ ۷

۲ - ۳)    ۰ ۱ ۳ ۵ ۴ ۷

۲ - ۴)    ۰ ۱ ۳ ۴ ۵ ۷ 

۳ - ۱)    ۰ ۱ ۳ ۴ ۵ ۷

۳ - ۲)    ۰ ۱ ۳ ۴ ۵ ۷

۳ - ۳)    ۰ ۱ ۳ ۴ ۵ ۷

۴ - ۱)    ۰ ۱ ۳ ۴ ۵ ۷

۴ - ۲)    ۰ ۱ ۳ ۴ ۵ ۷

۵ - ۱)    ۰ ۱ ۳ ۴ ۵ ۷

همونطور که می‌بینید انتهای مرحله ۲ داده‌ها مرتب هستن. تشخیص این مساله هم کار سختی نیست: اگه به مرحله‌ای رسیدیم که هیچ جابجایی در اون رخ نداد نتیجه می‌شه که داده‌ها مرتب هستن (مرحله سوم). پس بعد از مرحله ۳ مطمئن می‌شیم که داده هامون مرتب شدن و نیازی به مراحل ۴ و ۵ نیست.

الگوریتم پریم:

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

الگوریتم پریم برای ساخت درخت پوشای کمینه از یک گراف به کار می رود . درخت پوشای کمینه ، زیر گرافی از یک گراف موزون است که شامل تمام رئوس گراف و برخی یال های آن می باشد به طوری که مجموع اوزان آن درخت نسبت به سایر درخت های ممکن حداقل شود .( می دانیم که معادل عدد کاتالان می توان می توان با N راس درخت ایجاد کرد . )

الگوریتم پریم در هر مرحله : یالی با کمترین وزن را انتخاب می کند به طوری که:

الف ) کم ترین وزن را میان سایر یال ها داشته باشد

ب) قبلا انتخاب نشده باشد

ج) با یال های انتخابی قبلی تشکیل دور ندهد ( زیرا در این صورت درخت نیست . ) . این الگوریتم در هر مرحله یک درخت ایجاد می کند .

سایر الگوریتم ها را می توانید در کتب طراحی الگوریتم بیابید .

الگوریتم فلوچارت:

فلوچارت یا روندنما (به انگلیسی: Flowchart) نموداری است برای نمایش داده‌ها، اطلاعات و روند کار یک الگوریتم بر روی آنها، به‌وسیله نمادهای خاصی و خطوط جهت‌دار بین آنها.

فلوچارت به چه کاری می‌آید؟

فلوچارت در واقع نقشه‌ای است که برنامه‌نویسان رایانه قبل از نوشتن برنامه به زبان برنامه‌نویسی اصلی آن را ترسیم می‌کنند. با مروری بر فلوچارت روند اجرای عملیات، مراحل و جزئیات برنامه و ورودی و خروجی هر مرحله از برنامه مشخص می‌شود. استفاده از فلوچارت جهت حل هر مسئله‌ای مفید است و بدون در نظر گرفتن زبان برنامه‌نویسی، نوشتن برنامه را سهولت می‌بخشد. علاوه بر این فلوچارت جزئی باارزش از مستندات هر برنامه می‌باشد که با کمک آن تفسیر برنامه، عیب‌یابی و استفاده توسط شخصی به جز برنامه‌نویس را آسان می‌کند. برای رسم فلوچارت آگاهی و تسلط بر مراحل مورد نیاز و ترتیب آنها جهت به دست آوردن نتیجه مورد نظر با استفاده از داده‌های ورودی به الگوریتمی که فلوچارت برای آن کشیده می‌شود، لازم است. البته فلوچارت كاربردهاي ديگري در علوم ديگر و حتي در زندگي هم دارد. درحقيقت شايد بتوان گفت هر الگوريتمي يك فلوچارت دارد و زندگي نيز نوعي الگوريتم است پس زندگي نيز فلوچارت دارد!

نمادهای مورد استفاده

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

• آغاز و پایان

• ورودی و خروجی

• رابط
• تصمیم گیری (شرطی)

• پردازش

• فراخوانی زیرالگوریتم

• توضیحات اضافی و کمکی
• تلفیق
• ادغام
• استخراج
• ...

 

الگوریتم های تصادفی:

الگوریتم تصادفی: به الگوریتمی گفته می‌شود که رفتارش نه تنها به ورودی اش بلکه همچنین با مقادیر تولید شده توسط یک مولد تصادفی تعیین می‌شود.بنابراین در این نوع الگوریتم فرض می کنیم که ماشینی که در آن الگوریتم خود را پیاده سازی می کنیم باید دارای تولید کنندهٔ اعداد تصادفی باشد.

الگوریتم هافمن:

الگوریتم فشرده سازی هافمن را دیوید هافمن پروفسور دانشگاه MIT (Massachusetts

Institute of

Technology) آمریکا اختراع کرد. روش فشرده سازی هافمن الگوریتمی است که برای فشرده

سازی

متن مناسب می باشد.

الگوریتم هافمن جزو خانوادهء الگوریتم هایی است که طول کد متغییری دارند. این به آن

معناست که

نماد های مجزا (برای نمونه کاراکترهایی در یک فایل متنی) با رشته بیت هایی که طول

های

مختلفی دارند تعویض می شود. بنابراین نماد هایی که زیاد در یک فایل تکرار می شوند

یک رشته

بیت کوتاه می گیرند در حالی که نمادهای دیگر که به ندرت دیده می شوند رشته بیت

طولانی تری را

می گیرند.

تاریخچه

در سال ۱۹۵۱ David.A.Huffman و هم شاگردی‌هایش در کلاس «تئوری اطلاعات» دانشگاه

MIT، حق انتخاب بین تحقیق در مورد یک مفهوم یا دادن امتحان پایانی را داشتند.استاد

Robert M. Fano موضوع تحقیق را مسالهٔ پیدا کردن کارآمد ترین کد دودویی تعیین کرد.

هافمن ناتوان در پیدا کردن کارآمد ترین، تصمیم گرفته بود خودش را برای امتحان

پایانی آماده کندکه ایده‌ای به ذهنش رسید. ایدهٔ استفاده از درخت دودیی مرتب شده بر

حسب تکرار(frequency) وتوانست اثبات کند که این کارآمد ترین روش است. در انجام این

کار، شاگرد از استادش که با مبدع تئوری اطلاعات، Claude Shannon برای ساختن کدی

مشابه کار کرده بود، پیشی گرفت. هافمن از مشکل اصلی روش کدگذاری نیم بهینهٔ

Shannon-Fano coding جلوگیری کرده، درخت را به جای ساختن از بالا به پایین، از

پایین به بالا ساخت.

کد‌گذاری هافمن

 یک الگوریتم کد‌گذاری برای فشرده‌سازی بی‌اتلاف اطلاعات است. این تعبیر بر می‌گردد

به استفاده از جدول کد طول متغیر برای کد کردن هر کدام از نشانه‌های مبدا (مانند

کاراکترهای یک فایل). جدول کد طول متغیر از روشی بخصوص مبنی بر احتمال وقوع هر کدام

از نشان‌های مبدا بدست می‌آید. این روش بوسیلهٔ دیوید هافمن توسعه یافت. وی دانشجوی

دورهٔ دکتری در دانشگاه MIT بود و در سال ۱۹۵۲ مقالهٔ «روشی برای تولید کدی با

کمترین تکرار زوائد» را منتشر کرد.

در کد کذاری هافمن، از روشی خاص برای انتخاب نحوهٔ نمایش هر نماد استفاده می‌شود.

روشی به نام کد‌های بدون پیشوند(گاهی هم روش «کدهای پیشوندی» گفته می‌شود. یعنی در

این روش رشته‌ای که نشان دهندهٔ یک کاراکتر خاص است هیچ گاه پیشوند رشتهٔ دیگر که

نمایانگر کاراکتری دیگر است، نمی‌باشد.).در این روش کاراکتر‌های پرکاربرد تر با

رشته‌های بیتی کوتاهتری نسبت به آن‌هایی که کاربردشان کمتر است، نشان داده می‌شوند.

هافمن موفق شد کارآمد ترین روش فشرده سازی از این نوع را طراحی کند: نگاشت نکردن

نشان‌های منفرد مبدا به رشته‌های بیتی یکتا، هرگاه تعداد تکرار نماد‌های اصلی با

آنهایی که برای ایجاد این کد مورد استفاده قرار گرفتند مطابقت کند، خروجی‌هایی با

اندازهٔ کمتر تولید می‌کند. بعدها روشی برای انجام این کار پیدا شد که این کار را

در زمانی خطی انجام می‌داد.

برای مجموعه‌ای از نمادها با توزیع احتمالی یکنواخت و تعداد عضو‌هایی برابر با

توانی از ۲، کد گذاری هافمن هم ارز با قطعه کد سادهٔ دوجمله‌ای است. مانند کد گذاری

ASCII. کد گذاری هافمن روشی متداول برای ایجاد کد‌های بدون پیشوند است بطوریکه

عبارت «کد هافمن» به گستردگی به عنوان مترادفی برای «کد بدون پیشوند» استفاده

می‌شود، هرچند چنین کدی با الگوریتم هافمن بدست نیامده باشد.

اگرچه کد گذاری هافمن برای کد کردن نماد به نماد بهینه‌است، اما گاهی کارآمدی آن

بیش از مقدار واقعی پنداشته می‌شود. برای مثال، کد کردن حسابی و کد کردن LZW، گاهی

توانایی بالاتری در فشرده سازی دارند.

کد قانونی هافمن

اگر وزن های مربوط به ورودی های مرتب شده بر اساس الفبا، به ترتیب عددی باشند، کد

هافمن طولی برابر طول کد الفبایی بهینه دارد که می‌تواند از طریق محاسبه بدست آید.

کد بدست آمده از ورودی های مرتب شده از نظر عددی ، کد قانونی هافمن گفته می‌شود و

کدی است که به خاطر سادگی رمز کردن و رمز گشایی ،در عمل استفاده می‌شود. تکنیک پیدا

کردن این کد ، اکثرا کد گذاری Huffman-Shannon-Fano نامیده می‌شود. و این به خاطر

آن است که مانند کدگذاری هافمن بهینه، ولی در احتمال وزن ها مانند کد

گذاریShannon-Fano coding الفبایی است. کد هافمن Shannon-Fano مربوط به این مثال

{000,001,01,10,11} است که در آن طول کد کلمه‌ها ، همان مقداری است که در حل اصلی

آمده است. 

کد هافمن با ارزش حرفی متفاوت

در کد گذاری استاندارد هافمن، فرض شده است که هر نماد در مجموعه‌ای که کد ها از آن

استخراج می‌شوند،ارزشی یکسان با بقیه دارد: کد کلمه‌ای که طول آن N است ارزشی برابر

N خواهد داشت ،مهم نیس که چند رقم آن 1 و چند رقم آن 0 است. وقتی با این فرض کار می

کنیم، کم کردن هزینهٔ کلی پیام ، با کم کردن تعداد رقم های کل 2 چیز یکسانند. کد

هافمن با ارزش حرفی متفاوت به نحوی عمومیت یافته که این فرض دیگر صحیح نیست: حروف

الفبای کدگذاری ممکن است طول های غیر همسانی داشته باشند ، به خاطر خصوصیت های

واسطهٔ انتقال. مثالی بر این ادعا،الفبای کد گذاری کد مورس است، که در آن فرستادن

یک 'خط تیره' بیشتر از فرستادن یک 'نقطه' طول می‌کشد ، پس ارزش خط تیره در زمان

انتقال بالاتر است. درست است که هدف هنوز کم کردن میانگین طول وزنی کد است اما دیگر

کم کردن تعداد نماد های بکار برده شده در پیام، به تنهایی کافی نیست. هیچ الگوریتمی

شناخته نشده است که این را به همان روش و همان کارآیی کد قراردادی هافمن انجام دهد.

انواع:

انواع مختلفی از کد گذاری هافمن وجود دارد، که بعضی از آنها از الگوریتم‌هایی شبیه

الگوریتم هافمن و بعضی دیگر از کد‌های بهینهٔ پیشوندی (با محدودیت‌های خاص برای

خروجی)استفاه می‌کنند. در حالت اخیر، نیاز نیست که روش، شبیه روش هافمن باشد و حتی

ممکن است زمان اجرایی چند‌جمله‌ای هم نداشته باشد. لیست کاملی از مقالات مربوط به

انواع مختلف کد گذاری هافمن، در «درخت‌های کد و تجزیه برای کد کردن بی زیان

اطلاعات» [۱] داده شده‌است. 

کد هافمن n تایی

الگوریتم کد هافمن n تایی از الفبای {۰, ۱,..., n − ۱} برای کد کردن پیام‌ها و

ساختن درخت n تایی استفاده می‌کند. این روش دسترسی بوسیلهٔ هافمن و در مقاله اش

بررسی شده بود.

کد هافمن انطباقی

نوع دیگری به نام کد هافمن انطباقی، احتمالاتی را که به صورت پویا و بر اساس تکرار

واقعی در منبع اصلی است، محاسبه می‌کند. این به گونه‌ای مربوط به خانوادهٔ

الگوریتم‌های LZ است.

الگوریتم الگوی هافمن

بیشتر اوقات، وزن‌های مورد استفاده در اجرای کد هافمن، نمایانگر احتمالات عددی است

ولی این الگوریتم چنین چیزی را نیاز ندارد بلکه فقط به راهی برای منظم کردن وزن‌ها

و اضافه کردن آنها نیازمند است. الگوریتم الگو هافمن امکان استفاده از هر نوع وزنی

را می‌دهد.(ارزش-تکرار-جفت وزن ها-وزن‌های غیر عددی) و هر کدام از روش‌های ترکیبی

مختلف. اینگونه الگوریتم‌ها می‌توانند مسائل فشرده سازی دیگر را نیز حل کنند.

کد هافمن با طول محدود

کد هافمن با طول محدود نوعی دیگر از کد هافمن است. این نوع هنگامی مورد استفاده

قرار می‌گیرد که هدف هنوز بدست آوردن طول مسیر با کمترین وزن است اما یک شرط دیگر

نیز وجود دارد و آن این است که اندازهٔ هر کد، باید کمتر از مقدار ثابت خاصی باشد.

الگوریتم بسته بندی-ادغام این مشکل را بوسیلهٔ یک الگوریتم حریصانه ساده شبیه به

همانی که در الگوریتم هافمن بکار رفته بود، حل می‌کند. پیچیدگی زمانی این الگوریتم

O(nL), که L ماکزیمم طول یک کدکلمه(codeword)است.

هیچ الگوریتمی شناخته نشده که این کا را در زمان linear or linearithmic انجام

دهد,بر خلاف مسائل پیش مرتب شده و مرتب نشدهٔ هافمن.

یک مثال کاربردی اجزای کار را به شما نشان می دهد.

فرض کنید می خواهید تکه اطلاعات زیر رافشرده کنید:

ACDABA

از آنجایی که 6 کاراکتر داریم، این متن 6 بایت یا 48 بیت می باشد. با رمز گزاری

هافمن، فایل برای

بیشترین تکرار ظاهر شدن نمادها (در این مثال نماد A سه بار تکرار می شود) جستجو می

شود و

سپس یک درخت ساخته می شود که نماد ها را با رشته بیت های کوتاه تر جایگزین می کند.

در این

حالت خاص الگوریتم از جدول جایگزینی زیر استفاده می کند:

A=0 , B=10 , C=110 , D=111.

اگر این کد برای فشرده سازی فایل استفاده شود، اطلاعات فشرده شده به صورت زیر در می

آیند:

01101110100

این به این معنی است که 11 بیت به جای 48 بیت مصرف شد. در این مثال خاص نسبت فشرده

سازی 4 به 1 می باشد.

رمزگزاری هافمن به دو روش مختلف می تواند بهینه تر شود:

1. کد هافمن انطباقی (Adaptive Huffman code) به صورت پویا کلمات کد را با توجه به

تغییر احتمال

وقوع نماد ها تغییر می دهد.

2. فشرده سازی گستردهء هافمن (Extended Huffman Compression) می تواند گروهی از

نماد ها را

نسبت به یک نماد رمز گزاری کند.

این روش می تواند بین 20% تا 90% اطلاعات را فشرده کند.

این الگوریتم فشرده سازی اساسا برای فشرده سازی متون و فایل های برنامه سودمند است.

کد گذاری به روش هافمن

کد گذاری به روش هافمن، روشی است برای بهینه سازی مقدار حجم استفاده شده برای

نگهداری داده های معلوم. 

همانطور که می دانید، هر کاراکتری در کامپیوتر با یک کد (با استاندارد اسکی بین 0

تا 255) نمایش داده می شود، فرض کنید برای نمایش حرف  A از عدد 65 استفاده شود، عدد

65 در مبنای 2 (که مبنای ذخیره سازی کامپیوتر های رقمی است) به صورت 1000001 در

خواهد آمد و در نتیجه به 7 بیت فضا برای ذخیره سازی نیاز دارد.

در این صورت رشته ی AAAAAAAA که متشکل از 8 حرف A است نیاز به فضایی معادل 8*7=56

بیت یا به بیان ساده تر 7 بایت  دارد.

دلیل اینکه ما کد 65 را برای حرف A انتخاب کردیم این است که (در استاندارد Ascii)

254 کاراکتر مجاز دیگر به جز A برای کامپیوتر ها در نظر گرفته شده است. اما در رشته

فوق از آنجا که میدانیم فقط یک نوع کاراکتر به کار رفته است، می توانیم این کد را

به طور قراردادی به کد کوتاهتری (مثلا 1) تغییر دهیم، در این صورت رشته ی فوق در

فضایی به طول 8*1=8 بیت یا به بیان ساده تر 1 بایت قابل ذخیره سازی است.

و اما اینکه چگونه کد جدید (در این مثال 1 به جای 65) را به دست بیاوریم توسط روش

Huffman بیان میشود.

روش هافمن:

1-   چگالی هر کاراکتر را محاسبه میکنیم (تعداد دفعات حضور کاراکتر در متن مورد

نظر).

2-   دو کاراکتر با کمترین میزان تکرار (چگالی) را انتخاب میکنیم.

3-   کاراکتر های مرحله 2 را با کاراکتر جدیدی که دارای چگالی برابر با مجموع چگالی

دو کاراکتر فوق است جایگزین میکنیم.

4-   تا زمانی که فقط یک کاراکتر باقی مانده باشد، به مرحله 2 میرویم.

5-   از عملیات فوق یک درخت حاصل می شود، بر روی این درخت هر مسیر به سمت چپ با 0 و

هر مسیر به سمت راست با 1 وزن دهی میشود.

6-   کد هر کاراکتر با کنار هم گذاشتن وزن ها از ریشه تا آن کاراکتر به دست می آید.

درعلوم کامپیوتر و تئوری اطلاعات، کد‌گذاری هافمن یک الگوریتم کد‌گذاری برای

فشرده‌سازی بی‌اتلاف اطلاعات است.

این تعبیر بر می‌گردد به استفاده از جدول کد طول متغیر برای کد کردن هر کدام از

نشانه‌های مبدا (مانند کاراکترهای یک فایل). جدول کد طول متغیر از روشی بخصوص مبنی

بر احتمال وقوع هر کدام از نشان‌های مبدا بدست می‌آید. این روش بوسیلهٔ دیوید هافمن

توسعه یافت. وی دانشجوی دورهٔ دکتری در دانشگاه MIT بود و در سال ۱۹۵۲ مقالهٔ «روشی

برای تولید کدی با کمترین تکرار زوائد» را منتشر کرد.

در کد کذاری هافمن، از روشی خاص برای انتخاب نحوهٔ نمایش هر نماد استفاده می‌شود.

روشی به نام کد‌های بدون پیشوند(گاهی هم روش «کدهای پیشوندی» گفته می‌شود. یعنی در

این روش رشته‌ای که نشان دهندهٔ یک کاراکتر خاص است هیچ گاه پیشوند رشتهٔ دیگر که

نمایانگر کاراکتری دیگر است، نمی‌باشد.).در این روش کاراکتر‌های پرکاربرد تر با

رشته‌های بیتی کوتاهتری نسبت به آن‌هایی که کاربردشان کمتر است، نشان داده می‌شوند.

هافمن موفق شد کارآمد ترین روش فشرده سازی از این نوع را طراحی کند: نگاشت نکردن

نشان‌های منفرد مبدا به رشته‌های بیتی یکتا، هرگاه تعداد تکرار نماد‌های اصلی با

آنهایی که برای ایجاد این کد مورد استفاده قرار گرفتند مطابقت کند، خروجی‌هایی با

اندازهٔ کمتر تولید می‌کند. بعدها روشی برای انجام این کار پیدا شد که این کار را

در زمانی خطی انجام می‌داد.

برای مجموعه‌ای از نمادها با توزیع احتمالی یکنواخت و تعداد عضو‌هایی برابر با

توانی از ۲، کد گذاری هافمن هم ارز با قطعه کد سادهٔ دوجمله‌ای است. مانند کد گذاری

ASCII. کد گذاری هافمن روشی متداول برای ایجاد کد‌های بدون پیشوند است بطوریکه

عبارت «کد هافمن» به گستردگی به عنوان مترادفی برای «کد بدون پیشوند» استفاده

می‌شود، هرچند چنین کدی با الگوریتم هافمن بدست نیامده باشد.

اگرچه کد گذاری هافمن برای کد کردن نماد به نماد بهینه‌است، اما گاهی کارآمدی آن

بیش از مقدار واقعی پنداشته می‌شود. برای مثال، کد کردن حسابی و کد کردن LZW، گاهی

توانایی بالاتری در فشرده سازی دارند.

تعریف مساله

 پیدا کنید: کد دودویی بدون پیشوند، (مجموعه‌ای از کدها) با کمترین امید ریاضی برای

طول کد.(به طور معادل، درختی با کمترین مسیر وزن دار)

تاریخچه در سال ۱۹۵۱ David.A.Huffman و هم شاگردی‌هایش در کلاس «تئوری اطلاعات»

دانشگاه MIT، حق انتخاب بین تحقیق در مورد یک مفهوم یا دادن امتحان پایانی را

داشتند.استاد Robert M. Fano موضوع تحقیق را مسالهٔ پیدا کردن کارآمد ترین کد

دودویی تعیین کرد. هافمن ناتوان در پیدا کردن کارآمد ترین، تصمیم گرفته بود خودش را

برای امتحان پایانی آماده کندکه ایده‌ای به ذهنش رسید. ایدهٔ استفاده از درخت دودیی

مرتب شده بر حسب تکرار(frequency) وتوانست اثبات کند که این کارآمد ترین روش است.

در انجام این کار، شاگرد از استادش که با مبدع تئوری اطلاعات، Claude Shannon برای

ساختن کدی مشابه کار کرده بود، پیشی گرفت. هافمن از مشکل اصلی روش کدگذاری نیم

بهینهٔ Shannon-Fano coding جلوگیری کرده، درخت را به جای ساختن از بالا به پایین،

از پایین به بالا ساخت.

الگوریتم‌های موازی:

در علوم کامپیوتر، برخلاف الگوریتم‌های متوالی سنتی، الگوریتم‌هایی هستند که در آنها، هر بار قسمتی از برنامه روی پردازنده‌ای متفاوت اجرا می‌شود و در آخر برای کسب نتیجهٔ مطلوب، نتایج کنار هم قرار می‌گیرند.

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

برخی از الگوریتم‌ها برای اجرای مراحل بعد، نیاز به نتایج مراحل قبل دارند. اینگونه مسائل را مسائل ذاتا متوالی می‌گویند. روش‌های عددی تکرار شونده، مانند روش نیوتون یا مسالهٔ سه تن، نمونه‌هایی از الگوریتم‌های متوالی هستند.

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

الگوریتم‌های موازی ارزشمندند زیرا اجرای عملیات محاسباتی بزرگ از طریق الگوریتم‌های موازی، به دلیل کارکرد پردازنده‌های مدرن، بسیار سریع تر از اجرای آنها با الگوریتم‌های متوالی است. ساخت یک کامپیوتر با یک پردازندهٔ خیلی سریع بسیار سخت تر از ساختن یک کامپیوتر با تعداد زیادی پردازندهٔ کندتر با توان عملیاتی یکسان است.

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

الگوریتم ژنتیک:

(Genetic- Algorithm - GA) تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیست‌شناسی فرگشتی مانند وراثت و جهش استفاده می‌کند.
الگوریتمهای ژنتیک معمولاً به عنوان یک شبیه‌ساز کامپیوتر که در آن جمعیت یک نمونهٔ انتزاعی (کروموزومها) از نامزدهای راه‌حل یک مسأله بهینه‌سازی به راه حل بهتری منجر شود، پیاده‌سازی می‌شوند. به طور سنتی راه‌حلها به شکل رشته‌هایی از ۰ و ۱ بودند، اما امروزه به گونه‌های دیگری هم پیاده‌سازی شده‌اند. فرضیه با جمعیتی کاملاً تصادفی منحصر بفرد آغاز می‌شود و در نسلها ادامه می‌یابد. در هر نسل گنجایش تمام جمعیت ارزیابی می‌شود، چندین فرد منحصر در فرایندی تصادفی از نسل جاری انتخاب می‌شوند (بر اساس شایستگیها) و برای شکل دادن نسل جدید، اصلاح می‌شوند (کسر یا دوباره ترکیب می‌شوند) و در تکرار بعدی الگوریتم به نسل جاری تبدیل می‌شود.

عملگرهای یک الگوریتم ژنتیک:
در هر مسئله قبل از آنکه بتوان الگوریتم ژنتیک را برای یافتن یک پاسخ به کار برد به دو عنصر نیاز است: اول روشی برای ارائه یک جواب به شکلی که الگوریتم ژنتیک بتواند روی آن عمل کند لازم است. به شکل سنتی یک جواب به صورت یک رشته از بیتها، اعداد یا نویسهها.نمایش داده می‌شود.دوم روشی لازم است که بتواند کیفیت هر جواب پیشنهاد شده را با استفاده از توابع تناسب محاسبه نماید. مثلاً اگر مسئله هر مقدار وزن ممکن را برای یک کوله پشتی مناسب بداند بدون اینکه کوله پشتی پاره شود، (مسئله کوله پشتی را ببینید) یک روش برای ارائه پاسخ می‌تواند به شکل رشته ای از بیتهای ۰ و۱ در نظر گرفته شود, که ۱ یا ۰ بودن نشانه اضافه شدن یا نشدن وزن به کوله پشتی است.تناسب پاسخ، با تعیین وزن کل برای جواب پیشنهاد شده اندازه گیری می‌شود.
الگوریتم ژنتیک : الگوریتم ژنتیک که به‌عنوان یکی از روشهای تصادفی بهینه یابی شناخته شده, توسط جان هالند در سال ۱۹۶۷ ابداع شده‌است. بعدها این روش با تلاشهای گلدبرگ ۱۹۸۹, مکان خویش را یافته و امروزه نیز بواسطه تواناییهای خویش , جای مناسبی در میان دیگر روشها دارد. روال بهینه یابی در الگوریتم ژنتیک براساس یک روند تصادفی- هدایت شده استوار می‌باشد. این روش , بر مبنای نظریه تکامل تدریجی و ایده‌های بنیادین داروین پایه گذاری شده‌است.در این روش , ابتدا برای تعدادی ثابت که جمعیت نامیده می‌شود مجموعه‌ای از پارامترهای هدف بصورت اتفاقی تولید می‌شود , پس از اجرای برنامه شبیه ساز عددی را که معرف انحراف معیار و یا برازش آن مجموعه از اطلاعات است را به آن عضو از جمعیت مذکور نسبت می‌دهیم. این عمل را برای تک تک اعضای ایجاد شده تکرار می‌کنیم , سپس با فراخوانی عملگرهای الگوریتم ژنتیک از جمله لقاح , جهش و انتخاب نسل بعد را شکل می‌دهیم و این روال تا ارضای معیار همگرایی ادامه داده خواهد شد.

بصورت متداول سه معیار به‌عنوان معیار توقف شمرده می‌شود: ۱. زمان اجرای الگوریتم ۲. تعداد نسلهایی که ایجاد می‌شوند ۳. همگرایی معیار خطا

کاربردهای الگوریتم ژنتیک :
• روندیابی هیدرولوژیکی رواناب جاری در شبکه رودخانه خشک
• کمک در حل مسایل تصمیم گیری چند معیاره
• بهینه سازی چند هدفه در مدیریت منابع آبی
• بهینه سازی و بارآرایی شبکه های توزیع نیروی برق