payamvha/North_RAG huggingface dataset:
حل از بابت دوباره‌کاری هزینه‌ای را متحمل نشود. برای مثال در دنباله فیبوناچی برای محاسبهٔ عدد چهارم دنباله به دانستن عدد سوم نیاز داریم. برای محاسبهٔ عدد پنجم هم باز به عدد سوم نیاز داریم. حال اگر مثلاً در شرایطی بخواهیم عدد ششم دنبالهٔ فیبوناچی را حساب کنیم، در این محاسبه هم مقدار عدد پنجم را می‌خواهیم و هم مقدار عدد چهارم را. اگر تصمیم بگیریم اعداد چهارم و پنجم را به نوبت حساب کنیم در هنگام محاسبهٔ هرکدام به مقدار عدد سوم نیاز پیدا می‌کنیم و باید دوباره آن را محاسبه کنیم. برای جلوگیری از این محاسبات
آن را محاسبه کنیم. برای جلوگیری از این محاسبات چندباره، الگوریتمهایی که مبتنی بر برنامه‌ریزی پویا هستند، معمولاً یکی از دو راه زیر را استفاده می‌کنند. گراف زیرمسئله‌ها. زمانی که به یک مسئلهٔ برنامه‌نویسی پویا می‌اندیشیم، باید مجموعهٔ زیرمسئله‌های موجود و چگونگی وابستگی آن‌ها را درک کنیم. گراف زیرمسئله‌ها دقیقاً همین اطلاعات را برای یک مسئله در بر می‌گیرد. تصویر ۱ گراف زیرمسئله‌های دنباله‌های فیبوناچی را نشان می‌دهد. گراف زیرمسئله‌ها یک گراف جهت‌دار، شامل یک رأس به ازای هر زیرمسئلهٔ متمایز است و در صورتی یک
رأس به ازای هر زیرمسئلهٔ متمایز است و در صورتی یک یال جهت‌دار از رأس زیرمسئلهٔ x به رأس زیرمسئلهٔ y دارد که برای تعیین یک جواب بهینه برای زیرمسئلهٔ x مستقیماً نیاز به در نظر گرفتن یک جواب بهینه برای زیرمسئلهٔ y داشته‌باشیم. برای نمونه، گراف زیرمسئله دارای یک یال از x به y است، در صورتی که یک رویهٔ (procedure) بازگشتی بالا به پایین برای حل x، مستقیماً خود را برای حل y صدا بزند. می‌توان گراف زیرمسئله‌ها را یک نسخهٔ کاهش‌یافتهٔ درخت بازگشتی برای روش بازگشتی بالا به پایین در نظر گرفت، به گونه‌ای که همهٔ رئوس
به پایین در نظر گرفت، به گونه‌ای که همهٔ رئوس مربوط به یک زیرمسئله را یکی کنیم و یال‌ها را از والد به فرزند جهت‌دار کنیم. روش پایین به بالا برای برنامه‌نویسی پویا رئوس گراف زیرمسئله‌ها را به ترتیبی در نظر می‌گیرد که همهٔ زیرمسئله‌های مجاور یک زیرمسئله، پیش از آن حل شوند. در یک الگوریتم برنامه‌نویسی پویای پایین به بالا، رئوس گراف زیرمسئله‌ها را به صورتی در نظر می‌گیریم که «معکوس مرتب توپولوژیکی» یا «مرتب توپولوژیک وارون» زیرگراف مسئه‌ها است. به زبان دیگر، هیچ زیرمسئله‌ای تا زمانی که همهٔ زیرمسئله‌هایی که به
زیرمسئله‌ای تا زمانی که همهٔ زیرمسئله‌هایی که به آن‌ها وابسته است حل نشده‌اند، در نظر گرفته‌نمی‌شود. به‌طور مشابه، می‌توانیم رویکرد بالا به پایین (همراه به‌خاطرسپاری) برای برنامه‌نویسی پویا را به شکل جستجوی ژرفانخست گراف زیرمسئله‌ها ببینیم. اندازهٔ گراف زیرمسئله‌ها می‌تواند ما را در تعیین زمان اجرای الگوریتم برنامه‌نویسی پویا یاری کند. از آنجایی که هر زیرمسئله را فقط یک بار حل می‌کنیم، زمان اجرا برابر است با مجموع تعداد بارهایی که نیاز است هر زیرمسئله را حل کنیم. به‌طور معمول، زمان محاسبهٔ جواب یک
را حل کنیم. به‌طور معمول، زمان محاسبهٔ جواب یک زیرمسئله، متناسب با درجهٔ رأس متناظر در گراف، و تعداد زیرمسئله‌ها برابر با تعداد رئوس گراف است. مثال. یک پیاده‌سازی ساده از یک تابع برای یافتن عدد فیبوناچی nام می‌تواند به شکل زیر باشد. function fib(n) if n = 0 return 0 if n = 1 return 1 return fib(n − 1) + fib(n − 2) برای مثال اگر از چنین تابعی codice_1 را بخواهیم، تابع‌هایی که صدا می‌شوند به شکل زیر خواهند بود. مشخص است که چنین فرایندی پر از محاسبات تکراری است. مثلاً عدد فیبوناچی دوم به تنهایی سه بار حساب
است. مثلاً عدد فیبوناچی دوم به تنهایی سه بار حساب شده‌است. در محاسبات بزرگ‌تر چنین تکرارهایی برنامه را به شدت کند می‌کنند. این الگوریتم دارای پیچیدگی زمانی نمایی است. حال فرض کنید ما یک آرایه دوتایی map داریم که عدد n را به مقدار عدد فیبوناچی nام مربوط کرده و ذخیره می‌کند. پیچیدگی زمانی چنین الگوریتمی n خواهد بود. همچنین میزان فضای اشغال‌شده‌اش هم از مرتبه n خواهد بود. var m := map(0 → 1, 1 → 1) function fib(n) if map m does not contain key n m[n] := fib(n − 1) + fib(n − 2) return m[n] این نمونه‌ای از
− 1) + fib(n − 2) return m[n] این نمونه‌ای از فرایند بالا به پایین بود. چون ابتدا مسئله را شکستیم و بعد به محاسبه و ذخیرهٔ پاسخ زیرمسئله‌ها پرداختیم. در فرایند پایین به بالا برای حل چنین مسئله‌ای از عدد فیبوناچی یکم شروع می‌کنیم تا به عدد خواسته‌شده برسیم. با این کار باز هم پیچیدگی زمانی از مرتبه n است. function fib(n) var previousFib := 0, currentFib := 1 if n = 0 return 0 if n = 1 return 1 repeat n − 1 times var newFib := previousFib + currentFib previousFib := currentFib currentFib := newFib return
:= currentFib currentFib := newFib return currentFib برتری این روش به روش قبلی در این است که در این روش حتی به فضای ذخیره از مرتبه n هم نیازی نیست. فضای ذخیره از مرتبه ۱ کفایت می‌کند. علت این که همیشه از رویکرد پایین به بالا استفاده نمی‌کنیم این است که گاهی از قبل نمی‌دانیم باید کدام زیرمسئله‌ها را حل کنیم تا به مرحله اصلی برسیم، یا این که مجبوریم زیرمسئله‌هایی که استفاده نمی‌شوند را هم حل کنیم. تفاوت این روش و روش تقسیم و غلبه (تقسیم و حل). یکی از روش‌های پرکاربرد و مشهور طراحی الگوریتم روش برنامه‌نویسی
پرکاربرد و مشهور طراحی الگوریتم روش برنامه‌نویسی پویا (یا برنامه‌ریزی پویا - Dynamic Programming) است. این روش همچون روش تقسیم و حل (Divide and Conquer) بر پایه تقسیم مسئله بر زیرمسئله‌ها کار می‌کند. اما تفاوت‌های چشم‌گیری با آن دارد. زمانی که یک مسئله به دو یا چند زیرمسئله تقسیم می‌شود، دو حالت ممکن است پیش بیاید: روش برنامه‌نویسی پویا غالباً برای الگوریتم‌هایی به کار برده می‌شود که در پی حل مسئله‌ای به صورت بهینه می‌باشند. در روش تقسیم و غلبه ممکن است برخی از زیرمسائلِ کوچکتر، با هم برابر باشند که در این
از زیرمسائلِ کوچکتر، با هم برابر باشند که در این صورت زیرمسائلِ برابر، به‌طور تکراری چندین مرتبه حل می‌شوند که این یکی از معایب روش تقسیم و غلبه است. ایده‌ای که در فرایِ روش برنامه‌نویسی پویا نهفته‌است، جلوگیری از انجام این محاسبات تکراری است و روشی که معمولاً برای این عمل به کارگرفته می‌شود استفاده از جدولی برای نگهداری نتایج حاصل از حل زیرمسائل است. در این صورت اگر الگوریتم به زیرمسئله‌ای برخورد کرد که پیش از این حل شده است، به جای حل مجدد آن، نتیجه محاسبه قبلی را از جدول برداشته و کار را با زیرمسئله
قبلی را از جدول برداشته و کار را با زیرمسئله بعدی دنبال می‌کند. روش برنامه‌نویسی پویا یک روش پایین به بالا است (البته همان‌طور که گفته شد، اگر از قبل بدانیم باید کدام زیرمسئله‌ها را حل کنیم تا به مرحله اصلی برسیم، یا این که مجبور نباشیم زیرمسئله‌هایی که استفاده نمی‌شوند را هم حل کنیم) به این معنی که از حل مسائل کوچکتر به حل مسائل بزرگتر می‌رسیم. درحالی‌که از نظر ساختاری، روش تقسیم و غلبه روشی است از بالا به پایین، یعنی به‌طور منطقی (نه عملی) پردازش از مسئله اولیه آغاز شده و به سمت پایین و حل مسائلِ کوچکتر،
اولیه آغاز شده و به سمت پایین و حل مسائلِ کوچکتر، به پیش می‌رود. مجموع زیرمجموعه و کوله پشتی: اضافه کردن یک متغیر. ما بیشتر و بیشتر می‌بینیم که مسائل مربوط به برنامه‌ریزی منبع خیلی خوبی از مسایل الگوریتمی را با انگیزهٔ عملی ارائه می‌دهد. تاکنون مشکلاتی را در نظر گرفتیم که در آن درخواست‌ها با فاصلهٔ زمانی مشخص از یک منبع مشخص‌شده و همچنین مشکلاتی که در آن درخواست‌ها دارای مدت و مهلت هستند، اما فواصل خاصی را که در طی آن باید انجام شود تعیین نشده‌است. در این بخش، ما نسخه‌ای از نوع دوم مشکل را با مدت زمان و
بخش، ما نسخه‌ای از نوع دوم مشکل را با مدت زمان و مهلت در نظر می‌گیریم، که حل مستقیم با استفاده از تکنیک‌هایی که تاکنون دیده‌ایم، دشوار است. ما برای حل مسئله از برنامه‌نویسی پویا استفاده خواهیم کرد، اما با یک تغییر: مشخص می‌شود مجموعه زیرمسئله‌ها به اندازه کافی نخواهدبود، و بنابراین ما در نهایت به ایجاد یک مجموعه غنی‌تر از زیرمسئله‌ها می‌پردازیم. همان‌طور که خواهیم‌دید، این کار با اضافه کردن یک متغیر جدید به بازگشت در زیربرنامهٔ پویا انجام می‌شود. مسئله. در مسئلهٔ برنامه‌ریزی که در اینجا مورد توجه قرار
در مسئلهٔ برنامه‌ریزی که در اینجا مورد توجه قرار می‌دهیم، ما یک ماشین داریم که می‌تواند دستورها را پردازش کند همچنین یک سری درخواست‌ها formula_1 داریم که می‌توانیم از آن در بازهٔ زمانی formula_2 تا formula_3 استفاده کنیم. هر درخواست مربوط به یک دستور است که برای پردازش آن به formula_4 واحد زمانی نیاز داریم. اگر هدف ما این باشد که دستورها را پردازش کنیم به طوری که ماشین را تا زمان formula_3 مشغول نگه داریم، کدام دستورها را باید انتخاب کنیم؟ به زبان دقیق تر، فرض کنید که ما آیتم‌های formula_1 را داریم، که هر
فرض کنید که ما آیتم‌های formula_1 را داریم، که هر کدام دارای وزن formula_4 است. هدف ما انتخاب یک زیرمجموعه از این آیتم‌ها است به طوری که مجموع formula_4های آیتم‌های انتخاب شده از formula_3 کمتر مساوی باشند و با توجه به این محدودیت، مجموع این وزن‌ها بیشترین مقدار ممکن باشد. ما این مسئله را «مسئلهٔ مجموع زیرمجموعه» می‌نامیم. این مسئله یک حالت خاص رایج از مسئلهٔ کوله پشتی است، که هر درخواست formula_10 یک ارزش formula_11 و یک‌وزن formula_4 دارد. هدف در این مسئلهٔ کلی‌تر این است که زیرمجموعه‌ای با بیشترین مجموع
کلی‌تر این است که زیرمجموعه‌ای با بیشترین مجموع ارزش انتخاب کنیم با توجه به اینکه نباید مجموع وزن‌ها از formula_3 بیشتر باشد. به‌طور معمول مسئلهٔ کوله پشتی یک زیرمسئله از مسائل کلی‌تر است. نام «کوله پشی» اشاره به مسئلهٔ پر کردن یک کوله پشتی با ظرفیت formula_3 دارد که باید آن را تا جای ممکن با استفاده از مجموعه ای از آیتم‌ها پرکرد. ما از واژهٔ وزن یا زمان برای اشاره به formula_3، formula_4 استفاده خواهیم کرد. چون این مسئله، مسائل برنامه‌ریزی دیگری که قبلاً دیده‌ایم را شبیه‌سازی می‌کند، طبیعی است که از خود
دیده‌ایم را شبیه‌سازی می‌کند، طبیعی است که از خود بپرسیم آیا الگوریتم حریصانه‌ای برای راه‌حل بهینه وجود دارد یا خیر. به نظر می‌آید که پاسخ خیر باشد، حداقل تا کنون هیچ روش حریصانهٔ کارایی شناخته نشده‌است که آیتم‌ها را به صورت نزولی مرتب کند؛ یا حداقل این کار را برای آیتم‌های با وزن حداکثر formula_3 انجام دهد، و سپس ما شروع به انتخاب آیتم‌ها با این ترتیب کنیم تا جایی که مجموع وزن آیتم‌های انتخاب شده کمتر از formula_3 باشد. اما اگر formula_3 مضرب دو باشد، و ما سه آیتم با وزن‌های formula_20 داشته‌باشیم، خواهیم
سه آیتم با وزن‌های formula_20 داشته‌باشیم، خواهیم دید که الگوریتم حریصانه جواب بهینه را تولید نخواهد کرد. به‌طور جایگزین می‌توانستیم آیتم‌ها را بر اساس وزنشان به صورت صعودی مرتب کنیم و کار مشابه را انجام دهیم، ولی این بار در ورودی‌های formula_21 شکست می‌خورد. هدف ما این است که نشان دهیم که چگونه با استفاده از برنامه‌نویسی پویا این مسئله را حل کنیم. اصول اولیهٔ برنامه‌نویسی پویا را به یاد بیاورید: ما باید تعداد کمی از زیرمسئله‌ها را داشته باشیم به طوری که هر زیرمسئله را بتوان به راحتی با استفاده از
که هر زیرمسئله را بتوان به راحتی با استفاده از زیرمسئله‌های «کوچکتر» حل کرد و پاسخ به مسئلهٔ اصلی به‌راحتی به‌دست می‌آید، هنگامی که ما پاسخ همهٔ زیر مسئله‌ها را بدانیم. طراحی الگوریتم. می‌خواهیم از تعداد زیادی زیرمسئله استفاده کنیم. در واقع برای هر مجموعهٔ اولیه formula_22 از آیتم‌ها و هر مقدار ممکن w برای بیشینه وزن ممکن، زیرمسئله‌ای در نظر می‌گیریم تا با استفاده از آنها بتوانیم سریعتر مسئله را حل کنیم. فرض کنید که formula_3 یک عدد صحیح باشد و همهٔ درخواست‌های formula_24 مقادیر صحیح formula_4 هستند. ما یک
formula_24 مقادیر صحیح formula_4 هستند. ما یک زیرمسئله به ازای هر formula_24 و هر formula_27 داریم. ما formula_28 را به عنوان مقدار پاسخ بهینه برای آیتم‌های formula_29 و بیشینه وزن مجاز formula_30 تعریف می‌کینم که برابر است با: formula_31 که formula_32 روی زیرمجموعهٔ formula_33 است که formula_34 را ارضا می‌کند. استفاده از این مجموعهٔ جدید از زیرمسئله‌ها، این اجازه را به ما می‌دهد که مقدار formula_28 به عنوان یک عبارت ساده بر حسب مقادیر به‌دست آمده از مسائل کوچکتر بیان کرد. علاوه بر این formula_28 کمیتی است
بیان کرد. علاوه بر این formula_28 کمیتی است که ما در انتها به دنبال آن هستیم. فرض کنید که o نمایانگر راه‌حل بهینه برای مسئلهٔ اصلی باشد. دو حالت داریم: ۱- اگر formula_37 آنگاه formula_38 پس به راحتی می‌توانیم عبارت formula_39 را نادیده بگیریم. ۲- اگر formula_40 آنگاه formula_41، از این به بعد ما به دنبال استفاده از ظرفیت باقی‌ماندهٔ formula_42 هستیم. هنگامی که آیتم nام بسیار بزرگ است، formula_43 ما باید داشته باشیم formula_44. در غیر این صورت، ما راه‌حل بهینه را از این طریق با توجه به اینکه برای هر n
بهینه را از این طریق با توجه به اینکه برای هر n درخواست کدام یک از گزینه‌های بالا بهتر است به‌دست می‌آوریم. با استفاده از استدلال مشابه برای زیرمسئلهٔ آیتم‌های formula_45 و بیشینه وزن formula_30، رابطهٔ بازگشتی روبرو را می‌دهد: اگر formula_47 آنگاهformula_48. در غیر اینصورت:formula_49 مانند قبل، ما می‌خواهیم الگوریتمی طراحی کنیم که جدولی از همهٔ مقادیر ممکن formula_28 داشته باشیم درحالی که هر کدام از آنها را حداکثر یکبار محاسبه کرده باشیم. با استفاده از لم (*) می‌توان فوراً ثابت کرد که مقدار برگشتی
از لم (*) می‌توان فوراً ثابت کرد که مقدار برگشتی formula_51 برای در خواست‌های formula_1 و وزن در دسترس formula_3، پاسخ بهینه‌ای است .(formula_54 یک آرایهٔ دو بعدی است که مقادیر formula_28 را در خود ذخیره کرده‌است) آنالیز آلگوریتم. برای الگوریتمی که در این شرایط طراحی کرده‌ایم، اما به یک جدول دو بعدی نیاز داریم، که بازتاب دو بعدی جدول زیرسوالات است که در حال ساخته شدن هستند. به عنوان یک مثال از اجرای این الگوریتم، به یک نمونه با وزن formula_56 و formula_57 و آیتم‌هایی با اندازه formula_58 "و" formula_59
و آیتم‌هایی با اندازه formula_58 "و" formula_59 توجه کنید. ما در خواهیم یافت که مقدار بهینه formula_60 خواهدبود (که با استفاده از سومین آیتم و یکی از دو آیتم اول آن را به‌دست آورده‌ایم). قبل از آن، در مورد برنامه‌ریزی فواصل زمانی موزون، جدول راه حل‌های formula_54 را ساخته‌ایم، و مقادیر formula_62 را با استفاده از مقادیر قبلی در زمان اجرای formula_63محاسبه می‌کنیم؛ بنابراین مدت زمان اجرا متناسب با تعداد ورودی‌ها به جدول می‌باشد. الگوریتم مجموع زیرمجموعه formula_64 بهینه جواب مسئله را محاسبه می‌کند و زمان
بهینه جواب مسئله را محاسبه می‌کند و زمان اجرای آن formula_65 است. توجه کنید که زمان اجرای برنامه تابعی از چندجمله‌ای بر حسب n نیست، در واقع یک تابع چندجمله ای از formula_39 و formula_30 است. ما چنین الگوریتم‌هایی را «شبه چندجمله‌ای» می‌نامیم. الگوریتم‌های شبه‌چندجمله‌ای می‌توانند به‌طور قابل توجهی کارا باشند هنگامی که اعداد formula_68ی که به عنوان ورودی دریافت می‌کنیم به‌طور قابل توجهی کوچک باشند. هرچند هنگامی که formula_69ها بزرگ می‌شوند عملکرد این الگوریتم‌ها کاهش می‌یابد. برای به‌دست آوردن یک مجموعه
کاهش می‌یابد. برای به‌دست آوردن یک مجموعه بهینه formula_70 از آیتم‌ها، می‌توانیم آرایهٔ formula_54 را با استفاده از روشی که در قبل گفته شد ردیابی کنیم. یک جدول formula_54 از بهینه مقدارهای زیرمسئله‌ها داده شده‌است. بهترین مجموعه formula_70 را می‌توان در زمان formula_74 پیدا کرد. مسئلهٔ کوله پشتی. مسئلهٔ کوله پشتی کمی از مسئلهٔ برنامه‌ریزی که در قبل بحث کردیم سخت‌تر است. شرایطی را در نظر بگیرید که مانند قبل آیتم formula_10 یک‌وزن نامنفی formula_69 دارد و همچنین یک ارزش جداگانه formula_77 نیز دارد. هدف ما
یک ارزش جداگانه formula_77 نیز دارد. هدف ما پیدا کردن مجموعه formula_70 با بیشینه ارزش formula_79 با محدودیت مجموع وزن این آیتم‌ها نباید از formula_3 بیشتر شود. سخت نیست که الگوریتم پویای خود را برای این مسئله کلی تر گسترش دهیم. ما از مجموعه زیرمسئله‌های مشابه استفاده می‌کنیم، formula_28 تا مقدار راه‌حل بهینه را مشخص کنیم با استفاده از زیرمجموعه از آیتم‌های formula_22 و بیشینه وزن دردسترس formula_30. ما یک راه‌حل بهینه formula_84 در نظرمی‌گیریم و دوحالت را با توجه به اینکه formula_40 هست یا خیر، مشخص
را با توجه به اینکه formula_40 هست یا خیر، مشخص می‌کنیم: ۱- اگر formula_37 آنگاه formula_87 ۲- اگر formula_40 آنگاه formula_89 استفاده از این خط از استدلال برای زیرمسئله‌ها نتیجهٔ مشابه (*) را می‌دهد. اگر formula_90 آنگاه formula_91. در غیر این صورت: formula_92 با استفاده از این روش بازگشت، می‌توانیم یه الگوریتم پویای کاملاً مشابه پیاده‌سازی کنیم، که نتیجهٔ روبرو را می‌دهد: مسئلهٔ کوله پشتی در زمان اجرای formula_93 قابل حل است. الگوریتم ضریب دو جمله‌ای با استفاده از برنامه‌ریزی پویا. ورودی‌ها : اعداد صحیح
از برنامه‌ریزی پویا. ورودی‌ها : اعداد صحیح و مثبت formula_39 و formula_95 که در آن formula_96 است. خروجی‌ها : bin2 ضریب دو جمله‌ای formula_97 int bin2(int n, int k) int B[n + 1][k + 1]; for(int i = 0;i &lt;= n;i++) for(int j = 0;j &lt;= min(k, i);j++) if(j == 0 || j == i) B[i][j] = 1; else B[i][j] = B[i - 1][j - 1] + B[i - 1][j]; return B[n][k]; محدودیت‌های برنامه‌نویسی پویا: مسئلهٔ فروشندهٔ دوره‌گرد. برنامه‌نویسی پویا همیشه جواب نمی‌دهد. خوب است که علت این موضوع را بدانیم تا از اینکه در دام الگوریتم‌های
موضوع را بدانیم تا از اینکه در دام الگوریتم‌های نادرست و نابهینه بیفتیم، خودداری کنیم. ابتدا به بررسی مسئلهٔ زیر می‌پردازیم: مسئله: بلندترین مسیر ساده ورودی: یک گراف وزن دار formula_98 با راس‌های شروع و پایان formula_99 داریم . خروجی: مسیری از formula_70 به formula_101 بیابید که بیشترین وزن را داشته باشد و در آن هیچ رأسی را بیش از یک بار نبینیم. این مسئله از دو جهت با مسالهٔ فروشندهٔ دوره‌گرد(TSP) متفاوت است. اولاً، این مسئله به دنبال یک مسیر است نه یک تور بسته. این تفاوت قابل توجه نیست: به راحتی با اضافه
بسته. این تفاوت قابل توجه نیست: به راحتی با اضافه کردن یال formula_102 یک تور بسته به دست می‌آوریم. ثانیاً این مسئله به دنبال مسیر با بیشترین وزن است به جای مسیر با کمترین وزن. باز هم این تفاوت خیلی مهم نیست: این مسئله ما را تشویق می‌کند تا جایی که می‌توان راس‌ها را بازدید کرد (در حالت ایدئال تمام رئوس) دقیقاً مانند TSP. نکتهٔ مهم در این مسئله این است که ما نیابد از هیچ رأسی بیش از یک بار عبور کنیم. برای گراف‌های غیر وزندار، بزرگترین مسیر از formula_70 به formula_101 حداکثر formula_105 یال دارد. پیدا کردن
حداکثر formula_105 یال دارد. پیدا کردن چنین «مسیرهای همیلتونی» یک مسئلهٔ مهم در نظریه گراف است. چه زمان‌هایی الگوریتم‌های برنامه‌نویسی پویا درست هستند؟ درستی الگوریتم‌های برنامه‌نویسی پویا وابسته به روابط بازگشتی‌ای است که بر پایه آن بنا شده‌اند. فرض کنید ما تابع formula_106 را به عنوان تابعی که نمایانگر طول بلندترین مسیر ساده از formula_10 به formula_108 است تعریف کنیم. توجه کنید که بلندترین مسیر ساده از formula_10 به formula_108 باید قبل از رسیدن به formula_108، تعدادی رئوس formula_112 را بازید کند؛
تعدادی رئوس formula_112 را بازید کند؛ بنابراین، آخرین یال بازدید شده باید به صورت formula_113 باشد. این موضوع رابطهٔ بازگشتی روبرو را برای محاسبهٔ طول بلندترین مسیر ساده پیشنهاد می‌کند: formula_114 که در آن formula_115 وزن یال formula_113 است. ایده به نظر معقول می‌رسد، اما شما می‌توانید مشکلات را ببینید؟ به دو مورد زیر توجه کنید: اولاً، این رابطهٔ بازگشتی منجر به هیچ‌گونه سادگی نمی‌شود. ما از کجا می‌دانیم که راس formula_108 قبلاً در بلندترین مسیر ساده از formula_10 به formula_112 ظاهر نشده‌است؟ اگر ظاهر
formula_10 به formula_112 ظاهر نشده‌است؟ اگر ظاهر شده باشد، آنگاه اضافه کردن یال formula_113 منجر به ایجاد دور در گراف می‌شود. برای جلوگیری از چنین چیزی، ما باید یک تابع بازگشتی متفاوت تعریف کنیم که صراحتاً ذخیره کند که ما در چه مکان‌هایی حضور داشتیم. شاید بتوانیم formula_121 را تعریف کنیم به عنوان تابعی که نمایانگر بلندترین مسیر ساده از formula_10 به formula_108 است و از راس formula_95 عبور نمی‌کند؟ شاید این یک قدم در جهت درست باشد ولی هنوز ما را به یک تابع بازگشتی قابل اطمینان نمی‌رساند. مشکل دوم مربوط
بازگشتی قابل اطمینان نمی‌رساند. مشکل دوم مربوط به دستورالعمل ارزیابی است. ابتدا چه چیزی را ارزیابی می‌کنید؟ چون هیچ ترتیب چپ به راست یا بزرگ به کوچکی از رئوس وجود ندارد، واضح نیست که زیرمسئله‌های کوچکتر چه هستند. بدون داشتن چنین ترتیبی، ما در یک دور بینهایت می‌افتیم تا زمانی که بخواهیم کاری انجام دهیم. برنامه‌نویسی پویا را می‌توان در هر مسئله‌ای که اصل بهینه بودن را رعایت می‌کند بکار برد. برای مثال، در تصمیم‌گیری اینکه یک تطابق رشته‌ای را به‌وسیلهٔ جابه‌جایی، اضافه کردن یا حذف کردن گسترش دهیم، ما نیازی
اضافه کردن یا حذف کردن گسترش دهیم، ما نیازی نداریم که بدانیم کدام دنباله از عملگرها تا آن زمان انجام شده‌است. در واقع، ممکن است دنباله‌های متفاوت ویرایش وجود داشته باشد که هزینهٔ formula_125 را بر روی formula_126 حرف از الگوی formula_127 و formula_101 حرف از الگوی formula_129 اعمال می‌کند. مسئله‌ها هنگامی از اصل بهینگی پیروی نمی‌کنند که به جای هزینهٔ عملیات، مشخصهٔ عملیات مهم می‌شود. چنین چیزی می‌تواند شکلی از مسئلهٔ فاصلهٔ ویرایش که در آن مجاز به استفاده از عملگرها با یک ترتیب خاص نیستیم، باشد. هر چند
از عملگرها با یک ترتیب خاص نیستیم، باشد. هر چند بسیاری از مسائل ترکیبیات از اصل بهینگی پیروی می‌کنند. چه زمانی الگوریتم‌های برنامه‌نویسی پویا کارا هستند؟ زمان اجرای الگوریتم‌های برنامه‌نویسی پویا تابع دو چیز است :۱) تعداد زیر مسئله‌هایی که ما باید آنها را بررسی کنیم ۲) چه قدر طول می‌کشد تا هر زیرمسئله را بررسی کنیم. مورد اول – که معمولاً فضای حالات نامیده‌می‌شود – مشکل جدی‌تری است. تاکنون در مسئله‌هایی که بررسی کردیم، زیر مسئله‌ها به‌وسیلهٔٔ مکان‌های توقف در ورودی مشخص می‌شدند. این به این خاطر است که
در ورودی مشخص می‌شدند. این به این خاطر است که موضوعات ترکیبیاتی که روی آنها کار می‌شده مانند رشته‌ها، دنباله‌های عددی، چندضلعی‌ها و … به صورت ضمنی در عناصر خود دارای یک ترتیب هستند. این ترتیب را نمی‌توان به هم زد مگر با عوض کردن صورت مسئله. هنگامی که ترتیب مشخص شد، مکان‌های توقف یا حالات نسبتاً کمی وجود خواهد داشت، به طوری که ما می‌توانیم الگوریتم‌های بهینه را به‌دست بیاوریم. هنگامی که اشیا به صورت مشخص دارای یک ترتیب نیستند، ما تعداد نمایی از زیر مسئله‌ها را به‌دست می‌آوریم (برخلاف بالا). فرض کنید حالات
را به‌دست می‌آوریم (برخلاف بالا). فرض کنید حالات زیرمسئله ما شامل کل مسیرها از راس شروع تا مقصد است. پس formula_130 مشخص کنندهٔ بلندترین مسیر ساده از formula_10 تا formula_108 است که formula_127 دنبالهٔ دقیق رئوس میانی بین formula_10 و formula_108 است که در مسیر آمده‌است. رابطهٔ بازگشتی روبرو برای محاسبهٔ مقدار بالا است که در آن formula_136 به معنی اضافه کردن formula_112 به انتهای formula_127 است: formula_139 این رابطه درست است اما چه قدر بهینه است؟ مسیر formula_127 شامل حداکثر formula_141 راس با یک ترتیب
شامل حداکثر formula_141 راس با یک ترتیب مشخص است. پس ما formula_142 از چنین مسیرهایی داریم، در واقع، این الگوریتم واقعاً از جستجوی ترکیبیاتی استفاده می‌کند تا تمامی مسیرهای بین را بسازد. ما با این ایده می‌توانیم یک کار بهتر انجام دهیم. فرض کنید که formula_143 مشخص‌کنندهٔ بلندترین مسیر از formula_10 به formula_108 است که رأس‌های میانی روی مسیر دقیقاً در مجموعه formula_146 قرار دارد. بنابر این اگر formula_147، دقیقاً ۶ مسیر وجود دارد: formula_148 این فضای حالت حداکثر formula_149 حالت دارد، بنابراین کوچکتر از
حداکثر formula_149 حالت دارد، بنابراین کوچکتر از مسیرهای محاسبه شده در قسمت قبل است. علاوه بر این، تابع را می‌توان با رابطه بازگشتی روبرو محاسبه کرد: formula_150 پس می‌توان بلندترین مسیر ساده از formula_10 به formula_108 را با بیشینه کردن روی مجموعهٔ تمام رئوس بین این دو رأس به دست آورد. formula_153 تنها formula_149 زیر مجموعه از formula_39 راس وجود دارد، پس این یک بهبود چشمگیر روی شمردن تمام formula_156 تور ممکن است. در واقع این روش می‌تواند برای حل TSP هنگامی که بیش از ۳۰ رأس داریم استفاده شود. همچنان
هنگامی که بیش از ۳۰ رأس داریم استفاده شود. همچنان برنامه‌نویسی پویا بیشترین تأثیر را بر اشیایی که به صورت مناسب مرتب شده‌اند دارد.
قهوه‌خانه عرش، نام یکی از معروفترین قهوه‌خانه‌های تهران در عهد قاجاریه است، که در خیابان چراغ برق این شهر قرار داشت. در تهران قدیم، برخی از قهوه‌خانه‌های شهر، مرکز اجتماع و به اصطلاح پاتوق اشرار و افراد بدنام و ناراحت بودند و محل فسق و فجور آن‌ها به‌شمار می‌آمدند. یکی از شاخصترین و معروفترین این قهوه‌خانه‌ها، قهوه‌خانه عرش بود که پاتوق و محل تجمع افراد معتاد و الکلی محسوب می‌شد. به نظر می‌آید که وجه تسمیهٔ این قهوه‌خانه از سفر خیالی افراد معتاد و الکلی پس از مستی و نشئگی به عرش، گرفته شده باشد و این
پس از مستی و نشئگی به عرش، گرفته شده باشد و این قهوه‌خانه به دلیل سیر دادن مشتریان خود در عرش، بدین نام نامیده می‌شد. محل این قهوه‌خانه در خیابان چراغ برق قرارداشت و مرکز شبانه‌روزی معتادها و و عرق خورهای تهران به‌شمار می‌آمد. به این کیفیت که:
قُرنه به معنی شاخ و شهریست در جنوب شرق کشور عراق و از توابع شهرستان بصره با جمعیت ۴۵۰ هزار نفر است. قرنه در در محل تقاطع دو رود دجله و فرات و محل تشکیل شط العرب است. به واسطه استخراج نفت جز ثروتمندترین شهرهای عراق می‌باشد. تا زمان حکومت صدام حسین استخراج نفت از این چاه‌ها را شرکت‌های روسی انجام می‌دادند. همچنین قرنه محل قدیمی سکونت عشیره قرینی است که اکنون این محل سکونت این عشیره بصره می‌باشد. همچنین اجداد عشیره سادات آل جابر در این منطقه سکونت داشتند و سید جابر الصغیر یکی از اجداد عشیره سادات آل جابر
سید جابر الصغیر یکی از اجداد عشیره سادات آل جابر محمدیه در این منطقه به دست حکومت عثمانی مسموم شد و پدرش سید حسن نیز از سوی حکومت عثمانی اعدام شد. و فرزندان سید جابر الصغیر به اجبار از قرنه فرار کردند سید موسی بن سید علی بن سید جابر الصغیر پس از به قتل رسیدن مظلومانه برادرش سید حسین به خرمشهر و منطقه صلبوخ قدیم (جزیره مینو) رفت. و سید هاشم و سید جاسم فرزندان سید جابر بن سید محسن بن سید یوسف بن سید شریف بن سید جابر الصغیر نیز از منطقه کوت الزین به جزیره مینو مهاجرت کردند و فرزندانشان در آن منطقه و منطقه
مهاجرت کردند و فرزندانشان در آن منطقه و منطقه سلیچ در آبادان ساکن شدند. قرنه از در محاصره دو هور العظیم از شرق و هور الحمار از غرب می‌باشد. به واسطه فاصله ۴۰ کیلومتری با مرز ایران این شهر در طول جنگ هشت ساله ایران و عراق متحمل خسارات فراوانی شد. از اماکن تفریحی آن می‌توان به درخت آدم اشاره کرد. درختی که اهالی منطقه اعتقاد دارند در محل حضور آدم کاشته شده و ابراهیم بر آن نماز خوانده‌است. فاصله شهرک القرنه تا جزیره مجنون ۱۵ کیلومتر است.
سحام‌نیوز، وب‌سایت وابسته به مهدی کروبی، برگرفته از سر حروف ابتدای واژگان «سایت حزب اعتماد ملی» است. در بهار سال ۱۳۸۷، مهدی کروبی با صدور یک حکم، مهدی علی بابایی را به عنوان مدیر روابط عمومی حزب اعتماد ملی منصوب کرد. تا قبل از فعالیت مهدی علی بابایی به عنوان مدیر روابط عمومی، حزب اعتماد ملی دارای یک وب‌سایت اطلاع‌رسانی بود که در اردیبهشت سال ۱۳۸۷ با پیشنهاد مدیر روابط عمومی، مهدی علی بابایی و تصویب مهدی کروبی، نام سحام نیوز برای پایگاه خبری حزب اعتماد ملی انتخاب شد. نخستین سردبیر سایت حزب اعتماد ملی نیز