مطالبی راجع به هوش مصنوعی
عوامل هوشمند:
ماهيت عوامل، كامل يا غير از آن، تنوع محيطي و جانوران نمايشي حاصل از انواع عوامل مورد بحث و بررسي قرار مي گيرند.
در فصل1، مفهوم عوامل منطقي به عنوان اساس شيوه ها در هوش مصنوعي شناسايي گرديد. در اين فصل اين مفهوم راملموس تر مي سازيم. خواهيم ديد كه مفهوم عقلانيت رامي توان در بسياري از عوامل فعال در هر محيط قابل تصوي به كار گرفت. در اين كتاب، هدف ما، بهره گيري از اين مفهوم جهت توسعه مجموعه كوچكي از اصول طراحي براي ساختن عوامل موفق مي باشد سيستمهايي كه مي توان به طور معقول، هوش ناميد.
مبحث خود را با بررسي عوامل، محيطها و جفت نمودن اين دو آغاز خواهيم نمود. مشاهده اين نكته كه برخي از عوامل بهتر از بقيه عمل مي كنند، به طور طبيعي ما را به ا؟عامل منطقي رهنمون مي كند عاملي كه تا حد امكان خيلي خوب رفتار مي كند. اينك يك عامل تا چه حد به خوبي رفتار مي كند به ماهيت محيط بستگي دارد. برخي از محيطهاي دشوار تر از سايرين هستند.
ما طبقه بندي خام ونا پروده اي از محيطها را ارائه نموده ومشخص كرده ايم كه چگونه ويژگي هاي يك محيط بر طراحي عوامل مناسب براي آن محيط، تاثير مي گذارند، همچنين برخي از طرحهاي اصلي عامل (كالبدي) (ابتدايي) را كه در باقيمانده كتاب بدان تجسم مي بخشيم، توضيح خواهيم داد.
1-2 عوامل و محيطها
عامل هر چيزي است كه بتوان از عنوان درك محيط از طريق حسگرها و تاثير بر محيط از طريق محركها، آن در نظر گرفت. اين ايده ساده در شكل 1-2 به تصوير كشيده شده است يك عامل انساني داراي چشم، گوش و ديگر اندامها براي حسگرها و نيز دستها، پاها دهان و ديگر اعضاي بدن به عنوان محرك مي باشد. يك عامل روبوتيك نيز ممكن است براي حسگرها از دوربين و يابنده هاي طيف مادون قرمز و براي محركها از موتورهاي مختلف، بهره گيرد.
يك عامل نرم افزاري نيز، فشار بر كليدها، محتويات فايل و بسته هاي شبكه را به عنوان وروديهاي حسگر دريافت نموده و با نمايش روي صفحه، نوشتن فايلها و ارسال بسته هاي شبكه، بر محيط تاثير گذارد. اين فرض كلي در نظر گرفته خواهد شد كه هر عامل مي تواند اعمال خود را درك نمايد.
ما از اصطلاح آموزه يا ادارك براي اشاره به وروديهاي اداراكي در هر زمان ارائه شده، استفاده مي نماييم. توالي ادراك عامل، تاريخچه كامل هر چيزي است كه عامل دريافت نموده است. به طور كلي، انتخاب عمل عامل در هر زماني به توالي اداركي بستگي دارد كه تا آن زمان مشاهده شده است. در صورتيكه بتوانيم انتخاب عمل هرعاملي را بدان هرتوالي ادراك، مشخص نماييم، مي توانيم بگوييم كه چيزي براي گفتن در مورد عامل داريم. به لحاظ رياضي، گفته مي شودكه رفتار يك مل از طريق تابع عامل توضيح داده مي شود.
مي توانيم جدول بندي تابع عاملي را در نظر بگيريم كه هر عامل ارائه شد را توضيح مي دهد. در مورد اغلب عوامل، اين جدول بسيار بزرگ- بي نهايت، مگر اينكه مرزي را براي طول توالي ادارك مورد نظر مشخص نماييم. در اصل، با توجه به بررسي عامل، مي توانيم اين جدول را با آزمون كليه توالي هاي احتمالي و ثبت عملكرد عامل در پاسخ، ايجاد نماييم. البته اين جدول مشخص ساختن ويژگي خارجي عامل مي باشد. به لحاظ دروني، تابع عامل براي يك عامل مصنوعي از طريق برنامه عامل تحقق مي يابد. متمايز نمودن اين دو اين از اهميت زيادي برخوردار مي باشند. تابع عامل، توضيح رياضي انتزاعي است. برنامه عامل يك برنامه ملموس است كه در چهار چوب است كه در چهارچوب معماري عامل اجرا مي شود.
براي روشن نمودن اين پديده ها، از يك مثال بسيار ساده استفاده مي كنيم- دنياي جارو برقي در نمودار 2-2 نشان داده شده است. اين دنيا بسيار ساده است طوريكه هر چييز كه روي هوا مي توان توضيح داد- اين دنيا يك دنياي ساختگي است طوريكه مي توان تغييرات زيادي را ايجاد نمود. اين دنياي خاص تنها داراي دو مكان است مرجع A و مربع B عامل خلاء مشخص مي نمايد كه در كدام مربع بوده و آيا هيچ كثيفي در اين مربع وجود دارد يا خير. اين عامل مي تواند بين حركت به چپ، حركت به راست،مكش كثيفي را انجام هيچ كاري، يكي را انتخاب كند. يك تابع عامل بسيار ساده به صورت ذيل است. در صورتي كه مربع فعلي كثيف باشد، عامل شروع به مكش آن مي كند، در غير اينصورت به مربع ديگر مي رود. جدول بندي جزئي اين تابع عامل در تصوير 3-2 ارائه گرديده است در قسمتهاي بعدي، يك برنامه ساده براي اين تابع عامل داده خواهد شد.
با بررسي جدول 3-2، متوجه مي شويم كه عوامل مختلف جهان خلاء را مي توان از طريق پر كردن ستون سمت راست به هر شيوه اي، تعريف نمود. سوال اين است: راه درست پر كردن جدول چيست؟ به عبارت ديگر، چه چيزي عامل را به مورد خوب يابد، هوشمند يا كند ذهن، تبديل مي نمايد. پاسخ اين پرسش را در قسمت بعدي ارائه نموده ايم.
قبل از خاتمه اين قسمت، مشخص مي نماييم كه مفهوم يك عامل به معناي ابزاري براي آناليز سيستمهاست نه يك ويژگي مطلق كه جهان را به دو دسته يا غير عامل تقسيم مي نمايد. مي توان يك ماشين حساب دستي را به عنوان عاملي در نظر گرفت كه زماني كه به آن توالي ادراك =2+2 داده مي شود، عمل نمايش (4) را انتخاب مي نمايد، اما چنين تحليلي سختي به درك ما از ماشين حساب كمك مي كند.
2-2 رفتار خوب: مفهوم عقلانيت
عامل معقول، عاملي است كه كار درست را انجام مي دهد گفته مي شود كه هر قلمي در جدول تابع عامل به طور صحيح پر شده است. واضح است كه انجام كار صحيح بهتر از انجام كار غلط است، اما انجام كار درست به چه معناست؟ گفته مي شود كه عمل درست، عملي است كه باعث خواهد شد تا عامل موفق باشد. بنابراين، براي سنجش موفقيت به چند روش نياز خواهيم داشت. عامل همراه با توضيح محيط، حسگرها و محركهاي عامل امكان تخصيص كمل كاري كه در پيش روي عامل قرار دارد را فراهم مي آورد. باتوجه به اين نكته، مي توان به طور دقيق تر منظور از منطقي بودن را تعريف نمود.
مقياسهاي عملكرد
مقياس عملكرد، معياري را براي موفقيت رفتاريك عامل مجسم مي نمايد. زمانيكه عاملي به محيطي وارد مي شود، طبق دركي كه دريافت مي نمايد، توالي از اعمال را ايجاد مي نمايد. اين توالي اعمال باعث مي شود كه محيط وارد توالي از حالتها شود در صورتيكه اين توالي مطلوب باشد، عامل كار را به خوبي انجام داده است. مي توان از عامل درمورد ايده ذهني مبني بر اينكه تا چه حد از عملكرد خود رضايت داشته، سوال نمود، اما برخي از عوامل قادر به پاسخگويي نبوده و سايرين نيز خود را غفال مي نمايند. بنابراين، بر يك معيار عملكرد عيني كه از سوي طراح ايجاد كننده وعامل مطرح شده اصرار كرد
عامل جارو برقي از فصل قبلي را در نظر بگيريد. با توجه به مقدار كثيفي تميز شده دريك شيفت هشت ساعتي مي توان معيار عملكردي را پيشنهاد نمود.البته در مورد يك عامل منطقي آنچه شما مي پرسيد، چيزي است كه به دست مي آوريد عامل منطقي مي توان با پاك كردن كثافت و سپس خالي كردن آن روي زمين و دوباره جمع كردن و .... اين معيار عملكرد را به حداكثر برساند. يك معيار عملكردي مناسب به خاطر داشتن زميني پاكيزه به عامل پاداش مي دهد. به عنوان مثال مي توان براي هر مربع پاكيزه در هر مرحله زماني يك امتياز پاداش دارد (مي توان به خاطر برق مصرفي و نويز ايجاد شده، جريمه نمودم. به عنوان يك قانون كلي، بهتر است معيارهاي عملكردي را طبق آنچه كه واقعا از محيط خواسته مي شود طراحي نمود تا طبقي اينكه عامل بايد چگونه رفتار نمايد.
انتخاب معيار عملكرد همواره ساده نيست. به عنوان مثال، مفهوم (كف اتاق پاكيزه) در پاراگراف قبلي بر متوسط پاكيزيگي در طول زمان مبتي است. در حاليكه با دو عامل مختلف مي توان متوسط پاكيزيگي مشابهي را به دست آورد يكي از آنها در همه اوقات كار پيش پا افتاده اي را انجام مي دهد و ديگري، جايي را پاكيزه مي كند اما زمان زيادي را مي برد، كه يك نقطه خوب علم سرايداري بودن، ظاهرا از اولويت بوده، اما در واقع پرسشي فلسفي با معناي دور از دسترس است. كداميك بهتر است يك زندگي بي ملاحظه باپستي ها و بلندي يا يك زندگي ايمني با وجودي ملال آور؟ كداميك بهتر است
- اقتصادي كه در آن همه در فقر نسبي زندگي مي كنند يا اقتصادي كه در آن برخي از وفور و بر خي در فقر بسيار گذران عمر مي كنند؟ اين پرسشها را به عنوان تمريني به خواننده ساعي مي سپاريم.
عقلانيت
اينكه چيزي درزمان داده شده منطقي باشد به چهار مورد بستگي دارد:
- معيار عملكردي، مقياسي را براي موفقيت تعريف نمايد.
- دانش قبلي عامل از محيط
- اعمالي كه عامل مي تواند به انجام آنها مبادرت نمايد.
- توالي ادراك عامل تا امروز.
اين موارد ما را به سوي تعريف عامل منطقي رهنمون مي سازد.
در مورد هر توالي اداركي احتمالي، عامل منطقي بايد عملي را انتخاب نمايد كه انتظار مي رود معيار عملكردي آن را به حداكثرمي رساند كه اين كارايي نيز با توجه به توالي ادارك و دانش و دروني عامل مشخص مي گردد.
به مثال ساده اي كه در آن عامل جارو برقي مربع را در صورت كثيف بودن تميز نموده ودر غير اينصورت به مربع ديگري مي رود، توجه نمايد. اين همان تابع عاملي است كه در تصوير 3-2 به صورت جدول بيان گرديده است. آيا اين يك عامل منطقبي به بستگي دارد! نخست اينكه، لازم است تا بازده عملكردي، ميزان آگاهي از محيط، حسگرها و محركهاي عامل، توضيح داده شود. اجازه دهيد موارد ذيل را در نظر داشته باشيم.
معيار عملكردي براي هر مربع پاكييزه در هر مرحله زماني، امتياز مي دهد كه (دوره زندگي) 1000 مرحله زماني دارد.
جغرافياي محيط به عنوان يك قياس شناخته مي شود، اما در مورد توزيع كثيفي و مكان اوليه عامل، اينگونه نيست. مربعهاي پاكيزه، تمبر باقي مي ماند اعمال راست و چپ، عامل را به راست و چپ حركت مي دهد به استثناي زمانيكه عامل را به خارج از محيط هدايت مي نمايد كه در اين مورد هر جايي كه هست، باقي مي ماند.
تنها اعمال قابل دسترسي، چپ، راست، مكش و NoOp (هيچ كار) مي باشند.
عامل به طور صحيح مكان خود و اينكه آيا مكان كثيف هست يا خير را درك مي نمايد.
ما بر اين ادعا هستيم كه تحت اين شرايط، عامل منطقي است، حداقل، عملكرد مورد انتظار آن به اندازه ديگر عوامل بالاست تمرين 4-2 از شما مي خواهد تا اين مورد را اثبات نماييد.
به راحتي مي توان ديد كه همين عامل در شرايط متفاوت، غير منطقي خواهد بود به عنوان مثال، زمانيكه همه آلودگيهاي پاك شدند، عامل بي جهت به عقب و جلو نوسان مي نمايد. درصورتيكه معيار عملكرد، جريمه يك امتيازي را براي هر حركت چپ يا راست در نظر بگيريد، عامل عملكرد ضعيفي را خواهد داشت. در اين مورد، عامل بهتر زمانيكه مطمئن است همه مربعها پاكيزه هستند، كاري انجام نمي دهد. در صورتيكه مربعهاي پاكيزه دوباره كثيف شوند، عامل مي تواند در صورت نياز اوضاع را كنترل نمود و دوباره آنها را پاك نمايد. در صورتيكه جغرافياي محيط ناشناخته باشد، عامل به جاي جسبيدن به مربعهاي A و B، به بررسي آن نيازمند خواهد بود. تمرين 4-2 از شما خواسته تا در اين موارد، عواملي را طراحي نماييد.
علم مطلق، يا يادگيري و خود مختاري
لازم است تا در مورد تمايز ميان عقلانيت و علم كل، دقيق باشيد يك عامل داناي كل، نتيجه واقعي عملكرد را مي داند و مي تواند بر اساس آن عمل كند، اما علم كل در واقعيت غير ممكن است. به مثال ذيل توجه نماييد. من در طول خيابان شانزه ليزه قدم مي زنم. و در سوي ديگر خيابان يك دوست قديمي را مي بينيم. هيچ ترافيكي در آن نزديكي نيست و من به كار ديگري مشغول نيستم، بنابراين منطق آن است تا از خيابان عبور نمايم. در همين حين، درهواپيماي باري كه در ارتفاع 3000 پايي حركت مي كند، مي افتد و قبل از اينكه من به طرف ديگر خيابان برسم، مرا وسط خياران پهن زمين مي كند آيا من در عبور از خيابان غير منطقي بودم؟ غير ممكن است كه روي اعلان فوقت من در تلاشي عبث براي عبور از خيابان نوشته شود.
اين مثال نشان مي دهد كه عقلانيت به همان مقدار كامل نيست. عقلانيت، بازده مورد انتظار را به حداكثر مي رساند، در حاليكه كمال، بازده واقعي را به حداكثر مي رساند. برخورد از نطقه نظر كمال، موردي منصفانه براي عوامل نيست. نكته آن است، اگر انتظار داريم كه عاملي آنچه كه بهترين است، انجام دهد، طراحي عاملي براي رعايت اين تخصص غير ممكن مي باشد.
- مگر اينكه عملكرد گوي بلورين يا ماشين زمان را بهبود بخشيم.
تعريف ما از عقلانيت نيازي به علم مطلق ندارد، چرا كه انتخاب تنها به توالي اداراكي تا اين زمان وابسته است ما بايد مطمئن شويم كه به طور غير عمد امكان مبادرت عامل به فعاليتهاي لزوما غير هوشمند را فراهم نماورده ايم به عنوان مثال، در صورتيكه، عامل قبل از عبور از يك خيابان شلوغ، هر دو مسير را نگاه نكند، توالي اداركي آن به او نخواهد گرفت كه كاميون بزرگي در حال نزديك شدن است. آيا تعريف ما از عقلانيت، به ما خواهد گفت كه عبور از خيابان خوب است؟ دور از آن است! نخست اينكه، عبور از خيابان با توجه به اين توالي نا آگاهانه، منطقي نخواهد بود. ريسك تصادف بدون نگاه كردن به هنگام عبور بسيار بالاست. دوم اينكه عامل منطقي بايد قبل ازقدم نهادن به خيابان عمل (نگاه كردن) را انتخاب نمايد چرا كه نگاهكردن بازده مورد انتظار را به حداكثر مي رساند. مبادرت به اعمالي به منظور اصلاح آموزه هاي آتي كه گاهي جمع آوري اطلاعات ناميده مي شود – بخش مهمي از منطق بوده ودر فصل 16 كاملا مورد بررسي قرار خواهد گرفت. نمونه دوم جمع ؟آوري اطلاعات، از طريق بررسي فراهم مي آيد كه بايد يك عامل تميز كردن دريك محيط ناشناخته بر عهده مي گيرد.
تعريف ما، عامل منطقي را ملزم مي نمايد كه نه تنها اطلاعايت را جمع آوري مي نمايد، بلكه تا حدامكان از آنچه كه ادارك نموده چيزي بياموزد. پيكر بندي اوليه عامل مي تواند دانش قبلي از محيط را منعكس نمايد ؟ هنگاميكه عامل تجربه كافي به دست آورد، ممكن است پيكر بندي اصلاح شود يا بزرگتر شود. موارد نهايي وجود دارند كه درآنها محيط كاملا به طور قياسي شناخته مي شود. در چنين مواردي، لازم نيست تا عامل چيزي را درك نموده يا بياموزد، بلكه كافي است به طور صحيح عمل نمايد. البته اين عوامل بسيار شكننده اند. يك سوسك سرگين را در نظر بگيريد اين سوسك پس از كندن لانه خود و تخم ريزي درآن، سرگيتي را از توده نزديك مي آورد تا ورودي حفره را پر كند. در صورتيكه گوي سر گين از چنگ او بيرون بيايد، او به مسر خود ادامه داده و به صورت خيالي لانه را با گوي سرگيتي كه وجود ندارد، پر مي كند به نبود آن توجهي ندارد. تكامل فرضي را درمورد اين رفتار سوسك در نظر مي گيرد و زمانيكه اين فرضيه نقص گردد، نتايج رفتاري ناموفقي حاصل مي گردد. هوشمندي زنبوي sphex كمي بيشتر از اين سوسك است. sphox مادهف نقبي را حفاري نموده و كرم حشره اي را نيش مي زند و آن را به حفره مي كشاند و وارد نقب مي شود تا همه چيز را كنترل نمايد، سپس كرم حشره را به داخل نقب كشيده و تخم مي گذارد. كرم حشره به عنوان منبع غذايي تخمها عمل مي نمايد. اما در صورتيكه حشره شناسي به هنگام ورود زنبور ماده به داخل حفره جهت كنترل آن كرم حشره را چند اينچ جابه جا نمايد زنبور دوباره كرم را به داخل مي كشاند و بدون تغييري كار خود را دنبال مي نمايد حتي اگر كرم حشره، دوازده بار حركت داده شود زنبور shpox نمي تواند عدم موفقيت اين نقشه را بياموزد و در نتيجه تغييري در آن به وجود نمي آورد.
عوامل موفق كه به منظور محاسبه تايع عامل آن را به سه دوره مختلف تقسيم مي نمايد زمانيكه عامل طراحي مي شود برخي از محاسبات توسط طراحان آن انجام مي شود زمانيكه روي عمل بعدي برنامه ريزي مي نمايد، عامل محاسبات بيشتري انجام مي دهد و وقتي تجربه اي به دست آورد، براي تصيم گيري در مورد تغيير رفتار، محاسبات بيشتري نيز انجام مي دهد.
با توجه به مقدار تكيه به دانش قبلي طراحي، مي توان گفت كه عامل فاقد خود مختاري است. عامل منطقي بايد خود مختار باشد- يعني بايد بياموزد كه براي ؟ دانش قبلي نادرست يا جزئي، چه كاري انجام دهد به عنوان مثال عامل جارو برقي مي آموزدكه زمان و مكان وجود اشغال را پيش يني مي نمايد. به عنوان يك موضوع عملي به ندرت از ابتدا نياز به استقلال كامل خواهيم داشت. زمانيكه عامل تجربه اندكي داشته يا تجربه اي نداشته باشد، ناچار خواهد بود تا به طور تصادفي عمل نمايد مگر اينكه طراح به وي كمك كند. بنابراين، همانطور كه تكامل، رفلكسها يا واكنشهاي دروني كافي را براي حيوانات فراهمي مي نمايد طورريكه بتوانند بقاي بيشتري داشته باشند، فراهم آوردن عوامل هوش مصنوعي با مقداري دانش اوليه و نيز توانايي يادگيريف امري معقول خواهد بود پس از كسب تجربه كافي از محيط، رفتار عامل منطقي مستقل از دانش قبلي خواهد بود. بنابراين تلفيق يادگيري به فرد امكان ميدهد تا عامل را طراحي نمايد كه در محيطهاي مختلف، موفق خواهد بود.
3-2 ماهيت محيطها
اكنون كه تعريفي از عقلانيت داريم، تقريبا آماده ايم تا درمورد ايجاد عوامل منطقي فكر كنيم با اين حال، ابتدا بايد در مورد محيط هاي كاري كه لزوما مشكي هستند كه عامل، آن را حل مي كند به فكر كنيم كار خود را با نشان داده نحوه تعيين محيط كاري و توضيح فرآيند با چند مثال، آغاز مي نماييم سپس مشخص مي سازيم كه محيط هاي كاري، ويژگي ها متنوعي دارند ويژگي محيط كاري به طور مستقيم بر طراحي مناسب برنامه عامل اثر مي گذارد.
تعيين محيط كاري
در محبط عقلانيت عامل ساده جارو برقي، ناچار شديم تا معيار عملكردي، محيط، محركها و حسگرهاي عامل راتعيين نماييم كليه اين موارد با عنوان محيط كاري طبقه بندي مي گردد. براي اينكه اين موارد را به طور خلاصه به ذهن بسپاريم از توضيح سر واژه PEAS بهره مي گيريم. در طراحي يك عامل، اولين گام مشخص، نمودن كامل محيط كاري تا حد امكان است دنياي خلاء بسيار ساده اي است، اجازه بدهيد تا از مثال پيچيده تري استفاده كنيم يك راننده تاكسي خود كار در ادامه اين فصل، اين مثال را به كار مي گيريم. قبل از هوشياري خواننده بايد اشاره كنيم كه يك تاكس كاملا خود كار در حال حاضر ماوراي توانايي ها تكنولوژي موجود است كار رانندگي، بي نهايت مشخص است هيچ محدوديتي براي تركيب شرايط ؟ آمده وجود ندارد دليل ديگري بر اينكه ما اين مثال را به عنوان كانون مبحث خود انتخاب نموده ايم نمودار 4-2 توضيح PEAS را براي محيط كاري تاكسي خلاصه مي كند. در بندهاي ذيل هر عنصر را با جزئيات كامل مورد بحث قرار مي دهيم.
نخست اينكه معيار عملكرد كه ما مي خواهيم راننده تاكسي خود كار شبيه آن باشد، چيست؟ كيفيتهاي مطلوب شامل رسيدن به مقصد صحيح به حداقل رساندن مصرف سوخت و استهلاك، به حداقل رساندن زمان طي مسافت و يا هزينه به حداقل رساندن نقض قوانين ترافيكي و آسيب به ديگر راننده ها به حداكثر رساندن ايمني و راحتي مسافر، به حداكثر سود مي باشند.
بعد اينكه، محيط رانندگي كه تاكسي با آن مواجه خواهد شد، چيست؟ هر راننده تاكسي بايد جاده هاي مختلف را مسيرهاي روستايي و كوچه هاي شهري گرفته تا آزاد راههاي 12 باندي را بشناسد هر جاده خود شامل ترافيك پياده رو ها، حيوانات سرگردان، كاريها روي جاده، اتومبيلهاي پليس،چال و چوله ها و چالاسبها مي شود تاكسي نيز بايد با مسافران احتمالي و واقعي تقابل عمل داشته باشد. همچنين انتخابهاي احتمالي نيز وجود دارد ممكن است لازم باشد تاكسي در كاليفرنياي جنوبي حركت نمايد، جايي كه حداقل مشكلات وجود دارد، يا در آلاسكا يعني حائيكه به ندرت ممكن است مشكلي پيش نيايد تاكسي همواره مي تواند در سمت راست حركت كند، يا ممكن است بخواهيم زمانيكه در ژاپن يا بريتانياست، در سمت چپ حركت نمايد واضح است كه هر چه محيط محدودتر باشد، مسئله طراحي ساده تر خواهد بود.
محركهاي موجود در تاكسي خود كار كم و بيش مشابه محركهاي موجود براي يك تاكسي معمولي است، كنترل موتور از شتاب دهنده و كنترل فرمان و ترمز به علاوه، اين تاكسي براي نمايش صفحه يك تركيب كنند و صدا براي گفتگو به مسافران و احتمالا ارتباط با ديگر وسايل نقليه نيازمند خروجي خواهد بود.
براي دستيابي به اهداف محيط رانندگي، لازم است تاكسي بداندكه در كجاست، چه چيزهاي ديگري در جاده است و با چه سرعتي حركت مي كند. بنابراين، مسگرهاي اصلي آن بايد يك يا چند دروبين تلويزيوني قابل كنترل، سرعت منبع و كيلومتر شما را در بر گيرد به منظور كنترل صحيح وسيله به خصوص در پيچها تاكسي بايد يك شتاب سنج داشته باشد. همچنين بايد از وضعيت مكانيك خودرو نيز مطلع باشد بنابراين به رديف بندي معمول موتور و حسگرهاي سيستم الكتريكي نياز خواهد داشت ممكن است تاكسي خود كار، ابزارهايي را داشته باشد كه در دسترسي يك راننده معمولي انساني قرار نداشته باشد سيستم موقعيت يابي ماهواره اي جهاني براي ارائه اطلاعات موقيت با توجه به نقشه الكتريكي، و حسگرها سونا يا مادون قرمز براي كشف فاصله براي ديگر اتومبيلها و موانع رد نهايت اين تاكسي بايد يك ميكروفن يا صفحه كليد براي درخواست مسير در اختيار داشته باشد.
در تصوير 5-2، عناصر اصلي PEAS براي تعدادي از انوع عوامل را به تصوير كشيده ايم. مثالهاي بيشتر در تمرين 5-2 ازائه گرديده است. ممكن است براي برخي خوانندگان عجيب باشد كه بدانند ما برخي از برنامه هايي را كه در محيط هاي كاملا مصنوعي عمل مي كنند را در فهرست انواع عوامل خود لحاظ نموده ايم. به طور تعيين اين پرسش مطرح مي شود كه اين محيط واقعي نيست؟ در حقيقت، تفاوت ميان محيط هاي واقعي و مصنوعي مهم نيست بلكه پيچيدگي رابطه ميان رفتار عامل، توالي ادراكي ايجاد شده از طريق محيط و معيار عملكرد، موضوع قابل توجهي مي باشد. برخي محيط هاي (واقعي) در واقع كاملا ساده هستند به عنوان مثال، روبوت طراحي شده جهت بررسي قسمتهاي ارائه شده به وسيله تسمه انتقال دهنده ممكن است از چند فرضيه ساده بهره گيرند اينكه چراغها همواره، همينطور عمل مي كنند، تنها چيز در تسمه انتقال قسمتهايي خودهد بود كه بايد شناسايي گردند و اينكه تنها امكان دو عمل وجود دارد (پذيرش يا عدم پذيرش).
درارائه این فصل ما پیرامون 4 نوع برنامه واسطه اساسی که شامل مراحل اساسیکه درهمه سیستمهای هوشمند وجود دارد درزیراشاره میکنیم :
1- نتیجه ساده واسطه
2- نتیجه مدل اساسی واسطه
3- هدف اصلی واسطه
4- مزیت واسطه مرکزی (اساسی)
سپس ما شرح دادیم چگونگی تبدیل ومعکوس کردن آنها را درفهم واسطه دریک دوره عمومی
نتیجه ساده واولیه واسطه
ساده ترین نوع واسطه نتیجه وانعکاس ساده واسطه است این واسطه ها کارها واقدامات برگزیده راروی روش تصویری وادراکی انجام میدهند.
نادیده گرفتن ازادامه گزارش تصویری .برای مثال ، یک واسطه خالی همان واسطه تابع است
که درشکل 203 فهرست بندی شده ویک نتیجه ساده واسطه است زیرا این تصمیم فقط درمحل وموقعیت روشهای اصلی که شامل چیزهای بی ارزش دیگراست یک برنامه واسطه برای این نوع واسطه درشکل 208 نشان داده شده است . نکته مهم اینکه برنامه واسطه خالی خیلی کوچک است درواقع ودرمقایسه با جدول مشابه این تبدیل وکاهش واضع بیشترناشی ازنادیده
گرفتن تاریخ گزارش تصویر است ، همان که اعداد امکان پذیراز4 به توان T تا 4 کم می کند به علاوه کم تبدیل شدن اوواقعیت که زمانیکه روش مربعی زشت است ، این اقدامات مربوط به موقعیت نیست تصورکنید شما راننده یک تاکسی خودکارهستید اگرماشین جلویی ترمزبگیرد وچراغهای ترمزروشن شود
سپس شما باید به این نکته توجه کنید وشروع به ترمز گرفتن کنید به عبارت دیگربعضی ازمراحل ورودی visual رابرای برقراری وجداکردن ما آنهارا فراخوانی می کنیم ماشین جلویی درحال ترمزگرفتن است سپس پاشنه این ارتباط را برقرار می کند دربرنامه واسطه برای گرفتن اولین ترمز ما چنینارتباطی را ، چگونگی عمل به قوانین می نامیم که نوشته می شود : اگرماشین جلویی درحال ترمزگرفتن است سپس شروع کن به ترمزگرفتن انسان همچنینارتباطات زیادی برقرارمیکند بعضی ازآنها درمقابل عکس العملی یاد گرفته می شوند (برای مثال رانندگی) وبعضی ازآنها ذاتی ونتیجه غریزی دارند (مثلابه هم زدن چشم زمانیکه چیزی وارد چشم میشود ) درضمن این کتاب ما چندین راه مختلف راکه برای ارتباط برقرارکردن می توان آ موخت وانجام داد می بینیم
برنامه موجود درشکل 208 یک نوع خاص ازمحیط خلا به طورمخصوصاست راه ووسیله عمومی تروقابل تغییراست درابتدا ساخت یک مفسرمفهوم عمومی برای چگونگی عمل به قوانین وایجاد یک سری قوانین مخصوص به محیط کار.شکل 209 ساختاری ازیک برنامه عمومی وخلاصه شده را نشان میدهد (فکرنکنید اگراین جزیی است ،آن کمترجالب توجه است)
ما ازمربع مستطیل برای معنی کردن حالت معمولی ورایج درونی یک پردازش یک تصمیم واسطه استفاده می کنیم وازبیضی برای نمایش دادن اطلاعات زمینه استفاده می کنیم درپردازش یک برنامه واسطه همان طور که درشکل 201 نشان داده می شود خیلی ساده است تفسیرایجاد توابع ورودی به طورخلاصه شرح داده شده به مراحل روشها ازتصویر وتابع قوانین جفتی را برمی گرداند دراولین قاعده ازسری قواعدی که مراحل را شرح مید هند.
مهم اینکه توصیف وشرح برحسب قوانین وزوجیت آنها کاملا ادراکی وتصویری است درواقع این لوازم می توانند مجموعه ساده ای ازراههای منطقی برای انجام دادن جریان boolean باشند نتیجه ساده واسطه خاصیت قابل تحسین برای ساده بودن دارد اما این نتیجه اثبات کرده که هوش خیلی محدود است واسطه در شکل 2010 فقط اگرتصمیم درستی باشد کارمی کند و می تواند فقط براساس وروش تصوری وادراکی ساخته شود که این فقط اگر محیط کاملا معلوم وواضح باشد صورت می گیرد حتی یک ذره کوچک پیدا ومعلوم می تواند باعث زحمت وسختی شود برای مثال موضوع ترمزگرفتن یک فرضیه اولیه می دهد که شرایط " ماشین جلویی درحال ترمز گرفتن "می تواند ازقاعده جاری " تصاویرویدیوئی موجود" تعیین شود اگرماشین جلویی چراغهای خطرداشته باشد .متاسفانه مدلهای قدیمی ساختاروپیکربندی متفاوتی
ازچراغهای عقب اتومبیل (چراغهای خطر) وسیگنال های روشنایی داشتند.
واین همیشه امکان پذیرنمی باشد که ازروی یک تصویرصحبت کنیم هنگامیکه ماشین درحال ترمزکردن است یکی ازعوامل ساده عکس العمل دررانندگی پشت بعضی ازماشینها ترمزهای طولانی وغیرلازم یا اشتباه ترمزگرفتن ویا بطورکلی اصلا ترمزنگرفتن است می توانیم مشکلات را ببینیم که دردنیای خلا ایجاد می شود فرض کنید که یک عکس العمل ساده درفضای خلا حسگرمکانی محروم است وفقط یک حسگرخاک است مثل یک عامل که فقط دو قاعده امکان دارد :
تمییزوکثیف .این عامل می تواند کمبود پاسخگویی به خاک اما پاسخگویی به این عامل به فضای تمییزچیست ؟ حرکت کردن به سمت چپ درست نخواهد بود اگر این موضوع درمربع A اتفاق بیافتد وحرکت کردن به سمت راست درست نخواهد بود
اگر این موضوع درمربع B اتفاق بیافتد چرخه های بی نهایت برای یک عکس العمل ساده درفضای قابل مشاهده اغلبا غیرقابل اجتناب است خارج شدن ازچرخه پایان ناپذیرامکان پذیراست اگرعامل بتواند عملکرد خود را به صورت اتفاقی تبدیل کند برای مثال اگر عامل خلا حس شود (تمییز) ممکن است ضربه زدن به یک سکه برای انتخاب به چپ وراست باشد این بسیارساده است که بخواهیم نشان دهیم که عامل دریک عملیات دومرحله ای به یک مربع دیگرمی رسد .
سپس اگر مربع کثیف باشد تمییزخواهد شد وعمل تمییزسازی کامل خواهد شد بنابراین یک عکس العمل ساده ممکن است خارج ازاجرای قطعی باشد ما در بخش 3/2 که درمورد عکس العملها به صورت تصادفی به یک محیط چند عاملی است صحبت خواهیم کرد دریک محیط یک عاملی تصادفی بودن عقلی ومنطقی نیست این مفید است که به یک عکس العمل ساده دربعضی شرایط کمک می کند .ما می توانیم با عوامل پیچیده قطعی بهترازاین عمل کنیم
واکنش عوامل براساس مدل
موثرترین روش برای پشتیبانی کردن قسمتی عوامل قابل مشاهده نگهداری تعقیب بخشی ازجهان که قابل دیدن نمی باشد یک عامل می تواند بعضی ازوضعیت های داخلی که به درک تاریخ ودرنتیجه منجربه تفکر به صورت حداقل در مورد ابعادغیرقابل مشاهده وضعیت موجود می گردد.برای مشکل ترمزوضعیت یا شرح داخل زیاد پهناور نیست فقط قالب قبلی دوربین ها اجازه دادن به عوامل برای شناسایی هنگامیکه دونور قرمزرنگ درلبه یک وسیله روشن وخاموش می شود به صورت همزمان براین سایروظایف رانندگی مانند عوض کردن لنزنیازاست که مامورنگهدداری وتعقیب جایی هستند که سایرماشین ها به روزرسانی وظایف داخلی اطلاعات نیازبه دونوع اطلاعات دارد دربرنامه مامورابتداما بعضی ازاطلاعات درمورد چگونگی بیرون دادن با استنتاج کرد ن جهان به صورت مستقل است برای مثال سبقت گرفتن ماشین نزدیک ازان خواهد بود ازازیک لحظه پیشتردوما ما نیازبه بعضی ازاطلاعات درمورد تاییدات ماموربرجهان داریم برای مثال هنگامیکه فرمان ماشین را درجهت عقربه های ساعت می چرخانیم ماشین به سمت راست می پیچد این درمورداییکه جهان چگونه کار می کندجاییکه ازیک مدارساده بولین دریک نظریه کامل علمی این مدل جهان نامیده میشودو agent که به عنوان مدل استفاده می شود مرسوم به agent هایی درپایه مدلمی باشند نمودار11/2 ساختارمامورعکس العمل می باشد که نشان می دهد چگونه قاعده محلی با نمونه های وضعیت داخلی قدیمی ترکیب می شود برای ساختن توصیف ووضعیت جاری می باشد بخش جالب عملکرد به روزرسانی وضعیت برای توصیف وضعیت های داخلی جدید می باشد .
یک عامل یادگیری به چهارمفهومی قطعات چنانچه نشان داده شده درشکل 2015تقسیم مشود مهمترین تمایزمابین عناصریادگیری است که مسئول برای بهبودهای ساختن است وعنصر کارایی که مسئول انچه که ما داریم به طورقبلی رسیدگی کردن به عامل کامل : بودن ان درpercepts وتصمیم می گیرد (روی ) درعملها می گیردعنصر یادگیری پس خورد ازانتقاد کننده استفاده می شود چطورعامل ویقینها انجام می دهد چطورعنصرکارایی اصلاح خواهد شد که بهتردراینده انجام بدهد .
طراحی عنصریادگیری خیلی زیاد روی طراحی عنصرکارایی وابسته می باشد.
اول سوال نیست چطور من قصد دارم ان را بگیرم که این یاد بگیرد اما چه نوعی عنصرکارایی عاملم لازم است خواهد که انجام بدهد این یکی ان یاد گیردچطور؟ با توجه یک سازوکارهای یادگیری طراحی عامل ساخته میشوند که هرقسمت ازعامل بهتربشوند انتقادکننده عنصریادگیری را می گوید چقدرخوب عامل دارد با احترام به یک استاندارد کارایی ثابت انجام می دهد . انتقاد کننده ها لازم است برایاینکه percepts خودشان فرام نمودن هیچ نشان ازعامل موفقیت نیست .
برای مثال یک برنامه شطرنج می توانست یک percepts نشان دادن دریافت بکند کهآن checkmate حریفش دارد اما ان یک استاندارد کارایی نیازدارد که بداند که این یک چیز خوب است . percept خودش همچنین نمی گوید.ان است استاندارد کارایی که مهم تثبیت می کند .با به طورمفهومی یک فکرازان وقتیکه بیرون عامل رویهم رفته برای اینکه عامل نباید ان را اصلاح بکند که رفتارخودش را مناسب باشد . اخرین جزعامل یادگیری مولد مساله است . ان مسئول برای پیشنهاد کردن عملها است که به تجربه های جدید واموزنده هدایت خواهد نمود.
نقطه ان است اگرعنصرکارایی راهش را ان انجام دادن عملها داشت که بهترین معین چه ان knews هست .
اما اگرعامل راغب است که مقدارکمی کاوش بکند ومقداری شاید عملهای بهینه سازی تقریبی درکوتاه مدت ان ممکن بود خیلی بهترعملها برای اجرا کردن بلند کشف بکند . مساله مولد است کاراست که اینها عمل اکتشافی را پیشنهادبکند.این است انچه که دانشمندها انجام می دهند موقعیکه انها ازمایش انجام می دهند Galileio فکرنکرد که کاهش تکان می خورد ازاوج یک برجی درpisa ارزنده درخودبود. او noy سعی کردن بود که سنگها نه قطع بکند که مغزگذرنده های بدبخت اصلاح بکند که مغزخودش بوسیله مشخص نمودن یک بهترنظریه ازحرکت هدف بوسیله هدفش ها اصلاح بکند.برای ساختن روپوش desing واقعی زیادتری به ما برگشت به مثال تاکسی خودکارشده اجازه داد.
تشکیل شده ازعنصرکارایی هرچه جمع اوری دانش وروشها تاکسی برای انتخابکردن عملها راندنش دارند. تاکسی gose خارج روی جاده وکاربرد گرداننده ها این عنصرکارایی . انتقاد کننده هاکلمه را واطلاعات مرحله ها درطول به عنصریادگیری مشاده می کند .برای مثال بعد ازتاکسی یک گردش به چپ سریع درعرصه راه ترافیک می سازد. انتقاد کننده ها مشاهده میکند زبان تکان دهنده بوسیله راه اندازهای دیگراستفاده می کنند . عنصریادگیری قادراست که تدوین بکند یک گفتن قاعدهاین یک عمل بد بود وعنصرکارایی توسط نصب کردن قاعده جدید اصلاح شده است .مولد مساله ممکن است مشخص بنماید حوزه های مطمئن رفتاردراز بهبود نیازدارند وازمایش ها مثل (عبارتند از) امتحان کردن ترمزها را روی سطحهای جاده متفاوت زیرشرایط متفاوت پیشنهاد کنید .عنصریادگیری می تواند تغییرات به هرکدام ازقطعاتدانش نشان داده شده درنمودارهای عامل (2013،2011،209و2014) بسازد.ساده ترین موردها یادگیری مستقیما ازpercept رشته شامل می شوند .مشاهده ایالات پی درپی ازمحیط می تواند عامل را اجازه بدهد که یادبگیرد انچه که عملهایم انجام بدهند.
برای مثال اگرتاکسی یک متوقف کردن فشاربرخی چه موقع راند ن دریک جاده خیس به کاربندد درانوقت ان بزودی کشف خواهد کرد چه مقدارکاهش سرعت واقعابه نتیجه رسیده شده است . به وضوح این دوکاریادگیری مشکل ترهستند اگرمحیط تنها به طور جزئی قابل مشاهده است .
شکل ها یادگیری پاراگراف پیش لازم نیست که دسترسی بیابد استاندارد کارایی خارجیدریک sense استاندارد جهانی یک پیش بینی های ساختن است .این دوره دارد دارای کامپیوترwhirlwind (نوعی کامپیوتررقمی که ازلامپ خلا استفاده می کند) بازدیدی ازهوش مصنوعی است .
1 یک برنامه یا نماینده هست چیزی که دریافت می کند انجام میدهد دریک محیط وتابع برنامه برای یک برنامه خاص یا ویژه که انجام وظایف به وسیله برنامه پاسخ جواب دررشته محسوس شده اند.حد اجرا :سنجیدن وارزیابی رفتاریک برنامه درداخل یک محیط وبرنامه منطقی انجام می دهد خیلی ارزش ها انتظارداشتن درحد اجرا یک ارایش مرتب محسوس شدان را که به نظرامکان ندارد
· محیط برنامه: دارای ویژگی های که شامل حد اجرا ، محیط بیرونی به کارانداختن محرک یا راه انداز وحس گر. این طراحی کردن یک برنامه درمرحله اول بایدهمیشه مخصوص درمحیط برنامه به طور کامل ممکن شدنی باشد.
· محیط برنامه خیلی طولانی دارای چندین بعد یا اندازه معنی دارهستند ان می تواند به طورکامل یه به طور جزئی قابل مشاهده باشد جبرگرایانه یه اتفاقی جزیه جز یا متوالی وتک برنامه به چندگانه عملکرد برنامه وسایل تابع برنامه است ان جا وجود دارد برنامه های پایه ای متنوعی طراحی شده اند برگرداندن نوعی ازاطلاعات ساخته شده صریح وروشن واستفاده می
شود درپردازش وتصمیم گیری. طراحی ها خیلی کارایی کم حجم وانعطاف پذیرند
همه این برنامه ها ونماینده ها می تواند بهبود بخشد تااجرای ان را یاد گرفت نقش اصلی ازفعالیت دربهره هوشی تصورازاستدلال عملی – برمیگرددبه کمترین دوره دلایل ذره ای بود هم چنین موضوع mccarthy درسال 1958 شامل عنوان برنامه های با حواس پنج گانه معمولی ان رشته ای ازرباتیک وتئوری کنترل است که به وسیله انها خیلی طبیعی ، رابط اصلی ازفضا وساختمان ازفیزیک برنامه برقرارمیکنیم تصورمی شود که کنترلردرتئوری کنترل عینا دربرنامه درهوش مصنوعی هستند شایدبه طورشگفت انگیز هوش مصنوعی تمرکزمی کند برای بسیاری ازشرح حال روی گزینه های تنها روی چرخه برنامه هستند این بحث برنامه امتحان شده توسط geneser
& nilsson (1987) بود به استثنای پذیرفته شد ه وچرخه برنامه دیدگاه است که اکنون به طور وسیع پذیرفته شده دررشته ها وهست یک موضوع یا ارم کنترل شده درامتحانات تقسیمات اساسی یک اثریا مثال ریشه یک فکروعقیده عقلانی درفلسفه وسیاست است بحث درمورد فن واقعی تاسیس وایجاد یک رشته درهوش مصنوعی فکروعقیده بود ازعلاقه بیرونی تااینکه دراواسط سال 1980 زمانی که ان شروع کرد به بحث های سرشماری وتعداد زیادی یک مقاله به وسیله جان دویل پیشگویی کرد که طراحی برنامه عقل به نظرمیاید که قسمت اصلی ماموریت درهوش مصنوعی است یک نماینده بازتاب ساده با یک کارنماینده اتفاقی یک نماینده ساده می تواند چنین نماینده واندازه گیری اجرایش روی درچندین طراحی کنید؟
می توانید یک environment طراحی کنید که نماینده اتفاقیتان خیلی ناخوش ؟ انجام خواهد داد نتایجتان را نشان بدهید.
یک نماینده بازتابی با ایالت یک نماینده بازتاب ساده ؟ می توانید چنین نماینده واندازه گیری اجرایش درمحیطهای چندین طراحی کنید می توانید یک نماینده عقلیاین نوع طراحی کنید
تمرین 2010 برای مورد تکراربشوید که اندام حسی محل با یک اندام حسی ضربه سرجای خود گذاشته شده است که پیدا میکند که نماینده است که به یک مانع یا به تقاطع مرزها محیط حرکت بکند چطورنماینده بایستی رفتارکند برنامه های نماینده ممکن برای هریک ازدنباله را نگارش ها بحث کنید یک مورفی قانون است :
درصد - fivetwenty -five
اززمان چنان عمل به تمیزکف رااگرکثافت سپرده ها کثیف وروی کف رد می کند اگر کف تمیزاست برنامه نماینده تان چطورتاثیرگزاشته است اگراندام حسی کثافت پاسخ نادرست را %10 اززمان بدهد
Lng ازمایش کردن هدف مات درشطرنج یک جستجو بخش پشت لازم است بایستی که داشت ازمایش شده اند علیه ایالات بوسیله جستجو جلویی تولید بکند انجا راه عمومی نیست که این بهترانجام بدهد با مقایسه کردن شکل راه کارهای جستجو بی اطلاع 3017 مقایسه کردن راه کاردرضوابط ازچهارenaluation معیارمجموعه جلودربخش 304 جستجو می کند با اجتناب کردن ایالات مکرر بالا به این اشاره بکند ماتمام اما نادیده گرفته یکی ازمهمترین پیچیدگی های به فرایند جستجو :داریم امکان زمان تلف کردن بوسیله بسط دادن ایالات ان قبلا مواجه شده است ومنبسط شده است هرگزبرای تعدادی مساله این امکان پیش نمی اید فاصله وضعیت یک درخت است وانجا تنها یک مسیربه هروضعیت است تدوین کارامد مساله ملکه ها
برای اینکه این وضعیت تنها توسط یکی مسیررسیده می شود اگرما 8 مساله را تدوین بکنیم تا اینکه یک ملکه قرارگرفته شده درستونی می تواند بود درانوقت هروضعیت با ملکه ها توسط مسیرهای متفاوت رسیده میشود برای تعدادی مساله تکرارشدندایالات غیرقابل اجتناب هستند این تمام مساله ها شامل میشود کجا عملها قابل تغییرمثل Route-finjding مساله ها هستند وslidin-blocks گیج میکند درخت جستجوها برای این مساله بی پایان اما اگرما الو مقداری ازایالات مکررهستند ما می توانیم درخت جستجو را به اندازه محدود مولد تنها قسمت درخت خرد بکنیم که state-space نموداررا توسعه بدهد هم اکنون با توجه درخت جستجو بالا به یک عمق ثابت ان اسان است
که موردها پیدا بکند جائیکه با حذف کردن وضعیت مکرر یک کاهش توانی درهزینه جستجو را یه بدهد درمورد نهایی یک فاصله وضعیت اندازه d شکل 3018 (یک درخت یک برگ) b شکل 3018 مثال شبکه ای مستطیلی است بطوریکه درشکل C 3018 روشن ساخت دریک شبکه ای هروضعیت چهاربعدی دارد بنابراین شامل درخت جستجوی تکرارشدند.
یک گره دریک درخت جانشین نیست .درشکل 306 ریشه هردرخت شامل این ندها است با طرح مشخص.نمایش ریشه گروه گره ها ساده خواهد بود راهبرد جستجو سپس اطلاعات انتخاب .گره بعدی فاصله دارازاین گروه خواهد بود همچنین درک این ساده قابل فهم است وممکن محاسباتی هزینه برزیرااطلاعات راهبردی ممکن به نظرمیرسدخیلی ازالمنت هایی که انتخاب شده اند بهترازان هستند قبل ازاین ما فرض خواهیم کردکه مجموعه ای ازگره ها عضو تشکیل دهنده یک صف هستند عمل های یک صف پیرومیکند از:درست کردن صف بادادن المنت به صفهاخالی؟ درست برمیگرداند فقط اگرالمنت ها ی بیشتری درصف وجودنداشتهاولین صف اولین المنت راازصف برمیگرداند اولین حذف صف اولین برمیگرداند وان را ازصف حذف می کند درج یک المنت به صف اضافه می شود ونتیجه را به صف برمیگرداند (مانوع مختلف ازصف هاراخواهیم دید المنت ها ازدستورهای مختلف اضافه میشود)درج همه المنت ها را به صف اضافه کردن وبرگرداندن نتیجه به صف با این ویژگی ها ما ورژن های اساسی بیشتری می توانیم بنویسیم ازالگوریتم عمومی جستجوی درخت نشان داده شده است درشکل 309
اندازه گرفتن عملکرد مشکل حل شده محصول مشکل حل شده الگوریتم هریک ازکوتاهی یا یک جواب است (تعدادی ازالگوریتم ها ممکن است درحلقه نامحدود گیرکنند وهرگزیک محصول برنگردانند)ما اجرای الگوریتم ها را در4 روش ارزیابی خواهیم کرد:تکمیل: آیا الگوریتم تضمین می کند پیداکند جواب را وقتی درمکان یک است ؟
· ایا راهبرد پیدا میکند جواب توضیح داده شد ه درصفحه 62زمان پیچیدگی :چه مدت زمان طول می کشد تا جواب پیدا شود ؟فضای پیچیدگی : چه میزان حافظه نیازاست برای انجام جستجو؟
زمان وفضای پیچیدگی همیشه مورد توجه هستند با رعایت میزان مشکلات مختلفدرعلم نظری کامپیوتراندازه نوعی ازسایزوضعیت فضای گراف هست.زیراگراف نظریه هست ساختارداده اشکارنیست به برنامه جستجو(نقشه رومانیا مانند این است ) درAL مکانی که گراف نشان داده شده ضمنابا وضعیت اصلی واطلاعات دراغازقراردادن ونامحدود بی شماراست .پیچیدگی شرح داده شده در3 کمیت : B درجه رشته (شاخه ) یا ماکزیمم شماره هایی که دراغاز هرگره قراردادن d عمق کمترین هدف گره و m زمان که اغلباندازه گیری شده دردوره شماره های گره های تولید شده درطول جستجو و فضا دردوره ماکزیمم شماره ای گره های ذخیره شده درحافظهتشخیص دادن موثرالگوریتم جستجو ما میتوانیم فرض کنیم ارزش جستجو نوعیاست که مربوط بودن به زمان پیچیدگی اما همچنین می توانیم شامل یک دوره برایکاربرد حافظه یا ما می توانیم ازارزش جمع استفاده کنیم وبه طوریکه ترکیب میشودبا ارزش جستجو وبا ارزش مسیرجواب پیدا شده برای مشکل ازخط مسیرپیدا شوداز
arad به Bucharest
زیردرخت سمت چپ دارای ارزش یکسان بوده عمق نامحدود بوده ولی شامل هیچ جوابی نیست وجستجوی عمق نخست برای ان هیچگاه پایان نمی پذیرد از اینجا نتیجه میشود که ان کامل نیست دربدترین حالت جستجوی عمق نخست تمامی گره های
احترام به یک استاندارد کارایی ثابت انجام می دهد . انتقاد کننده ها لازم است برایاینکه percepts خودشان فرام نمودن هیچ نشان ازعامل موفقیت نیست .برای مثال یک برنامه شطرنج می توانست یک percepts نشان دادن دریافت بکند کهآن checkmate حریفش دارد اما ان یک استاندارد کارایی نیازدارد که بداند که این یک چیز خوب است . percept خودش همچنین نمی گوید.ان است استاندارد کارایی که مهم تثبیت می کند .با به طورمفهومی یک فکرازان وقتیکه بیرون عامل رویهم رفته برای اینکه عامل نباید ان را اصلاح بکند که رفتارخودش را مناسب باشد . اخرین جزعامل یادگیری مولد مساله است . ان مسئول برای پیشنهاد کردن عملها است که به تجربه های جدید واموزنده هدایت خواهد نمود.نقطه ان است اگرعنصرکارایی راهش را ان انجام دادن عملها داشت که بهترین معین چه ان knews هست .اما اگرعامل راغب است که مقدارکمی کاوش بکند ومقداری شاید عملهای بهینه سازی تقریبی درکوتاه مدت ان ممکن بود خیلی بهترعملها برای اجرا کردن بلند کشف بکند . مساله مولد است کاراست که اینها عمل اکتشافی را پیشنهادبکند.این است انچه که دانشمندها انجام می دهند موقعیکه انها ازمایش انجام می دهند فکرنکرد که کاهش تکان می خورد ازاوج یک برجی درpisa ارزنده درخودبود. او noy سعی کردن بود که سنگها نه قطع بکند که مغزگذرنده های بدبخت اصلاح بکند که مغزخودش بوسیله مشخص نمودن یک بهترنظریه ازحرکت هدف بوسیله هدفشها اصلاح بکند.برای ساختن روپوش desing واقعی زیادتری به ما برگشت به مثال تاکسی خودکارشده اجازه داد.تشکیل شده ازعنصرکارایی هرچه جمع اوری دانش وروشها تاکسی برای انتخاب کردن عملها راندنش دارند. تاکسی gose خارج روی جاده وکاربرد گرداننده ها این عنصرکارایی . انتقاد کننده هاکلمه را واطلاعات مرحله ها درطول به عنصریادگیری مشاده می کند .برای مثال بعد ازتاکسی یک گردش به چپ سریع درعرصه راه ترافیک می سازد. انتقاد کننده ها مشاهده می کند زبان تکان دهنده بوسیله راه اندازهای دیگراستفاده می کنند . عنصریادگیری قادراست که تدوین بکند یک گفتن قاعده این یک عمل بد بود وعنصرکارایی توسط نصب کردن قاعده جدید اصلاح شده است .مولد مساله ممکن است مشخص بنماید حوزه های مطمئن رفتاردراز بهبود نیازدارند وازمایش ها مثل (عبارتند از) امتحان کردن ترمزها را روی سطحهای جاده متفاوت زیرشرایط متفاوت پیشنهاد کنید .عنصریادگیری می تواند تغییرات به هرکدام ازقطعات دانش نشان داده شده درنمودارهای عامل (2013،2011،209و2014) بسازد.ساده ترین موردها یادگیری مستقیما ازpercept رشته شامل می شوند .مشاهده ایالات پی درپی ازمحیط می تواند عامل را اجازه بدهد که یادبگیرد انچه که عملهایم انجام بدهند.برای مثال اگرتاکسی یک متوقف کردن فشاربرخی چه موقع راند ن دریک جاده خیس به کاربندد درانوقت ان بزودی کشف خواهد کرد چه مقدارکاهش سرعت واقعا به نتیجه رسیده شده است . به وضوح این دوکاریادگیری مشکل ترهستند اگرمحیط تنها به طور جزئی قابل مشاهده است .شکل ها یادگیری پاراگراف پیش لازم نیست که دسترسی بیابد استاندارد کارایی خارجی دریک sense استاندارد جهانی یک پیش بینی های ساختن است .این دوره دارد دارای کامپیوترwhirlwind (نوعی کامپیوتررقمی که ازلامپ خلا استفاده می کند) بازدیدی ازهوش مصنوعی است .
1 یک برنامه یا نماینده هست چیزی که دریافت می کند انجام میدهد دریک محیط وتابع برنامه برای یک برنامه خاص یا ویژه که انجام وظایف به وسیله برنامه پاسخ جواب دررشته محسوس شده اند.
· حد اجرا :سنجیدن وارزیابی رفتاریک برنامه درداخل یک محیط وبرنامه منطقی انجام می دهد خیلی ارزش ها انتظارداشتن درحد اجرا یک ارایش مرتب محسوس شدان را که به نظرامکان ندارد
· محیط برنامه: دارای ویژگی های که شامل حد اجرا ، محیط بیرونی به کارانداختن محرک یا راه انداز وحس گر. این طراحی کردن یک برنامه درمرحله اول بایدهمیشه مخصوص درمحیط برنامه به طور کامل ممکن شدنی باشد.
· محیط برنامه خیلی طولانی دارای چندین بعد یا اندازه معنی دارهستند ان می تواند به طورکامل یه به طور جزئی قابل مشاهده باشد جبرگرایانه یه اتفاقی جزیه جز یا متوالی وتک برنامه به چندگانه عملکرد برنامه وسایل تابع برنامه است ان جا وجود دارد برنامه های پایه ای متنوعی طراحی شده اند برگرداندن نوعی ازاطلاعات ساخته شده صریح وروشن واستفاده میشود درپردازش وتصمیم گیری. طراحی ها خیلی کارایی کم حجم وانعطاف پذیرند همه این برنامه ها ونماینده ها می تواند بهبود بخشد تااجرای ان را یاد گرفت نقش اصلی ازفعالیت دربهره هوشی تصورازاستدلال عملی – برمیگرددبه کمترین دوره دلایل ذره ای بود هم چنین موضوع mccarthy درسال 1958 شامل عنوان برنامه های با حواس پنج گانه معمولی ان رشته ای ازرباتیک وتئوری کنترل است که به وسیله انها خیلی طبیعی ، رابط اصلی ازفضا وساختمان ازفیزیک برنامه برقرارمیکنیم تصورمی شود که کنترلردرتئوری کنترل عینا دربرنامه درهوش مصنوعی هستند شایدبه طورشگفت انگیز هوش مصنوعی تمرکزمی کند برای بسیاری ازشرح حال روی گزینه های تنها روی چرخه برنامه هستند این بحث برنامه امتحان شده توسط geneser & nilsson (1987) بود به استثنای پذیرفته شد ه وچرخه برنامه دیدگاه است که اکنون به طور وسیع پذیرفته شده دررشته ها وهست یک موضوع یا ارم کنترل شده درامتحانات تقسیمات اساسی یک اثریا مثال ریشه یک فکروعقیده عقلانی درفلسفه وسیاست است بحث درمورد فن واقعی تاسیس وایجاد یک رشته درهوش مصنوعی فکروعقیده بود ازعلاقه بیرونی تااینکه دراواسط سال 1980 زمانی که ان شروع کرد به بحث های سرشماری وتعداد زیادی یک مقاله به وسیله جان دویل پیشگویی کرد که طراحی برنامه عقل به نظرمیاید که قسمت اصلی ماموریت درهوش مصنوعی استیک نماینده بازتاب ساده با یک کارنماینده اتفاقی یک نماینده ساده می تواند چنین نماینده واندازه گیری اجرایش روی درچندین طراحی کنید می توانید یک environment طراحی کنید که نماینده اتفاقیتان خیلی ناخوش ؟ انجام خواهد داد نتایجتان را نشان بدهید.یک نماینده بازتابی با ایالت یک نماینده بازتاب ساده ؟ می توانید چنین نماینده واندازه گیری اجرایش درمحیطهای چندین طراحی کنید می توانید یک نماینده عقلیاین نوع طراحی کنید .
تمرین 2010 برای مورد تکراربشوید که اندام حسی محل با یک اندام حسی ضربه سرجای خود گذاشته شده است که پیدا میکند که نماینده است که به یک مانع یا به تقاطع مرزها محیط حرکت بکند چطورنماینده بایستی رفتارکند برنامه های نماینده ممکن برای هریک ازدنباله را نگارش ها بحث کنید یک مورفی قانون است درصد - fivetwenty -fiveاززمان چنان عمل به تمیزکف رااگرکثافت سپرده ها کثیف وروی کف رد می کند اگر کف تمیزاست برنامه نماینده تان چطورتاثیرگزاشته است اگراندام حسی کثافتپاسخ نادرست را %10 اززمان بدهد lng ازمایش کردن هدف مات درشطرنج یک جستجو بخش پشت لازم است بایستی کهداشت ازمایش شده اند علیه ایالات بوسیله جستجو جلویی تولید بکند انجا راه عمومی نیست که این بهترانجام بدهد با مقایسه کردن شکل راه کارهای جستجو بی اطلاع مقایسه کردن راه کاردرضوابط ازچهارenaluation معیارمجموعه جلودربخش جستجو می کند با اجتناب کردن ایالات مکرر بالا به این اشاره بکند ماتمام اما نادیده گرفته یکی ازمهمترین پیچیدگی های به فرایند جستجو :داریم امکان زمان تلف کردن بوسیله بسط دادن ایالات ان قبلا مواجه شده است ومنبسط شده است هرگزبرای تعدادی مساله این امکان پیش نمی اید فاصله وضعیت یک درخت است وانجا تنها یک مسیربه هروضعیت است تدوین کارامد مساله ملکه ها برای اینکه این وضعیت تنها توسط یکی مسیررسیده می شود اگرما 8 مساله را تدوین بکنیم تا اینکه یک ملکه قرارگرفته شده درستونی می تواند بود درانوقت هروضعیت با ملکه ها توسط مسیرهای متفاوت رسیده میشود برای تعدادی مساله تکرارشدندایالات غیرقابل اجتناب هستند این تمام مساله ها شامل میشود کجا عملها قابل تغییرمثلRoute-finjding مساله ها هستند وslidin-blocks گیج میکند درخت جستجوها برای این مساله بی پایان اما اگرما الو مقداری ازایالات مکررهستند ما می توانیم درخت جستجو را به اندازه محدود مولد تنها قسمت درخت خرد بکنیم که state-space نموداررا توسعه بدهد هم اکنون با توجه درخت جستجو بالا به یک عمق ثابت ان اسان است که موردها پیدا بکند جائیکه با حذف کردن وضعیت مکرر یک کاهش توانی درهزینه جستجو را یه بدهد درمورد نهایی یک فاصله وضعیت اندازه d شکل 3018 (یک درخت یک برگ) b شکل 3018 مثال شبکه ای مستطیلی است بطوریکه درشکل 3018 روشن ساخت دریک شبکه ای هروضعیت چهاربعدی دارد بنابراین شامل درخت جستجوی تکرارشدند.یک گره دریک درخت جانشین نیست .درشکل 306 ریشه هردرخت شامل این ندها است با طرح مشخص.نمایش ریشه گروه گره ها ساده خواهد بود راهبرد جستجو سپس اطلاعات انتخاب .گره بعدی فاصله دارازاین گروه خواهد بود همچنین درک این ساده قابل فهم است وممکن محاسباتی هزینه برزیرااطلاعات راهبردی ممکن به نظرمیرسدخیلی ازالمنت هایی که انتخاب شده اند بهترازان هستند قبل ازاین ما فرض خواهیم کردکه مجموعه ای ازگره ها عضو تشکیل دهنده یک صف هستند عمل های یک صف پیرومیکند از:درست کردن صف بادادن المنت به صفهاخالی؟ درست برمیگرداند فقط اگرالمنت ها ی بیشتری درصف وجودنداشته اولین صف اولین المنت راازصف برمیگرداند
· اولین حذف صف اولین برمیگرداند وان را ازصف حذف می کند
· درج یک المنت به صف اضافه می شود ونتیجه را به صف برمیگرداند (مانوع مختلف ازصف هاراخواهیم دید المنت ها ازدستورهای مختلف اضافه میشود)درج همه المنت ها را به صف اضافه کردن وبرگرداندن نتیجه به صف با این ویژگی ها ما ورژن های اساسی بیشتری می توانیم بنویسیم ازالگوریتم عمومی جستجوی درخت نشان داده شده است درشکل 309اندازه گرفتن عملکرد مشکل حل شده محصول مشکل حل شده الگوریتم هریک ازکوتاهی یا یک جواب است (تعدادی ازالگوریتم ها ممکن است درحلقه نامحدود گیرکنند وهرگزیک محصول برنگردانند)ما اجرای الگوریتم ها را در4 روش ارزیابی خواهیم کرد:
· تکمیل: آیا الگوریتم تضمین می کند پیداکند جواب را وقتی درمکان یک است ؟
· ایا راهبرد پیدا میکند جواب توضیح داده شد ه درصفحه 62
· زمان پیچیدگی :چه مدت زمان طول می کشد تا جواب پیدا شود ؟
· فضای پیچیدگی : چه میزان حافظه نیازاست برای انجام جستجو؟
زمان وفضای پیچیدگی همیشه مورد توجه هستند با رعایت میزان مشکلات مختلف درعلم نظری کامپیوتراندازه نوعی ازسایزوضعیت فضای گراف هست.زیراگراف نظریه هست ساختارداده اشکارنیست به برنامه جستجو(نقشه رومانیا مانند این است ) درAL مکانی که گراف نشان داده شده ضمنا با وضعیت اصلی واطلاعات دراغازقراردادن ونامحدود بی شماراست .پیچیدگی شرح داده شده در3 کمیت : B درجه رشته (شاخه ) یا ماکزیمم شماره هایی که دراغاز هرگره قراردادن d عمق کمترین هدف گره و m زمان که اغلب اندازه گیری شده دردوره شماره های گره های تولید شده درطول جستجو و فضا دردوره ماکزیمم شماره ای گره های ذخیره شده درحافظه تشخیص دادن موثرالگوریتم جستجو ما میتوانیم فرض کنیم ارزش جستجو نوعیاست که مربوط بودن به زمان پیچیدگی اما همچنین می توانیم شامل یک دوره برایکاربرد حافظه یا ما می توانیم ازارزش جمع استفاده کنیم وبه طوریکه ترکیب میشودبا ارزش جستجو وبا ارزش مسیرجواب پیدا شده برای مشکل ازخط مسیرپیدا شوداز arad به Bucharest زیردرخت سمت چپ دارای ارزش یکسان بوده عمق نامحدود بوده ولی شامل هیچ جوابی نیست وجستجوی عمق نخست برای ان هیچگاه پایان نمی پذیرد از اینجا نتیجه میشود که ان کامل نیست دربدترین حالت جستجوی عمق نخست تمامی گره های o(b^m) ها دردرخت جستجو را تولید می کند m عمق بیشینه هرگره است توجه میشود که m می تواند خیلی بزرگتراز d باشد (عمق کم عمق ترین جواب ) ونامحدود است اگر درخت نامحدود باشد
جستجوی عمق محدود
مساله درختهای نامحدود می تواند با اعمال جستجوی عمق نخست با یک محدودیت عمق
پیش فرض ما ساده تر گردد بدین معنی که با گره های واقع درعمق l بگونه ای برخورد می شود که گویی هیچ جایگزینی ندارند این رویکرد جستجوی عمق محدود نامیده
میشود عمق محدود مساله مسیر نامحدود را حل میکند متاسفانه چنانچه ما l جستجوی عمق نخست با عمیق سازی بازگشتی جستجوی عمیق سازی بازگشتی این روش یک
استراتژی عمومی است که اغلب به همراه روش جستجوی عمق نخست بکار میرود وتوسط ان می
توان بهترین عمق نخست را یافت اینکار با افزایش تدریجی محدویدیت از0،1،2،000 مادام که هدف پیدامی شود صورت می گیرد این مساله وقتی رخ می
دهد که محدودیت عمق به ممقدار d برسد (عمق کم
ترین گره) الگوریتم ان درشکل 3014 نشان داده شده است عمیق سازی بازگشتی شامل مزایای
دوروش جستجوی عمق نخست وچستجوی پهنای نخست است مانند روش عمق نخست مقدارحافظه مورد
نیاز ان خیلی کم است مانند روش جستجوی پهنای نخست موقتی فاکتور شاخه گزینی محدود
باشد جستجو کامل است ووقتی تابع هزینه مسیر یک تابع غیرنزولی از عمق گره باشد روش
بهینه محسوب می شود شکل 3015 چهارتکرار از اعمال روش جستجوی عمیق سازی بازگشتی
برای یک درخت چستجوی دودویی را نشان می دهد که در ان جواب درتکرار چهارم پیدا
میشود روش عمیق سازی بازگشتی ممکن است روش وقت گیری بنظر برسد زیرا حالات چندین
بار تکرار می شوند .این است که دریک درخت جستجو با فاکتور شاخه گزینی یکسان یا
تقریبا یکسان درهر مرحله اکثر گره ها درمرحله پایینی هستند بنابراین اینکه مراحل
بالایی چندین با ر تکرار شوند مساله ای نیست دریک جستچوی عمیق سازی بازگشتی گره
هایی واقع درمراحل پایینی تنها یک بار تولید می شوند و گره های نزدیک گره های
پایینی دوبار تولید می شوند به همین ترتیب الی اخرتارسیدن به بچه های ریشه درخت
بنا براین مجموع تعداد گره های تولید شده به قرار زیرخواهد بود: N(ids)=(d)b+(d-1)b^2+…+(1)b^4 که رتبه زمانی ان o(b^d ) می شود میتوانیم این تعداد را با تعداد گره های تولید شده
در روش پهنای (عرض) نخست مقایسه کنیم پس داریم : N(bfs )=b+b^2+…+b^d+(b^d-1-b) توجه شود که روش جستجوی عرض نخست برخی گزه هارا درعمق d+1 تولید میکند درحالیکه درروش جستجوی عمیق گری بازگشتی
این چنین نیست نتیجه می وشد که روش جستجوی عمیق سازی بازگشتی سریع ترازجستجوی عرض
نخست است علیرغم اینه حالات دراین روش بصورت تکراری تولید میشوند برای مثال اگر b=10, d=5 باشد تعداد تکرارها دراین درروش بصورت زیراست : N(ids)=50+400+3000+20000+100000=123450 N(bfs)=10+1000+1000+10000+100000+999990=101110100 جستچوی زیاد تکراری
تشبیه وسعت جستجوی اولیه است که این جستجو کردن دریک لایه کامل یک گره جدید
درهربارتکرار قبل ازرفتن به لایه بعدی است به نظرمی رسد که شباهت برابر ویکسانی
بین تکراراهای رخ داده وتکرارهای مشابه ویکسان درجستجو است الگوریتم دومی(اخری) به
ارث می برد ضمانت تا موقعی که دور ازنیاز حافظه است این یک عقیده است که برای
افزایش ارزش وقیمت نهایی مسسیروراه به جای افزایش مدت طولانی استفاده میشود نتیجه
الگورینم جستجوی مدارم یا چستجوی تکراری وطولانی نامیده می شود که درتمرین
3011نمایان شده است درمجموع متاسفانه این تکرارطولانی با مقایسه وسنجش عمومی وروی
هم رفته محکم واساسی مواجه می شود میزان جستجوی یکسان دستور،عنوان جستجونظریه
عنوان جستجوی قبلی منتشرشده است دردو جستجوی همزمان حالت اول یکی به طوف جلو
ودیگری از انتهای برنامه وهدف متوقف شدن زمانیکه در جستجو در مرکز تلاقی میکنند
متوقف میشوند (شکل 3016) انگیزش تحریک است که b^d/2+b^d/2 که خیلی کمترازb^d
یا انچه درشکل است می باشد ناحیه دو دایره کوچک
خیلی کمترازناحیه یکی ازدایره بزرگ مرکزی درشروع ووسعت دادن به هدف است
دستورجستججو ابزاری است که به وسیله ان یکی یا هردومانع جستجو درهر گره قبل ازتوسعه
برای دیدن است که اگر این ریشه دردرختهای جستجوی دیگری باشد وهمچنین اگریک راه حل
پیدا شود . برای مثال اگر یک
مساله راه حلی به عمق d=6 داشته باشد
وهرچرخش دستوروسعت اولین جستجو گره دریک زمان سپس درحالت بی ارزش وبه کد دو برخورد
میکنند موقعی که همه توسعه یافتند اما یکی ازگره ها درعمق 3 است برای B=10 درمجموع 2202 گره تولید کند درمقایسه با 1101110100از
اولیه وسیع واستاندارد بررسی گره ازعضویت
دردرختان جستجو می تواند زمان ثابتی را درجدول ترکیبی ایجاد وبه وجود اورد
همچنین پیچیدگی زمانی دردستور جستجوd/2) است سرانجام
یکی ازدرختان جستجو باید درحافظه نگهداری شود همچنین این عضویت می تواند چک وبررسی
شود ازاین رو پیچیدگی ها ی خالی می شود این نیازفضای خالی خیلی مهم وقابل توجه درضعف وسستی دستور جستجو است الگوریتم کامل وتمام است op+imal برای متوقف کردن وثابت ماندن ارزش هردو جستجو ابتدایی وطولانی هستند ترکیبات دیگر
ممکن است کاملا متوقف شوند جداگانه یاهردو با هم کاهش درپیچیدگی زمانی دستورات
جستجو جذاب را ایجاد می کند اما چگونه ما جستجو عقبی کنیم انجام دهیم این به اسانی
صورت نیست اجازه دهید اجداد وریشه های یک گره (n)pred همه این گره ها که n دارند یک جانشین هستند دستور جستجو نیازدارد که pred به طورموثروکافی حساب کند اسانترین حالت زمانی است که
همه فعالیتهای دریک مرحله متوقف شود که قابل نقض است همچنین pred(n)=succدرحالتهای دیگرممکن
است که مهارت اساسی ومهمی نیازباشد .فرض
کنید سئوالاتی که ما معنی می کنیم به وسیله هدف وبرنامه درجستجوی قبلی وپشت زمینه ازهدف
وبرنامه برای 8 جدول وبرای پیداکردن مسیردرromaniaفقط یکه هدف وحالت برنامه وجود دارد بنابراین جستجوی قبلی
خیلی شبیه چستجوی بعدی است اگر چندین حالت لیست برنامه واضح وجو د داشته باشد
دراین مثال 2 حالت برنامه ازاد وشلوغ درشکل 303 سپس ما می توانیم یک حالت برنامه
ساختگی بسازیم که بلافاصله پردازش کند که همه حالتهای برنامه کنونی را شامل است
وپردازش می کند به طوریک درمیان بعضی وتعدادی گره زاید تولید میشود که می توان
ازانها دوری کرد به وسیله دیدن ومشاهد یک سری حالتهای ومراحل برنامه درکی مرحله
جداومفرد . هرکی ازپردازشها
همچنین یک سری مرحله به طورخاص وویژه دارد
که سری مراحل شبیه ومطابق جانشین درسری مراحل برنامه است به فصل 306 نیزنگاه کنید
بیشترین تفاوت واختلاف حالت ومرحله برای دستور جستجو زمانی است که برنامه فقط یک
اشاره توصیفی دربعضی ازسری های بزرگ مراحل برنامه ممکن باشد برای مثال همه مراحل مورد نیاز. ارزش يكسان جستجو : وسعت اولين جستجو ،زمانيكه همه مراحل هزينه ارزش يكساني
دارند ، بهينه مي باشد. زيرا هميشه بسط مي دهد با يك ساده ما مي توانيم الگوريتم
را پس با هر مرحله عملگرد ارزشي بهينه است پيدا كنيم . به جاي بسط دادن ارزش يكسان
جستجو گسترش مي دهد . n را با پائين
ترين هزينه راه توجه داشته باشيد كه اگر همه هزينه مراحل مساوي هستند اين براي
وسعت اولين جستجو . ارزش يكسان جستجو توجهي در مورد تعداد مراحل در راه ندارد . اما فقط در مورد هزينه كلي توجه مي
كند . بنابراين آن متوقف خواهد شد در يك لوپ بي اندازه . اگر آن بسط دهد ند را كه
عملكرد هزينه صفر دارد براي هدايت به عكس براي مرحله مشابه .( به عنوان مثال يك
عملكرد NOOP )
ما مي تونيم تضمين كنيم كامل كننده
اي پس فراهم مي كند هزينه هر مرحله را كه بزرگتر است از و يا اينكه مساوي است با
برخي ثبات هاي مثبت كوچك . اين شرايط همچنين براي انتشار بهينگي كافي مي باشد .
اين بدان معني مي باشد كه هزينه يك راه هميشه افزايش مي يابد به طوري كه ما در راه
پيش مي رويم . از اين دارائي آسان است ديدن اينكه الگوريتم ند ها را گسترش مي دهد
در صورت افزايش هزينه راه . بنابراين اولين هدف ند انتخاب شد براي گسترش يك راه حل
بهينه است . ( به خاطر داشته باشيد كه جستجو سه گانه درخواست مي كند قسمت نهائي را
فقط براي ندي كه براي گسترش انتخاب شده اند.) ما پيشنهاد مي كنيم براي سعي كردن
الگوريتم براي يافتن كوتاه ترين مسير به " پو كارست " ارزش يكسان جستجو بيشتر با هزينه راه هدايت مي شود تا عمق
ها . بنابراين تكامل پيچيدگي آن نمي تواند به آساني توصيف اختصاصي كند در سطوح A وB در عوض اجازه
دهيد كه C هزينه راه حل بهينه باشد و فرض شود كه هر عمل حداقل شامل هزينه E مي شود . سپس
زمان مورد بر الگوريتم و فضاي پيچيدگي O مي باشد [b [c^x/e]]كه مي تواند خيلي بزرگتر از b^d باشد . اين
بخاطر اين است كه ارزش و هزينه يكسان جستجو مي تواند و اغلب انجام مي دهد . كشف
درخت هاي بزرگ از هر مرحله كوچك را بنابراين كشف راه ها شامل بزرگ مي باشد و شايد
مرحله هاي مورد استفاده و مفيد .زمانيكه هزينه همه مرحله ها مساوي است البته b[c^x/e] فقط b^d مي باشد . عمق و عرض اولين جستجو : عمق و عرض اولين جستجو هميشه گسترش مي دهد همينقدر ندها را
در ريشه جاري اولين درخت جستجو . پيشرفت جستجو در شكل 3.12 به تصوير كشيده شده است
. جستجو اقدام مي كند فوراً عميقترين سطوح
درخت جستجو جائيكه ند ها هيچ جانشيني ندارند . همانطور كه آن ند ها در حال گسترش
مي باشند آنها از ريشه گذاري جا مي مانند
. بنابراين سپس جستجو برگشت مي كند و پشتيباني مي كند به ند بعدي كه هنوز جانشين
كشف نشده اي دارد . اين استراژدي مي تواند انجام شود توسط درخت جستجو با يك نمايش آخر- در- اول –خارج(LIFO) همچنين به
عنوان يك استك خمانطور كه يك پيشنهاد به درخت جستجو كامل نمي كند ،آن رايج است به
انجام دادن عمق اولين جستجو با يك بازگشتي عملكرد كه خودش ناميده مي
شود روي هر يك از بچه ها به نوبت . عمق اولين جستجو يك حافظه خيلي فروتني دارد . احتياج به
ذخيره فقط يك راه ساده از ريشه يك ند برگي . همراه با ند هاي هم نشود باقيمانده
براي جستجوي ند در راه – زمانيكه يك ند كشف
شده است ، آن مي تواند از ميان بر داشته
شود از حافظه به محض اينكه نسل ها بطور كامل گسترش يافته باشند – ( شكل 3.12 ) براي
يك فضاي واحد با عامل شاخه اي B و حداكثر عمق M عمق اولين جستجو
نياز به ذخيره سازي ند BM+1 دارد .
استفاده كردن از همان فرضيه در شكل 3.11 و فرض اينكه ند ها در عمق يكساني قرار
دارند بعنوان اينكه ند نهائي هيچ جانشيني ندارد و ما متوجه مي شويم كه عمق اولين
جستجو مورد نياز واقع مي شده 118 كيلو بايت بجاي 10 پتا بايت در عمق D=12 يك عامل از 10 بيليون دفعه فضاي كمتر . شكل 3.12 : عمق اولين جستجو روي يك درخت باينري ند هائي كه
گسترش يافته اند و هيچ نسلي ندارند در ريشه گذاري مي تواند از حافظه حذف شود .
اينها با ند هاي سياه نشان داده شده اند . ند هاي در عمق 3 فرض مي شوند به نداشتن
هيچ جانشيني و AF فقط ند نهائي است . يك تنوع و گوناگوني عمق اولين جستجو جستجوي " بك
تركينگ " ناميده مي شود كه هنوز حافظه كمي استفاده مي كند . در اين سيستم فقط
يك جانشين عموميت داده مي شود در يك زمان از همه جانشين ها هر چند ند گسترش يافته
است كه جانشين عمومي بعدي مي باشد . در
اين روش فقط حافظه O(M) مورد نياز است
در عوض O( BM ) . جستجو بك
تركينگ آسان مي كند يك حافظه ديگري را . درا بك عمق اولين جستجو آنست كه مي تواند يك انتخاب اشتباه
كند و يك مسير طولاني را در پيش بگيرد زمانيكه انتخاب متفاوت وجود دارد براي حل .
ريشه درخت جستجو اگر ند J يك ند نهائي بود ، سپس عمق جستجوي اولين بر مي گرداند آن
را بعنوان اولين راه حل . از اين جهت كه عمق اولين جستجو بهينه نيست . پازل شماره 8 ، مربوط به پازل هاي بلوكي متحرك مي شود . پس
اغلب به خاطر مشكلات تستي براي جستجوي جديد الگوريتم در A1 ، استفاده مي شوند . اين كلاس عمومي به كامل بودن NP ، مشهور است .
بنابراين براي يافتن روشهاي قابل توجهي بهتر در بدترين نمونه از جستجوي الگوريتم
هاي توصيف شده در اين بخش و متن انتظار نمي رود . پازل شماره 8
، 440،181=!9 ، به بخشها دسترسي دارد و به آساني حل مي شود .
پازل شماره 15 ( در يك صفحه 4×4 ) حدود 103 تريليون بخش دارد و موارد اتفاقي
ميتواند حل شود به صورت بهتر در صدم هاي ثانيه بوسيله بهترين جستجوي الگوريتمي .
پازل شماره 24 ( روي صفحه 5×5 ) حدود 1025 بخش دارد و موارد اتفاقي هنوز خيلي مشكل است براي بهتر حل كردن ماشين ها و الگوريتم هاي
اخير و در جريان . هدف مشكل 8 ملكه ، جاي دادن 8 ملكه روي يك صفحه شطرنج مي
باشد . به طوري كه هيچ ملكه اي به ديگري حمله نكند . ( يك ملكه به هر بخش در هر
رديف . بخش و شماره مشابه حمله مي كند ) شكل 5-3 يك راه حل سع شده نشان مي دهد ،
كه مردود شد . ملكه در راست ترين بخش توسط ملكه اي كه در بالاترين قسمت چپ قرار
دارد ، مورد حمله قرار مي گيرد . اگر چه بخصوص كافي الگوريتم باقي مي ماند براي اين مشكل و
همه ي خانواده ملكه ها ، بعنوان يك مشكل تستي جالب براي جستجوي الگوريتم . 2 نوع
اصلي فرمول وجد دارد . يك فرمول افزايشي
پس عمل كننده ها در مي گيريد و هر حركت و عمل اضافي مي كند يك ملكه به بخش . دوم
فرمول بخش كامل . با 8 ملكه شروع مي
شود روي صفحه و آنها را به اطراف حركت مي دهد . در همان مورد ، هزينه ي راه جالب
نيست . چونكه بخش پاياني به حساب مي آيد . اولين فرمول افزايشي پس يكي بايد امتحان
و اجرا كند . شامل موارد زير مي شود : 1-
بخش ها : هر ترتيب و تركيب ملكه ها از
0 تا 8 عدد روي صفحه را يك بخش است . 2-
بخش ها ابتدائي : هيچ ملكه اي روي صفحه نيست . 3-
عملكردهاي جانشيني : به هر خانه يك ملكه
اضافه مي كنيم . 4-
تست نهائي : 8 ملكه روي صفحه قرار دارد و هيچ حمله اي در كار نيست . عملكردهاي نهائي : اين به بخش هاي مجاز عموميت مي بخشد .پس
نتيجه اي است از انجام 4 عملكرد ( حركتهاي
خالي به چپ و راست ، بالا و پائين ) تست نهائي : اين بخش چك مي كند پس آيا بخش مطابقت مي كند با
وضعيت نشان داده شده در شكل شماره 3.4 ( هدف هاي ديگر ممكن مي باشد ) هزينه راه : هر بخش يك هزينه دارد ، بنابراين هزينه راه ،
تعداد بخش ها در راه مي باشد . چه مواردي ما در اينجا در بر داشته ايم ؟ عملكرد خلاصه شده
، به شروع آنها و بخش نهائي . ناديده شدن مكان هاي مياني ، جائي كه بلوك متحرك است
. ما خلاصه كرده ايم عملكردهائي را مثل
لرزش صفحه ، زمانيكه تكه ها نصب شده اند يا بيرون كشيدن تكه ها را با چاقو و آنها
را دوباره برگرداندند . ما با يك توصيف از قانون هاي پازلي باقي مانده ايم . با
اجتناب كردن از انجام هاي مهارتي فيزيكي .
این وبلاگ جهت ایجاد تعامل بین اساتید و دانشجویان کامپیوتر و مشتریان نرم افزار طراحی و ساخته شده است.(نمایندگی نرم افزارهای حسابداری نوین و حسابداری هوشمند نوین)
