در اين روش، با شروع از يك جواب تهي، تصميم‌ها مرحله به مرحله گرفته مي‌شود تا يك جواب كامل به دست آيد. هر تصميم، يك تصميم آزمند است؛ يعني قصد دارد با استفاده از اطلاعات به دست آمده از آنچه كه تا كنون انجام شده است، بهترين تصميم را بگيرد.

آنچه كه يك الگوريتم سازنده و يك الگوريتم آزمند را از هم متمايز مي‌كند، نحوه ساختن جواب‌ها مي‌باشد. يك الگوريتم سازنده، جواب را به هر طريق ممكن توليد مي‌كند، اما در يك الگوريتم آزمند، جواب مرحله به مرحله و با توجه به يافته‌ها، ساخته مي‌شود (در هر مرحله، بخشي از جواب ساخته مي‌شود). جستجوي سازنده در مسائلي مانند زمانبندي ماشين و بودجه‌بندي سرمايه كاربرد داشته است. در اينجا مثال مسيريابي كاميون مطرح مي‌شود. در اين مسأله كالا بايد به نقاط مشخصي (هر يك با ميزان مشخصي از تقاضا براي كالا) حمل شود؛ مسأله، سازماندهي اين نقاط در مسيرهاي مشخص با توجه به محدوديت ظرفيت كاميون است.

جستجوي بهبود يافته[2]

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

روش جستجوي همسايه[3]

استفاده از الگوريتم مبتني بر تكرار مستلزم وجود يك سازوکار توليد جواب است. سازوکار توليد جواب، براي هر جواب i يك همسايهبه وجود مي‌آورد كه مي‌توان از i به آن منتقل شد. الگوريتم‌هاي تكراري به عنوان جستجوي همسايه يا جستجوي محلي نيز شناخته مي‌شوند. الگوريتم بدين صورت بيان مي‌شود كه از يك نقطه (جواب) شروع مي‌شود و در هر تكرار، از نقطه جاري به يك نقطه همسايه جابه‌جايي صورت مي‌گيرد. اگر جواب همسايه مقدار كمتري داشته باشد، جايگزين جواب جاري مي‌شود (در مسأله حداقل‌سازي) و در غير اينصورت، نقطه همسايه ديگري انتخاب مي‌شود. هنگامي كه مقدار جواب از جواب تمام نقاط همسايه آن كمتر باشد، الگوريتم پايان مي‌يابد.

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

اشكالات الگوريتم فوق بدين شرح است:

1-   ممكن است الگوريتم در يك بهينه محلي متوقف شود، اما مشخص نباشد كه آيا جواب به دست آمده يك بهينه محلي است يا يك بهينه سراسري.

2-   بهينه محلي به دست آمده به جواب اوليه وابسته است و در مورد چگونگي انتخاب جواب اوليه هيچ راه حلي در دسترسي نيست.

3-   به طور معمول نمي‌توان يك حد بالا براي زمان اجرا تعيين كرد.

البته الگوريتم‌هاي مبتني بر تكرار مزايايي نيز دارند؛ از جمله اينكه يافتن جواب اوليه، تعيين مقدار تابع و سازوکار توليد جواب همسايه به طور معمول ساده است.

با وجود آنكه تعيين حد بالاي زمان اجرا امكان‌پذير نيست، ولي با اطمينان مي‌توان گفت كه يك تكرار از الگوريتم در زمان مشخص قابل اجراست.

 

[1] Constructive Search

[2] Improving Search

[3] Neighbourhood Search