تبلیغات
آموزش برنامه نویسی سی ++،سی شارپ،جاوا اسکریپت - الگوریتم Forward Checking
آموزش برنامه نویسی سی ++،سی شارپ،جاوا اسکریپت

مرتبه
تاریخ : جمعه 7 خرداد 1395

برنامه :الگوریتم حرکت پیشرو یا Forward Checking
نکته: الگوریتم تقریبا در سطح بالا نوشته شده و برای استفاده باید یکم باهاش ور برید :-)
ه
این الگوریتم یکی از روش های حل مسائل ارضای محدودیت به شمار می رود،( بنوعی شبیه الگوریتم های عقبگر هست ) بطور مثال برای حل مسئله هایی چون
بازی مسئله هشت وزیر و رنگ آمیزی گراف استفاده میشه


یا برای حل انواع بازی های معمایی چون معمای کلمات، بازی سودوکو، جدول کلمات و ...

فرض کنید یک کلاس تعریف کردیم بصورت زیر
calss cell
{
int Value
List<T> Domain
};
class game
{
cell[][] board;

bool IsSolved(){ if Game is Finished return true else return false}

FindNextCell(){Retrun  A Cell( By Random or ...) }

UpdateDomain(Value,String Mode)
{
if Mode==Remove
Remove Value From All Cell That Are Connected To This Cell
if Mode==Restore
AddValue To All Cell That Are Connected To This Cell
}
};

با این فرضیات الگوریتم به این شرحه:
اگه بازی تمام شده و جواب پیدا شده مقدار درست رو برگردون
(در غیر اینصورت)
خانه ی بعدی رو انتخاب کن
اگه خانه دردسترسه
اگه خانه مقداری در دامنه داره که بشه استفاده کرد
به ازای همه ی عناصر موجود در دامنش
یک مقدار بردار
دامنه ی بقیه رو بروزرسانی کن(این انتخاب رو ازشون حذف کن)
وارد فراخوانی بعدی شو و به جواب رسیدی درست رو برگردون
(حالا که به این وضعیت برگشتی) انتخاب فعلی رو به دامنه ها برگردون

چنانچه جواب پیدا نشد شکست را برگردان


public bool ForwardChecking(Game g)
{
            if (g.Solved() == true)              return true;

            Cell NextCell = g.FindNextCell();

            if (NextCell != null)
            {
                if (NextCell.DomainIsEmpty() == false)
                {
                    int NewValue;
                    for (int i = 0; i < NextCell.Domain.Count; i++)
                    {
                            NewValue = NextCell.value;

                            g.UpdateDomains(NewValue,  "Remove");

                            if ( ForwardChecking( g ) == true )     return true;

                            g.UpdateDomains(NewValue,  "Restore");
                    }
                }
            }
            return false;
}

کد الگوریتم رو به اکثر زبون ها می تونید استفاده کنید فقط باید کلاس game ,... رو پیاده سازی کنید

سوالی اگه داشتید در خدمتم.



می تونید با ارسال شارژ از من حمایت کنید 09392888216
برچسب ها: پروژه، سی شارپ، سی++، سی پلاس پلاس، سی، forward checking، الگوریتم forward checking،
آرشیو مطالب
صفحات جانبی
پیوند های روزانه
امکانات جانبی
blogskin

قالب وبلاگ