2-2-9-درس: طراحي الگوريتم
1401/09/21 14:13فصل قبل
سرفصل: جستجوي اکتشافي
مطلب درسي: الگوريتم‌هاي حريصانه
الگوريتم‌هاي حريصانه:
جستجوي حريصانه يکي از روش‌هاي جستجوي «اول-بهترين» [1]است در اين روش هدف به حداقل رساندن هزينه براي رسيدن به مقصد است.[2] براي رسيدن به هدف از يک نقطه، شروع به حرکت نموده و گزينه‌هاي بعدي بصورتي انتخاب ميشود که نسبت به ساير حالتها در اين مرحله مناسبتر به نظر مي‌رسد (اصطلاحاً «بهينه محلي»[3] است). اين بدان معناست که در روش حريصانه، صرفاً بر مبناي دانش فعلي خود از بهينگي نسبي و فعلي راه‌حل نسبت به ساير راه‌حل‌ها، به گزينش دست مي‌زنيم.
روش انتخاب راه‌حل بهينه محلي که در الگوريتم‌هاي حريصانه به کار مي‌رود، در بسياري از امور زندگي نيز کاربرد دارد. ما انسان‌هاي عادي از جانب خداوند مأمور به انجام تکاليف متعدد هستيم به گونه اي که گاهي در يک زمان چند تکليف متوجه انسان مي شود. و چه بسا اگر هر کدام از اين تکاليف را انتخاب کند و انجام دهد باز با چند تکليف جديد مواجه مي شود که قابل جمع نيست و ناچار بايد يکي را انتخاب کند. اين در حالي است که انسان هر کدام از اين تکاليف را انجام دهد از آينده و نتيجه آن بي خبر است. در اينجا بايد بدون آنکه صرفاً به نتيجه نگاه کند تکليف خود را بر اساس معيارهاي عقلي و شرعي[4] انتخاب کند و انجام دهد.
در چنين شرايطي اگر به تشخيص و تکليف خود عمل کند، معذور و بلکه مأجور است. هرچند ممکن است در نهايت معلوم گردد که تشخيص و انتخاب وي بهينه نبوده و يا حتي اشتباه بوده است. البته در اين رابطه نيز مانند ساير موارد بايد از افراط پرهيز نمود. بدين معني که چنانچه در همه امور زندگي فقط به جلوي پايمان توجه کنيم و از دورانديشي غافل شويم، مي‌توانيم خود و اطرافيانمان را به ورطه‌هاي خطا و خسارت سنگين بيندازيم. در طراحي الگوريتم نيز معمولا روش هاي حريصانه در نقاط بهينه محلي دچار مشکل شده و معمولا نسبت به روش هاي اکتشافي و آگاهانه ضعيفتر عمل مي‌کنند.
سرفصل: کارايي و تحليل الگوريتم
مطلب درسي1: الگوريتم
مفهوم Module يا پيمانه يکي از مفاهيم کليدي در دنياي نرم‌افزارها مي‌باشد. پيمانه‌اي يا Modular کردن به معني تقسيم کل سامانه به واحدهاي کوچکتر نسبتاً مستقل است، به نحوي که در عين حال با يکديگر ارتباط دارند و همگي در جهت هدف کل سامانه حرکت مي‌کنند.
امروزه معمولاً هر برنامه کامپيوتري از پيمانه‌ها تشکيل ميشود که وظايف مشخص را انجام مي‌دهند. کل الگوريتم متشکل از پيمانه‌هايي است که مانند قطعات يک جورچين با يکديگر مرتبط هستند و هرکدام امور مشخصي را پوشش مي‌دهند. مانند برنامه يک ربات انسان نماي فوتباليست که از پيمانه‌هاي مختلفي از قبيل: راه رفتن، پيدا نمودن توپ، شوت کردن و ... تشکيل شده است؛ و در صورت نقص در هر کدام از پيمانه‌ها (مثلاً اشکال در پيمانه شوت کردن) به هدف اصلي نمي‌رسيم.
البته مفهوم پيمانه‌ها فقط مختص حوزه رايانه و نرم‌افزارها نيست، بلکه تقريباً در هر حوزه علم، فناوري، صنعت، سازمان‌ها و ... که دقت کنيم، مي‌توانيم ردپاي اين مفهوم و کاربردهاي آن را بيابيم. به همين صورت مي‌توان چنين قالبي را در امور انساني و معنوي هم مشاهده نمود.
در زندگي انسان نيز سه برنامه (بخش) براي رشد و رسيدن انسان به هدف اصلي و جايگاه تعيين شده براي او وجود دارد که عبارتند از اعتقادات، اخلاق و احکام؛ و به مجموع اين سه برنامه «دين» گفته ميشود. هر يک از اين سه برنامه (بخش) از دستورالعمل ها و گزاره‌هاي متعدد و متفاوتي تشکيل شده است و بالطبع ضعف در هر يک از آنها منجر به عدم نيل به نتيجه نهايي (که همان سعادت ابدي انسان است) ميشود.
مطلب درسي2: ويژگيهاي الگوريتم
الگوريتم‌ها داراي ويژگيهاي مختلفي از جمله موارد زير است:[5]
ورودي‌هاي مشخص
خروجي‌هاي مشخص
محدوديت‌هاي مختلف در منابع
قطعيت
کارايي
اين ويژگي ها مختص به الگوريتم هاي رايانه اي نيست، بلکه برنامه ريزي براي تحقق هر هدف مهمي در گرو پيروي از يک الگوريتم صحيح است، از جمله تربيت فرزند که طبيعتاً والدين عاقل و فهميده براي حل صحيح آن به دنبال الگوريتمي مناسب خواهند بود. براي نيل به موفقيت، اين الگوريتم نيز بايد داراي ويژگيهاي فوق باشد.
از اين رو در تربيت فرزند بايد اين ويژگي‌ها را ملاحظه کرد که عبارتند از:
توجه به آموزش‌هاي مورد نياز، که براي زندگي او مفيد و عملياتي باشد (ورودي‌ها).
عملکرد او بايستي متناسب با آموزه‌ّهاي تربيتي دريافتي باشد (خروجي‌ها).
توجه به اينکه در تربيت او زمان محدودي در اختيار ماست (محدوديت منابع).
رعايت اين نکته که آموزه‌هاي تربيتي ما بايد ثبات داشته و کامل باشد (قطعيت).
دقت کنيم آموزش‌ها و تربيت ارائه شده کيفيت و سزاواري لازم را داشته باشد (کارايي).
سرفصل: روش تقسيم و حل
مطلب درسي: آشنايي با روش تقسيم و حل
اين روش مسئله اصلي را به دو يا چند مسئله کوچکتر تقسيم مي‌کند[6]. اگر حل نمونه‌هاي کوچکتر به راحتي به دست آيد، حل مسئله اصلي با ترکيب اين راه‌حل‌ها به دست خواهد آمد. اگر نمونه‌هاي کوچکتر باز هم بزرگتر از آن باشند که به راحتي قابل حل نباشند، مي‌توان آنها را به نمونه‌هاي کوچکتري تقسيم نمود. اين فرآيند تقسيم چندان ادامه پيدا مي‌يابد که حل آنها به راحتي امکان پذير گردد.
بنابراين حل مسائل بزرگتر گاهي در گرو حل مسائل کوچکتر و زير مجموعه هاست، همانطور که ايجاد جامعه جهاني اسلامي در گرو اسلامي شدن فرد و جامعه هاي زيرمجموعة آن است. يعني براي تحقق يک امت واحده اسلامي ابتدا بايد کشورهاي نمونه اسلامي داشته باشيم. داشتن کشورهاي اسلامي نيازمند دولت‌هاي اسلامي است. دولت‌هاي اسلامي برخاسته از جوامع اسلامي هستند و جامعه اسلامي از خانواده‌هاي اسلامي تشکيل مي‌گردد. بالطبع خانواده اسلامي نيز از افراد تابع تعاليم اسلام تشکيل ميشود. بنابراين اگر افراد جامعه، اسلامي شوند، خانواده اسلامي شده، سپس جامعه اسلامي، در ادامه دولت اسلامي، کشور اسلامي و در نهايت جامعه جهاني اسلامي خواهيم داشت.
خداوند در قرآن کريم مي‌فرمايد «...إِنَّ اللَّـهَ لَايُغَيّرُ مَا بِقَوْمٍ حَتَّى يغَيرُوا مَا بِأَنفُسِهِمْ... [7]» «خداوند سرنوشت هيچ قوم (و ملّتي) را تغيير نمي‌دهد مگر آنکه آنان آنچه را در خودشان است تغيير دهند». اين يعني آنکه به قول آيت الله العظمي بهجت e: «... ما خودمان حاضر نيستيم خودمان را اصلاح بکنيم. اگر خودمان را اصلاح بکنيم، به تدريج همه بشر، اصلاح مي شوند ... آيا کار ما بدون اصلاح نفس درست مي شود ؟ ... آيا تا اصلاح نکنيم خودمان را، مي توانيم جامعه را اصلاح بکنيم؟ ...»[8].
[1]. Best First
[2]. طراحي الگوريتم ها تحليل، طراحي و ارزيابي کارايي، ص 167.
[3]. Local Optimum
[4]. براي انتخاب يک تکليف از ميان تکاليف مختلف که همزمان بر عهده انسان گذاشته شده است معيار هايي وجود دارد از جمله : انتخاب تکليف مهم تر ( ترجيح اهم بر مهم )، انتخاب تکليفي که با هواي انسان مخالف است يا انتخاب تکليفي که سخت تر است.
[5]. طراحي الگوريتم ها تحليل ، طراحي و ارزيابي کارايي، ص13- 22.
[6]. طراحي الگوريتم ها تحليل، طراحي و ارزيابي کارايي، ص 13.
[7]. سوره مبارکه رعد آيه 11.
[8]. بيانات آيت الله العظمي بهجت e تحت عنوان: «علاج ما، اصلاح نفس است».