payamvha/North_RAG huggingface dataset:
الهی را بر عقل کلی و سپس از طریق آن بر جهان متجلی می‌سازد. فیلسوفان اسماعیلیه، مانند نصیرالدین طوسی، معتقد بودند آفریدگار با جهان از طریق مظهر (محل ظهور) ارتباط برقرار می‌کند. شهاب الدین سهروردی، بنیان‌گذار مکتب فلسفی حکمت اشراق، از کلمه «تجلّی» برای بیان همین مفهوم استفاده می‌کرد و آن را در مورد انسانها و روح القدس به کار می‌برد. ملاصدرا فیلسوف شیعه معتقد بود که خداوند خود را از طریق اسماء و صفات خود ظاهر می‌سازد. جریان فکری دیگری نیز در اسلام وجود دارد مانند مکتب ابن عربی که تجلی خداوند را تجلی ذات او
مانند مکتب ابن عربی که تجلی خداوند را تجلی ذات او می‌داند نه تجلی صفاتش. عرفان شیعی. در عرفان شیعی، عبارت مظهر ظهور به پیامبران و امامان گفته شده‌است. انسان کامل یا الحقیقة المحمدیة مظهر اسماء و صفات الهی است. امامان نیز مظاهر «امام جاودان» و دارای صفات الهی هستند. این امام است که به عنوان مرکز ظهور الهی عمل می‌کند. احمد احسائی در حدیثی منتسب به سجاد، امام چهارم شیعیان، آورده‌است: «نحن معانیه و ظاهره فیکم: ما معانی و ظاهرش در بین شما هستیم.» احسائی در حدیث دیگری از سجاد نقل می‌کند که وجود خارجی من به صورت
دیگری از سجاد نقل می‌کند که وجود خارجی من به صورت امامت است اما درونم نادیدنی و نافهمیدنی است. ابن‌عربی. در آثار ابن عربی، ظهور ارتباط نزدیکی با تجلی یا خودآشکارسازی الهی دارد؛ مظاهر مراکز خارجی برای آشکارشدن تجلیات حق هستند. در اینجا، کلمهٔ مظهر هم‌معنی کلمهٔ مجلی و به معنی وجودی خارجی که اسم الهی را نشان دهد استفاده شده‌است. در نظریهٔ انسان کامل ابن عربی، انسان کامل به مانند آینه‌ای است که حق خود را در آن متجلی می‌بیند. این بیان ابن‌عربی مشابه بیان شیعه در مورد امام است که در آن انسانی جلوه‌گاه الوهیت
در مورد امام است که در آن انسانی جلوه‌گاه الوهیت است. در این بیان، انسان کامل برزخی است که جهان‌های خالق و مخلوق را به هم پیوند می‌دهد. بابیه. سید علی‌محمد باب نظریهٔ پیچیده‌ای برای مظاهر ظهور در آثار متاخر خود، به‌ویژه بیان فارسی و کتاب پنج شأن، تدوین کرد. در تقابل با بطون، ظهور به معنی آشکارسازی خویش توسط خداوند بر مخلوقاتش است. این آشکارسازی در یک «مظهر» انجام می‌شود که در آن الوهیت خود را به بقیهٔ مخلوقات آشکار کرده‌است: حقیقت نهان وحدت الهی (غیب التوحید) تنها از طریق ظهوراتش در پیام‌اورانش تأیید
تنها از طریق ظهوراتش در پیام‌اورانش تأیید می‌شود. خداوند خود را از طریق مظاهرش به خلق می‌شناساند. هرکسی که خداوند را شناخت، تنها از طریق پیامبرانش بود که علت شناخت خدا بودند. این ذات الهی نیست که ظهور می‌کند، بلکه "امر اولی" است که بر انسان ظاهر می‌شود: این امر (مظهر) ذات ازلی و غیبی نیست، بلکه مشیتی است که برای خود از هیچ خلق کرده‌است. از ازلی که آغازی ندارد و ابدی که پایان ندارد، همیشه تنها یک مشیت واحد بوده که ظاهر شده‌است. این مظهر که نام‌های مختلفی مانند عرش، کرسی، هیکل، آینه (مرآة)، شجرة الحقیقة، و
عرش، کرسی، هیکل، آینه (مرآة)، شجرة الحقیقة، و نقطة الاولی دارد، یک مخلوق دارای اضداد است. در وجود خارجی‌اش میرا و فناپذیر است اما در وجود درونی‌اش الهی است. مظاهر تاریخی در حقیقت همه یک فرد بودند. برای تشبیه، مظاهر را به خورشیدی که در آینه‌های مختلف دیده می‌شوند را مثال زنده‌اند. به‌طور خاص، پیامبران اولوالعزم و امامان شیعه از مظاهر بوده‌اند. در سال‌های آخر، باب خود را آخرین مظهر امر اولی خواند و یک آئین و شریعت جدید آغاز کرد. علاوه بر این، او به بسیاری از پیروانش مقام جزئی یا کلی ظهور الهی نسبت داد. او به
مقام جزئی یا کلی ظهور الهی نسبت داد. او به صراحت پیرو اصلی‌اش محمدعلی بارفروشی مشهور به قدوس را مظهر خدا نامید. در بحث‌های الهیاتی بابیه، وجود همزمان مظاهر ردهٔ دوم و سوم در کنار مظهر اصلی توسط تمثیلی توضیح داده می‌شود که در آن آینه‌های دیگری نور بازتابیده از آینهٔ اصلی را دوباره باز می‌تابانند. دیانت بهائی. در هیچ‌یک از این آثار اسلامی، مفهوم مظهر ظهور آنچنان که در آثار مقدس بهایی آمده اهمیت و محوریت ندارد. در آثار بهائی بین خداوند (عالم حق) و خلقت و بشریت (عالم خلق) واسطه‌ای هست به نام عالم امر. طبق گفته
(عالم خلق) واسطه‌ای هست به نام عالم امر. طبق گفته بهاءالله عالم حق (خداوند) برای بشر غیرقابل درک است از این رو خداوند افرادی (پیامبران و بنیانگذاران ادیان جهان) را معین کرده که واسطه بین او و بشریت باشند. این واسطه‌ها ماهیتی دوگانه دارند، جسم مادی و فطرت انسانی آنها متعلق به عالم خلق است و حقیقت روحانی آنها متعلق به عالم امر. آنها نمایندگان خدا بر روی زمین هستند و با تجلی کامل همه اسماء و صفات او، هر آنچه را که بشر می‌تواند از خداوند درک کند در خود منعکس و ظاهر می‌سازند از این رو به آنها مظهر الهی گفته
و ظاهر می‌سازند از این رو به آنها مظهر الهی گفته می‌شود و این اصطلاحی است که بهاءالله در رابطه با خود از آن استفاده می‌کند نه رسول یا نبی. در آیین بهایی، این اصطلاح بیانگر تجلی صفات الهی است نه حلول خداوند. یکی از پیامدهای آموزه مظهریت الهی این است که ماهیت و جایگاه ذاتی همه مظاهر الهی (پیامبران) یکی است و در واقع می‌توان آنها را از لحاظ روحانی یک حقیقت دانست، حقیقتی که در زمانهای مختلف در جهان ظاهر شده‌است؛ لذا وحدتی استعلایی در ادیانی که این مظاهر الهی آورده‌اند وجود دارد. از سوی دیگر بهاءالله تصریح
آورده‌اند وجود دارد. از سوی دیگر بهاءالله تصریح می‌کند که هر یک از مظاهر الهی در زمان خاصی ظاهر می‌شود و مأموریت خاصی برعهده دارد که بر حسب شرایط بشرِ آن زمان مشخص می‌شود. از این رو مظاهر الهی و همچنین ادیانی که می‌آورند متفاوت به نظر می‌رسند. مظاهر الهی که پی در پی ظاهر می‌شوند عوامل ظهور تدریجی اراده الهی و کاتالیزورهای اصلی تکامل اجتماعی بشر هستند و هر یک آموزه‌های خود را با تکیه بر آموزه‌های مظهر الهی پیشین تکمیل می‌کند. متون مقدس بهائی علاوه بر شخصیت‌هایی که در کتاب مقدس و قرآن ذکر شده‌است، مانند
که در کتاب مقدس و قرآن ذکر شده‌است، مانند ابراهیم، موسی، عیسی و محمد افراد دیگری را نیز در زمره مظاهر الهی می‌شمارند نظیر زرتشت، کریشنا و بودا. همچنین بر طبق متون مقدس بهائی مظاهر الهی متعدد دیگری نیز ظهور کرده‌اند - به عنوان مثال در میان بومیان آمریکا - که نام‌شان در تاریخ گم شده‌است. در تفسیر سید علی‌محمد باب و بهاءالله ملاقات با خدا (لقاءالله) در روز قیامت که کتابهای آسمانی به آن بشارت داده‌اند، دلالت بر ظهور یک مظهر الهی در پایان دور دین قبل دارد، زمانی که پیروان دین پیشین بر مبنای این که آیا موفق به
که پیروان دین پیشین بر مبنای این که آیا موفق به شناخت مظهر الهی جدید می‌شوند یا نه، مورد داوری قرار می‌گیرند، از این به رستاخیز روز داوری نیز گفته می‌شود. در این تفسیر، قیامت زنده شدن روحانی آدمیان از طریق شناخت مظهر الهی جدید است. تعالیم بهائی بسیار شبیه دیدگاه‌های بابیه‌اند، با این تفاوت که در بهائیت دامنهٔ مظاهر الهی محدودتر است و معمولاً منحصر به بنیان‌گزاران ادیان بزرگ می‌شود. هم‌زمان، تعریف گسترده‌تر از حقیقت دینی اجازه می‌دهد که بودا و کریشنا (که بهائیان آنان را بنیان‌گزاران هندوئیسم می‌پندارند) نیز
آنان را بنیان‌گزاران هندوئیسم می‌پندارند) نیز مظهر الهی دانسته شوند. بنا بر اعتقاد بهائیان، بهاءالله آخرین مظهر الهی است و حداقل تا هزار سال مظهر دیگری نخواهد آمد. نه‌تنها بهائیان برای بهاءالله مقام بالاتری در میان مظاهر قبل و بعدش قائل شده‌اند، خود بهاءالله با بیانی شبیه به حلول خداوند در او صحبت کرده‌است. گرچه چندین مورد عبارات شبیه به حلول از بهاءالله وجود دارد، اعتقاد امروزی بهائیان هرگونه تعبیر حلول‌گونه در مورد مظهر را رد می‌کند. ماهیّت مظهر ظهور. ظهور یعنی ظاهر ساختن و نشان دادن چیزی که از قبل معلوم
یعنی ظاهر ساختن و نشان دادن چیزی که از قبل معلوم نبوده‌است. مظاهر ظهور الهی افرادی هستند که کلمات خدا را برای بشر ظاهر و عیان می‌نمایند. آن‌ها به تمام جنبه‌های زندگی بشر آگاه‌اند. آنان مربیان جهان هستند که به بشر یاد می‌دهند چگونه طبق ارادهٔ الهی زندگی کنند و به سعادت حقیقی برسند. طبق اصول اعتقادات بهائی، مظهر ظهور، تجلّی‌گاه کامل اسماء و صفات الهی است. بهائیان این اصل را این گونه توضیح می‌دهند که اگر خداوند را همانند خورشید در نظر بگیریم، مظهر ظهور همانند آینه‌ای پاک و صیقلی است که تصویر و پرتوهای خورشید
آینه‌ای پاک و صیقلی است که تصویر و پرتوهای خورشید را به بهترین نحو منعکس می‌سازد. امّا این بدین معنا نیست که خداوند از مقام خود در آینه تنزّل نموده‌است، بلکه فقط رحمت و فیض او و صفات و اسماء او در آن آینه تجلّی می‌نماید. مظهر ظهور الهی معصوم است و عصمت او ذاتی است. از نظر بهائیان، تنها راه شناسایی خداوند، شناخت مظهر ظهور است، زیرا تفکّر و تعقّل آدمی هیچ‌گاه به مقام الهی راه ندارد و هرآنچه که انسان در مورد ذات الهی بیندیشد، زاییدهٔ فکر و خیال او است. امّا مظهر ظهور الهی، جامع تمام صفات و اسماء الهی است و
مظهر ظهور الهی، جامع تمام صفات و اسماء الهی است و قابل شناسایی می‌باشد. البته شدّت ظهور صفات الهی در مظاهر ظهوری که در زمان و مکان متفاوت ظهور نموده‌اند متفاوت است. مراتب مظهر ظهور. بهائیان اعتقاد دارند که مظاهر ظهور الهی دارای سه مرتبه هستند: نیاز بشر به مظهر ظهور. بهائیان بر این باورند که خدا در هر زمانی بنا بر اقتضای زمان و مکان فردی را برای پیامبری بر روی زمین انتخاب می‌نماید. همچنین، نیاز بشر به مظهر ظهور هیچ‌گاه از بین نمی‌رود، زیرا انسان همواره به مربّی و راهنمایی نیازمند است تا او را به سمت کمال
مربّی و راهنمایی نیازمند است تا او را به سمت کمال هدایت نماید. این مربّی باید بر تمام جنبه‌های زندگی انسان آگاه و در این مورد بصیرتی روشن داشته‌باشد. از نظر بهائیان، فقط مظهر ظهور است که چنین بصیرت و قوّه‌ای را داراست. مظهر ظهور بشر را از سه جنبهٔ جسمانی، انسانی، و روحانی تربیّت می‌نماید. تربیّت جسمانی مربوط به سلامت جسم و مسائل مرتبط با آن است. تربیّت انسانی مربوط به مدنیّت، اجتماع، سیاست، علوم و صنایع و هنر است و در نهایت تربیّت روحانی است که بهائیان آن را تربیّت حقیقی می‌دانند. این تربیّت مربوط به کسب
را تربیّت حقیقی می‌دانند. این تربیّت مربوط به کسب کمالات الهی و صفات روحانی می‌باشد. بهائیان معتقدند که بهاءالله، بنیان‌گذار دین بهائی جدیدترین فرستادهٔ الهی در سلسلهٔ پیامبران پیشین چون ابراهیم، موسی، بودا، زردشت، مسیح، محمّد و باب است.
روش حریصانه یا الگوریتم حریصانه (به انگلیسی: Greedy algorithm) یکی از روش‌های مشهور و پرکاربرد طراحی الگوریتم‌ها است که با ساختاری ساده در حل بسیاری از مسائل استفاده می‌شود. این روش اغلب در حل مسائل بهینه‌سازی به کار می‌رود و در پاره‌ای مواقع جایگزین مناسبی برای روش‌هایی مانند برنامه‌ریزی پویا است. در حالت کلی این روش سرعت و مرتبهٔ اجرایی بهتری نسبت به روش‌های مشابه خود دارد؛ اما متناسب با مسئله ممکن است به یک جواب بهینهٔ سراسری ختم نشود. این دسته از الگوریتم‌ها در علوم رایانه کاربرد وسیعی دارند. در روش
در علوم رایانه کاربرد وسیعی دارند. در روش حریصانه رسیدن به هدف در هر گام مستقل از گام قبلی و بعدی است؛ یعنی در هر مرحله برای رسیدن به هدف نهایی، مستقل از این که در مراحل قبلی چه انتخاب‌هایی صورت گرفته و انتخاب فعلی ممکن است چه انتخاب‌هایی در پی داشته باشد، انتخابی صورت می‌پذیرد که در ظاهر بهترین انتخاب ممکن است. به همین دلیل است که به این روش، روش حریصانه گفته می‌شود. به‌طور مثال، زمانی که یک دزد عجول و حریص وارد خانه‌ای می‌شود، در مسیر حرکت خود هر وسیله و کالای با ارزشی را داخل کیسه می‌اندازد. وی در این
کالای با ارزشی را داخل کیسه می‌اندازد. وی در این حالت چندان توجهی نمی‌کند که چه اشیایی را قبلاً برداشته و ممکن است در آینده چه اشیاء گران‌بهاتری به دست آورد. او در هر گام تنها از بین اشیای دم‌دست خود باارزش‌ترین آن را انتخاب کرده و به وسایل قبلی اضافه می‌کند. این روش کاربردهای عمومی نیز دارد. به‌طور مثال زمانی که در مقابل خرید از یک فروشگاه یک اسکناس تحویل فروشنده داده می‌شود، وی با یک حساب سرانگشتی سعی می‌کند با حداقل اسکناس‌ها و سکه‌های ممکن باقیماندهٔ پول را تولید کرده و به خریدار تحویل دهد. این حساب
پول را تولید کرده و به خریدار تحویل دهد. این حساب سرانگشتی ممکن است روش حریصانه باشد. در بسیاری از موارد مسئله به‌طور مستقیم یا غیرمستقیم از ما می‌خواهند که یک متغیر را کمینه یا بیشینه کنیم. در اکثر مسائل این‌چنینی ما باید تعدادی انتخاب انجام دهیم و مسئله در تعدادی مرحله حل شود. بازهٔ وسیعی از این مسائل توسط الگوریتم‌های حریصانه قابل حل هستند. تاریخچه. نام این روش از شخصیت معروف اسکروج در داستان سرود کریسمس گرفته شده‌است. یکی از تفریحات و انگیزه‌های اسکروج، به دست آوردن پول بیشتر بود؛ الگوریتم حریصانه
به دست آوردن پول بیشتر بود؛ الگوریتم حریصانه (Greedy) نیز مانند شیوه اسکروج می‌باشد؛ مثلاً فرض کنید اسکروج در یک مسابقه شرکت کرده‌است و باید در مرحلهٔ اول مسابقه یک در را انتخاب کند، به ازای انتخاب هر در فقط می‌تواند درهای بعد آن را باز کند و پول دریافت کند: در مرحله اول باید بین دو در، اولی پنج سکه و دومی دو سکه، انتخاب کند؛ چون او حریص است بهترین انتخاب را در لحظه انتخاب در اول می‌داند. در مرحله دوم در بعد از در اول دارای سه سکه است و او با هشت سکه خارج می‌شود؛ حال در بعد از در دوم را بررسی می‌کنیم؛ ممکن
حال در بعد از در دوم را بررسی می‌کنیم؛ ممکن است دارای یک سکه باشد که در این صورت انتخاب حریصانه اسکروج بهینه بوده‌است یا ممکن است ده سکه باشد که در این صورت نشان می‌دهد که انتخاب بهینه در هر مرحله لزوماً منجر به سود بیشینه نمی‌شود. ساختار روش حریصانه. کلیت روش حریصانه در هر مرحله، انتخاب یک عنصر از عناصر موجود است. کار با یک مجموعه تهی شروع شده و این عنصر قسمتی از جواب مسئله است که به ترتیبی خاص به مجموعه عناصر نهایی اضافه می‌شود. به دلیل این که هر الگوریتم حریصانه الزاماً حل بهینه را نمی‌دهد، برای هر
حریصانه الزاماً حل بهینه را نمی‌دهد، برای هر مسئلهٔ خاص باید اثبات کنیم که آیا الگوریتم حریصانه برای آن، جواب بهینه می‌دهد یا خیر و این موضوع اغلب سخت‌ترین مرحله کار است. در طی این مسیر گام‌های زیر اتفاق می‌افتد: به زبان ساده، در روش حریصانه طی هر مرحله یک عنصر به روش حریصانه به مجموعه جواب اضافه شده، شرط محدودیت‌ها بررسی شده و در صورت نبود مشکل، عنصر و عناصر بعدی به همین ترتیب به مجموعه جواب اضافه می‌شوند. در طی این گام‌ها اگر به یک شرط نهایی خاص برسیم، یا امکان انتخاب عنصر دیگری برای اضافه کردن به مجموعه
امکان انتخاب عنصر دیگری برای اضافه کردن به مجموعه جواب وجود نداشته باشد، الگوریتم پایان می‌یابد و مجموعه جواب به‌دست‌آمده به‌عنوان جواب بهینه ارائه می‌شود. توجه داشته باشید که ممکن است بر اساس نوع مسئله، ترتیب اضافه شدن عناصر به مجموعه جواب اهمیت داشته باشد. set_greedy(C){ S = ∅; while(!solution(s) &amp;&amp; C != ∅){ X = select(C); C = C - {x}; if (feasible(S,{x})){ S = S + {x}; if(solution(S)){ return S; else return ∅; روش اثبات درستی. هرچند روش یکتایی برای اثبات درستی الگوریتم حریصانه وجود ندارد ولی روش
اثبات درستی الگوریتم حریصانه وجود ندارد ولی روش زیر در خیلی از مواقع الگوریتم را اثبات می‌کند. روش اثبات به این صورت است که دنبالهٔ تصمیمات اتخاذ شده در هر مرحله را در نظر گرفته، دنباله‌ای بهینه پیدا می‌کنیم که با دنبالهٔ ساخته شده یکسان باشد (منظور از دنبالهٔ بهینه، دنباله‌ای از کارها می‌باشد که جواب بهینه را به ما می‌دهد). برای پیدا کردن دنباله، ابتدا یک دنباله بهینه را درنظر می‌گیریم و در هر مرحله یک دنباله شبیه‌تر به دنباله خودمان پیدا می‌کنیم که بهینه باشد و سرانجام دنباله‌ای که پیدا کردیم با دنبالهٔ
باشد و سرانجام دنباله‌ای که پیدا کردیم با دنبالهٔ ما یکسان می‌شود. میزان شباهت دنباله formula_1 و formula_2 را بزرگ‌ترین اندیسی مثل formula_3 در نظر می‌گیریم که formula_4 درواقع شباهت دو دنباله، بزرگ‌ترین عددی مثل formula_3 است که formula_3 عضو اول ابتدای هر دو دنباله با هم یکسان باشد. محدودیت‌های الگوریتم حریصانه. چون روش این الگوریتم گرفتن بهترین تصمیم در هر مرحله است، در بسیاری از موارد به راه‌حل بهینه سراسری ختم نمی‌شود. عمده مسائلی که این الگوریتم به جواب درست منتهی نمی‌شود، مسائل مربوط به گراف‌های
جواب درست منتهی نمی‌شود، مسائل مربوط به گراف‌های وزن‌دار است؛ مثل مسئله فروشنده دوره‌گرد یا پیدا کردن بزرگ‌ترین مسیر در گراف وزن‌دار. کاربردها. مسئلهٔ کوله‌پشتی. ما n شی و یک کوله‌پشتی داریم که هر شیء دارای وزنی است؛ ظرفیت کوله‌پشتی نیز محدود است. ما می‌خواهیم ارزش شی‌ءهای قرار داده شده در کوله‌پشتی بیشینه شود: ما به دنبال formula_7 Max هستیم، طوری که formula_8 کمتر از W (بیشترین وزنی که در کوله‌پشتی قرار می‌گیرد. حال با توجه به روش حریصانه، راه حل‌های زیر موجودند: جواب‌های حاصل از مورد ۱ و ۲ لزوماً بهینه
موجودند: جواب‌های حاصل از مورد ۱ و ۲ لزوماً بهینه نیستند اما جواب حاصل از روش سوم بهینه است. حل یک مسئله با روش اول. "مسئله": خریداری از یک فروشگاه یک جنس ۶۴ تومانی می‌خرد و ۱۰۰ تومان به فروشنده می‌دهد و فروشنده باید ۳۶ تومان به او بازگرداند. اگر فروشنده سکه‌های ۵۰ ,۲۵ ,۱۰ ,۵ ,۱ تومانی (از هر کدام حداقل یک نمونه) داشته باشد، چگونه می‌توان بقیه پول خریدار را برگرداند به نحوی که تعداد سکه‌ها (در کل) کمترین مقدار ممکن باشد؟ "پاسخ:" فرض کنید می‌خواهیم n تومان را با سکه‌های ۲۵ تومانی، ۱۰ تومانی، ۵ تومانی و ۱
را با سکه‌های ۲۵ تومانی، ۱۰ تومانی، ۵ تومانی و ۱ تومانی پرداخت کنیم؛ به‌طوری که کمترین تعداد سکه را بپردازیم. ما می‌توانیم یک الگوریتم حریصانه برای حل این مسئله ارائه دهیم که تعداد سکه بهینه را در هر مرحله به دست آورد. برای این کار ما در هر مرحله بزرگ‌ترین سکه‌ای را که از پول باقی‌مانده تجاوز نکند انتخاب می‌کنیم در این صورت تعداد سکه‌ها بهینه خواهد بود. در ابتدا هیچ سکه‌ای در مجموعه جواب نداریم. از بین سکه‌های موجود بزرگ‌ترین ممکن یعنی ۲۵ تومانی را انتخاب می‌کنیم. این مرحله از الگوریتم حریصانه را روال
می‌کنیم. این مرحله از الگوریتم حریصانه را روال انتخاب (select procedure) گویند. اگر یک سکه ۲۵ تومانی دیگر را انتخاب کنیم حاصل از ۳۶ تومان بیشتر شده، لذا آن را کنار گذاشته به سراغ سکهٔ ۱۰ تومانی می‌رویم. حال بررسی می‌کنیم اگر این سکهٔ ۱۰ تومانی را به مجموعهٔ انتخابی قبلی اضافه کنیم، حاصل از ۳۶ تومان بیشتر می‌شود یا خیر. این مرحله را تحقیق عملی بودن (feasibility check) می‌نامند. حال اگر این ۱۰ تومان را به ۲۵ تومان اضافه کنیم، جمع مجموعهٔ انتخاب‌شده ۳۵ می‌شود که هنوز به ۳۶ نرسیده‌است. این مرحله را تحقیق حل
که هنوز به ۳۶ نرسیده‌است. این مرحله را تحقیق حل شدن (Solution check) می‌گوییم. در ادامه سکه‌های دیگر را به ترتیب مقایسه می‌کنیم و در نهایت با انتخاب سکه یک تومانی در کل با ۳ سکه (۲۵ تومانی و ۱۰ تومانی و یک تومانی) ۳۶ تومان به دست می‌آید و این حداقل تعداد سکه ممکن است. توجه کنید در انتخاب فوق، ملاک انتخاب، برای انتخاب بهترین سکه در هر مرحله (بهینهٔ محلی) سکه است و در انتخاب سکه در هر مرحله به انتخاب‌های قبلی و بعدی کاری نداریم. در این شیوه اجازهٔ فکر کردن دربارهٔ یک انتخاب انجام شده را نداریم؛ یعنی هنگامی
یک انتخاب انجام شده را نداریم؛ یعنی هنگامی که سکه‌ای پذیرفته شد به‌طور دائم جزو حل به حساب می‌آید و هنگامی هم که سکه‌ای رد می‌شود به‌طور دائم از حل کنار گذاشته می‌شود. کد مربوط به روش اول: procedure change ({c_1}, {c_2}, {...}, {c_r}: value of denominations of coin, where {c_1}&gt; {c_2}&gt; {...}&gt; {c_r}; n : a positive integer) { for i := 1 to r { while n&gt;= {c_i} { // add a coin with value {c_i} to change همان‌طور که مشاهده کردید این روش بسیار ساده است، ولی اصلی‌ترین نکته این است که آیا این روش
است، ولی اصلی‌ترین نکته این است که آیا این روش الزاماً به یک حل بهینه می‌رسد؟ در رابطه با مسئلهٔ خاص فوق می‌توان اثبات کرد که جواب بهینه است ولی با مثال زیر نشان می‌دهیم که ممکن است این گونه نباشد. فرض کنید قرار است به فردی ۱۶ تومان پس بدهیم. سکه‌های موجود ۵۰ ,۲۵ ,۱۰ ,۵ ,۱ تومانی است (با این که ما در ایران سکهٔ ۱۲ تومانی نداریم ولی این فرض را بکنید که داریم). با الگوریتم حریصانهٔ فوق به این نتیجه می‌رسیم که باید به این فرد یک سکه ۱۲ تومانی و ۴ سکه ۱ تومانی بدهیم؛ یعنی جمعاً ۵ سکه. در حالی که حل بهینهٔ
بدهیم؛ یعنی جمعاً ۵ سکه. در حالی که حل بهینهٔ مسئلهٔ فوق یک سکهٔ ۱۰ تومانی، یک سکهٔ ۵ تومانی و یک سکهٔ یک تومانی است؛ یعنی در کل ۳ سکه. حل یک مسئله با روش سوم. "مسئله (کوله‌پشتی صفر و یک)": مثالی از این مسئله مربوط به دزدی می‌شود که با کوله‌پشتی وارد یک جواهر فروشی می‌شود. اگر وزن قطعات از یک حد بیشینه W فراتر رود، کوله‌پشتی پاره خواهد شد. هر قطعه دارای ارزش و وزن معینی خواهد بود. مسئله‌ای که دزد با آن مواجه است، تعیین حداکثر ارزش قطعات است در حالی که وزن کل آن‌ها از حد معین W فراتر نرود. این مسئله را
کل آن‌ها از حد معین W فراتر نرود. این مسئله را کوله‌پشتی صفر و یک می‌گویند. "پاسخ:" فرض کنید n قطعه وجود داشته باشد، به طوری که: [s = [item1, item2, item3, ..., itemn وزن Wi = item1 ارزش Pi = itemi W = حداکثر وزنی که کوله پشتی قادر به تحمل آن است. و wi ,pi ,w همگی اعداد صحیح هستند. راه حل جستجوی جامع این است که همهٔ زیرمجموعه‌های این n قطعه را در نظر بگیریم، زیرمجموعه‌هایی را که وزن کل آن‌ها از w فراتر نرود، کنار می‌گذاریم و از میان آن‌هایی که باقی می‌ماند، آن را که بیشترین ارزش را دارد، انتخاب می‌کنیم.
آن را که بیشترین ارزش را دارد، انتخاب می‌کنیم. void greedy_knap_sack(w, n){ sort(p, w); for(i = 0; i &lt;n; i++){ x[i] = 0; u = w for(i = 0; i &lt;n; i++){ if(w[i]&gt; u) break; x[i] = 1; u = u - w[i]; if (i &lt;n) { x[i] = u / w[i]; مسئلهٔ رنگ‌آمیزی رأس‌های گراف:. با تعداد m رنگ داده شده، رأسهای گراف باید به گونه‌ای رنگ شوند که هیچ دو رأس مجاوری دارای رنگ مشابه نباشند. هدف رنگ کردن رأس‌ها به شیوه‌ای است که هیچ دو رأس مجاوری دارای رنگ مشابه نباشند. هیچ الگوریتم کارآمدی برای رنگ‌آمیزی گراف با حداقل رنگ‌های
کارآمدی برای رنگ‌آمیزی گراف با حداقل رنگ‌های ممکن وجود ندارد و این مسئله از جمله مسائل «ان‌پی کامل» (NP Complete) محسوب می‌شود. «الگوریتم‌های تقریبی» (Approximate Algorithms) گوناگونی برای حل این مسئله وجود دارند، که رنگ‌آمیزی حریصانه از جمله آنهاست. رنگ‌آمیزی حریصانه به این صورت است که رأس اول را با رنگ اول رنگ می‌کنیم و همه رأس‌های بعدی را با اولین رنگی که در رأس‌های مجاور آن وجود نداشت رنگ می‌کنیم. اگر چنین رنگی وجود نداشت، رنگ جدیدی اضافه می‌کنیم. void greedyColoring(std::vector&lt;V&gt;) int
void greedyColoring(std::vector&lt;V&gt;) int result[V.size()]; result[0] = 0; for (int u = 1; u &lt;V.size(); u++) result[u] = -1; bool available[V.size()]; for (int cr = 0; cr &lt;V.size(); cr++) available[cr] = false; for (int u = 1; u &lt;V.size(); u++) list&lt;int&gt;::iterator i; for (i = adj[u].begin(); i != adj[u].end(); ++i) if (result[*i] != -1) available[result[*i]] = true; int cr; for (cr = 0; cr &lt;V.size(); cr++) if (available[cr] == false) break; result[u] = cr; for (i = adj[u].begin(); i
break; result[u] = cr; for (i = adj[u].begin(); i != adj[u].end(); ++i) if (result[*i] != -1) available[result[*i]] = false; مسئلهٔ برنامه‌ریزی چندین فعالیت همزمان:. مسئلهٔ برنامه‌ریزی چندین فعالیت که همزمان انجام می‌پذیرند نیاز به استفادهٔ همزمان از یک منبع مشترک با هدف انتخاب مجموعه‌ای با ماکزیمم اندازه از فعالیت‌هایی که با هم ندارند، دارند. فرض کنید یک مجموعهٔ {s = {a1, a2, …, an از n فعالیت پیشنهادی داریم که می‌خواهند از یک منبع استفاده نمایند، مانند یک تالار سخنرانی که در یک زمان می‌تواند تنها مورد
یک تالار سخنرانی که در یک زمان می‌تواند تنها مورد استفادهٔ یک فعالیت قرار گیرد. هر فعالیت ai دارای زمان شروع si و زمان خاتمهٔ fi است به‌طوری‌که ۰ ≤ fi&gt; si &lt;∞. اگر فعالیت ai انتخاب شود، می‌تواند در طول بازهٔ (si, fi] رخ دهد. تعریف: دو فعالیتی را سازگار می‌گوییم که با یکدیگر هم‌پوشانی نداشته باشند. مسئله انتخاب فعالیت عبارت است از انتخاب یک زیرمجموعه با ماکزیمم اندازه از فعالیت‌هایی که هم‌پوشانی ندارند. برای مثال زیرمجموعهٔ s از فعالیت‌ها را در نظر بگیرید که آن‌ها را برحسب زمان پایان به ترتیب صعودی
که آن‌ها را برحسب زمان پایان به ترتیب صعودی یکنواخت مرتب کرده‌ایم: i -&gt; 1 2 3 4 5 6 7 8 9 10 11 si -&gt; 1 3 0 5 3 5 6 8 8 2 12 fi -&gt; 4 5 6 7 8 9 10 11 12 13 14 برای این مثال زیرمجموعهٔ {a3, a9, a11} شامل فعالیت‌هایی است که هم‌پوشانی ندارند. اگرچه این زیرمجموعه بیشینه نیست، چون زیرمجموعهٔ {a1, a4, a9, a11} بزرگ‌تر از آن است. در حقیقت {a1, a4, a9, a11} بزرگ‌ترین زیرمجموعه از فعالیت‌های متقابلاً سازگار است. حال یک الگوریتم حریصانه بازگشتی برای حل مسئلهٔ زمان‌بندی فعالیت‌ها ارائه خواهیم نمود. با تعریف
زمان‌بندی فعالیت‌ها ارائه خواهیم نمود. با تعریف مجموعهٔ {sij = {ak € s: fi ≤ sk &lt;fk ≤ sj شروع می‌کنیم، به‌طوری‌که sij زیرمجموعه‌ای از فعالیت‌ها در S است که می‌توانند بعد از خاتمه فعالیت ai شروع شده و قبل از شروع فعالیت aj خاتمه یابند. در حقیقت sij شامل همه فعالیت‌هایی است که با ai و aj و همچنین با همه فعالیت‌هایی که بعد از خاتمه ai خاتمه نیافته و همه فعالیت‌هایی که قبل از شروع aj شروع نمی‌شوند، سازگارند. به منظور بیان کل مسئله، فعالیت‌های ساختگی a0 و an+1 را اضافه کرده و توافق می‌کنیم که f0 = ۰ و ∞ =
را اضافه کرده و توافق می‌کنیم که f0 = ۰ و ∞ = sn+1 پس s = s0, n+1 و محدودهٔ تغییر i و j به صورت زیر خواهد بود: 0 ≤ i, j ≤ n+1 دامنهٔ تغییر i و j را به صورت زیر می‌توانیم بیشتر محدود کنیم. فرض می‌کنیم که فعالیت‌ها در یک ترتیب یکنواخت صعودی از زمان‌های خاتمه مرتب شده‌اند: f0 ≤ f1 ≤ f2 ≤ … ≤ fn ≤ fn+1 ادعا می‌کنیم که sij = ᴓ هر گاه i ≥ j باشد. فرض کنید یک فعالیت ak € sij برای i ≥ j وجود دارد به‌طوری‌که ai بعد از aj در ترتیب مرتب قرار دارد. پس خواهیم داشت fi ≤ sk &lt;fk ≤ sj &lt;fj. بنابراین fi &lt;fj که با
≤ sk &lt;fk ≤ sj &lt;fj. بنابراین fi &lt;fj که با این فرض که ai بعد از aj در ترتیب مرتب قرار دارد در تناقض است. می‌توانیم نتیجه بگیریم با این فرض که فعالیت‌ها را در یک ترتیب صعودی یکنواخت از زمان‌های خاتمه مرتب کرده‌ایم، فضای زیر مسائل انتخاب زیر مجموعه با ماکزیمم اندازه شامل فعالیت‌های متقابلاً سازگاراز sij است، که با آگاهی از این مطلب که تمام sijهای دیگر تهی هستند رابطه زیر برقرار است: 0 ≤ i, j ≤ n+1 برای مشاهدهٔ زیرساختار مسئلهٔ انتخاب فعالیت، تعدادی زیرمسئله غیر تهی sij را در نظر بگیرید؛ و فرض کنید که
غیر تهی sij را در نظر بگیرید؛ و فرض کنید که یک جواب برای sij شامل تعدادی فعالیت ak است. به‌طوری‌که fi ≤ sk &lt;fk ≤ sj. استفاده از فعالیت ak سبب ایجاد دو زیرمسئله می‌شود، sik (فعالیت‌هایی که پس از خاتمهٔ فعالیت ai شروع شده و قبل از شروع فعالیت ak خاتمه می‌یابند) و skj (فعالیت‌هایی که پس از خاتمهٔ ak شروع شده و قبل از شروع فعالیت aj خاتمه می‌یابند)، که هر کدام از یک زیرمجموعه شامل فعالیت‌های داخل sij تشکیل شده‌اند. جواب sij اجتماع جواب‌های مربوط به sik و skj است، همراه با فعالیت ak. بنابراین تعداد فعالیت‌ها
است، همراه با فعالیت ak. بنابراین تعداد فعالیت‌ها در جواب sij برابر اندازه جواب skj به علاوه یک (برای ak) می‌باشد. اکنون فرض کنید جواب Aij برای sij شامل فعالیت ak می‌باشد. پس جواب‌های Aik برای sik و Akj برای skj که در این جواب بهینه برای sij استفاده می‌شوند نیز باید بهینه باشند. بحث برش – و – الصاق معمول در این مورد بکار می‌رود. اگر یک جواب Áik برای sik می‌داشتیم که شامل فعالیت‌های بیشتری از Aik می‌بود، می‌توانستیم Aik را از داخل Aij برش داده و به داخل Áik الصاق نماییم، بنابراین یک جواب دیگر برای sij با