پروژه دات کام

مساله هشت وزیر از جمله مسائل پرمخاطب مباحث طراحی الگوریتم است. ۸  مهره وزیر رو روی صفحه شطرنج چنان بچینید که نتونن همدیگه رو تهدید کنن.

برای افرادی که با بازی شطرنج آشنایی ندارن:

وزیر مهره ای از مهره های بازی شطرنجه که می تونه در تمامی ۸ جهت هر تعداد خانه – تا زمانی که مهره ای مانع نباشه – حرکت کنه و اگه در یکی از این خانه ها مهره حریف قرار داشته باشه تهدیدش کنه.

مساله هشت وزیر :  ما مساله رو در حالت کلی در نظر می گیریم. یعنی زمانی که ابعاد صفحه شطرنج n در n و تعداد مهره ها n هستش. ( n > 3 ) روشهای مختلفی برای پیدا کردن جواب وجود داره. یکی از این روشها چیدن تصادفی مهره ها روی صفحه شطرنجه! به عبارت دیگه n مهره رو به صورت تصادفی در خانه های مختلف صفحه قرار می دیم و بررسی می کنیم که آیا شرط مساله رو برآورده می کنن یا نه؟ این روش بسیار سریع ما رو به جواب می رسونه. اما ایرادی که داره نمی شه مطمئن بود بشه به همه حالتهای چینش دست پیدا کرد. در صفحه ۸ در ۸ شطرنج این مساله ۹۲ جواب مختلف داره. شما ممکنه روش تصادفی رو هزار بار به کار ببرید، اما نتونید همه ۹۲ حالت ممکنه رو به دست بیارید. این روش زمانی مفیده که پیدا کردن یه جواب برای ما کافی باشه.

در این دسته روشها مهره ها رو یکی یکی و به صورت بازگشتی روی صفحه طوری می چینیم که مطمئن باشیم با مهره های قبلی تداخل نداره و شرط مساله برآورده می شه. معمولا از سطر اول صفحه شروع می کنیم به قرار دادن مهره ها. پر واضحه که هر سطر فقط می تونه یه مهره رو تو خودش جا بده. مهره سطر دوم رو طوری قرار می دیم که توسط مهره سطر اول تهدید نشه. برای این کار خانه های مختلفی از سطر رو می شه انتخاب کرد. برای نظم داشتن کارهامون فرض می کنیم همیشه انتخاب خانه ها از سمت چپ سطر شروع می شه. به عبارت دیگه با شروع از سمت چپ سطر اولین خانه ای که شرط رو برآورده کنه انتخاب می کنیم. به همین ترتیب سطرهای بعدی رو هم می چینیم. اگر به سطری رسیدیم که بر اساس چیدمان سطرهای قبلی هیچ خانه امنی برای مهره وجود نداشت ( یعنی همه خانه ها توسط مهره های قبلی تهدید می شدن ) یه مرحله به عقب بر می گردیم و مهره سطر قبل رو جابجا می کنیم. این کار هم با حرکت مهره به اولین خانه سمت چپ موقعیت فعلی که شرط رو برآورده کنه، انجام می شه. با ادامه دادن این روال و با جابجا کردن مهره ها به صورت منظم و بازگشتی تمامی حالتهای ممکنه به دست می یان.

برای پیاده سازی چنین الگوریتمی و تشخیص اینکه چه خانه هایی از سطر امن هستن روشهای مختلفی وجود داره. ساده ترینشون اینه که هر بار تمامی خانه هایی رو که امکان تهدید شدن از اونها وجود داره بررسی کنیم تا از قرار نداشتن مهره وزیر در اونها مطمئن باشیم. اما این روش اصلا کارا و بهینه نیست.

روش دیگه تعریف کردن صفحه شطرنج به صورت یه آرایه n در n هستش که خونه های امن و غیر امن با علامتگذاری مشخص می شن. هر بار که مهره ای رو صفحه قرار می گیره تمام خونه هایی که توسط این مهره تهدید می شن به صورت غیر امن علامتگذاری می شن. به این ترتیب می شه فهمید که هر خونه با توجه به چینش مهره های قبلی امن هست یا نه؟ اما این روش هم معایبی داره که باعث می شه به روش سوم رجوع کنیم. برای آشنایی با این معایب کافیه سعی کنید کد برنامه رو بنویسید!

در روش سوم که من ازش استفاده کردم، برای علامتگذاری خانه های امن و غیر امن از شیوه دیگه ای بهره می بریم. به این ترتیب که اقطار راست به چپ، چپ به راست و ستونها با شماره هایی مشخص می شن که کار علامتگذاری رو بسیار ساده می کنن. این روش بدون شک از کاراترین روشهای رسیدن به جواب مساله ماست. هم سرعت اجرای بالایی داره و هم حافظه مصرفی بسیار کم!

کدی که به زبان ++C درباره این مساله نوشته شده با استفاده از روش سوم تعداد جوابهای ممکن – و نه خود جوابها – برای مقادیر مختلف n رو مشخص می کنه. به عنوان مثال اگر n رو ۸ وارد کنید خروجی برنامه ۹۲ خواهد بود. توصیه می کنم برای nهای بزرگ برنامه رو امتحان نکنید! اگر n رو ۱۶ وارد کنید بعد از گذشتن زمان زیادی عدد ۱۴۷۷۲۵۱۲ روی صفحه نمایش چاپ می شه. یعنی در صفحه شطرنج ۱۶ در ۱۶ حدود ۱۵ میلیون حالت مختلف برای چیدمان صحیح وجود داره!!

در ادامه میتونید الگوریتم، تحلیل و سورس کد این مسئله را ( با زبان های مختلف ) از سایت پروژه دانلود کنید

در فصل۱، مفهوم عوامل منطقی به عنوان اساس شیوه ها در هوش مصنوعی شناسایی گردید. در این فصل این مفهوم راملموس تر می سازیم. خواهیم دید که مفهوم عقلانیت رامی توان در بسیاری از عوامل فعال در هر محیط قابل تصوی به کار گرفت. در این کتاب، هدف ما، بهره گیری از این مفهوم جهت توسعه مجموعه کوچکی از اصول طراحی برای ساختن عوامل موفق می باشد سیستمهایی که می توان به طور معقول، هوش نامید. مبحث خود را با بررسی عوامل، محیطها و جفت نمودن این دو آغاز خواهیم نمود. مشاهده این نکته که برخی از عوامل بهتر از بقیه عمل می کنند، به طور طبیعی ما را به ا عامل منطقی رهنمون می کند عاملی که تا حد امکان خیلی خوب رفتار می کند. اینک یک عامل تا چه حد به خوبی رفتار می کند به ماهیت محیط بستگی دارد. برخی از محیطهای دشوار تر از سایرین هستند. ما طبقه بندی خام ونا پروده ای از محیطها را ارائه نموده ومشخص کرده ایم که چگونه ویژگی های یک محیط بر طراحی عوامل مناسب برای آن محیط، تاثیر می گذارند، همچنین برخی از طرحهای اصلی عامل (کالبدی) (ابتدایی) را که در باقیمانده کتاب بدان تجسم می بخشیم، توضیح خواهیم داد.

سرفصل :

عوامل هوشمند

عوامل و محیطها

رفتار خوب: مفهوم عقلانیت

مقیاسهای عملکرد

علم مطلق، یا یادگیری و خود مختاری

ماهیت محیطها

هوش مصنوعی

تعیین محیط کاری

arad  به Bucharest

مجموعا ۵۰ صفحه فایل Word

« هوش مصنوعی، دانش ساختن ماشین‌‌ ها یا برنامه‌های هوشمند است. »   همانگونه که از تعریف فوق-که توسط یکی از بنیانگذاران هوش مصنوعی ارائه شده است- برمی‌آید،حداقل به دو سؤال باید پاسخ داد:

۱ـ هوشمندی چیست؟

۲ـ برنامه‌های هوشمند، چه نوعی از برنامه‌ها هستند؟تعریف دیگری که از هوش مصنوعی می‌توان ارائه داد به قرار زیر است:

« هوش مصنوعی، شاخه‌ایست از علم کامپیوتر که ملزومات محاسباتی اعمالی همچون ادراک (Perception)، استدلال(reasoning) و یادگیری(learning) را بررسی کرده و سیستمی جهت انجام چنین اعمالی ارائه می‌دهد.» و در نهایت تعریف سوم هوش مصنوعی از قرار زیر است:

«هوش مصنوعی، مطالعه روش‌هایی است برای تبدیل کامپیوتر به ماشینی که بتواند اعمال انجام شده توسط انسان را انجام دهد.»   به این ترتیب می‌توان دید که دو تعریف آخر کاملاً دو چیز را در تعریف نخست واضح کرده‌اند.

۱ـ منظور از موجود یا ماشین هوشمند چیزی است شبیه انسان.

۲ـ ابزار یا ماشینی که قرار است محمل هوشمندی باشد یا به انسان شبیه شود، کامپیوتر است.   هر دوی این نکات کماکان مبهم و قابل پرسشند. آیا تنها این نکته که هوشمندترین موجودی که می‌شناسیم، انسان است کافی است تا هوشمندی را به تمامی اعمال انسان نسبت دهیم؟ حداقل این نکته کاملاً واضح است که بعضی جنبه‌های ادراک انسان همچون دیدن و شنیدن کاملاً ضعیف‌تر از موجودات دیگر است.   علاوه بر این، کامپیوترهای امروزی با روش‌هایی کاملاً مکانیکی(منطقی) توانسته‌اند در برخی جنبه‌های استدلال، فراتر از توانایی‌های انسان عمل کنند.