الگوریتم امروز

وبلاگ تخصصی الگوریتم

الگوریتم امروز

وبلاگ تخصصی الگوریتم

وبلاگ علمی و مخصوص مباحث الگوریتمی است.
نظر خصوصی نگذارید چون جواب نمی‌دهم نظر عمومی بگذارید بدون نام هم که باشد همانجا جواب می‌دهم.

بایگانی

استراتژی‌های حل مسأله

جمعه, ۱۲ ارديبهشت ۱۳۹۳، ۱۱:۳۷ ق.ظ

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

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

ناوردایی: مسأله مشخصاتی داره که با یک عمل ثابت می‌مونه. برای حل مسأله دو جور میشه از این استفاده کرد یکی اینکه بگیم ویژگی توی حالت‌های مجاز مسأله هست که توی حالت جواب نیست پس هیچ وقت به جواب نمی‌رسه. حالت دیگه اینه که بگیم مثلاً رشد تابع هدف مسأله ثابته. اگر مسأله هدفش یک تابع صعودی /نزولی باشه یعنی هر بار مقدارش زیاد/کم بشه. مثلاً تابع هدف میتونه تعداد حالت‌های مسأله باشه که محدوده یا هزینه‌ی مسأله باشه که کرانداره چون همه‌اش داره کم/زیاد میشه حداکثر به اندازه‌ی تعداد حالت‌ها (کران) تقسیم بر تغییری که هر بار میکنه تکرار برای رسیدن به جواب لازمه.

http://en.wikipedia.org/wiki/Invariant_(mathematics)

نظریه بازی‌ها: حالت‌های مسأله به دو دسته‌ی برد و باخت تقسیم می‌شوند که با یک گراف میشه نشون داد که با هر حرکت مثلاً از مجموعه برد به باخت میریم یا توی برد می‌مونیم. شبیه اتوماتاست بیشتر به نظرم (از این نظر که روی گرافش داریم می‌نویسیم که چه کاری باید انجام بشه).

رنگ‌آمیزی: من قبلاً با این مسأله حل کردم توی همین وبلاگ ولی اشاره به اسمش نکردم. یک سری ویژگی توی مسأله هستند که هر کدام را با یک رنگ مشخص می‌کنیم و بعد وقتی مسأله را حل می‌کنیم می‌توانیم با نگه داشتن هزینه‌ی هر کدام از رنگ‌ها (ویژگی‌ها) بدانیم اوضاع چطوریه! :) این را با اسم پارامتر ثابت می‌شناسند که هر کدام از رنگ‌ها یک پارامتر اند و تعداد اشیای هر رنگ مقدار آن پارامتر است.

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

موافقین ۱ مخالفین ۰ ۹۳/۰۲/۱۲
سپیده آقاملائی

نظرات  (۰)

هیچ نظری هنوز ثبت نشده است

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی