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

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

الگوریتم این برنامه خیلی ساده هست. به طوریکه ابتدا مثبت یا منفی بودن عددهای ورودی رو با یه شرط مشخص میکنیم. بعد هم داخل یک حلقه که به تعداد عدد اول a تکرار میشه عدد دوم b رو داخل یک متغیر قرار میدهیم و هر بار به اندازه عدد دوم به اون اضافه یا کم ( بسته به مثبت یا منفی بودن) اعداد می‌کنیم.
برای حل این مسئله ابتدا ورودی‌ها را دریافت می‌کنیم بعد چهار حالت زیر پیش می‌آید:

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

ابتدا ورودی‌هایمان را دریافت می‌کنیم، سپس به تعداد عدد دوم، عدد اول را به خودش ضرب می‌کنیم و در یک متغیر قرار می‌دهیم. برای این کار از یک حلقه استفاده می‌کنیم.

دو عدد از ورودی دریافت کرده و یک عدد برای جمع گذاشته می‌شود. سپس حلقه‌ای تعریف می‌کنیم که از i=0 باشد تا انتهای عدد دوم. و اگر مساوی عدد دوم بود تکرار کن c=c+a و اگر c مساوی عدد دوم به پایان برود و c را چاپ کند.

برای حل این الگوریتم دو متغیر به عنوان پایه و نمای توان مانند x, y در نظر گرفته‌ایم. حال اگر بخواهیم عمل توان را پیاده‌ساوزی نماییم، نیاز داریم که از خاصیت عضو خنثی در ضرب استفاده شود. همانطور که میدانید عضو خنثی در ضرب، عدد ۱ می‌باشد و نیاز به یک حبقه داریم که باید تا عدد دوم شمارش شود و مقدار متغیر عضو خنثی در داخل حلقه‌ی ضرب در عدد اول می‌شود تا در اتمام کار حلقه، توان محاسبه شود.

1. شروع
2. دو متغیر x و y را بخوان
3. عدد ۱ را به متغیر p نسبت بده
4. عدد ۱ را به متغیر i نسبت بده
5. اگر مقدار i کوچکتر از y باشد برو به مرحله‌ی ۷
6. در غیر این صودرت برو به مرحله‌ی ۹
7. p را در x ضرب کن و حاصل را در p بریز
8. یک واحد به i اضافه کن
9. برو به مرحله‌ی ۵
10. p را چاپ کن
11. پایان

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

از دید کامپیوتری، همانطور که مشاهده می‌کنید برای محاسبه‌ی فاکتوریل، ما یک متغیر داریم که از آن یک واحد کم شده و در عین حال در اعداد قبلی ضرب می‌شود. در الگوریتم زیر، متغیر مورد نظر، n بوده و برای سیر نزولی اعداد از خود متغیر a استفاده کردیم. با اجرای خط ۴ و ۵ همزمان، هم a متغیر مورد نظر ضرب شده، هم اینکه از آن یک واحد کم می‌شود. در خط ۶ یک کنترل گذاشته شده‌ تا a به صفر نرسد. چون اگر a برابر یک بشود و دوباره حلقه ادامه پیدا کند، در این دور، a برابر صفر شده و n را برابر صفر کرده و کل محاسبات را خراب می‌کند.

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

1. شروع
2. عدد را در a قرار بده
3. n=1
4. n=n*a
5. از aیکی کم کرده و دوباره در aقرار بده
6. اگر a بزرگتر از یک است برو به مرحله‌ی ۴
7. n را چاپ کن
8. پایان

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

برای نوشتن الگوریتم مورد نظر، یک خانه از حافظه را به کوچکترین عدد در هر مرحله اختصاص می‌دهیم.

1. min را دریافت کن
2. 2-i=1
3. a را دریافت کن
4. اگر a کوچکتر از min بود، آنگاه min=a
5. i=i+1
6. اگر iبزرگتر یا مساوی ۱۰۰۰ بود، به مرحله‌ی شماره‌ی ۸ برو
7. به مرحله‌ی ۳ برگرد
8. min را چاپ کن

یک متغیر برای جمع تعریف می‌کنیم sum = 0. و یک متغیر شرط با مقدار ۳ قرار می‌دهیم i = 3 تا جایی که sum = sum + i را در هر مرحله متغیر شرطی با متغیر، جمع می‌کنیم. در هر بار متغیر شرطی را با ۳ جمع می‌کنیم. اگر متغیر شرطی کوچکتر از ۵۰ بود. در پایان متغیر جمع را چاپ می‌کنیم.

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

1. a, b را دریافت کن
2. temp = 0
3. temp = a
4. a = b
5. b = temp

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

1. A را دریافت کن
2. اگر a mod 2 = 0 آن‌گاه
3. پیغام a زوج است را نمایش بده
4. در غیر این صورت
5. پیغام aفرد است را نمایش بده

1. a را دریافت کن
2. n را دریافت کن
3. max = a
4. max = n
5. c = 2
6. مادامی که n >= cتکرار کن {
7. a را دریافت کن
8. اگر max < a آن‌گاه max = a
9. اگر min < a آن‌گاه min = a
10. c = c + 1 }
11. min , max را چاپ کن

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

برای مثال، اگر تاریخ ۳/۲ وارد شد، عدد ۶۴ را نمایش دهد

1. m , d را دریافت کن
2. اگر m - 1 < = 6 بود، آن‌گاه
3. days = 31 + d (m - 1) در غیر این‌صورت
4. days= (m - 7) * 30 + (6*31) + d
5. days را چاپ کن

توضیح: در علم حساب و برنامه‌نویسی کامپیوتر الگوریتم تعمیمیافته اقلیدس تعمیمی بر الگوریتم اقلیدس است که در کنار محاسبه‌ی بزرگترین مقسومم علیه مشترک دو عدد صحیح a , b ضرایب بزو را هم محاسبه می‌کند.

همچنین می‌توان بدون هزینه‌ی اضافی خارج قسمت a,b را با بزرگترین مقسم علیه مشترک محاسبه کرد.
الگوریتم تعمیم یافته‌ی اقلیدس به الگوریتمی بسیار مشابه به الگوریتمی برای محاسبه بزرگترین مقسوم علیه مشترک چند جمله‌ای و ضرایب قضیه‌ی بزو از دو چند جمله‌ای با یک متغیر ارجاع دارد. الگوریتم تعمیم یافته اقلیدس زمانی که a,b نسبت به هم اول هستند مفیدتر است. چون x برابر وارون ضربی پیمانه‌ای a به پیمانه‌ی b و y برابر وارون ضریب پیمانه b به پیمانه‌ی a است. در الگوریتم اقلیدس برای چند جمله‌ای می‌تان وارون ضربی را در بسط‌ها ی میدان جبری محاسبه کرد.
از آن نتیجه می‌شود که هر دو نوع الگوریتم اقلیدسی تعمیم یافته معمولی و چند جمله‌ای کاربردی گسترده در رمزنگاری دارند. بخصوص در محاسبه‌ی وارون ضربی پیمانه‌ای در روش RSA یک گام ضروری است.
توضیح: در الگوریتم اقلیدسی معمولی فقط باقیمانده ها نگاه داشته می‌شوند و خارج قسمت استفاده نمی‌شود. اما در الگوریتم تعمیم یافته اقلیدسی خارج قسمت های متوالی ستفاده می شوند. به طور دقیق‌تر، در الگوریتم تعمیم یافته‌ که a، b را به عنوان ورودی می‌گیرد، دنباله‌ی q1 ... . .q(k)از خارج قسمت‌ها و دنباله‌ی r0 ... .r(k)+1 از باقیمانده‌ها را شامل می‌شود.
مهمترین ویژگی تقسیم اقلیدسی نامساوی سمت راست است که ri+1 را متفاوت از ri-1و riتعریف ‌ می‌کند. وقتی باقیمانده به صفر رسید محاسبه متوققف میشود. بزرگترین مقسوم علیه مشترک آخرین باقیمانده‌ی غیر صفر است. الگوریتم تعمیم یافته‌ی اقلیدسی روشی مشابه دارد با این تفاوت که دو دنباله‌ی زیر نیز به آن اضافه می‌شود:
در این الگوریتم هم وقتی rk + 1 = 0می‌شود کار الگوریتم به اتمام می‌رسد.
rkبزرگترین مقسوم علیه برای دو ورودی a = R0 و b = R1 است.
ضرایب بزو هم که بربر sk , tkدر رابطه‌ی زیر صدق می‌کند:
خارج قسمت تقسیم a,b بر بزرگترین مقسوم علیه مشترک‌شان به این صورت ایست: که این یعنی جفت ضرایب بزو که از این الگوریتم به دست می‌آیند یکی از کمترین جفت ضرایب بزو هستند.

عدد کامل عددی است که مجموع مقسوم علیه‌های آن عدد به جز خود عدد برابر با خود عدد باشد. مثال:
مقسوم علیه عدد ش برابر است با ۱ و ۲ و ۳ که جمع اینن سه عدد برابر است با ۶ . و این یعنی این که عدد شش کامل است.
پس ما برای این کار باید از یک for استفاده کنیم که متغیر شمارنده‌ی آن از شماره‌ی یک شروع شود و تا یکی مانده به عدد تمام شود. در داخل بلوک کد for باید بنویسیم که اگر باقیمانده تقسیم a بر i برابر با صفر باشد. بعلاوه متغیر S می‌شود و در sقرار می‌گیرد. همین عمل چند بار انجام می‌گیرد.
در آخر باید بررسی کنیم که عدد s برابر با عدد a هست یا خیر. اگر برابر باشد عدد کامل است و اگر نه عدد کامل نیست.

عدد اول عددی طبیعی بزرگتر از یک است که بر هیچ عددی بجز خود و یک بخش پذیر نباشد. تنها استثنا عدد یک است که جزو این اعداد قرار نمی‌گیرد. اگر عددی طبیعی و بزرگتر از یک اول نباشد مرکب است.
رقم یکان اعداد بزرگتر از ده فقط ممکن است ارقام ۱، ۳، ۷، ۹ باشد.
عددی را از ورودی دریافت می‌کنیم و یک متغیر را ۲ قرار می‌دهیم. و شرط یم‌گذاریم از یک تا خود عدد تکرار شود و یک یک شمارنده را معادل یک قرار می‌دهیم. اگر باقیمانده تقسیم آن صفر شود عدد اول است در غیر اینصورت عدد اول نیست.
خواص اعداد اول:

عر عدد اول برابر است با n+1 یا n-1 که n یک عدد صحیح است.
مجذور هر عدد اول برابر است با n+1.24
تفاضل مجذورهای دو عدد اول مضربی از 24 است.
حاصل ضرب هر دو عدد اول بجز ۲ و ۳ مضربی از ۶ بعلاوه یا منهای یک است.
توان چهارم هر عدد اول بجز ۲ و ۳ مضربی از ۲۴۰ بعلاوه یک است.

1. n را دریافت کن
2. c = 2 , sum = 0
3. مادامی که c <= n / 2 تکرار کن:
{
4. اگر n mod c = 0 آنگاه sum = sum + 1 }
5. اگر sum=0
6. پیغام عدد مربوطه اول است را نمایش بده
7. در غیر این صورت پیغام عدد مربوطه اول نیست را نمایش بده

از روش غربال برای ب.م.م استفاده می‌کنیم. به این ترتیب عدد بزرگتر را بر عدد کوچک‌تر تقسیم و اگر باقیمانده صفر شد عدد کوچک‌تر که مقسوم‌علیه تقسیم است ب.م.م می‌باشد. اگر صفر نشد مقسوم علیه قرار داده و دوباره عمل تقسیم انجام می‌شود تا زمانی که باقی‌مانده صفر شد که آن‌را صفر باشد ب.م.م است.

1. a, b را دریافت کن
2. temp =
3. mul = a * b
4. مادامی که a mod b < > 0 تکرار کن
5. { /n temp = b /n a mod b = b /n temp = a /n }
6. bmm = b
7. mul / bmm = kmm
8. ب.م.م و ک.م.م را نمایش بده

1. n را دریافت کن
2. sum = 0
3. مادامی که n > 0تکرار کن {
4. n / 10 = n
5. sum + 1 = sum }
6. sum را نشان بده

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

1. n را دریافت کن
2. sum = 0
3. مادامی که n > 0 تکرار کن {
4. b = n mod 10
5. n = n / 10
6. sum = sum + b }
7. sum را نمایش بده

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

1. n را دریافت کن
2. sum = 0
3. مادامی‌ که n > 0 {
4. b = n mod 10
5. n = n / 10
6. sum = sum * 10 + b }
7. sum را نمایش بده

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

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

1. n را دریافت کن
2. اگر، n >= 0 باشد. برو به گام چهارم
3. در غیر این صورت n = n * -1
4. n را چاپ کن

مربع کامل، عددی است که بتواند به صورت ضرب یک عدد صحیح در خودش نوشته شود. مثلا ۳۶ برابر است با ۶*۶. و ۴۹ برابر است با ۷ ضرب هفت.
نکته:
تمام مربع‌های کامل به ۰، ۱، ۴، ۵، ۶ و ۹ ختم می‌شود.

1. عدد را از ورودی گرفته و داخل متغیر از نوع صحیح قرار می‌دهیم.
2. جذر تابع عدد را گرفته و داخل متغیر از نوع اعشاری قرار می‌دهیم.
3. عدد را در خودش ضرب کرده و سپس حاصلضرب را درون متغیر نگهداری می‌کنیم.
4. اگر حاصل برابر با عدد صحیح ورودی باشد یعنی مربع کامل است. در غیر این‌صورت مربع نیست.
5. چون متغیر از نوع اعشاری با دقت بالا است در نتیجه عددی که مربع نباشد را گرد نمی‌کند برنامه درست کار می‌کند.

یک عدد را برای تعداد خط‌های چاپ ستاره وارد می‌کنیم سپس تا جایی که (تعداد خط یا سطر) i کوچک‌تر از عدد وارد شده بود و همچنین ستون‌های آن از j = 1 تا جایی که کوچک‌تر یا مساوی با مقدار ه بود، ستاره را چاپ کن و این عمل تکرار شود تا زمانی که به عدد وارد شده رسیدیم و پایان یابد.

ما می‌دانیم که برای حل یک دستگاه دو معادله دو مجهولی ابتدا باید یا x و یا y را از دو عبارت موجود حذف کنیم. البته در این سورس، x از هر دو عبارت حذف می‌شود.
برای حذف x از هر دو عبارت باید ضریب x در هر دو عبارت صفر شود. که برای این کار، عبارت اول را بر قرینه‌ی عدد d ضرب می‌کنیم و عبارت دوم را نیز بر عدد a ضرب می‌کنیم.
بعد از انجام این کار یک دستگاه دو معادله‌ی دو مجهولی جدید به وجود می‌آید که در آن هر دو عبارت را با هم جمع می‌کنیم. در نتیجه x از عبارت‌ها پاک می‌شود. اکنون ما با توجه به عبارت زیر، y را بدست می‌آوریم.
b y = c ----> y = c / b

بعد از به دست آوردن y آن‌را در یکی از عبارت‌ها جایگزین می‌کنیم و x را با استفاده از فرمول زیر محاسبه می‌کنیم.
x = ( c - (b * y ) ) / a

البته در عبارت بالا و سورس و الگوریتم برنامه از اولین عبارت ax + by = c برای محاسبه‌ی مقدار x استفاده شده است.

1. a, b, c را دریافت کن
2. delta = b * b - 4 * a * c
3. اگر delta >= 0 {
4. 1x = a / (2 delta) (-b + sqrt)
5. 2x = a / (2 delta) (-b - sqrt)
6. x1 و x2 را نمایش بده }
7. در غیر اینصورت پیغام "این معادله ریشه ندارد" را نمایش بده

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

int A[4] = 14 15 16 5

برای مثال: اگر عدد مورد نظر ما ۵ باشد، ابتدا چک می‌کند که آیا ۵ و ۱۴ برابر هستند یا نه. در صورت نابرابری به خانه‌ی بعد می‌رود و آن‌قدر این کار را انجام می‌دهد تا عدد را پیدا کند.

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

1. راسی را که الگوریتم باید از آن شروع کند و همچنین حداکثر عمق جست و جو را مشخص کنید.
2. چک کنید که آیا راس کنونی حالت هدف است:
3. اگر نیست هیچ کاری انجام ندهید.
4. اگر پاسخ مثبت است: از الگوریتم خارج شوید.
5. چک کنید که آیا راس کنونی در عمق کمتر از حداکثر عمق جست و جو قرار دارد:
6. اگر چنین نیست هیچ کاری انجام ندهید.
7. اگر مثبت است: راس را بسط دهید و تمامی نودهای زیرمجموعه‌ی آن‌را در پشته ذخیره کنید.
8. DLS را به طور بازگشتی برای تمامی رئوس موجود در پشته فراخوانی کنید و به مرحله‌ی ۲ برگردید.

یک الگوریتم برای پیدا کردن یک کلید در یک آرایه‌ی مرتب است. این الگوریتم با چک کردن همه‌ی آیتم‌های lkm، جایی که l، آرایه است و k، عضو اعداد طبیعی و m اندازه‌ی بلوکی هست که در آن کلید را جستجو می‌کند و این الگوریتم ادامه می‌دهد این جستجو را تا زمانی که یک آیتم پیدا شود که از کلید جستجو بزرگ‌تر باشد. در آن صورت از یک مرحله قبلش به اندازه‌ی m یکی یکی چک می‌کند و در صورت وجود کلید آن‌را پیدا می‌کند.
مقدار بهینه‌ی m رادیکال n است. جایی که n اندازه‌ی آرایه l است. در هر دو مرحله الگوریتم به اندازه‌ی رادیکال n، پیش می‌رود پس این الگوریتم در o (√n) اجرا می‌شود که این الگوریتم از الگوریتم خطی بهتر و از الگوریتم دو دویی بدتر است. اما مزیت این الگوریتم به الگوریتم دودویی این است که در این الگوریتم فقط یک‌بار به عقب برمی‌گردد و لی در الگوریتم دودویی می‌تواند تا log n بار به عقب برگردد و این در مواقعی که برگشت به عقب موثر است از به جلو پیش رفتن خیلی اهمیت دارد.

1. ورودی: یک لیست مرتب L، که طول آن آرایه n، و کلید مورد نظر s است.
2. خروجی: محل قرار گرفتن s در L یا هیچی اگر s موجود نباشد در L.

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

فرض کنید آرایه‌ی ما این باشد:
int A[5] = {3, 0, 1, 2, 5,};
روش مرتب‌سازی به این صورت خواهد بود:
گام اول: اندیس صفرم یعنی ۳، ابتدا با ۰ و بعد با ۱، سپس با ۲ و سپس با ۵ مقایسه می‌شود.
گام دوم: اندیس یک یعنی ۰ با ۱ و ۲ و ۵ مقایسه می‌شود.
و در گام‌های بعدی هم به همین صورت ادامه خواهد داشت. در تصویر زیر می‌توانید بهتر متوجه شوید. مقایسه‌ها با خط نمایش داده شده‌است.

بسیاری از فرآیندهای طبیعی از جمله ترکیب ساختار بدن موجودات زنده، نظم مشخصی دارند و از دنباله‌ی اعدادی تبعیت می‌کنند که امروزه با نام دنباله‌ی اعداد فیبوناچی شناخته می‌شود. مشهرترین خاصیت این اعداد نسبت دو جمله‌‌ی متوالی آن‌ها به ازای جملات بزرگ دنباله است که به عدد طلایی مشهور است.
همان‌گونه که از تعریف مشخص است، جملات این دنباله از جمع دو جمله‌ی قبلی آن با شروع از دو مقدار صفر و یک به دست می‌آیند:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... .

الگوریتم Risch برای تابع اولیه انتگرال استفاده شده‌است. این‌ها توابعی هستند که شامل ترکیب تابع‌های نمایی، لگاریتم‌ها، رادیکال‌ها، مثلثات و چهار عمل اصلی علم حساب می‌باشند.
انتگرال نامعین یک تابع منطقی، تابعی است منطقی و یک عدد از ضرب تعداد محدودی از ضرب‌های ثابت لگاریتم تابع منطقی است.
Liouville، مسئله‌ی حل‌شده توسط الگوریتم Risch، را به صورت فرمول در آورده است. Liouville، به روش تحلیلی اثبات کرد که اگر یک راه حل ابتدایی یا اولیه که اسمش g باشد وجود داشته باشد برای معادله‌ی g'=f آن‌گاه برای ثابت a_i و تابع اصلی u_i و v پاسخ به شکل زیر می‌باشد.

Risch، روشی ساخت که اجازه می‌داد شخص فقط نگران مجموعه‌‌ای محدود از توابع اولیه به صورت فرمول لیوویل باشد.
فراست الگوریتم ریش، از وفتار توابع نمایی و لگاریتمی در مشتق گیری می‌آید. برای توابع f_e^g که f و g توابع متغیری هستند که ما داریم.
لذا اگر e^g در نتیجه انتگرال نامعین بود، باید انتظار داشت که داخلِ انتگرال نیز باشد همانگونه که :

سپس اگر lnⁿg در نتیجه انتگرال باشد آنوقت فقط توان‌های کمی از لگاریتم می توان انتظار داشت..
تبدیلِ فرایندِ تصمیمِ رِیش به یک الگوریتم که بتواند توسط کامپیوتر اجرا شود وظیفه ی پیچیده‌ای است که نیازمند مطالعات ابتکاری و پالایشِ زیاد می باشد. هیچ نرم‌افزاری (تا فوریه ۲۰۱۱) شناخته نشد که بتواند الگوریتمِ رِیش را به طورِ کامل پیاده سازی کند، اگرچه چندین سیستم جبری کامپیوتری جزئی از آن را پیاده سازی کرده‌اند.

برای حل این مسئله، می‌توانیم از یک الگوی باینری که تعداد صفر و یک‌های اون برابر n هست استفاده کنیم. مثلا برای یک مجموعه‌ی ۳ عضوی می‌توانیم از الگوی زیر استفاده کنیم.

000
001
010
011
100
101
110
111

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

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

1. بریا محاسبه‌ی رقم کنترل از روی سایر ارقام، هر رقم را در موقعیت آن ضرب کرده و حاصل را با هم جمع می‌کنیم.
2. مجموع بدست آمده از مرحله‌ی ۱ را بر یازده تقسیم می‌کنیم.
3. اگر باقی‌مانده کم‌تر از ۲ باشد، رقم کنترل باید برابر باقی‌مانده باشد در غیر این صورت رقم کنترل باید برابر یازده منهای باقی‌مانده باشد.

مثال:
آیا کد ۷۷۳۱۶۸۹۹۵۱، یک کد ملی معتبر است؟ برای این منظور،حاصل جمع ضرب ارقام ۲ لی ۱۰ را در موقعیت آن‌ها محاسبه می‌کنیم.

۷*۱۰+۷*۹+۳*۸+۱*۷+۶*۶+۸*۵+۹*۳+۵*۲=۳۱۳
۳۱۳÷۱۱=۲۸
R= ۵

چون باقی‌مانده برابر با ۵ و بزرگ‌تر مساوی ۲ است، پس باید رقم کنترل این کد برابر با ۶ باشد. با دقت در کد متوجه می‌شویم که رقم کنترل ورودی برابر با ۱ است. پس کد مورد نظر به عنوان یک کد معتبر قابل قبول نیست.

هر ویراست از یک کتاب دارای شمارهٔ شابک خاص خود است و این شماره دارای ۱۰ تا ۱۳ رقم است و پنج بخش دارد:
اگر شماره ۱۳رقمی باشد دارای یک عددِ ۹۷۸ یا ۹۷۹ است.
هر زبان یا کشور دارای شمارهٔ خاص خود است.
برای مثال، کد کشور انگلیس صفر یا یک، فرانسه دو، آلمان سه، و کد ایران ۹۶۴ یا ۶۰۰ است. اگر شابکی این کد را نداشته‌باشد در جهان رسمیت ندارد. این کد برای کشورها حداکثر پنج رقم خواهد بود.
هر انتشارات دارای شمارهٔ خاص خود است که در شابک گنجانده می‌شود.
هر کتاب دارای شمارهٔ خاص خود است.
یک نویسه وارسی در مبنای یازده است و در اصل یک مجموع مقابله‌ای (Checksum) از تمام شناسه‌است. به‌وسیلهٔ این نویسه می‌توان صحت شابک موردنظر را بررسی کرد.
نویسهٔ وارسی (عدد کنترل) با استفاده از روش زیر محاسبه می‌شود:
هریک از نویسه‌های شناسهٔ شابک (از چپ به راست) در وزنی که از ۱۰ تا ۲ به‌ترتیب برای هریک از آنها در نظر گرفته می‌شود، ضرب می‌شود.
حاصل نتایج ضرب‌ها با هم جمع می‌شود.
نویسهٔ وارسی با استفاده از حاصل نتایج ضرب در مبنای ۱۱ تعیین می‌شود (یعنی برای مقدار مجموع حاصل‌ضرب‌های برابر با ۱۰، نویسهٔ X استفاده می‌شود).
مثلاً برای:
۱۰×۶ + ۹×۰ + ۸×۰ + ۷×۵ + ۶×۸ + ۵×۲ + ۴×۵ + ۳×۰ + ۲×۰ = ۶۰ + ۰ + ۰ + ۳۵ + ۴۸ + ۱۰ + ۲۰ + ۰ + ۰ = ۱۷۳
حاصل مضرب کامل قبلی «۱۱ × ۱۵ = ۱۶۵» ۱۱ است.
باقی‌مانده تقسیم ۱۷۳ بر ۱۱ عدد ۸ می‌شود. به عبارت دیگر: ۱۷۳–۱۶۵ = ۸ عدد کنترل شابک این مثال ۸ است که سمت راست عدد آمده‌است.
همان‌طور که می‌بینید حاصل محاسبه فوق عدد ۱۳۲ شده است و اکنون کافیست این عدد را بر عدد ۱۱ تقسیم کنیم. چنانچه باقیمانده صفر شود بعنی شابک مورد نظر صحیح است و در غیر اینصورت اشتباه می‌باشد. شابک ۱۳ رقمی:
برای اعتبارسنجی شابک ۱۳ رقمی باید تمام اعداد را از سمت چپ به ترتیب در اعداد ۱ یا ۳ ضرب کرده و سپس حاصل هرکدام را با هم جمع کنیم. به عنوان مثال شابک ۷-۴۰۶۱۵-۳۰۶-۰-۹۷۸ را به صورت زیر اعتبارسنجی می‌کنیم.

همان‌طور که می‌بینید نتیجه محاسبه عدد ۱۰۰ شده و چنانچه نتیجه را بر عدد ۱۰ تقسیم کنیم خواهیم دید که باقیمانده صفر خواهد شد و بنابراین شابک مورد نظر ما صحیح است. لازم است ذکر شود در ماشین حساب معمولی اگر جواب صفر شد ملاک ما است و در ماشین حساب مهندسی دکمه mod وجود دارد که برای محاسبه باقیمانده استفاده می‌شود.

تمامی کارت‌های اعتباری بانکی دارای الگوریتمی بین‌المللی هستند که فرمول آن به این شکل است که ابتدا از رقم اول، دو تا دو تا جدا می‌کنیم و آن‌ها را در دو ضرب می‌کنیم. در صورتی که این ارقام از ده بیشتر باشند، آن‌ها را از ۹ کم می‌کنیم، نتایج را ذخیره میکنیم. حال مابقی ارقام را که از ده بیشتر نبودند را نیز ذخیره کرده و ارقامی که در این عملیات شرکت نداشتند را هم ذخیره می‌کنیم و ارقام ذخیره شده را نهایتا با هم جمع می‌کنیم. حاصل باید مضربی از ۱۰ باشد.
6104 3370 2926 0526
6 1 0 4 3 3 7 0 2 9 2 6 0 5 2 6
x2 x2 x2 x2 x2 x2 x2 x2
12-9 0 6 14-9 4 4 0 4
3 1 0 4 6 3 5 0 4 9 4 6 0 5 4 6
3+1+0+4+6+3+5+0+4+9+4+6+0+5+4+6= 60
60 mod 10 = 0 این کارت یک کارت معتبر است.

برای ساخت ۱۹ رقم سمت راست شبا، به ترتیبی که در الگوریتم محاسبه‌ی سیستم حساب هر بانک ذکر شده‌است عمل می‌شود. پس از ساخت این ۱۹ رقم، قواعد محاسبه شبا همانند دستورالعمل صورت می‌پذیرد. در این الگوریتم‌ها شماره‌ی حساب بانک به معنی ۱۹ رقم سمت راست شبا است.
اولین رقم شماره‌ حساب بانک به صورت زیر معین می‌شود:

1. اگر شماره‌ی مربوط به حساب سپرده‌ی متمرکز باشد، معادل عدد صفر است.
2. اگر شماره‌ی مربوط به حساب سپرده‌ی غیر متمرکز وابسته به شعبه باشد، معادل عدد ۱.
3. اگر شماره مربوط به حساب تسهیلات متمرکز باشد، معادل عدد ۲.
4. اگر شماره مربوط به حساب تسهیلات غیر متمرکز باشد، معادل عدد ۳.

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

فرمت شماره سریال استاندارد بین‌المللی یک شماره هشت رقمی است که توسط اتصال‌ها و فواصل به دو قسمت چهار رقمی تقسیم می‌شود. عدد آخر که می‌تواند از ۰ تا ۹ و یا x باشد، شماره‌ی کنترل نامیده می‌شود. گزارش خوانش این شماره برای مثال ممکن است چیزی مانند ۵۹۵۵-۰۳۷۸ باشد که از طریق الگوریتم زیر به تطبیق و کنترل آن مبادرت می‌شود.
محاسبه‌ی حاصل جمع هفت رقم ابتدایی شماره‌ی issn به ترتیب، در حاصل ضرب در شماره‌‌های ۸، ۷، ۶، ۵، ۴، ۳، ۲،:
0*8+3*7+7*6+8*5+5*4+9*3+5*2 == 0+21+42+40+20+27+10= 160
سپس ضریب عدد ۱۶۰ را به پیمانه‌ی ۱۱ محاسبه می‌کنیم:
۱۶۰ بر ۱۱ = ۱۶
شما می‌بایست متناوبا این تقسیم را بر پایه‌ی ۱۱ انجام دهید.
۱۶۰ ÷ ۱۱ = ۱۴.۶
سپس قدر مطلق باقی‌مانده که در بالا شش هست، ارزش شماره کنترل ما را وقتی که از میزان ۱۱ تفریق می‌شود را مشخص می‌کند:
۱۱ -۶ = ۵
شماره‌ی کنترل ما پنج می‌شود. همچنین x نشان‌دهنده‌ی شماره‌ی ده در شماره‌ی کنترل می‌باشد.

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

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

برای بررسی این شماره‌، مراحل زیر را دنبال کنید:

1. هر رقمی که در جایگاه زوج قرار دارد، در عدد ۳ ضرب می‌شود. شمارش را از سمت راست به چپ انجام می‌دهیم. ارقامی که در جایگاه فرد قرار دارند در ۱ ضرب می‌شوند.
   3(7)+1(8)+3(6)+1(9)+3(3)+1(6)+3(2)+1(4)+3(4)+1(4)+3(4)+1(2)+3(5)+1(0)
2. نتایج را با یکدیگر جمع کنید.
   0+15+2+12+4+6+6+9+9+18+8+21=110
3. اعتبار این شماره را با تقسیم آن بر عدد ده تعیین نمایید.

تقسیم بر 10 دارای باقی مانده ی صفر می باشد (11=110/10). پس این شماره ی UPC، معتبر است.
دانش آموزان ممکن است از ضرایب فاکتور بگیرند، به این صورت که ابتدا رقم های موجود در جایگاه زوج را با یکدیگر جمع و سپس در 3 ضرب کنند، رقم های موجود در جایگاه فرد را نیز جمع کرده و در 1 ضرب کنند.

سپس شماره ی UPC مقابل را برای دانشجویان مثال بزنید: 7-96714-78601-y در این جا y، رقم چک کننده است. با استفاده از فرآیند فوق، دانش آموزان باید رقم چک کننده را تعیین کنند. مجموع نتایج 112 است. پس رقم چک کننده باید 8 باشد، زیرا باقیمانده ی تقسیم (8+112) بر 10، 0 است. در تمرین شماره ی 1، دانش آموزان باید رقم چک کننده را برای 2 شماره ی UPC به دست آورند.

نوع دیگری از سیستم های بارکد، شماره ی استاندارد بین المللی کتاب یا ISBN است. این سیستم در اواخر 1960 و اوایل 1970 به وجود آمد. آشکار است که سیستم واحدی برای شناسایی کتاب هایی که در تمام نقاط دنیا انتشار می یابند، مورد نیاز است. اکنون هر کتابی می تواند یک شماره ی شناسایی انحصاری داشته باشد. ISBN، یک عدد ده رقمی است که شامل بلوک های عددی با معانی متفاوت است. این شماره شامل چهار قسمت می باشد که با خط تیره یا فاصله از هم جدا شده اند. اولین قسمت شماره که نشان دهنده ی زبان یا کشور است، شناسه ی گروه نام دارد و حداکثر 5 رقمی است. بخش دوم شماره، نشان دهنده ی ناشر و حداکثر 7 رقمی است. سومین بخش شماره، نشان دهنده ی تجدید چاپ یا تعداد چاپ است و بیش از 6 رقم نیست. قسمت نهایی، رقم چک کننده است. قسمتی از انعطاف پذیری این سیستم در این نکته است که تعداد زیادی شماره جهت استفاده موجود می باشد. به یاد آورید که یک شماره ی 10 رقمی داریم که رقم آخر آن، رقم چک کننده است. بنابراین سه قسمت اول شماره می باید در مجموع، یک عدد نه رقمی را تشکیل دهند. رقم های صفر، به عنوان پر کننده های فضا در ابتدای عدد، در صورتی که تعداد رقم ها به تعداد کافی نباشد، استفاده می شوند. شکل زیر، نمونه ای از شماره ی ISBN را نشان می دهد.

در این سیستم، رقم چک کننده، به روشی متفاوت با روش UPC محاسبه می شود. به این صورت که اولین رقم در 10 ضرب می شود، رقم دوم در 9، رقم سوم در 8 و این فرایند را ادامه می دهیم تا رقم نهم که در 2 ضرب می شود. سپس مجموع نتایج را محاسبه می کنیم. این سیستم پیمانه ی11 نامیده می شود، به این معنی که مجموع نتایج نه رقم اول به علاوه ی رقم چک کننده باید مضرب 11 باشد. یکی از مشکلات این روش این است که ممکن است رقم چک کننده 10 باشد، در حالی که ما فقط می توانیم از ارقام 0 تا 9 برای این منظور استفاده کنیم و بنابر این X به جای رقم چک کننده نوشته می شود. (این X نشان دهنده ی شماره 10 رومی است.) تمرین های شماره ی 3 تا 6، مشخصات مربوط به ISBN می باشند.
کارت های اعتباری، از یک سیستم بلوک های شماره ای، مشابه سیستم ISBN استفاده می کنند. یک تفاوت واضح این است که در این جا حداکثر طول شماره 19 رقم است، اگرچه بسیاری از شماره ها بین 13 تا 16 رقم می باشند.

یک تابع بنهانی درهم تصویب شده H را انتخاب کنید. بر روی طول کلید L, N تصمیم بگیرید. این اندازه‌گیری اولیه قدرت پنهانی کلید است. دی‌اس‌اس اصلی مارا وادار می‌کند تا مضربی از ۶۴ بین ۵۱۲ و ۱۰۲۴ باشد.

1. یک بیت اولیه n را به گونه‌ای برگزینید که n q کمتر یا مساوی با طول خروجی درهم باشد.
2. یک بیت اولیه l با مدول p را به گونه‌ای انتخاب کنید که p-1 مضربی از q باشد.
3. عددی را به عنوان (q1 / g)=-hp برگزینید.

پارامترهای الگوریتم (p, q, g) ممکن است بین کاربران سیستم به اشتراک گذاشته‌شود. به ازای هر کاربر یک مجموعه از پارامترها به کلیدهها تخصیص میابد. مرحله‌ی دوم کلیدهای عمومی و اختصاصی را برای یک کاربر مجزا محاسبه می‌کند.

1. انتخاب x با روش‌های تصادفی
2. محاسبه‌ی باقی‌مانده gx=y
3. کلید عمومی (p, q, g, y)و کلید خصوصی x است.
4. تولید یک کلید تصادفی k باید بعد از یک بار استفاده از بینن رفته و دیگر مورد استفاده قرار نگیرد.
5. سپس زج مرتب امضا (r, s) به صورت زیر محاسبه می‌شوند.
   
6. (r, s) به پیام M الحاق شده و فرستاده می‌شود.

روش کار به این صورت است:

1. فرستنده با استفاده از الگوریتم هش PGPو متن خام اطلاعات مثلا ایمیل، یک رشته HASH را ایجاد می‌نماید. که با نام Message Digest شناخته می‌شود.
2. رشته‌ی ایجاد شده توسط کلید خصوصی فرستنده رمزنگاری می‌شود. به عنوان مثال: امضای دیجیتال.
3. امضای دیجیتال به همراه اطلاعات ارسال می‌شود. میتوان اطلاعات را نیز توسط PGP رمزنگاری کرد.
4. در سمت گیرنده‌ی این امضا با استفاده از کلید عمومی فرستنده رمزگشایی می‌شود. و MEssage Digest اولیه بدست می‌آید.
5. اطلاعات اصلی نیز در صورت نیاز رمزگشایی شده و با استفاده از الگوریتم‌های هش PGP یک رشته HASH تولید می‌شود.
6. در صورتی که HASH بدست آمده با Message Digest برابر بود، به این معنی است که اطلاعات و فرستنده معتبر هستند.

برای POP کردن از پشته، داده‌ای که در اندیس Top قرار دارد برگردانده می‌شود و Top یک واحد کم می‌شود.

1. عددی را دریافت می‌کنیم.
2. شرط ‌گذاشته که اگر پشته خالی بود، Top=0 بود چاپ کند پشته خالی است. به مرحله‌ی آخر برو.
3. در غیر این صورت عدد را از پشته برمی‌داریم.
4. از بالاترین سطح پشته‌، یک واحد کم می‌کنیم
5. عدد ۱ را چاپ کن.

اندیس عنصر بالای پشته Stack را نگه‌می‌دارد. Top=n دلالت بر خالی بودن پشته دارد.
برای Push کردن یک داده‌ی جدید به پشته، به Top یکی اضافه می‌شود. و داده‌ی جدید در آرایه‌ در اندیس Top درج می‌کند.

برای اضافه کردن عدد به صف، باید از انتهای صف یک واحد اضافه کنیم تا بتوانیم عدد را وارد کنیم.
در صف دو اشاره‌گر Front که به ابتدای ارایه اشاره و Rear به انتهای آرایه اشاره می‌کند.
از عمل اصلی Queue برای تست خالی بودن یا پر بودن استفاده می‌شود. اگر Rear ما برابر با n بود، چاپ کن که پر است. در غیر این صورت، به Rear یک واحد اضافه و عدد را وارد صف کن.
صف، لیست مرتبی است که عناصر در انتهای آن اضافه و از ابتادی آن حذف می‌شود. به عبارت دیگر طول صف از انتهای آن افزایش و از ابتدای آن کاهش می‌یابد.
اولین عنصری که وارد صف می‌شود اولین عنصری است که از صف خارج می‌شود. بنابراین عناصر به همان ترتیبی که به صف اضافه می‌شوند از آن حذف می‌شوند. به همین دلیل به صف، لیست FIFO یا First In First Out گفته‌می‌شود.

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

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

الگوریتم بیم برای اینکه در حافظه صرفه‌جویی کند یک تابع h برای پیش‌بینی هزینۀ رسیدن به راس موردنظر از راس داده‌شده در نظر می گیرد.همچنین از یک پارامتر به نام B(عرض بیم) استفاده می‌کند که نشان‌دهندۀ تعداد راس‌هایی است که در هر مرحله از الگوریتم جستجوی اول سطح ذخیره شده‌است. بنابراین زمانی که الگوریتم جستجوی اول سطح همۀ راس‌های مرزی ( راس‌هایی که با نزدیک‌ترین راس ارتباط دارند)را ذخیره می‌کند الگوریتم بیم فقط راس‌های B با بهترین مقدار در هر مرحله از جستجو را ذخیره می‌کند. ایده اصلی این است که تابع h به الگوریتم اجازه می‌دهد که راس‌هایی انتخاب شوند که مسیر را به سمت راس مقصد راهنمایی کنند و پارامتر B باعث می‌شود که الگوریتم فقط این راس‌های مهم را ذخیره کند و از پر شدن حافظه قبل از رسیدن به هدف جلوگیری می‌کند.برخلاف الگوریتم جستجوی اول سطح که از یک لیست(open list)استفاده می‌کند این الگوریتم راس‌هایی را که در حلقۀ بعد الگوریتم بسط داده می‌شود رادر(BEAM)ذخیره می‌کند؛ همچنین از یک جدول‌هش برای ذخیرۀ راس‌هایی که دیده شده‌اند استفاده می‌کند شبیه(close list)درالگوریتم جستجوی اول سطح.

الگوریتم بیم در ابتدا راس شروع را به BEAM وجدول‌هش اضافه می‌کند سپس در هر مرحله از حلقۀ اصلی از الگوریتم، راس‌های همسایه باراس‌های BEAM را به یک مجموعه که شامل راس‌های جانشین(successor)است اضافه می‌کند و سپس راس‌های B با بهترین مقدار از مجموعۀ جانشین را به BEAM و جدول‌هش اضافه می‌کند. راس‌هایی که در حال حاضر در جدول‌هش قرار دارند به BEAM اضافه نمی‌شوند چرا که مسیر کوتاهتر برای آن راس پیدا شده.این فرایند ادامه دارد تا زمانی که راس مقصد پیدا شود، جدول‌هش پر شود، یا BEAM بعد از حلقۀ اصلی خالی شود.
در ادامه شبه کد الگوریتم آورده شده.

/* initialization */

      g = 0;

      hash_table = { start };

      BEAM = { start };

      /* main loop */

      while(BEAM ≠ ∅){                             // loop until the BEAM contains no nodes

        SET = ∅;                                   // the empty set

        /* generate the SET nodes */
        for(each state in BEAM){
          for(each successor of state){
            if(successor == goal) return g + 1;
            SET = SET ∪ { successor };             // add successor to SET
          }
        }

        BEAM = ∅;                                  // the empty set
        g = g + 1;

        /* fill the BEAM for the next loop */
        while((SET ≠ ∅) AND (B> |BEAM|)){         // set is not empty and the number of nodes in BEAM is less than B
          state = successor in SET with smallest h value;
          SET = SET \ { state };                   // remove state from SET
          if(state ∉ hash_table){                  // state is not in the hash_table
            if(hash_table is full) return ∞;
            hash_table = hash_table ∪ { state };   // add state to hash_table
            BEAM = BEAM ∪ { state };               // add state to BEAM
          }
        }
      }
      

الگوریتم اسپیگوت (به انگلیسی: Spigot Algorithm) یک نوع خاص از الگوریتم‌ها است که برای محاسبه ی مقدار یک ثابت ریاضی مانند π یا e استفاده می‌شود، که می‌تواند یک رشته ی خروجی از ارقام را بدون نیاز به استفاده ی مجدد از آنها تولید کند.این اسم از کاربرد کلمۀ اسپیگوت در برخی از شاخه‌های انگلیسی به معنی دریچه یا شیری که جریان یک مایع را کنترل می‌کند برگفته شده است.

علاقه به چنین الگوریتم‌هایی در روز‌های آغازین ریاضیات محاسباتی با تاکید شدید بر حافظه رواج پیدا کرد، و یک نمونه از این الگوریتم‌ها برای محاسبۀ ارقام عدد e می‌باشد. منتشرشد. نام الگوریتم اسپیگوت توسط استنلی رابینوویتز و استان واگن ابداع شد که الگوریتم ابداعی آنها برای محاسبه عدد π برخی اوقات تحت عنوان اگوریتم اسپگوت برای "π" نام برده می‌شو

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

این مثال نحوه ی کار کردن الگوریتم اسپیگوت را با محاسبه ی ارقام باینری لگاریتم طبیعی ۲ نشان می‌دهد (دنباله ی A068426 درOEIS ) با استفاده از تساوی ذیل :

برای محاسبه ارقام باینری از جایگاه هشتم ما طرفین تساوی فوق را در 27 ضرب می‌کنیم ( با توجه به اینکه ۷=۸-۱)

سپس ما سری نا محدود را به دو قسمت تقسیم می‌کنیم : قسمت "head" که در آن توان ۲ بزرگتر یا مساوی ۰ است و قسمت "tail" که در آن توان ۲ منفی است.

از آنجایی که ما فقط علاقه‌مند به بخش کسری این مقدار هستیم می‌توانیم هر مؤلفه سری در "head" را با مقدار زیر جایگزین کنیم

با محاسبه هر کدام از این مقادیر و اضافه کردن آنها به سری کلی که در حال اجراست ( که مجدداً در این سری کلی ما تنها علاقه‌مند به بخش کسری هستیم) به نتایج زیر می‌رسیم :

ما مقادیری را به بخش "tail" می‌افزاییم،با توجه به اینکه خطای تولید شده به موجب کوتاه کردن سری کمتر از مقدار نهایی است.

با اضافه کردن بخش "head" و تعداد اندکی از مقادیر نخستین بخش "tail" به نتایج زیر می‌رسیم :

بنابراین ارقام ۸ ام تا ۱۱ ام در بسط باینری (ln(2 ارقام ۱،۱،۰،۱ می‌باشند.توجه کنید که ما مقادیر ۷ رقم نخست باینری را محاسبه نکرده‌ایم - در واقع تمامی اطلاعات مربوط به آنها با استفاده از هم نهشتی(نظریه اعداد) در بخش سری "head" به صورت عمدی حذف شده است. روش مشابهی می‌تواند برای محاسبه ی ارقام بسط باینری (ln(2 با شروع از جایگاه دلخواه n ام مورد استفاده قرار بگیرد. تعداد عبارت‌های موجود درقسمت "head" سری به صورت خطی با n افزایش میابد ، اما چناچه یک روش کارآمدی با استفاده از به‌توان‌رساندن مدولار به کار گرفته شود پیچیدگی هرعبارت تنها با لگاریتم n افزایش میابد. دقت محاسبات،نتایج میانی و تعداد عبارت‌های گرفته شده از قسمت "tail" سری همگی مستقل از n می‌باشند و تنها وابسته به تعداد ارقام باینری هستند که در حال محاسبه است - یک واحد محاسباتی می‌تواند برای محاسبه حدودا ۱۲ رقم باینری صرف نظر از جایگاه شروع مورد استفاده قرار گیرد.

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

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

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

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

هر پاره خط در صفحه مختلط به وسیله 2 عدد قابل نمایش است که همان ابتدا و انتهای پاره خط‌ می‌باشد.مثلا ab پاره خطیست که عدد a یک سر آن و عدد b سر دیگر پاره خط است.حال برای پیدا کردن محل تقاطع 2 پاره خط بایستی شرط‌هایی لازم و کافی برای یک نقطه دلخواه مانند X بیابیم که در صورت برقراری آن‌ها نقطه X روی خط حاصل از امتداد پاره خط ab قرار داشته باشد.حال فرض کنید نقطه X روی خط حاصل از امتداد ab باشد ، در این صورت خواهیم داشت :

بنابراین:

حال دو طرف معادله (1) را در (d-c) ضرب‌ می‌کنیم :

هم چنین دو طرف معادله (2) را در (b-a) ضرب‌ می‌کنیم :

حال از تفاضل معادله (3) و (4) خواهیم داشت :

که مقدار x بدست‌ می‌آید :

برای پیاده سازی اعداد مختلط با استفاده از دستگاه مختصات دو بعدی‌ می‌بایست قوانین جمع و ضرب اعداد مختلط را برای دوتایی‌های (x,y) به وسیله ایجاد تعدادی تابع در برنامه تعریف کرد .اما به طور مستقل نیز‌ می‌توان با اضافه کردن کتاب خانه اعداد مختلط در برنامه ، از توابع تعریف شده در این کتاب خانه کمک گرفت :

#include <complex>
using namespace std;
typedef complex<double> point;
 
 
//The Dot And Cross Products
double dot (const point &a, const point &b) {return real (conj (a) * b);}
double cross (const point &a, const point &b) {return imag (conj (a) * b);}
 
// returns intersection of infinite lines ab and pq (undefined if they are parallel)
point intersect (const point &a, const point &b, const point &p, const point &q)
{double d1 = cross (p -a, b -a);
double d2 = cross (q -a, b -a);
return (d1 * q -d2 * p) / (d1 -d2);}

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

در نظریه گراف و علوم‌کامپیوتر پایین‌ترین جد مشترک برای دو راس مثل $u$ و $v$ در هر درخت ریشه دار پایین‌ترین راسی است که هر دوی $u$ و $v$ در زیر درخت آن باشند . درخت $n$ راسی ریشه‌دار $T$ و $m$ پرسش به صورت $(u_i,v_i)$ به طوری که $u_i$ و $v_i$ راس‌هایی از $T$ هستند داده‌شده است. مسئله پیدا کردن پایین‌ترین جد مشترک برای هر دو راس $u_i$ و $v_i$ است.
مثلا در شکل زیر راس 4 پایین‌ترین جد مشترک راس‌های 10 و 8 است.

ساده‌ترین راهی که به ذهن میرسد این است که به ازای هر پرسش $(u_i,v_i)$ ، ابتدا راسی که در عمق پایین‌تری وجود دارد را تا جایی که عمق آن برابر با عمق راس دیگر شود بالا بیاوریم(یعنی $u=father[u]$ ).

سپس تا زمانی که دو راس برابر نشدند در هر مرحله هر دو را یکی بالا میاوریم. از آنجایی که راس ریشه جد مشترک آن‌هاست این فرایند حتما متوقف می‌شود و راسی که در آن متوقف شدیم پایین‌ترین راسی‌است که جد مشترک $u_i$ و $v_i$ است. این الگوریتم اولیه از مرتبه‌ی $O(n)$ برای هر پرسش عمل می‌کند و هزینه کل از مرتبه‌ی $O(n\ast <!--\; \ast \; -->m)$ خواهد بود. (چرا؟)

ایده‌ایی که برای بهبود عملکرد این الگوریتم به ذهن می‌رسد استفاده از روشی است که i-امین راس بالای هر راس دلخواه را در مرتبه‌ی خوبی در اختیار ما قرار بدهد. مقدار $ancestor[v][i]$ را برابر با $2^i$ -امین راس بالای راس v در نظر می‌گیریم. برای تعیین مقادیر آرایه ancestor از روش برنامه‌ریزی پویا استفاده می‌کنیم:

1. به ازای هر v و i = 0 مقدار $ancestor[v][i]=father[v]$
2. به ازای هر i ناصفر $ancestor[v][i]=ancestor[ancestor[v][i-<!--\; -\; -->1]][i-<!--\; -\; -->1]$ است.

در قسمت اول الگوریتم ابتدا لازم بود که v و u را هم ارتفاع کنیم، می‌توانیم برای پیدا کردن x-امین راس بالای v با گام‌های به اندازه‌ی $2^i$ بالا برویم و در $O(lgn)$ مرحله راس مورد نظر را پیدا کنیم. (چرا؟) در قسمت بعدی برای پیدا کردن پایین‌ترین جد مشترک u و v می‌توانیم با جستجوی‌دودویی روی فاصله‌ی راس جواب و v جواب را در مرتبه‌ی $O(l{g}^{2}n)$ پیدا کنیم. می‌توانیم با کمی هوشمندی مرتبه‌ی پیدا کردن جواب برای هر پرسش را از $O(lgn+l{g}^{2}n)=O(l{g}^{2}n)$ کاهش دهیم.
(راهنمایی: نمایش دودویی هر عدد کوچک‌تر از n حداکثر $lgn$ رقم دارد).

#include <iostream>
	    #include <vector>
	     
	    using namespace std;
	     
	    const int MAXN = 100 * 1000 + 1;
	    const int MAX_LG_N = 17 + 1;
	    const int MAXM = 100 * 1000;
	     
	    int ancestor[MAXN][MAX_LG_N];
	    int father[MAXN];
	    int n, m; 
	    int query[MAXM][2];
	    int answer[MAXM];
	    int depth[MAXN];
	    vector<int> child[MAXN];
	    bool dfs_mark[MAXN];
	     
	    void dfs(int v);
	    int up(int v, int dist);
	    void input();
	    void preprocess();
	    int calculate_lca(int v, int u);
	     
	    int main(){
	        // get tree from input
	        cin >> n;
	        for(int i = 2; i <= n; i++){
	            cin >> father[i];
	            child[ father[i] ].push_back(i);
	        }
	        for(int i = 1; i <= m; i++)
	            cin >> query[i][0] >> query[i][1];
	     
	        preprocess();
	     
	        // get queries form input and print answers
	        cin >> m;
	        for(int i = 1; i <= m; i++){
	            int v, u;
	            cin >> v >> u;
	            cout << calculate_lca(v, u) << endl;
	        }
	        return 0;
	    }
	     
	    void preprocess(){
	        // calculate ancestor[v][i]
	        father[1] = 1; // father[root] = root
	        for(int i = 1; i <= n; i++)
	            ancestor[i][0] = father[i];
	        for(int j = 1; j < MAX_LG_N; j++)
	            for(int i = 1; i <= n; i++)
	                ancestor[i][j] = ancestor[ ancestor[i][j-1] ][j-1];
	     
	        // calculate depth[v] 
	        dfs(1); // dfs(root)
	    }
	     
	    int calculate_lca(int v, int u){
	        if(depth[v] > depth[u]) 
	            swap(u, v); // to sure depth[v] < depth[u]
	        u = up(u, depth[u] - depth[v]);
	        for(int j = MAX_LG_N - 1; j >= 0; j--)
	            if(ancestor[u][j] != ancestor[v][j]){
	                u = ancestor[u][j];
	                v = ancestor[v][j];
	            }
	        if(u == v) 
	            return v;
	        return ancestor[v][0];
	    }
	     
	     
	    void dfs(int v){
	        dfs_mark[v] = true;
	        for(int i = 0; i < child[v].size(); i++){
	            int u = child[v][i];
	            if(!dfs_mark[u]){
	                depth[u] = depth[v] + 1;
	                dfs(u);
	            }
	        }
	    }
	     
	    int up(int v, int dist){
	        for(int i = MAX_LG_N - 1; i >= 0; i--)
	            if(dist >= (1 << i)){
	                v = ancestor[v][i];
	                dist -= (1 << i);
	            }
	        return v;
	    }
	

در نظریهٔ گراف الگوریتم حذف معکوس(به انگلیسی: Reverse-delete algorithm) الگوریتمی است که در یک گراف همبند، با یال وزن دار درخت پوشای کمینه را بدست می‌آورد. اگر گراف ناهمبند باشد این الگوریتم درخت پوشای کمینه را برای هر مولفهٔ همبندی می‌یابد که در این صورت مجموعهٔ این درخت‌های پوشای کمینه را یک جنگل پوشای کمینه گویند.
این الگوریتم الگوریتمی حریصانه است که در هر لحظه بهترین انتخاب را انجام می‌دهد و برعکس الگوریتم کروسکال که الگوریتم دیگری برای پیدا کردن درخت پوشای کمینه‌است، عمل می‌کند. الگوریتم کراسکال با یک گراف خالی شروع می‌کند و یال‌ها را به آن اضافه می‌کند در حالیکه الگوریتم حذف معکوس با گراف اصلی شروع می‌کند و یال‌ها را از آن حذف می‌کند. الگوریتم به صورت زیر عمل می‌کند:

1. با گراف G که لیستی از یال‌های E دارد شروع کن.
2. E را به ترتیب نزولی وزن یال‌ها مرتب کن.
3. برای هر یال چک کن که آیا حذف این یال گراف را ناهمبند می‌کند یا نه.
4. اگر حذف کردن منجر به ناهمبندی گراف نمی‌شود یال را حذف کن

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

نمونه‌ی برنامه:

function ReverseDelete(edges[] E)
        sort E in decreasing order
        Define an index i ← 0
        while i <size(E)
           Define edge temp ← E[i]
             delete E[i]
             if temp.v1 is not connected to temp.v2
                 E[i] ← temp
             i ← i + 1
        return edges[] E
      

تعدادی از تکنیک‌های کلاس‌بندی آماری و یادگیری ماشینی در روش کلاس‌بندی در متن کاوی به کار بده می‌شود. برخی از این تکنیک‌هاعبارتند از مدل‌های رگرسیون، کلاسه‌بندهای بیزی، درخت‌های تصمیم‌گیری، کلاسه‌بندهای نزدیک‌ترین همسایه و ماشین‌های برداری و ... که ما در این مقاله به بررسی و تحلیل بعضی از این تکنیک‌ها می‌پردازیم.
KNN: K-Nearest Neighbor

مجموعه سندهای آموزشی است. D = {D1, D2, ..., Dn}

Q سند جدیدی است که قرار است مورد بررسی قرار گیرد.

TF، یا Term Frequency، یک عبارت در یک سند است که به عنوان داده‌های آموزشی پیش‌پردازش شده‌است.
V، مقدار کسینوس شباهت Q و Di است. به طوری که (i=1, 2, ..., n)

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

1. وقتی یک سند به عنوان ورودی به برنامه داده می‌شود، ابتدا TF را برای همه‌ی کلمه‌های کلیدی در سند به دست می‌آوریم.
2. سپس یک آرایه به سایز K در نظر می‌گیریم که ابتدا خالی است. این آرایه شامل id و نام و مقدار شباهت هر سند است.
3. یک شمارنده با مقدار اولیه صفر در نظر می‌گیریم counter=0.
4. برای هر یک از سندهای Di، در مجموعه‌ی D اگر count<=k ، مقدار v بین Q و Di را محاسبه می‌کنیم. توجه داشته باشید که هنگام محاسبه V فقط کلمات کلیدی که در هر دوی Q و Di دیده می‌شوند در نظر گرفته می‌شوند.
5. سپس به شمارنده یکی اضافه می‌شود و v و نام سند در آرایه A[] نوشته می‌شود.
6. در غیر این صورت یعنی اگر count<=0 نباشد. اگر مجموع TFها در سند Di بیش‌تر از حداقل مقدار v در آرایه A[] باشد.
7. مقدار کسینوس شباهت v بین سند Q و Di را محاسبه می‌کنیم. باز هم توجه داشته باشیم که هنگام محاسبه v فقط کلمات کلیدی که در هر دوی Q و Di دیده می‌شوند در نظر گرفته می‌شود.
8. اگر مقدار جدید v محاسبه شده از حداقل مقدار v در آرایه‌ی A[] بیش‌تر بود، سند را به همراه min(v) از آرایه‌ A[] حذف می‌کنیم. و سند Qi و مقدار جدید v را به A[] اضافه می‌کنیم. در غیر این صورت سند را رها می‌کنیم.
9. کلاسی را که پیش‌ترین تعداد سند در آرایه A[] را دارد برمی‌گردانیم.

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

فرض کنید میله‌ها را با اعداد 1 تا 3 شماره‌گذاری کنیم. هدف بردن n دیسک از میله شماره 1 به میله شماره 3 است. می‌توان مسأله را به این صورت شکست : ایتدا فرض می‌کنیم بزرگترین حلقه وجود ندارد. این فرض صحیح است، چرا که حلقه‌ای وجود ندارد که اندازه‌ی آن از این میله بزرگتر باشد. مسآله را تبدلی می کنیم به این مسآله که، می خواهیم n-1 حلقه را از میله شماره 1 به میله شماره 2 منتقل کنیم. سپس حلقه‌ی شماره n را به میله‌ی شماره 3 منتقل کنیم و سپس مسأله‌ی انتقال n-1 حلقه از میله‌ی شماره 2 به میله‌ی شماره 3 را حل کنیم. پیاده سازی این الگوریتم به صورت زیر است :

void Hanoi (int start, int end, int count) {
          if(count == 1 ) {
              cout<<"Ring number 1 from "<<start<<" to "<<end<<endl;
              return;
          }
          Hanoi(start, 6-start-end, count-1);
          cout << "Ring number "<<count<<" from "<<start<<" to "<<end<<endl;
          Hanoi(6-start-end, end , count-1);
      }
      

دو ظرف به ظرفیت‌های ۵ و ۶ لیتری، ابتدا هر دو ظرف خالی هستند.

1. ظرف ۶لیتری را از آب پر می‌کنیم.
2. ظرف ۵لیتری را پر می‌کنیم.
3. هر دو ظرف را خالی می‌کنیم.
4. می‌تواینم آب ظر‌ها را درون یکدیگر بریزیم.
5. نکته: فقط در هر لحظه می‌توانیم یک کار را انجام دهیم.

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

1. جارو در محیط ۱ – هر دو محیط خاکی
2. جارو در محیط ۱ – محیط ۱ خاکی
3. جارو در محیط ۱ – محیط ۲ خاکی
4. جارو در محیط ۱ – هیچکدام از محیط ها خاکی نیست
5. جارو در محیط ۲ – هر دو محیط خاکی
6. جارو در محیط ۲ – محیط ۱ خاکی
7. جارو در محیط ۲ – محیط ۲ خاکی
8. جارو در محیط ۲ – هیچکدام از محیط ها خاکی نیست

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

حالا تصور کنید که عامل تمام اثرهای عمل هایش را می داند، اما دسترسی به محیط محدود است. برای مثال، عامل هیچ حسگری ندارد. در این حالت فقط می داند که وضعیت اولیه اش یکی از اعضای مجموعه (۱،۲،۳،۴،۵،۶،۷،۸) است. ممکن است فکر کنید که وضعیت عامل ناامید کننده است! اما در حقیقت اینقدر ها هم که به نظر می آید ناگوار نیست. زیرا عامل می داند که هر کدام از اعمالش چه اثری دارند. برای مثال می تواند محاسبه کند که عمل راست موجب می شود تا در یکی از حالات (۲،۴،۶،۸) باشد. بنابراین می تواند با انتخاب یک دنباله عملیاتی، به هدف برسد. به طور خلاصه هنگامی که محیط تماما قابل دسترسی نیست، عامل باید در مورد مجموعه حالت هایی که ممکن است هدف برسد، استدلال کند. به این نوع از مسئله مسئله چند حالته می گویند.

اگر عامل اثر اعمال خودش را نادیده بگیرد می تواند به مشکلات دیگری دچار شود. برای مثال تصور کنید که محیط غیر قطعی باشد از این رو باید از قانون مورفی(Murphy) تبعیت کند. برای مثال عامل می داند که در یکی از وضعیت های ۱ یا ۳ است. با انجام هر عمل در یک حالت دیگر قرار می گیرد که امکان دارد آن را به هدف برساند و یا با شکست مواجه شود. در چنین مواردی عامل تمام درخت عملیات را محاسبه کند. به طور کلی هر شاخه درخت با یک امکان احتمالی که از آن ناشی می شود، بررسی می شود. به همین علت به آن مسئله احتمالی می گویند.

حال تصور کنید که عامل هیچ اطلاعی در مورد اثرات اعمالش و اینکه در کجا قرار دارد، ندارد.(بدبخت تر از این عامل سراغ ندارید!؟) مانند کسی که در یک کشور غریب و بدون هیچ نقشه ای گم شده است. در ای حالت عامل باید تجربه کند و به تدریج کشف کند که چه عملی باید انجام شود و چه وضعیت هایی وجود دارند. این روش یک نوع جستجو است که بر خلاف جستجو در دنیای فرضی، می تواند عامل را با خطرات جدی مواجه کند. به مسائلی از این قبیل، مسئله اکتشافی می گویند.

از جستجوی ابتدا بهترین استفاده می‌کند و کوتاه ترین مسیر را بین دو گره مبدا و مقصد داده شده به وسیله گره‌های دیگر می‌یابد.
این روش با ترکیب $g(n)$ هزینه رسیدن به گره $n$ و $h(n)$ هیوریستیک یا تخمین هزینه رسیدن از گره $n$ م تا هدف گره‌ها را ارزیابی می‌کند:

از آنجایی که $g(n)$ هزینه مسیر از گره شروع به گره $n$ و $h(n)$ هزینه تخمینی ارزان ترین مسیر از $n$ به هدف است، داریم:
$f(n)$ = هزینه برآورد ارزان ترین راه حل از طریق $n$

بنابراین اگر به دنبال ارزان ترین راه حل هستیم، اولین کار معقول امتحان گره‌ای است که کمترین مقدار $h(n)+g(n)$ را داراست. مشخص می‌شود که این راهبرد کاملاً معقولانه‌است. اگر تابع آروین $h(n)$ شرایط خاصی داشته باشد. جستجوی A* هم کامل و هم بهینه‌است.

اگر A* همراه با الگوریتم جستجوی درخت استفاده شود، آنگاه تحلیل بهینگی آن بسیار ساده و سر راست می‌شود. A* بهینه‌است اگر $h(n)$ یک آروین قابل قبول باشد. یعنی $h(n)$ هرگز هزینه رسیدن به هدف را بیش از اندازه واقعی برآورد نکند. این آروین‌ها ذاتاً بهینه هستند زیرا آنها فکر می‌کنند که هزینه راه حل مسئله کمتر از مقدار واقعی آن است. از آنجا که $g(n)$ هزینه رسیدن به $n$ را به طور دقیق نشان می‌دهد، می‌توان بلافاصله نتیجه گرفت که $f(n)$ هرگز هزینه واقعی راه حلی که از $n$ می‌گذرد را اضافه برآورد نمی‌کند.

function A*(start,goal)
           closedset:= the empty set  // The set of nodes already evaluated.
           openset:= {start}    // The set of tentative nodes to be evaluated,
                                // initially containing the start node
           came_from:= the empty map // The map of navigated nodes.

           g_score[start]:= 0 // Cost from start along best known path.
           h_score[start]:= heuristic_cost_estimate(start, goal)
           f_score[start]:= g_score[start] + h_score[start] // Estimated total cost
                                                            // from start to goal through y.

           while openset is not empty
               x:= the node in openset having the lowest f_score[] value
               if x = goal
                   return reconstruct_path(came_from, came_from[goal])

               remove x from openset
               add x to closedset
               foreach y in neighbor_nodes(x)
                   if y in closedset
                       continue
                   tentative_g_score:= g_score[x] + dist_between(x,y)

                   if y not in openset
                       add y to openset
                       tentative_is_better:= true
                   else if tentative_g_score <g_score[y]
                       tentative_is_better:= true
                   else
                       tentative_is_better:= false

                   if tentative_is_better = true
                       came_from[y]:= x
                       g_score[y]:= tentative_g_score
                       h_score[y]:= heuristic_cost_estimate(y, goal)
                       f_score[y]:= g_score[y] + h_score[y]

           return failure

       function reconstruct_path(came_from, current_node)
           if came_from[current_node] is set
               p:= reconstruct_path(came_from, came_from[current_node])
               return (p + current_node)
           else
               return current_node
      

جست‌و‌جوی اول‌سطح (‌Breadth First Search) که به bfs مشهور است، روشی برای پیمایش گراف است که بعد از جست‌وجوی عمق‌اول مهم‌ترین و پرکاربرد‌ترین الگوریتم پیمایش گراف است. این الگوریتم معمولا در گراف‌ها‌ی وزن دار کاربرد خاصی ندارد و عمده نقش آن در گراف‌های بی‌وزن و برای پیدا کردن کوتاه‌ترین فاصله بین یک راس تا بقیه‌ی راس‌هااست.

این الگوریتم ابتدا یک راس ریشه مانند v را به عنوان شروع میگیرد. سپس راس‌ها را سطح بندی میکند. سطح بندی به این صورت است که تمام راس‌های مجاور v را در سطح اول قرار میدهیم، حال برای سطح $i+1$ راس u که مجاور یکی از رئوس سطح $i$ است را در این سطح قرار میدهیم به شرطی که u در هیچ سطح دیگری نیامده باشد. به عبارت دیگر راس هارا بر اساس کوتاه‌ترین فاصله از v سطح بندی میکنیم. حال برای پیمایش به ترتیب سطح، و در هر سطح به ترتیب دلخواه وارد راس‌ها میشویم. پس اولین زمانی که به هر راس می‌رسیم، با کمترین فاصله ممکن نسبت به v رسیده ایم.

با توجه به اینکه به هر راس حداکثر یکبار وارد میشویم در نتیجه هر یالی هم حداکثر دوبار به ازای دو سر آن شمرده می‌شود، پس در کل هزینه الگوریتم از $O(n+e)$ است که e تعداد یال‌ها و n تعداد راس‌ها است.

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

#include <queue>
          #include <vector>
           
          const int MAXN = 100 * 1000 + 10;
           
          bool mark[MAXN];
          int vector<int> adj[MAXN];
           
          void bfs(int v) {
              queue<int> q;
           
              mark[v] = 1;
              q.push(v);
           
              while(q.size()) {
                  v = q.front(); //    راس ابتدایی را از صف بر میداریم
                  q.pop();
                  // کار‌ها‌ی پیش‌ترتیب را اینجا مینویسیم
                  for(int i = 0; i < adj[v].size(); i++) {
                      int u = adj[v][i];
           
                      if (mark[u] == 1) //    قبلا این راس را به صف اضافه نکرده باشیم
                          continue;
           
                      mark[u] = 1;
                      q.push(u);
                  }
           
              }
          }
      

می‌دانیم که جستجوی عمیق کننده تکراری تکنیکی مفید برای کاهش درخواست حافظه‌است حال می‌توانیم از این تکنیک استفاده نموده و هر بار یک جستجوی عمقی تا هزینهf-limite را جستجو کنیم. اگر به جواب نرسیدیم هزینه f-limite را افزایش داده و از اول به بسط فضای حالت می‌پردازیم.

1. محدودیت هزینه در هر مرحله به گونه‌ای انتخاب می‌شود که در مراحل قبلی ثابت شده‌است که جوابی با هزینهٔ کمتر از این مقدار وجود ندارد.
2. می‌توان هزینه مرحله جدید را برابر با کمترین هزینهٔ نودی که در مرحله قبلی بسط داده نشده قرار داد از آنجا که این روش به صورت عمقی است پس پیچیدگی فضایی آن در بدترین حالت (S(b.d است.
3. ‍‍‍‍‍‍پیچیدگی زمانی بستگی به تابع اکتشافی دارد.
4. ‍‍‍‍‍‍این روش نیز مشابه *A کامل و بهینه‌است.

جست‌و‌جوی عمق‌اول که به $DepthFirstSearch$ معروف است در واقع الگوریتمی برای پیمایش گراف است. شاید با کمی شک بتوان گفت که پرکاربرد‌ترین الگوریتم در گراف همین الگوریتم است چراکه هم کد آن کم است، هم هزینه زمانی و حافظه‌ای آن کم است، هم برای اکثر سوال‌های گراف نیاز به پیمایش است.

الگوریتم به این شکل است که ابتدا یک رأس مانند v را انتخاب می‌کنیم و آن را ریشه می‌نامیم. ریشه را علامت‌گذاری می‌کنیم. سپس یک رأس دل خواه علامت نخورده‌ی مجاور با $v$ را انتخاب می‌کنیم و آن را $u$ می‌نامیم. را یکی از بچه‌های $v$ می‌کنیم، سپس $u$ را علامت می‌زنیم. حال همین الگوریتم را روی $u$ از ابتدا اجرا می‌کنیم (یعنی یکی از همسایه‌های مجاور و علامت نخورده $u$ را انتخاب می‌کنیم و …).

الگوریتم گفته شده زمانی به بن‌بست می‌خورد که به ازای راسی مانند $u$ ، تمام همسایه‌هایش علامت خورده باشند. در این صورت به راس پدر (رأسی که از آن وارد $u$ شدیم) بر‌می‌گردیم و دوباره همین الگوریتم را از ادامه اجرا می‌کنیم (یعنی وارد پدر $u$ می‌شویم و اگر همسایه‌ی علامت نخورده‌ای داشت وارد آن می‌شویم و اگر نداشت به رأس پدرش باز می‌گردیم).

برنامه زمانی متوقف میشود که به رأس $v$ برگشته باشیم و تمام همسایه‌هایش علامت خورده باشند که در این صورت می‌گوییم الگوریتم پایان یافته است. \\دقت کنید که اگر گراف شما همبند نباشد، این جست‌و‌جو تنها رأس‌های مؤلفه ریشه را پیمایش می‌کند پس اگر برای پیمایش روی تمام رأس‌ها این الگوریتم را به ازای هر رأس علامت‌نخورده‌ای تکرار می‌کنیم.

جست‌وجوی اول‌عمق یال‌هایی که تشکیل دور می‌دهند را نمی‌رود؛ در نتیجه اگر یال‌های رفته شده را کنار هم بگذاریم، تشکیل یک درخت ریشه‌دار می‌دهند که به آن درخت جست‌و‌جوی اول‌عمق می‌گویند. همچنین زمان ورود و خروج رأس‌ها نیز ویژگی‌های منحصر به فردی دارد. مجموع این ویژگی‌هاباعث شده که این الگوریتم تبدیل به الگوریتمی مهم و کاربردی شود.

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

زمان ورود یا شروع ( $startingtime$ ) و خروج یا پایان ( $finishingtime$ ) را به ترتیب این‌گونه تعریف می‌کنند: اولین زمان دیده شدن رأس و آخرین زمان دیده شدن رأس. یعنی زمانی که برای اولین بار وارد یک راس می‌شویم و آن را علامت گذاری می‌کنیم را زمان ورود و آخرین زمانی که از رأس خارج می‌شویم و تمام همسایه‌هایش دیده شده است و در حال بازگشت به راس پدر هستیم را زمان خروج می‌گیریم. پس اگر بخواهیم با رنگ‌ها این دو زمان را معادل کنیم، زمان خاکستری شدن برابر زمان شروع و زمان سیاه شدن برابر زمان خروج است.

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

1. لم: زمان شروع رأس $v$ کمتر از $u$ است اگر و تنها اگر $v$ جد $u$ باشد یا در درخت ریشه‌دار قبل از $u$ آمده باشد.
2. لم: زمان خاتمه رأس $v$ کمتر از $u$ است اگر و تنها اگر $u$ جد $v$ باشد یا در درخت ریشه‌دار قبل از $u$ آمده باشد.
3. لم: اگر زمان شروع رأس $v$ کمتر از $u$ و زمان پایان رأس $u$ کمتر از $v$ باشد، آنگاه $v$ جد $u$ است.

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

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

1. یال‌‌های درخت ساخته شده (یال درختی یاTree Edge)
2. از یک راس به جدش (یال عقب‌رو یا Back Edge)
3. از یک راس به زیر درختش (یال جلو‌رو یا Forward Edge)
4. هیچ کدام از سه مورد بالا (یال میانی یا Corss Edge)

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

همچنین در گراف های جهت‌دار یال میانی از سمت چپ درخت به سمت راست نداریم. (یعنی یال میانی از v به u داریم اگر و تنها اگر زمان خاتمه u زودتر از v باشد).

1. ابتدا همه رأس‌ها را سفید و بی‌علامت کن.
2. رأس دل‌خواه $v$ را به عنوان ریشه انتخاب می‌کن.
3. رأس $v$ را علامت بزن و خاکستری کن.
4. کار‌های پیش ترتیب روی $v$ را انجام بده.
5. به ازای تمام یال های $w$ ، که از راس $v$ به $u$ هستند کار‌های را انجام بده:
6. اگر راس $u$ علامت نخورده بود به خط ۳ برو و $u$ را به جای $v$ فرض کن و برنامه را اجرا کن.
7. کارهای پس ترتیب روی یال $w$ را انجام بده.
8. کارهای پس ترتیب روی $v$ را انجام بده و این رأس را سیاه کن.
9. کار این رأس را تمام کن و به رأس پدر بازگرد.

از آنجایی که به رأس حداکثر یک‌بار وارد می‌شویم در نتیجه الگوریتم هر یالی را حداکثر دوبار می‌بیند (یک‌بار به ازای هر سر یال) پس در کل زمان اجرای آن از $O(n+e)$ است. که $n$ تعداد رأس‌ها و $e$ تعداد یال‌ها است.

اگر گراف را به صورت لیست مجاورت داده باشند، کد آن به صورت زیر می‌شود.

#include <vector>
        #include <iostream>
         
        const int MAXN = 100 * 1000 + 10;
         
        using namespace std;
         
        bool mark[MAXN];
        int color[MAXN];  // رنگ رأس
        int start[MAXN];  // زمان شروع
        int finish[MAXN];  // زمان پایان
        vector <int> adj[MAXN];  // لیست مجاورت
        int n;   // تعداد رأس‌ها
        int m;   // تعداد یال‌ها
        int now_time;  // زمان فعلی
         
        void dfs(int v) {
            mark[v] = 1;
            color[v] = 1;        // این رأس را خاکستری کن
            start[v] = now_time++;
            // کارهای پیش‌ترتیب را انجام بده
            for(int i = 0; i < adj[v].size(); i++) {
                int u = adj[v][i];
                if(mark[u] != 1)
                    dfs(u);
         
                // کار‌های پس‌ترتیب این یال را انجام بده
            }
            color[v] = 2;        // این رأس را سیاه کن
            finish[v] = now_time;  // می‌توانید هنگام خروج هم زمان را اضافه کنید.
            // کار‌های پس‌ترتیب این رأس را انجام بده
        }
         
         
        void input()
        {
            cin >> n >> m;
            for (int i = 0; i < m; i++) {
                int v, u;
                cin >> v >> u;
                adj[--v].push_back(--u);
                adj[u].push_back(v);
            }
        }
         
        int main()
        {
            input();
            for (int i = 0; i < n; i++)
                if(mark[i] == 0)
                    dfs(i);
        }
    

در روش قبلی(*IDA)استفاده بسیار جزئی از حافظه داشت و بین تکرارها این جستجو فقط یک عدد خاص از محدوده جاری را نگه می‌داشت (f-cost) و چون نمی‌توانست تاریخچه اش را به خاطر آورد مجبور به تکرار می‌شد الگوریتم *SMA قادر خواهد بود تا از تمام حافظه موجود برای اجرای جستجو استفاده نماید هرچه حافظه بیشتر باشد کارآیی جستجو بالاتر خواهد بود.

1. می‌توان از تمام حافظه مورد دسترس خود استفاده کرد.
2. تا جایی که حافظ اجازه می‌دهد از تولید حالات تکراری جلوگیری می‌کند.
3. در صورتی کامل است که حافظه برای ذخیره کم عمق‌ترین مسیر راه حل وجود داشته باشد.
4. در صورتی بهینه‌است که حافظهٔ کافی برای ذخیره کم عمق‌ترین مسیر راه حل وجود داشته باشد.

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

چگونه می توان $n$ مهره‌ی وزیر شطرنج را در یک صفحه‌ی $n\ast <!--\; \ast \; -->n$ شطرنج چید به طوری که هیچ ۲ مهره از این $n$ مهره یک دیگر را تهدید نکنند؟

ساده‌ترین شکل الگوریتم به این صورت است:
از سطر اول صفحه شروع کرده ، در هر سطر به صورت بازگشتی هر دفعه یکی از ستون ۱ تا $n$ را به وزیر سطر $i$ اختصاص داده و سپس به سطر های بعد می‌رویم. در صورتی که دو وزیر همدیگر را تهدید کنند به مرحله‌ی قبل باز می‌گردیم. در صورتی که همه‌ی $n$ وزیر را در صفحه قرار دهیم، جواب را گزارش می کنیم.

پیچیدگی الگوریتم

پیچیدگی الگوریتم بالا $O(n!)$ است.

پیاده‌سازی

کد زیر برای حالت شمارش جواب ها ( SINGLE_SOLUTION=0 ) تا $n=14$ جواب می‌دهد و برای حالت گزارش یک جواب تا $n=30$ در زمان خوبی جواب می‌دهد.

#include <iostream>
      #define SINGLE_SOLUTION 0
      #define PRINT_SOLUTIONS 0
       
      using namespace std;
      const int maxn = 100;
      int n;
      int a[maxn];
      int mark[maxn];
      int markd1[maxn*2];
      int markd2[maxn*2];
      int ans=0;
       
       
      void acceptboard(){
          ans++;
          if(PRINT_SOLUTIONS){
      	    for(int i = 0 ; i < n ; ++i){
      		for(int j = 0 ; j < n ; ++j)
      		    if(a[i]==j)
      			cout << "Q";
      		    else{
      			cout << ".";
      		    }
      		cout << endl;
      	    } 
         	    cout << endl;
          }
          if(SINGLE_SOLUTION){
      	    exit(0);
          }
      }
      

پیاده‌سازی سریع‌تر

حالت یافتن یک جواب را می‌توان با روش های پیشرفته تر از روش پس‌گرد تا اندازه‌ی زیادی سریع کرد. مثلا کد زیر در طی چند ثانیه یک جایگشت از ستون های ۱۰۰۰۰ وزیر که یک دیگر را تهدید نمی‌کنند به دست می‌آورد. برای مطالعه ی بیشتر می‌توانید به لینک های زیر در ویکی‌پدیا مراجعه کنید:
Hill Climbing
Simulated annealing

#include <iostream>
    	#include <iostream>
    	#include <cstdlib>
    	#include <algorithm>
    	#include <queue>
    	#include <deque>
    	#include <set>
    	#include <vector>
    	#include <map>
    	#include <string>
    	#include <cstring>
    	#include <iomanip>
    	#include <cstdio>
    	#include <fstream>
    	#include <sstream>
    	 
    	#define For(i,a,n) for(int i =a ; i < n ; ++i )
    	#define all(x) (x).begin(),(x).end()
    	#define n(x) (int)(x).size()
    	#define pb(x) push_back(x)
    	 
    	using namespace std;
    	typedef long long ll;
    	typedef pair<int,int> pii;
    	const int maxn = 50000;
    	int n;
    	int t=100*1000;
    	int dl[maxn*2];
    	int dr[maxn*2];
    	int ja[maxn];
    	int r(int i , int j)
    	{
    		return j-i+n-1;
    	}
    	int l(int i,  int j)
    	{
    		return i+j;
    	}
    	ll k;
    	int it;
    	 
    	int main()
    	{
    		ios::sync_with_stdio(false);
    		srand(4131);
    		cin >> n;
    		For(i,0,n)
    			ja[i]=i;
    	 
    		do
    		{
    			random_shuffle(ja,ja+n);
    			it=0;
    			For(i,0,2*n)
    				dl[i]=dr[i]=0;
    			For(i,0,n)
    			{
    				dl[l(i,ja[i])]++;
    				dr[r(i,ja[i])]++;
    			}
    			k=0;
    			For(i,0,n)
    				k-=dr[r(i,ja[i])]-1;
    			For(i,0,n)
    				k-=dl[l(i,ja[i])]-1;
    			k/=2;
    			while(it<t)
    			{
    				For(f,0,n){
    					For(s,f+1,n){
    						it++;
    	//					int f=rand()%n;
    	//					int s=f;
    	//					while(s==f)
    	//						s=rand()%n;
    						int si=dr[r(s,ja[s])]+dl[l(s,ja[s])]-dl[l(s,ja[f])]-dr[r(s,ja[f])]-2;
    						dr[r(s,ja[s])]--;
    						dl[l(s,ja[s])]--;
    						dl[l(s,ja[f])]++;
    						dr[r(s,ja[f])]++;
    						int fi=dr[r(f,ja[f])]+dl[l(f,ja[f])]-dl[l(f,ja[s])]-dr[r(f,ja[s])]-2;
    						dr[r(f,ja[f])]--;
    						dl[l(f,ja[f])]--;
    						dl[l(f,ja[s])]++;
    						dr[r(f,ja[s])]++;
    						if(fi+si>0|| (!(rand()%(5))) && (k < -1000000))
    						{
    							swap(ja[f],ja[s]);
    							k+=fi+si;
    						}
    						else
    						{
    							dr[r(s,ja[s])]++;
    							dl[l(s,ja[s])]++;
    							dl[l(s,ja[f])]--;
    							dr[r(s,ja[f])]--;
    							dr[r(f,ja[f])]++;
    							dl[l(f,ja[f])]++;
    							dl[l(f,ja[s])]--;
    							dr[r(f,ja[s])]--;
    						}
    					}
    				}
    			}
    		}while(k);
    		const int DBG=0;
    		if(DBG)
    		{
    			For(i,0,n)
    			{
    				For(j,0,ja[i])
    					cout << ".";
    				cout << "Q";
    				For(j,ja[i]+1,n)
    					cout << ".";
    				cout << endl;
    			}
    		}
    		else
    		{
    			For(i,0,n)
    				cout << ja[i]+1 << endl;
    		}
    		return 0;
    	}
    	//
    	//el psy congroo
    	//
    	

تعریف

این مسئله شکل‌های متنوع‌ای دارد، یکی از فرم‌های آن در کوله‌پشتی پویا بررسی شده‌است. در حالت کلی این مسئله به صورت زیر تعریف می‌شود:
فرض کنید یک کوله‌پشتی با حجمی ثابت و مجموعه‌ای از اشیاء دارید که هر کدام از آن ها حجمی و ارزشی دارند. می‌خواهید کوله‌پشتی خود را به نحوی پرکنید که حجم اشیا برداشته شده از حجم کوله‌پشتی بیشتر نباشد و مجموع ارزش اشیا بیشینه باشد.

در بعضی از شکل های مسئله تعداد یک شی بیشمار و در بعضی محدود است، در بعضی از اشکال اشیا ارزشی برابر دارند و در بعضی اشیا می‌توانند به صورت پیوسته برداشته شوند (2.5 کیلوگرم شن یا بنزین در یک مخزن(کوله‌پشتی)).
لازم به ذکر است که در بیشتر این شکل ها الگوریتم حریصانه جواب بهینه را نمی‌دهد.

الگوریتم

برای حالت گسسته معمولا مثال نقضی پیدا می‌شود که این الگوریتم جواب بهینه را ندهد. برای همین در اینجا حالت پیوسته را بررسی می‌کنیم، فرض کنید $n$ نوع شی متفاوت داریم که از $i$ امین نوع، به حجم $w_i$ و ارزش $c_i$ موجود است ، می‌خواهیم به حجم $W$ از آنها برداریم به صورتی که مجموع ارزش بیشینه شود، می توان کسری از یک شی را برداشت.

فرض کنید شی $i$ ام بیشترین مقدار $\frac{c_i}{w_i}$ را دارد، یک جواب بهینه دلخواه را در نظر بگیرید، در صورتی که مقداری از این شی استفاده نشده باشد و در کوله‌پشتی مقداری از شی دیگری (مثلا $j$ ) باشد ، می‌توان جواب را با تعویض مقداری از $j$ با مقداری از $i$ بهتر کرد یا بهینه نگه‌داشت. پس شی $i$ انتخاب حریصانه‌ی مناسبی است و الگوریتم زیر جواب بهینه را می دهد :
از کوله‌پشتی خالی شروع کرده و در هر مرحله کوله پشتی را با شیئی که بیشترین ارزش را نسبت به حجم دارد پر می‌کنیم تا وقتی که کوله‌پشتی پرشود یا آن شی تمام شود.

پیچیدگی الگوریتم

در صورت مرتب بودن اشیا بر حسب $\frac{c_i}{w_i}$ ، پیچیدگی الگوریتم از $O(n)$ است، در غیر این صورت از $O(nlgn)$ می‌باشد.

// مرتب سازی در صورت نیاز انجام شود
      for(int i = 0 ; i < n ; ++i){
          double v=min(W,w[i]);
          W-=v;
          ans+=v*c[i];
      

تعریف

الگوریتم تپه نوردی (Hill climbing) الگوریتمی است که برای یافتن بهترین پاسخ یک مسئله یا برای پیدا کردن پاسخی از مسئله که به اندازهٔ کافی مناسب و بهینه باشد، استفاده می شود.

بررسی

برای بررسی الگوریتم تپه نوردی مسئلهٔ زیر را بررسی می کنیم:
برای بررسی الگوریتم تپه نوردی مسئلهٔ زیر را بررسی می کنیم:
- تابع f به هر یک از اعضای مجموعهٔ متناهی S یک عدد حقیقی نسبت می دهد. هدف ما یافتن عضوی از S است که بیش‌ترین (یا کم ترین) مقدار به آن نسبت داده شده است.
همان گونه که گفته شد در این جا فرض بر این است که مقدار تابع f برای چندین عضو مختلف S بیشینه است و هدف ما یافتن تنها یکی از آن هاست. (در غیر این صورت معمولاً الگوریتم تپه نوردی، الگوریتم کار آمدی نیست.)

الگوریتم

ابتدا یکی از اعضای مجموعهٔ S را (به صورت تصادفی) انتخاب می کنیم و آن را A می نامیم. سپس در میان اعضایی از S که به A نزدیکند به دنبال پاسخ مناسب تری برای مسئله می گردیم. به بیانی دیگر نلاش می کنیم در میان اعضایی که به A نزدیکند عضوی بیابیم که مقدار تابع f برای آن بیش تر از $f(A)$ باشد. سپس این روند را ادامه می دهیم تا به یک بیشینهٔ نسبی برای f دست یابیم.
بدیهی است که بیشینهٔ نسبی به دست آمده لزوماً پاسخ خواسته شده نیست. ولی اگر الگوریتم گفته شده چندین بار تکرار شود می توان به یافتن پاسخی مطلوب امیدوار بود. (در هر بار اجرای الگوریتم نخستین عضو به صورت تصادفی انتخاب می شود.) بدی این الگوریتم این است که در یک تابع که مینیمم ویا ماگزیمم محلی زیادی دارد(مانند تابع Ackley)به راحتی در ان گیر میفتد و قدرت خروج از انجا را ندارد چون این الگوریتم فقط نقاط اطراف خود را میبیند که در لحظه حضور در یک ماگزیمم محلی این احساس را دارد که از همه نقاط بالاتر است در حالی که چنین نیست و ان در یک ماگزیمم محلی اسیر شده است.

سورس برنامه تپه نوردی در محیط دو بعدی (که با f سه بعدی می شود)

Hill Climbing Algorithm

    	bestEval = -INF;

    	currentNode = startNode;

    	bestNode = NULL;

    	for MAX times

    	if (EVAL(currentNode)> bestEval)

    	bestEval = EVAL(currentNode);

    	bestNode = currentNode;

    	L = NEIGHBORS(currentNode);

    	nextEval = -INF;

    	for all x in L

    	if (EVAL(x)> nextEval)

    	currentNode = x;

    	nextEval = EVAL(x);

    	return currentNode
    	

الگوریتم تپه نوردی تعمیم یافته

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

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

Procedure HillClimbing

    	 Generate a solution ( s' )
    	 Best = S'
    	 Loop
    	   S = Best
    	   S' = Neighbors (S)
    	   Best = SelectBest (S')
    	   IF there is no changes in Best solution THEN
    	        Jump to new state in state space
    	 Until stop criterion satisfied
    	

تعریف

الگوریتم تبرید شبیه‌سازی شده (Simulated Annealing) (SA)، یک الگوریتم بهینه‌سازی فراابتکاری ساده و اثربخش در حل مسائل بهینه‌سازی است. منشأ الگوریتم تبرید شبیه‌سازی شده، کارهای کریک پاتریک و کرنی و همکارانشان در سال‌های ۱۹۸۳ و ۱۹۸۵ است. کریک پاتریک و همکارانش، متخصصانی در زمینهٔ فیزیک آماری بودند. آنها برای حل مسائل سخت بهینه‌سازی، روشی مبتنی بر تکنیک تبرید تدریجی پیشنهاد نمودند. تکنیک تبرید تدریجی، به وسیلهٔ متالورژیست‌ها برای رسیدن به حالتی که در آن ماده جامد، به خوبی مرتب و انرژی آن کمینه شده باشد، استفاده می‌شود. این تکنیک شامل قرار دادن ماده در دمای بالا و سپس کم کردن تدریجی این دماست.

در روش شبیه‌سازی تبریدی (SA)، هر نقطه s در فضای جستجو مشابه یک حالت از یک سیستم فیزیکی است، و تابع (E(s که باید کمینه شود، مشابه با انرژی داخلی سیستم در آن حالت است. در این روش، هدف انتقال سیستم از حالت اولیه دلخواه، به حالتی است که سیستم در آن کمترین انرژی را داشته باشد.

ساختار کلی

برای حل یک مسئلهٔ بهینه‌سازی، الگوریتم SA ابتدا از یک جواب اولیه شروع می‌کند و سپس در یک حلقه تکرار به جواب‌های همسایه حرکت می‌کند. اگر جواب همسایه بهتر از جواب فعلی باشد، الگوریتم آن را به عنوان جواب فعلی قرار می‌دهد (به آن حرکت می‌کند)، در غیر این صورت، الگوریتم آن جواب را با احتمال exp(-ΔE/T) به عنوان جواب فعلی می‌پذیرد. در این رابطه ΔE تفاوت بین تابع هدف جواب فعلی و جواب همسایه‌است و T یک پارامتر به نام دما است. در هر دما، چندین تکرار اجرا می‌شود و سپس دما به آرامی کاهش داده می‌شود. در گام‌های اولیه دما خیلی بالا قرار داده می‌شود تا احتمال بیشتری برای پذیرش جواب‌های بدتر وجود داشته باشد. با کاهش تدریجی دما، در گام‌های پایانی احتمال کمتری برای پذیرش جواب‌های بدتر وجود خواهد داشت و بنابراین الگوریتم به سمت یک جواب خوب همگرا می‌شود. الگوریتم SAیک الگوریتم غیرمقید می‌باشد که برای طراحی‌های سخت به کار می‌رود.

همسایه‌های یک حالت (جواب)، حالت‌های جدیدی از مسئله هستند که با تغییر در حالت کنونی و با توجه به روشی از پیش تعیین شده ایجاد می‌شوند. برای مثال در مسئله فروشندهٔ دوره‌گرد، هر حالت به طور کلی یک جایگشت خاص از شهرهایی است که باید ملاقات شوند. همسایهٔ یک جواب، جایگشت‌هایی هستند که با انتخاب یک جفت از شهرهای هم جوار، از کل مجموعه جایگشت‌ها، و جابجا کردن آن دو شهر ایجاد می‌شوند. عمل تغییر در جواب فعلی و رفتن به جواب‌های همسایه «حرکت» (move) خوانده می‌شود و «حرکت» های متفاوت، همسایه‌های گوناگون را بدست می‌دهد.

تعریف

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

شرح

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

1. راس‌های گراف را به دو مجوعه $V^{\prime }$ (شامل همه راس‌های گراف به جز راس دلخواه v) و $V$ (شامل v) افراز کن.
2. تا زمانی که $V$ شامل تمام راس‌ها نشده کار‌های زیر را انجام بده
   1. بین تمام یال‌هایی که بین مجوعه $V$ و $V^{\prime }$ کم‌وزن‌ترین را انتخاب کن(مثلا یال (u,v) که u در $V$ ).
   2. راس v را از $V^{\prime }$ حذف و به $V$ اضافه کن.
   3. یال (u,v) را به عنوان یالی از درخت پوشای کمینه انتخاب کن.
3. پایان

ادعا: اگر گراف را به دو مجموعه $V$ و $V^{\prime }$ از راس‌ها افراز کنیم، کم‌وزن‌ترین یال بین یال‌هایی که یک طرفشان در مجموعه $V$ و طرف دیگرشان در مجموعه $V^{\prime }$ است باید جزء درخت پوشای کمینه باشد. (اگر چند یال با کم‌ترین وزن وجود داشت، باید دقیقا یکی از آن‌ها جزء درخت پوشای کمینه باشد).

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

مثال

تصویر زیر نمایشی از اجرای الگوریتم پریم روی یک مثال است.

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

پیچیدگی الگوریتم

یک روش خوب برای بهینه کردن الگوریتم نگه داشتن کم‌ترین فاصله‌ی هر راس تا راس‌های انتخابیست. وقتی یک راس به مجموعه‌ی ما اضافه شد. فاصله‌ی بقیه راس‌ها را به روز می‌کنیم. در این صورت هر بار برای پیدا کردن راس نزدیک‌تر و به روز رسانی $O(n)$ عملیات انجام می‌دهیم و چون $n$ بار این کار انجام می‌دهیم، پیچیدگی کل الگوریتم $O(n^2)$ می‌شود. اگر فاصله‌هر راس تا نزدیک‌‌ترین راس از بین راس‌هایی که در مجموعه قرار گرفته‌اند را در داه‌ساختاری مناسب ذخیره کنیم می‌توانیم پیچیدگی الگوریتم را بهتر کنیم. اگر این داده‌ساختار هرم کمینه باشد، چون حذف و اضافه از $O(logn)$ است و به ازای یال حداکثر یک بار عملیات اضافه کردن رخ می‌دهد و چون قطعا تعداد عملیات حذف کم‌تر از تعداد عملیات اضافه کردن است پیچیدگی الگوریتم به $O(mlogn+n)$ تغییر می‌کند که برای حالاتی که تعداد یال‌ها از $\mathrm{\theta <!--\; \theta \; -->}(\frac{n^2}{logn})$ کم‌تر باشد پیچیدگی کل کاهش پیدا می‌کند. حال اگر از هرم فیبوناچی استفاده کنیم پیچیدگی به $O(m+n)$ کاهش پیدا می‌کند.

پیاده‌سازی اولیه

#include <iostream>
          #include <vector>
          #include <algorithm>
          using namespace std;
          const int INF=2*1000*1000*1000+5; // ثابتی بسیار بزرگ که از هر ورودی بزرگ‌تر باشد
          const int N=1000; // حداکثر تعداد راس‌ها
          int n,m; //به ترتیب تعداد راسها، تعداد یال‌ها
          int min_e[N]; // کم‌ترین فاصله‌ی هر راس تا راس‌های انتخاب شده
          int sel_e[N]; // نزدیک‌ترین راس از بین راس‌های انتخاب شده
          bool used[N]; // جزء مجموعه شده یا نه
          vector <pair<int,int> > ans; // پشته‌ای که جواب را نگه می‌دارد
          vector <pair<int,int> > V[N]; // وزن و شماره راس‌هایی که به آن یال دارد
          bool find_mst(){
          	fill_n(min_e,n,INF); // مقدار دهی اولیه
          	fill_n(sel_e,n,-1);  // مقدار دهی اولیه
          	fill_n(used,n,false);  // مقدار دهی اولیه
          	min_e[0]=0;	 // صفر قرار می‌دهیم تا ابتدا راس صفر(یک) انتخاب شود
          	for (int i=0; i<n; i++) {
          		int v = -1;
          		for (int j=0; j<n; j++)
          			if (!used[j] && (v == -1 || min_e[j] < min_e[v]))
          				v = j;
           
          		if (min_e[v] == INF) 
          			return false; // هیچ یالی از راس‌هایی انتخابی به بیرون وجود ندارد
           
          		used[v] = true;
          		if (sel_e[v] != -1)
          			ans.push_back(make_pair(sel_e[v],v)); // به مجموعه v اضافه کردن راس
           
          		for (int j=0; j<(int)V[v].size(); j++) // به روز کردن مقادیر آرایه‌ها
          			if (V[v][j].second < min_e[V[v][j].first]) {
          				min_e[V[v][j].first] =V[v][j].second;
          				sel_e[V[v][j].first] = v;
          			}
          	}
          	return true;
          }
           
          int main() {	
          	cin >> n>>m;
          	for(int i=0; i<m; i++){ // حلقه گرفتن یال‌ها
          		int a,b,w;
          		cin >>a>>b>>w; // به ترتیب ۲ راس و سپس وزن یال
          		V[a-1].push_back(make_pair(b-1,w)); // است n-1 یکی کم می‌کنیم چون بازه‌ی معتبر ما صفر تا
          		V[b-1].push_back(make_pair(a-1,w)); // است n-1 یکی کم می‌کنیم چون بازه‌ی معتبر ما صفر تا
          	}
          	if(find_mst()==false)
          		cout << "No MST!\n";
          }
      

در انتها پشته‌ی ans شامل یال‌های درخت پوشای کمینه است.

پیاده‌سازی دیگر

این‌بار نزدیک‌ترین راس‌از بین راس‌های انتخاب شده را در یک داده‌ساختار آماده ++C به اسم set می‌ریزیم که عملیات حذف و اضافه را در $O(logn)$ انجام می‌دهد و پیچیدگی کل را به $O(mlogn+n)$ تغییر می‌دهد. این پیاده‌سازی برای زمانی که تعداد یال‌ها خیلی زیاد نباشد سریع‌تر از پیاده‌سازی اولیه عمل می‌کند.

#include <iostream>
          #include <vector>
          #include <algorithm>
          using namespace std;
          const int INF=2*1000*1000*1000+5; // ثابتی بسیار بزرگ که از هر ورودی بزرگ‌تر باشد
          const int N=1000; // حداکثر تعداد راس‌ها
          int n,m; //به ترتیب تعداد راس‌ها، تعداد یال‌ها
          int min_e[N]; // کم‌ترین فاصله‌ی هر راس تا راس‌های انتخاب شده
          int sel_e[N]; // نزدیک‌ترین راس از بین راس‌های انتخاب شده
          vector <pair<int,int> > ans; // پشته‌ای که جواب را نگه می‌دارد
          vector <pair<int,int> > V[N]; // وزن و شماره راس‌هایی که به آن یال دارد
          bool find_mst(){
          	fill_n(min_e,n,INF); // مقدار دهی اولیه
          	fill_n(sel_e,n,-1);  // مقدار دهی اولیه
          	fill_n(used,n,false);  // مقدار دهی اولیه
          	min_e[0]=0;	 // صفر قرار می‌دهیم تا ابتدا راس صفر(یک) انتخاب شود
          	set < pair<int,int> > q; // داده‌ساختاری که فاصله هر راسی که به مجومه انتخاب شده راه دارد را نگه می‌دارد
          	q.insert (make_pair (0, 0)); 
          	for (int i=0; i<n; ++i) {
          		if (q.empty()) 
          			return false;
          		int v = q.begin()->second; // کوچک‌ترین عضو یعنی نزدیک‌ترین عضو است set عضو ابتدایی
          		q.erase (q.begin());
           
          		if (sel_e[v] != -1)
          			ans.push_back(make_pair(sel_e[v],v));
           
          		for (int j=0; j<V[v].size(); j++) {
          			int to = V[v][j].first,
          				cost = V[v][j].second;
          			if (cost < min_e[to]) {
          				q.erase (make_pair (min_e[to], to));
          				min_e[to] = cost;
          				sel_e[to] = v;
          				q.insert (make_pair (min_e[to], to));
          			}
           		}
          	}
          }
           
          int main() {	
          	cin >> n>>m;
          	for(int i=0; i<m; i++){ // حلقه گرفتن یال‌ها
          		int a,b,w;
          		cin >>a>>b>>w; // به ترتیب ۲ راس و سپس وزن یال
          		V[a-1].push_back(make_pair(b-1,w)); // است n-1 یکی کم می‌کنیم چون بازه‌ی معتبر ما صفر تا
          		V[b-1].push_back(make_pair(a-1,w)); // است n-1 یکی کم می‌کنیم چون بازه‌ی معتبر ما صفر تا
          	}
          	if(find_mst()==false)
          		cout << "No MST!\n";
          }
      

تعریف

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

شرح

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

اما چگونه متوجه شویم که یال جدید با یال‌های انتخابی قبلی دور نمی‌سازد؟ کافیست گرافی که تا کنون از یال‌های انتخابی تشکیل شده را به مؤلفه‌های همبندی تقسیم کنیم و اگر یال جدید هر دو سر آن در یک مؤلفه بود، یال جدید دور ایجاد می‌کند و در غیر اینصورت اضافه کردن یال جدید مشکلی ندارد.

هر راس متغیری همراه خود دارد که شماره مولفه‌ی همبندیش را نشان می‌دهد. در ابتدا هر راس، خود یک مؤلفه‌ی همبندیست. و وقتی یک یال بین دو مؤلفه ارتباط ایجاد می‌کند باید شماره مولفه‌ی همبندی هر دو گروه یکی شود.

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

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

شبه کد

1. تمام یال‌ها را به ترتیب صعودی وزن مرتب کن
2. برای هر راس v یک مجموعه بساز.
3. اگر مجموعه‌ی u و v یکی نیستند. کارهای زیر را انجام بده.
4. 1. مجموعه‌ی آنها را ادغام کن.
   2. یال (u,v) را به عنوان یالی از درخت پوشای کمینه بردار.
5. اگر هنوز n-1 یال انتخاب نشده به شماره ۳ برو.
6. پایان

پیچیدگی الگوریتم

مرتب کردن یال ها و بررسی یال‌ها از $O(m+mlogn)$ است که برابر $O(mlogn)$ است و هر‌بار اتصال دو مولفه از $O(n)$ است که چون اتصال $n-<!--\; -\; -->1$ بار انجام می‌شود پیچیدگی الگوریتم $O(mlogn+n^2)$ می‌شود.

پیاده‌سازسی اولیه

همانطور که گفته شده پیچیدگی این پیاده‌سازی از $O(mlogn+n^2)$ است.

#include <iostream>
          #include <vector>
          #include <algorithm>
          using namespace std;
           
          const int N=1000; // حداکثر تعداد راس ها
          int n,m;
          vector <pair <int, pair <int, int> > > g; // پشته شامل یال و وزن ‌انها
          vector <pair <int, int> > MST; // پشته‌ای که  در آن درخت پوشای کمینه را خواهیم ریخت
          int tree_ID [N]; // شماره مولفه‌همبندی هر راس
          void find_mst(){
          	sort (g.begin (), g.end ());
          	MST.clear();
          	for(int i=0; i<n; i++)
          	    tree_ID[i]=i;
          	for(int i=0; i<m; i++){
          		int f=g[i].second.first;
          		int t=g[i].second.second;
          		if(tree_ID[f]!=tree_ID[t]){ 
          		    MST.push_back(g[i].second);
          			int old_ID = tree_ID [t], new_ID = tree_ID [f];
          			for(int j=0; j<n; j++) // یکی کردن شماره‌مولفه همبندی ها برای ادغام دو مجموعه
          				if (tree_ID [j] == old_ID)
          					tree_ID [j] = new_ID;
          		}
          	}
          }
           
          int main() {
          	cin >> n>>m;
          	g.clear();
          	for(int i=0; i<m; i++){
          		int f,t,w;
          		cin >>f>>t>>w;
          		g.push_back(make_pair (w, make_pair (--f, --t)));
                          /* 
                          * است n است ولی بازه معتبر راس ها در ورودی ۱ تا n-۱ بازه معتبر راس ها برای ما صفر تا 
                          * پس ما باید قبل از ذخیره یکی از آنها کم کنیم
                          */
          	}
              find_mst();	
           
          }
      

درخت پوشای کمینه در پشته MST ریخنه می‌شود. می‌توانید بر حسب نیاز به جای اینکار مجموع وزن یال‌های درخت را نگه دارید یا همراه با یال‌ها وزنشان را هم نگه دارید.

پیاده‌سازی سریع‌تر

می‌توان از داده‌ساختار مجموعه‌های مجزا برای مولفه‌های همبندی استفده کرد، در این صورت پیچیدگی الگوریتم به $O(mlogn+n)$ که برابر $O(mlogn)$ است کاهش پیدا می‌کند.

#include <iostream>
          #include <vector>
          #include <algorithm>
          using namespace std;
           
          const int N=1000;
          int n,m;
          vector <pair <int, pair <int, int>>> g; // پشته شامل یال و وزن ‌انها
          vector <pair <int, int>> MST; // پشته‌ای که  در آن درخت پوشای کمینه را خواهیم ریخت
          int parent [N];
           
          int root (int a){ // هر مولفه‌ یک ریشه دارد که نماد آن است
              if(parent[a] ==a)
                  return a;
              parent[a]=root(parent[a]);
              return root(parent[a]);
          }
           
          void Union (int a,int b){ // تابع ادغام
              parent[root(a)]=root(b);
          }
           
          void find_mst(){
          	sort (g.begin (), g.end ());
          	MST.clear();
          	for(int i=0; i<n; i++)
          	    parent[i]=i;
          	for(int i=0; i<m; i++){
          		int f=g[i].second.first;
          		int t=g[i].second.second;
          		if(root(f)!=root(t)){
          		    MST.push_back(g[i].second);
          			Union(f,t);
          		}
          	}
          }
           
          int main() {
          	cin >> n>>m;
          	g.clear();
          	for(int i=0; i<m; i++){
          		int f,t,w;
          		cin >>f>>t>>w;
          		g.push_back(make_pair (w, make_pair (--f, --t)));
                          /* 
                          * است n است ولی بازه معتبر راس ها در ورودی ۱ تا n-۱ بازه معتبر راس ها برای ما صفر تا 
                          * پس ما باید قبل از ذخیره یکی از آنها کم کنیم
                          */
          	}
           
              find_mst();	
           
           
          }
      

1. اعضای مجموعه‌ی اول را در آرایه‌ی a دریافت کن
2. اعضای مجموعه‌ی دوم را در ارایه‌ی b دریافت کن
3. تعداد اعضای مجموعه‌ی اول را در n‌ قرار بده
4. تعداد اعضای مجموعه‌‌ی دوم را در m قرار بده
5. مقدار ماکزیمم دو مقدار m و n را در max قرار بده
6. مقدار مینیمم دو مقدر m و n را در min قرار بده
7. ارایه‌ی c را به طول max خانه ایجاد کن
8. آرایه‌ی d را به طول min خانه ایجاد کن
9. در متغیر i مقدار یک را قرار بده
10. در متغیر x مقدار یک را قرار بده
11. در متغیر y مقدار یک را قرار بده
12. اگر مقدار i از n بزرگ‌تر بود به مرحله‌ی ۲۲ برو
13. اگر مشابه مقدار a[i] در داخل آرایه‌ی c بود به مرحله‌ی ۱۹ برو
14. مقدار خانه‌ی c[x] را برابر a[i] قرار بده
15. مقدار x را یک واحد افزایش بده
16. اگر مشابه مقدار a[i] در داخل آرایه‌ی b نبود به مرحله‌ی ۱۹ برو
17. مقدار خانه‌ی d[y] را برابر a[i] قرار بده
18. مقدار y را یک واحد افزاش بده
19. مقدار i را یک واحد افزایش بده
20. به مرحله‌ی ۱۲ برو
21. در متغیر j مقدار یک را قرار بده
22. اگر مقدار j از m بزرگ‌تر بود به مرحله‌ی ۲۸ برو
23. اگر مشابه مقدار b[j] در داخل آرایه‌ی c بود به مرحله‌ی ۲۶ برو
24. مقدار خانه c[x] را برابر b[j] قرار بده
25. مقدار x را یک واحد افزایش بده
26. مقدار j را یک واحد افزایش بده
27. به مرحله‌ی ۲۲ برو
28. اعضای آرایه‌ی c به طول x خانه را به عنوان اجتماع دو مجموعه نمایش بده
29. اعضای آرایه‌ی d به طول y خانه را به عنوان اشتراک دو مجموعه نمایش بده
30. پایان

ماتریس‌ها به طور ساده، همانند آرایه‌های دوبعدی اند. یک ماتریس $n\times <!--\; \times \; -->m$ یعنی ماتریسی که n $n$ سطر و $m$ ستون دارد (تعداد سطر‌ها و ستون‌ها می‌تواند برابر باشد). برای ضرب کردن دو ماتریس، باید تعداد ستون‌های اولی با تعداد سطر‌های دومی برابر باشد. ضرب‌کردن یک ماتریس $n\times <!--\; \times \; -->m$ در یک ماتریس $m\times <!--\; \times \; -->p$ به اندازه‌ی $n\times <!--\; \times \; -->m\times <!--\; \times \; -->p$ هزینه (زمان) می‌برد و خروجی‌اش یک ماتریس $n\times <!--\; \times \; -->p$ است.

اما اگر بیش از دو ماتریس داشته باشیم، این که به چه ترتیبی این ضرب‌ها را انجام بدهیم (یا چگونه بین ماتریس‌ها پرانتزگذاری کنیم) در هزینه‌ی نهایی تاثیر دارد (دقت کنید که جواب یکسان است، فقط هزینه‌ای که ما صرف می‌کنیم فرق می‌کند.)
برای مثال، فرض کنید، سه ماتریس به ابعاد (۲،۳) و (۳،۴) و (۴،۵) داشته باشیم. اگر ابتدا اولی و دومی و سپس نتیجه را با سومی ضرب کنیم، هزینه‌ی ما ۶۴ واحد می‌شود. اما اگر ابتدا دومی و سومی را ضرب کرده و سپس اولی را با نتیجه ضرب کنید، ۹۰ واحد باید هزینه کنید.
$$2\times <!--\; \times \; -->3\times <!--\; \times \; -->4+2\times <!--\; \times \; -->4\times <!--\; \times \; -->5=64$$
$$3\times <!--\; \times \; -->4\times <!--\; \times \; -->5+2\times <!--\; \times \; -->3\times <!--\; \times \; -->5=90$$

تعریف سوال

فرض کنید ابعاد $k$ ماتریس به شما داده شده است. کمترین هزینه‌ی ضرب کردن این ماتریس‌ها در هم چقدر می‌شود؟ (دقت کنید که شما نمی‌توانید جای ماتریس‌ها را با هم عوض کنید، بلکه فقط می‌توانید ترتیب انجام شدن ضرب‌ها را انتخاب کنید.)

الگوریتم

اگر کمی سوال را بررسی کنید، می‌توانید ببینید که تعداد حالت‌های مختلف انجام این پرانتز‌گذاری بسیار زیاد است. در واقع این مقدار برابر $(k-<!--\; -\; -->1)!$ است. اما در مجموع، برای حل بسیاری از این حالت‌های مختلف، باید مقادیر تکراری زیادی حساب کنیم.
همانطور که در ابتدا گفته شد، در این مسئله فقط باید مشخص کنیم که پرانتزگذاری بین ماتریس‌ها باید چگونه باشد. و اگر دقت کنید، در صورتی که تمام ماتریس‌های $i$ ام تا $j$ ام در یک پرانتز کلی قرار داشته باشند، فرقی نمی‌کند که چگونه عملیات ضرب را در این تکه انجام دهید، چون در هر صورت، ماتریس پایانی این مجموعه یکسان است (درنتیجه ابعاد آن نیز یکسان است). پس بهتر است این تکه را هم به بهترین روش (با کمترین هزینه) حل کنیم. این مسئله خود شبیه مسئله‌ی اصلی است با این تفاوت که دنباله‌ی ماتریس‌هایمان فقط ماتریس‌های $i$ ام تا $j$ ام اند.

با داشتن این ایده در ذهن بیایید به سراغ سوال اصلی برویم. می‌خواهیم سوال اصلی را به یک سری از زیر‌سوال‌هایی که در بالا تعریف کردیم، تبدیل کنیم. با کمی بررسی بیشتر، متوجه می‌شویم که اگر آخرین ضربی که باید انجام شود را تعیین کنیم، باید چیزی به این شکل باشد:
$$(A_1,A_2,\dots <!--\; \dots \; -->,A_i)\times <!--\; \times \; -->(A_{i+1},A_{i+2},\dots <!--\; \dots \; -->,A_k)$$
که تکه‌ی اول و دوم آن را می‌توان با زیرمسئله‌هایی که در بالا تعریف کردیم حل کنیم. پس راه حل به دست آمده را می‌توان به زبان ریاضی به شکل زیر تعریف کرد: (فرض کنید اندازه‌ی بعد اول یا همان سطر‌های ماتریس اول تا $k$ ام را $a_1$ تا $a_k$ و بعد دوم یا ستون‌های ماتریس آخر را $a_{k+1}$ بنامیم. می‌دانیم که باید برای مثال اندازه‌ی بعد دوم ماتریس $i$ ام، برابر بعد اول ماتریس $i+1$ باشد، وگرنه ضرب ممکن نیست).
مقدار $d_{i,j}$ را برابر کمترین هزینه‌ی ضرب کردن ماتریس $i$ ام تا $j$ ام در نظر بگیرید. پس جواب مسأله برابر مقدار $d_{۱,k}$ است.
مقدار اولیه: $d_{i,i}$ برابر صفر است، چون هیچ نیاز به انجام هیچ ضربی نیست.
به روز رسانی: مقدار $d_{i,j}$ با شرط $j>i$ بسته به اینکه کدام ضرب در انتها انجام شود، به صورت روبرو تعریف می‌شود:
$$d_{i,j}=\underset{i\le <!--\; \le \; -->m<j}{min}(d_{i,m}+d_{m+1,j}+a_i\times <!--\; \times \; -->a_{m+1}\times <!--\; \times \; -->a_{j+1})$$

شبه کد (باید دقت کنید که ابتدا دسته‌های به طول ۱ را پر کنید، سپس طول ۲ و …) :

for i from 1 to k 
      	d[i][i] = 0 


      for len from 1 to k
      	for i from 1 to k

      		if i+len > k
      			break
      		j = i+len

      		d[i][j] = inf 
      		for m from i to j-1
      			value = d[i][m] + d[m+1][j] + a[i] * a[m+1] * a[j+1] 
      			d[i][j] = min( d[i][j] , value )
      

پیچیدگی الگوریتم

حافظه مورد نیاز از $O(n^2)$ است. و هر به روز رسانی نیز از $O(n)$ است. پس پیچیدگی زمانی از $O(n^3)$ است.

پیاده‌سازی اولیه

#include <iostream>
          using namespace std;
          typedef pair<int, int> pii;
           
          const int MAXK = 1000;
          const int INF = 1<<30; // 2 ^ 30
           
          pii inp[MAXK+10];
          int a[MAXK+10];
          int d[MAXK+10][MAXK+10];
           
          int main() {
          	ios::sync_with_stdio(false);
          	int k;
          	cin >> k;
          	for(int i=0; i<k; i++)
          		cin >> inp[i].first >> inp[i].second;
           
          	for(int i=1; i<k; i++){
          		if( inp[i].first != inp[i-1].second ){
          			cout << "matrix sizes are not valid" << endl;
          			return 0;
          		}
          		a[i] = inp[i].first;
          	}
          	a[0] = inp[0].first;
          	a[k] = inp[k-1].second;
           
          	for(int i=0; i<k; i++)
          		d[i][i] = 0;
           
          	for(int len=1; len<=k; len++)
          		for(int i=0; i<k; i++){
          			if( i+len >= k )
          				break;
          			int j = i+len;
           
          			d[i][j] = INF;
          			for(int m=i; m<j; m++)
          				d[i][j] = min( d[i][j] , d[i][m] + d[m+1][j] + a[i] * a[m+1] * a[j+1] );
          		}
           
          	cout << d[0][k-1] << endl;
           
          	return 0;
          }
      

تعریف

والکر استراسن الگوریتم استراسن را در سال ۱۹۶۹ منتشر کرد. اگرچه الگوریتم او فقط کمی سریع تر از الگوریتم‌های استاندارد برای ضرب ماتریس است، اما او اولین کسی بود که اشاره کرد رویکرد استاندارد مطلوب نمی‌باشد. مقالهٔ او به جستجوی الگوریتم‌های سریعتر مانند الگوریتم پیچیده تر Coppersmith–Winograd منتشر شده در سال ۱۹۸۷ پرداخت.

الگوریتم

ستون سمت چپ، ضرب ماتریسی ۲x۲ را نشان می‌دهد. ضرب ماتریسی Naïve به یک ضرب برای هر “۱” از ستون سمت چپ نیاز دارد. هر یک از ستون‌های دیگر نشان دهندهٔ یک واحد از ۷ ضرب در الگوریتم می‌باشند و از مجموع ستون‌ها، ضرب ماتریس کامل در سمت چپ حاصل می‌شود.

بگذارید A،B دو ماتریس مربعی در یک حلقه R باشند. ما می‌خواهیم حاصل ماتریس C را به صورت زیر محاسبه کنیم:

اگر ماتریس‌های A،B از نوع ۲n x ۲n نباشند، ما ردیف‌ها و ستون‌های خالی را با صفر پر می‌کنیم.
ما A،B و C را به ماتریس‌های بلوکی هم سایز تجزیه می‌کنیم.

ما با این ساختار، تعداد ضرب‌ها را کاهش ندادیم. هنوز هم به ۸ ضرب نیاز داریم تا ماتریس‌های Ci،j را محاسبه کنیم، زمانی که از ضرب ماتریسی استاندارد استفاده می‌کنیم نیز به همان تعداد ضرب نیاز داریم.
حالا بخش مهم در اینجا آمده‌است. ما ماتریس‌های جدید را به شرح زیر تعریف می‌کنیم:

که سپس برای بیان Ci،j به صورت Mk مورد استفاده قرار می‌گیرند. با تعریف مان از Mk می‌توانیم یک ضرب ماتریس را حذف کنیم و تعداد ضرب‌ها را به ۷ کاهش دهیم (یک ضرب برای هر Mk) و Ci،j را به صورت زیر بیان کنیم:

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

پیچیدگی مجانبی

ضرب ماتریسی استاندارد تقریباً عملیات محاسباتی ۲n^۳ (که n=۲^n) (جمعها و ضرب‌ها) را می‌پذیرد؛ پیچیدگی مجانبی (O(N۳می‌باشد. تعداد جمع‌ها و ضرب‌های مورد نیاز در الگوریتم استراسن را می‌توان به صورت زیر محاسبه کرد:
اجازه دهید (f(n تعداد عملیات برای یک ماتریس ۲n × ۲n باشد. آنگاه با عملیات بازگشتی الگوریتم استراسن می‌بینیم که برای برخی l ثابت که به تعداد جمع‌های انجام شده در هر عملیات الگوریتم وابسته‌است. یعنی پیچیدگی مجانبی برای ضرب ماتریسها با استفاده از الگوریتم استراسن به شرح زیر است:

هرچند کاهش در تعداد عملیات محاسباتی تا حدودی به بهای کاهش ثبات عددی می‌باشد.
برای اطلاعات بیش‌تر:
نمایش ماتریس Z-order

تعریف

الگوریتم مؤلفه قوی مبتنی بر مسیر (به انگلیسی: Path-based strong component algorithm) در نظریه گراف برای پیدا کردن مولفه‌های قویا همبند یک گراف جهت‌دار استفاده می‌شود. قبل از این الگوریتم، الگوریتم کساراجو و الگوریتم تارژان نیز به همین منظور ارایه شده است.

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

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

الگوریتم

فرض کنید گراف G داده شده است. در این الگوریتم رأس‌های گراف را از ۱ تا n و مولفه‌های قویا همبند را با شروع از n+۱ شماره‌گذاری می‌کنیم. همچنین در این الگوریتم گراف H را که در ابتدا همان گراف G می‌باشد در نظر می‌گیریم و در این گراف مسیر P را به صورت زیر می‌سازیم: ابتدا یک رأس دلخواه از گراف را در نظر می‌گیریم و از این رأس در جهت کاملاً دلخواه حرکت می‌کنیم تا یکی از دو حالت زیر رخ دهد:

1. اگر به رأسی رسیدیم که قبلاً در مسیر P وجود داشت، تمام گره‌های بین این رأس که تا کنون پیموده شده است را هم در گراف H و هم در مسیر p منقبض می‌کنیم. یعنی همه آن‌ها را به عنوان یک رأس در نظر می‌گیریم.
2. اگر به رأسی رسیدیم که دیگر نتوانستیم مسیر P را ادامه دهیم، گره آخر مسیر P را هم در گراف H وهم در مسیر P حذف کرده و آن را به عنوان یک مولفه قویا همبند معرفی می‌کنیم.

این الگوریتم از الگوریتم جستجوی عمق اول و همچنین دو پشته برای نمایش مسیر P استفاده می‌کند. پشته S که شامل دنباله رأس‌های مسیر P است و پشته B که شامل کران‌های رأس‌های منقبض شده است. در این الگوریتم آرایه I نیز وجود دارد که هم اندیس پشته S را و هم شماره مولفه قویا همبند را ذخیره می‌کند. به عبارت دقیق تر این ارایه به صورت زیر تعریف می‌شود:

1. I[v]=۰ هرگاه گره v در مسیر P نباشد.
2. I[v]=j هرگاه گره v اکنون در مسیر P باشد و S[j]=v.
3. I[v]=c هرگاه مولفه قویا همبند شامل v حذف شده و با عدد c شماره گذاری شده باشد.

این الگوریتم شامل قسمت اصلی STRONG و قسمت بازگشتی DFS است:

AlgorithmSTRONG(G)
      	empty stacks S and B
      	for v ∈ V do I[v]=۰
      	c=n
      	for v ∈ V do if I[v]=۰ then DFS(v)
      	

AlgorithmDFS(G)
      	PUSH(v,S);I[v]=TOP(S);PUSH(I[v],B);/*add v to the end of P*/
      	for edges (v,w) ∈ E do
      	  if I[w]=۰ then DFS(w)
      	  else /*contract if necessary*/
      	     while I[w]<B[TOP(B)] do POP(B)
      	if  I[v]=B[TOP(B) then{/*number vertices of the next strong component*/
      	   POP(B);increase c by 1
      	   while I[v]≤TOP(S) do I[POP(S)]=c}
      	

در قضیه زیر برهان درستی و همچنین پیچیدگی این الگوریتم آمده است:
هنگامی که (STRONG(G متوقف شود هر رأس v ∈ V به مولفه قویا همبندی که توسط [I[v شماره گذاری شده است تعلق دارد. همچنین زمان و حافظه مصرفی (O(m+n می‌باشند.

برای دیدن الگوریتم‌های مرتبط با این الگوریتم می‌توانید به الگوریتم کساراجو و الگوریتم مؤلفه‌های همبند قوی تارجان مراجعه کنید.

تعریف

الگوریتم چریَن- ملورن/ گابو در نظریه گراف، یک روش با پیچیدگی زمانی خطی برای یافتن مولفه‌های همبندی قوی در یک گراف جهتدار است. این الگوریتم در سال ۱۹۹۶ توسط جوزف چِریَن و کورت ملورن ارائه شد و در سال ۱۹۹۹ توسط هارولد گابو بهبود یافت.

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

الگوریتم گابو با پشتیبانی دو پشتهٔ S و P یک جستجوی عمق اول بر روی گراف داده شدهٔ G انجام می‌دهد. پشتهٔ S تمامی گره‌هایی را تاکنون به یک مولفهٔ همبندی قوی اختصاص داده نشده‌اند، شامل می‌شود. گره‌ها در این پشته به ترتیبی که جستجوی عمق اول به آن می‌رسد قرار دارند. پشتهٔ P شامل گره‌هایی است که هنوز اختصاص آن‌ها به مولفه‌های همبندی قوی متفاوت از هم، تعیین نشده است. همچنین در الگوریتم از یک شمارندهٔ C که تعداد گره‌های مشاهده شده تاکنون است، برای محاسبهٔ اعداد پیش‌ترتیب گره‌ها استفاده می‌شود.

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

1. عدد پیش‌ترتیب v را برابر C قرار می‌دهد، و مقدار C را یکی افزایش می‌دهد.
2. گره v را در پشتهٔ S و همینطور P قرار می‌دهد.
3. برای هر یال از گره v به گره مجاور w:
   1. اگر عدد پیش‌ترتیب w هنوز مقدار‌دهی نشده، به طور بازگشتی جستجو را روی w انجام می‌دهد؛
   2. در غیر اینصورت، اگر w هنوز به یک مولفهٔ همبندی قوی اختصاص داده نشده:
      1. تا زمانی که عدد پیش‌ترتیب عنصر بالای پشته P، بزرگتر اکید عدد پیش‌ترتیب w است، عنصر بالای P را خارج می‌کند.
4. اگر v عنصر بالای P بود:
   1. عناصر بالای S را تا زمانی که v خارج شود، خارج کرده و این عناصر را به یک مولفهٔ همبندی اختصاص می‌دهد.
   2. گره v را از P خارج می‌کند.

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

تعاریف

الگوریتم دایکسترا راه‌کاری برای پیدا کردن کم‌وزن مسیر از رأس مشخص آغاز به بقیه رئوس در گراف جهت‌دار و وزن‌دار (با وزن‌های مثبت) می‌دهد. وزن یک مسیر در گراف وزن‌دار برابر مجموع وزن یال‌های آن است. جهت‌دار نبودن یال‌ها هم مشکلی ایجاد نمی‌کند و می‌توان برای یال‌های غیر جهت‌دار دو یال فرض کرد.

الگوریتم

فرض کنید $1\le <!--\; \le \; -->‌s\le <!--\; \le \; -->n$ که در آن رأس ‌ $s$ رأس آغاز است و فرض کنید:
$$dist(s)=0$$
و به ازای هر $v\ne <!--\; \ne \; -->s$ $$dist(v)=\mathrm{\infty <!--\; \infty \; -->}$$

فرض کنید مجموعه‌ی $T$ برابر رئوسی باشد که تا کنون کم وزن‌ترین مسیر آن‌ها را پیدا کرده‌ایم. این الگوریتم در هر مرحله نزدیک‌ترین رأس به $s$ را که تا کنون به مجموعه‌ی ‌ $T$ اضافه نشده را انتخاب می‌کند (مثلا ‌ $x$ ) و آن را به مجموعه‌ی $T$ اضافه می‌کند و فاصله‌ی دیگر رأس‌ها را با توجه به فاصله‌‌ی $x$ بروز می‌کند. به ازای هر رأس $v$ خارج $T$ :
$$dist(v)=min(dist(v),dist(x)+w(x,v))$$
که در آن $w(x,v)$ برابر وزن یال بین $x$ و $v$ است. این الگوریتم در هر مرحله رأسی را که کوتاه‌ترین فاصله‌ی آن تا $s$ پیدا شده‌ است را به $T$ اضافه می‌کند. زیرا کوتاه ترین مسیر این رأس از یکی از رأس‌های $T$ می‌گذرد که در مراحل قبلی فاصله آن‌ها بدست آمده و دیگر رئوس را بروز کرده‌اند.

یک مثال

در گراف زیر، روند اجرای این الگوریتم را می‌توانید مشاهده کنید:

در صورت منفی بودن یال‌ها فرض اینکه در هر مرحله رأسی که کوتاه‌ترین مسیر آن پیدا شده اضافه می‌شود زیر سوال می‌رود. زیرا این رأس می‌تواند بدون استفاده از رأس‌های $T$ و یال‌های منفی مسیری کوتاه‌تر به ‌ $s$ پیدا کند.

پیچیدگی الگوریتم

به ازای هر رأس باید روند بالا را طی کنیم. یعنی دنبال آن بگردیم و همه‌ی همسایه‌های آن را پیمایش کنیم. پس پیچیدگی زمانی برنامه از $O(n\times <!--\; \times \; -->n)=O(n^2)$ است. هر چند می‌توان با استفاده از داده ساختار هرم پیاده‌سازی از $O(e\times <!--\; \times \; -->lg(n))$ ارائه داد.

پیاده‌سازی اولیه

function Dijkstra(s):

            dist[s]  = 0                         

            for each vertex v in Graph:            // Initializations
                if v ≠ s                      
                    dist[v]  = infinity
                end if 
            end for
            
            while Size(T) ≠ n :                  // The main loop
                u := vertex not in T with min dist[u] 
                add u to T 
                
                for each neighbor v of u:           
                    dist[v] = min(dist[v], dist[u]+w[u][v])
                end for
            end while

        end function
      

پیاده‌سازی

#include <iostream>
           
          using namespace std;
           
          const int MAXN = 1000 + 10;
          const int INF = 1000*1000*1000;
           
          int n, m;
          int adj[MAXN][MAXN];
          int w[MAXN][MAXN];
          int dist[MAXN];
          int mark[MAXN];
           
          void readInput(){
          	cin >> n >> m;
          	for(int i=0; i<m; ++i){
          		int v, u, z;
          		cin >> u >> v >> z;
          		adj[u][v] = 1;
          		w[u][v] = z;
          	}
          }
           
          void dijkstra(int s){
          	dist[s] = 0;
          	for(int i=0; i<n; ++i) 
          		if(i!=s)
          			dist[i] = INF;
          	for(int rep=0; rep<n; ++rep)
          	{
          		int u = -1;
          		int du = INF;
          		for(int i=0; i<n; ++i)
          			if(!mark[i] && dist[i] <= du){
          				u = i;
          				du = dist[i];
          			}
          		mark[u] = 1;
          		for(int v=0; v<n; ++v)
          			if(adj[u][v])
          				dist[v] = min(dist[v], dist[u]+w[u][v]);
          	}
          }
           
          void writeOutput(){
          	for(int i=0; i<n; ++i)
          		cout << dist[i] << " ";
          	cout << endl;
          }
           
          int main(){
          	readInput();
          	dijkstra(0);
          	writeOutput();
          	return 0;
          }
      

پیاده‌سازی با استفاده از داده ساختار هرم

می‌توان یافتن نزدیک‌ترین رأس در هر مرحله را به کمک این داده ساختار انجام داد. در این صورت باید گراف را به صورت لیست مجاورت نگه داریم. که در $C++$ برای راحتی کار از $Set$ استفاده می کنیم.

#include <iostream>
          #include <vector>
          #include <set>
           
          using namespace std;
           
          const int MAXN = 1000*100 + 10;
          const int INF = 1000*1000*1000;
          typedef pair<int, int> pii;
          int n, m;
          vector<int> adj[MAXN];
          vector<int> w[MAXN];
          set<pii> q;
          int dist[MAXN];
           
           
          void readInput(){
          	cin >> n >> m;
          	for(int i=0; i<m; ++i){
          		int v, u, z;
          		cin >> u >> v >> z;
          		adj[u].push_back(v);
          		w[u].push_back(z);
          	}
          }
           
          void dijkstra(int s){
          	dist[s] = 0;
          	for(int i=0; i<n; ++i) 
          		if(i!=s)
          			dist[i] = INF;
          	for(int i=0; i<n; ++i)
          		q.insert(pii(dist[i], i));
          	while(!q.empty())
          	{
          		set<pii> :: iterator it = q.begin();
          		int u = it->second;
          		q.erase(it);
          		for(int i=0; i<adj[u].size(); ++i){
          			int v = adj[u][i];
          			q.erase(pii(dist[v], v));
          			dist[v] = min(dist[v], dist[u]+w[u][i]);
          			q.insert(pii(dist[v], v));
          		}
          	}
          }
           
          void writeOutput(){
          	for(int i=0; i<n; ++i)
          		cout << dist[i] << " ";
          	cout << endl;
          }
           
          int main(){
          	readInput();
          	dijkstra(0);
          	writeOutput();
          	return 0;
          }
      

تعریف

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

الگوریتم

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

الگوریتم میانگین–خطی درخت پوشای کمینه یک الگوریتم تصادفی برای یافت درخت پوشای کمینه در یک گراف وزن دار بدون راس تنها است. این الگوریتم توسط David Karger، فیلیپ کلین و Robert Tarjan ابداع شده است. این الگوریتم متکی بر شیوه الگوریتم بروکا است که برای یافت درخت پوشای کمینه در زمانی خطی است. این الگوریتم تشکیل شده از الگوریتم تقسیم و حل، الگوریتم حریصانه و الگوریتم‌های تصادفی برای رسیدن به زمان خطی مورد نظر. الگوریتم‌های قطعی برای یافت درخت پوشای کمینه عبارتند از: الگوریتم‌های پریم، کروسکال، بروکا.

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

حرکت بروفکا

هر تکرار الگوریتم مبتنی بر الگوریتم بروفکا را یک گام در نظر می‌گیریم.

1. یک گراف که راس تنها ندارد
2. یک گراف منقبض به وسیله ی جایگزینی مولفه های ساخته شده با یال های مرحله یک با یک راس بساز
3. تمام راس های تنها، طوقه ها، یال های تکراری غیر کمینه را حذف کن
4. خروجی: یال های انتخاب شده در مرحله یک و گراف منقبض شده ی باقی‌مانده.

یک گام بروفکا از اردر m است (تعداد یال ها) زیرا هر یال حداکثر از دو طرفش دیده می شود. بعد از این مرحله تعداد مولفه ها حداکثر n/2 است.

یال‌های F-heavy و F-light

در هر تقسیم یال هایی با خواصی که آن ها را از بودن در درخت پوشای کمینه محروم می کند حذف می شوند. این یال ها را F-heavy می نامیم که این گونه اند: فرض کنید F یک جنگل پوشای کمینه از گراف H است، یک F-heavy یالی است که راس های u و v را به هم دیگر متصل می کند که وزنش از وزن بیشترین یال مسیر u و v در F بیشتر است. هر یالی که F-heavy نیست F-light نام دارد. اگر H یک زیرگراف از G باشد، هیچ F-heavy نمی‌تواند در درخت کمینه باشد. برای گراف G می توان F-heavy ها را در زمان مورد نظر خطی محاسبه کرد.

1. یک گراف که راس تنها ندارد بگیر
2. اگر گراف تهی بود یک جنگل تهی بده
3. یک گراف منقبض با اجرای 2 مرحله پی در پی بروفکا بساز
4. یک زیر گراف با انتخاب یال ها به احتمال (2/1) بساز و درخت پوشای کمینه ی آن را بیاب
5. با استفاده از linear time minimum spanning tree verification algorithm تمام F-heavy ها را حذف کن
6. به صورت بازگشتی درخت پوشای کمینه را برای 'G بدست بیاور
7. درخت پوشای کمینه ی 'G و یال های منتخب بروفکا را چاپ کن

درستی الگوریتم

درستی الگوریتم را با استقرا روی تعداد رئوس گراف ثابت می کنیم. پایه به وضوح درست است. T را د.پ.ک (درخت پوشای کمینه) ی G در نظر می گیریم. هر یال انتخاب شده در گام بروکا از همه ی یالهال کات آن سوپرراس ها و همچنین دورهای شامل آن کوچکتر است. هر یال F-heavy حذف شده نیز در د.پ.ک نیست زیرا در دوری است که یال کوچکتر از آن وجود دارد یا در هیچ کاتی نیست که کوچکترین یال باشد. همچنین حداکثر تعداد یالهای F-light که به گراف اضافه می شود برابر n-1 است و هر د.پ.ک ای نیز n-1 یال دارد. پس تعداد یالهای درخت محدود به یالهای F-heavy است و یالهای F-heavy نیز n-1 تاست. پس د.پ.ک ساخته می شود.

کارایی

کارایی در صورتی تضمین می شود که نمونه گیری تصادفی باشد. اثر مرحله نمونه گیری تصادفی، توسط لم زیر که یک حد بر روی تعداد یال های F-light در G در نتیجه محدود کردن اندازه زیر مسئله دوم است توصیف شده.

لم تصادفی

لم، نشان می دهد اگر H زیرگرافی از G باشد به گونه ای که هر یال G به احتمال p در آن باشد، و F د.پ.ک H باشد، تعداد یالهای F-light در G حداکثر n/p است (n تعداد رئوس G است). برای اثبات لم تعداد یالهای G که به H اضافه شده اند را حساب می کنیم. تعداد یالهای F-light در G بستگی به روش انتخاب H دارد در حالیکه د.پ.ک H برای همه ی انتخاب ها یکی است. برای اثبات انتخاب یالها را از سبک به سنگین در نظر می گیریم.

تحلیل میانگین

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

جهت مطالعه‌ی بیش‌تر

https://en.wikipedia.org/wiki/Minimum_spanning_tree#Possible_multiplicity
http://en.wikipedia.org/wiki/Expected_linear_time_MST_algorithm

تعریف

مسئله انتخاب فعالیت‌ها از مسائل بهینه‌سازی ریاضی است که می‌توان برای آن الگوریتمی به روش حریصانه تولید کرد. برای نمونه فرض کنید n سخنران خود را به عنوان ورودی مسئله اعلام کرده‌اند. هدف انتخاب بیشترین تعداد سخنران به گونه‌ای است که هیچ دو سخنرانی با هم اشتراک بازهٔ زمانی نداشته باشند.
جهت عدم تداخل در زمان شروع یا پایان می‌توان بدون کم‌شدن از کلیت مسئله فرض کرد که پایان بازه سخنرانی‌ها باز است یعنی به صورت (...} است.

ورودی‌ها:

• si :شروع فعالیت iام
• Fi :پاین فعالیت iام
• n :تعداد فعالیت‌ها
• هدف : انتخاب بیشترین تعداد فعالیت به قسمی که اشتراک بازه زمانی نداشته باشند.

1. در ابتدا فعالیت‌ها را بر اساس زمان پایان آنها مرتب کرده و سپس اولین فعالیت (زودترین زمان پایان) را انتخاب می‌کنیم. به ازای i از 2تا n مرحله 3 را تکرار می‌کنیم اگر فعالیت iام با آخرین فعالیت انتخاب شده تداخل بازه زمانی نداشت آن را انتخاب می‌کنیم.
2. در ابتدا فعالیت‌ها را بر اساس زمان پایان آنها مرتب کرده و سپس اولین فعالیت (زودترین زمان پایان) را انتخاب می‌کنیم. به ازای i از 2تا n مرحله 3 را تکرار می‌کنیم اگر فعالیت iام با آخرین فعالیت انتخاب شده تداخل بازه زمانی نداشت آن را انتخاب می‌کنیم.
3. در ابتدا فعالیت‌ها را بر اساس زمان پایان آنها مرتب کرده و سپس اولین فعالیت (زودترین زمان پایان) را انتخاب می‌کنیم. به ازای i از 2تا n مرحله 3 را تکرار می‌کنیم اگر فعالیت iام با آخرین فعالیت انتخاب شده تداخل بازه زمانی نداشت آن را انتخاب می‌کنیم.

شبه‌ کد

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

Procedure Activity_selector (A, S, F, n) 
      A {1} 
      j 1 
      for i 2 to n do 
      if Si ≥Fj
      then 
      A   A ∪{i} 
      j i 
      endif 
      repeat 
      end.
      

تطابق با روش حریصانه: فعالیتی که زودترین زمان پایان را داشته باشد

Select :

با آخرین فعالیت انتخاب شده تداخل زمانی نداشته باشد

Feasibility :

اضافه کردن آن به مجموعه انتخاب شده‌ها

Union :

تحلیل زمانی :بیشترین زمان در الگوریتم مربوط به مرتب سازی ابتدای کار است و لذا الگوریتم دارای مرتبه زمانی (o(n log n می‌باشد.

تعریف

الگوریتم امید ریاضی-بیشینه‌سازی (EM) یک روش تکرارشونده (iterative) است که به دنبال یافتن برآوردی با بیشترین درست نمایی برای پارامترهای یک توزیع پارامتری است. این الگوریتم روش متداول برای زمانهایی است که برخی از متغیرهای تصادفی پنهان هستند.

فرض کنید که مشاهدات $x_{\mathrm{۱}},x_{\mathrm{۲}},...x_n$ را با $d$ نمایش دهیم، متغیرهای پنهان $h_{\mathrm{۱}},h_{\mathrm{۲}},...h_n$ را با $h$ و همه ی پارامترهای توزیع را نیز با $\theta$ در این صورت لگاریتم درست نمایی کل داده ها (پنهان و نمایان=مشاهدات) برابر خواهد بود با:

از آنجا که لگاریتم تابع اکیداً صعودی است، می توان لگاریتم درست نمایی کل داده ها را نسبت به $\theta$ بیشینه کرد. هرچند، آرگومان لگاریتم یک مجموع است و نمی توان به سادگی پاسخ تحلیلی برای $\theta$ یافت. از این رو، الگوریتم ب-ا ترفندی را برای بیشینه کردن حد پایین لگاریتم درست نمایی بکار می برد.
این حد پایین از نابرابری جنسن بدست می آید. بر اساس نابرابری جنسن که از مجموعه مقعر بودن تابع لگاریتم استفاده می کند برای هر دسته $k$ تایی از $t_{\mathrm{i}}$ ها و $w_{\mathrm{i}}$ ها اگر $t_{\mathrm{i}}>\mathrm{۰}$ و $\mathrm{\Sigma <!--\; \Sigma \; -->}{w}_{\mathrm{i}}=\mathrm{۱}$ خواهیم داشت:

اکنون $L$ را به صورت زیر باز می نویسیم:

با گزینش $k(\mathrm{h})=p(\mathrm{h};d,\theta )$ نابرابری بالا تنگ می شود. این به معنای آن است که نابرابری به برابری تبدیل می شود. این گام الگوریتم همانند بیشینه کردن حدپایین درست نمایی نسبت به $q$ است. در نتیجه روش کار الگوریتم امید ریاضی-بیشینه کردن به صورت زیر است:

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

فرض کنید عبارت زیر را دارید :

((a+b)*(c-d))/(e-f)

عبارت بالا یک عبارت infix (میان ترتیب) است زیرا عملگر بین عملوند هایش آمده است ، به طور مثال در عبارت بالا ” – ” بین c و d آمده است.
در این‌جا عباراتی را که بررسی می کنیم شامل عملگرهای + , – , / , * و پرانتز است. اولویت این عملگرها به ترتیب زیر است:

• * ، /
• – ، +

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

اگر عبارت بالا را به صورت inorder پیمایش کنیم یعنی ابتدا ریشه را ببینیم بعد فرزند چپ و بعد فرزند راست، دقیقا عبارت بالا بدون پرانتز به دست می آید که همان شکل infix است:

In-order:
      1-Traverse the left subtree by recursively calling the in-order function
      2-Display the data part of root element (or current element)
      3-Traverse the right subtree by recursively calling the in-order function
       
      inorder(node)
        if node == null then return
        inorder(node.left)
        visit(node)
        inorder(node.right)