مسئله ای که با آن روبرو هستید، از یک گراف بدون جهت تشکیل شده است. این گراف، دارای گره هایی است که هر گره در هر لحظه، میتواند یکی از سه رنگ سبز، قرمز یا مشکی را اختیار نماید. در ابتدا، گراف شامل گره هایی با رنگ هایی از بین سه رنگ فوق است. در هر مرحله، می توان یکی از گره ها را انتخاب کرد، و هدف نهایی مسئله این است که همه گره های گراف به رنگ سبز در بیایند. در ادامه، رفتار گره ها پس از انتخاب شدنشان، با توجه به رنگ گره توضیح داده شده است
گره سبز/قرمز:
با انتخاب یک گره به رنگ سبز یا قرمز، گره انتخاب شده و هر یک از گره های همسایه آن گره:
اگر سبز باشد به رنگ قرمز تغییر رنگ میدهد.
اگر قرمز باشد به رنگ سبز تغییر رنگ میدهد.
اگر هریک از گره های همسایه گره انتخاب شده، به رنگ مشکی باشد، آن گره همسایه، بدون تغییر باقی میماند.
گره مشکی: برای رسیدن به هدف مسئله، الزم است که گره های مشکی به نحوی به یکی از رنگ های سبز یا قرمز تبدیل شوند، تا پس از آن قابلیت تغییر رنگ به شکل عادی را پیدا کنند. با انتخاب یک گره به رنگ مشکی، مراحل زیر اتفاق می افتد:
1 .هریک از گره های همسایه این گره، اگر سبز باشد به رنگ قرمز، و اگر قرمز باشد به رنگ سبز تغییر میکند، و اگر مشکی باشد بدون تغییر باقی میماند.
2 .پس از تغییر رنگ همسایه ها، با توجه به اینکه رنگ اکثریت همسایه ها چه رنگی است، یکی از حالت زیر برای گره مشکی انتخاب شده اتفاق می افتد:
اگر اکثریت همسایه ها به رنگ قرمز باشند، گره مشکی به رنگ قرمز تغییر رنگ میدهد.
به طور مشابه، اگر اکثریت همسایه ها به رنگ سبز باشند، گره مشکی به رنگ سبز تغییر رنگ میدهد.
در غیر این صورت، گره مشکی انتخاب شده، بدون تغییر و مشکی باقی میماند.
تابع هیوریستیک
این مسئله با توجه به دشواری ای که دارد باید برای بدست آوردن تابع ارزیابی ،مسئله را relax کرد.بنابراین برای ساده سازی مسئله فرض های زیر درنظر گرفته میشوند
۱.برای ساده سازی نیازی به درنظر گرفتن جابجایی های بعد تغییر نیست بنابراین نباید نگران این شد که سبز ها با تغییر بقیه مهره هاتغییر کنند
۲.تابع هیوریستیک ما admissible است چرا که h(n) هیچوقت بیشتر از هزینه واقعی مسیر مستقیم به goal نمیشود.همانطور که در تابع هیوریبستیک ما مشخص است همیشه سعی شده بهترین h بازگردانده شود
۳. تابع هیوریستیک ما لزوما بر اساس تعداد قرمز و سیاه هزینه را اعلام نمیکند.
۴. تابع هیوریستیک بر اساس قرمز های گروه شده کار میکند.یعنی سعی میکند همه قرمز هایی که با هم مشترک هستند و در یک گروه قرار دارند و به عبارتی همه همسایه یک گره هستند را یکی در نظر میگیرد.
۵.همچنین خود گره انتخابی نیز بررسی میشود و درصورت نیاز با همسایه ها هم گروه میشود.
