معمای 8 شامل یک صفحه 3×3 با 8 مربع شماره دار است. همه شما با این معما آشنا هستید. نکته مهم این است که به جای اینکه بگوییم مربع شماره 4 را به داخل فضای خالی حرکت بده بهتر است بگوییم فضای خالی جایش را با مربع سمت چپش عوض کند.در این الگوریتم در ابتدا از کاربر حالت ورودی را دریافت می کنیم. حالت ورودی شامل اعداد 1 تا هشت و عدد صفر به عنوان خانه خالی است. این داده های اصلی را به عنوان ریشه در نظر میگیریم. با انجام یک جا به جایی بر روی این ریشه، یک گره به دست می آید. همچنین با انجام یک جابه جایی بر روی این گره، گره دیگری به دست می آید. یعنی با انجام دو حرکت از ریشه، این گره به دست می آید که فاصله آن تا ریشه 2 است. در هر مرحله، بین 1 و 4 جابجایی خواهیم داشت. و لذا هر جابه جایی باعث به وجود آمدن یک تا چهارگره می شود. با انجام جابجایی ها بر روی هر گره، یک درخت به وجود می آید و هدف ما یافتن گره ای است که اعداد داخل خانه هایش دقیقا با آنچه که کاربر میخواهد(یعنی خانه های هدف) برابر باشد. پس از ساخت یک تا چهار گره در هر مرحله، باید یک گره را انتخاب کنیم و زیر گره های آن را بررسی کنیم. در الگوریتم آگاهانه انتخاب گره به این شکل است که هر گره ای با تعداد خانه های صحیح بیشتر، زودتر انتخاب می شود.
توضیحات بیشتر »