چکیده:
امروزه تنوع و گستردگی مسائل در شاخههای گوناگون علوم تا حد بسیار زیادی افزایش یافته است و یافتن پاسخ برای چنین مسائلی در مدت زمان کم، چالشی بسیار اساسی محسوب میشود. استفاده از هوش مصنوعی میتواند فرآیند حل مسائل پیچیده را تا حد قابل قبولی سرعت بخشیده و زمان پاسخدهی را به نحو محسوسی کاهش دهد. مسأله تعقیب و گریز از جمله مسائلی است که میتواند دارای سطح بالایی از پیچیدگی باشد. از جمله عوامل ایجاد پیچیدگی میتوانیم به تعداد عوامل درگیر، برد میدان دید اعضاء و موانع موجود در زمین بازی اشاره کنیم. تاکنون الگوریتمهای گوناگونی برای حل مسأله تعقیب و گریز ارائه شده که هر یک دارای نقاط ضعف و قوت خود هستند. در این مقاله با استفاده از الگوریتم هندسه زبانشناختی، به بررسی بازی تعقیب و گریز بطور خاص در یک مسأله با ابعاد زمین بازی 9×9 و برای بررسی تعمیم کارایی الگوریتم در مسائلی با ابعاد مختلف پرداخته شده است. نشان داده شده که این رهیافت میتواند بیش از 90% بهبود در سرعت پاسخیابی ایجاد کند. در این مقاله عوامل مؤثر در واقعگرایی بازی تعقیب و گریز با دقت بیشتری در هندسه زبانشناختی بررسی میشوند و در نهایت با سادهسازی فضای مسأله به تعدادی زیر فضا که در آن گشتهای حرکت هر عامل بازی مشخص است، اقدام به حل مسأله میکنیم. نشان میدهیم علیرغم پیچیدهتر شدن فضای مسأله، الگوریتم هندسه زبانشناختی بهبودی در حدود 91% نسبت به سایر الگوریتمها ایجاد میکند.
Nowadays, the diversity and expansions of problems in various branches of science has greatly increased and finding the answer to such problems in a short period of time is considered as a very essential challenge. Using artificial intelligence can significantly accelerate the solving process for complex problems and considerably reduce the response time. The pursuit-evasion problem is one of the problems that can have a high level of complexity due to the nature of the factors involved. Factors causing complexity include the number of factors involved, the range of member’s vision and barriers exist on the playground. Various algorithms have been proposed to solve the pursuit-evasion problem so far, each has its own strengths and weaknesses. In this paper, the pursuit-evasion game is examined by using the linguistic geometry algorithm specifically in a problem with 9×9 playground dimensions and to examine the generalization of the algorithm's performance in problems with different dimensions. It has been shown that this approach can improve the response speed by more than 90%. In this work, the factors affecting the realism of the pursuit-evasion game are examined more carefully in linguistic geometry and finally the problem is solved by simplifying the problem space to a number of subspaces in which the movement paths of each element of the game are clear. We show that, despite the problem space became more complex, the linguistic geometry algorithm creates about 91% improvement over the other algorithms.
خلاصه ماشینی:
دوپرسش بنياديدرمسائل تعقيب وگريزعبارتنداز(٢٠٠٩ ,Bonato): ١-کمينه تعداد تعقيب کننده براياطمينان از اين که الگوريتم ارائه شده همگرا شودچه تعداد است ؟ ٢-مناسب ترين استراتژيحرکت والگوريتم برايدستيابيبه نتيجه درکمترين زمان چيست ؟ نشان داده شده است که اگردربازيدزدوپليس تعداددزدها١وتعدادپليس ها٢باشد، الگوريتم حتما همگرااست (٢٠٠٤ ,Alspach).
در اين مقاله ،به بررسيپرسش دوم پرداخته شده است به نحويکه ،ابتدابه حل مسأله تعقيب وگريزدرحالت تعميم نيافته بااستفاده از روش هايکمينه بيشينه ١،هرس آلفا-بتا٢وهندسه ي زبان شناختي ٣ميپردازيم ونتايج آنهارا با يکديگر مقايسه ميکنيم .
در هندسه زبان شناختي يک سيستم پيچيده (به عنوان مثال ، يک بازيدرگراف )به صورت رشته زيرنمايش داده ميشود: برايروشن شدن تعاريف ،مثال ساده ايازمسأله دزدوپليس درشبکه ي ٥×٥درشکل (١) نشان داده شده است .
(به تصوير صفحه مراجعه شود) شکل (٢) نمايش گرافيکي يک انتقال (گذار) سلسله مراتب زبان هاي رسمي در هندسه زبان شناختي ، سلسله مراتب زيرسيستم ها به عنوان سلسله مراتب زبان هاي رسمينمايش داده ميشود.
در شکل (٤)، يک روش معمول برايحل مسأله توسط هندسه زبان شناختيکه از پايين سمت چپ شروع ميشودو در بالا سمت راست به پايان ميرسدنشان داده شده است .
Stilman زبان جستجو و زبان تبديل مفهوم جستجو در هندسه زبان شناختي يک "ساختار"است ، به اين مفهوم که بر خلاف بسيارياز روش هايموجود،کل يافضايکوچکترشده ايراجستجونميکند( & Stilman ٢٠٠٢ ,Yakhnis).
(به تصوير صفحه مراجعه شود) شکل (٧) نوع کارکرد روش هرس آلفا-بتا در کمينه بيشينه (٢٠١٦ ,Kopec) توسعه و حل مسأله مطالعات پيشين رويهندسه زبان شناختي،نشان داده است که اين روش درحل برخياز مسائل مرتبط با بازيهايتخته ايانتزاعي ١،نسبت به ساير روش ها عملکرد بهتري دارد.