جستجو در هوش مصنوعی چه انواعی دارد؟

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

مهم‌ترین پیشرفت‌ها در بخش جستجو به دلیل تغییر تکنیک‌های این حوزه رخ می‌دهند. با افزایش آگاهی از توانایی‌های مغز انسان، امکان پیدایش الگوریتم‌های پیچیده بیشتری وجود دارد که کارآمدتر باشند.

این مقاله به منظور آشنایی با پایه و اساس الگوریتم‌های مختل. به بررسی انواع جستجو در هوش مصنوعی می‌پردازد. با دانستن و درک آن‌ها شاید توانایی خلق این الگوها در ذهن شما افزایش یابد و منجر به خلق نوع جدیدی از آن‌ها شود.

انواع جستجو در هوش مصنوعی را بشناسید

در بازی‌های فکری مانند چیدن آجرهای ۳×۳ یا بیشتر از چالش‌های مسیریابی تک‌بعدی استفاده می‌شود. در این بازی‌ها فضای افقی و عمودی با توجه به تعداد کاشی‌های در دسترس پر می‌شود تا جایی که فضای مورد نظر کاملا پر شده و امتیاز دریافت شود. مکعب روبیک نیز در این قاعده مسیریابی قرار می‌گیرد.

در هنگام جستجو مشکلات متفاوتی بر سر راه قرار دارند که آشنایی با آنها کمک می‌کند در استفاده از انواع روش‌های جستجو، آگاهانه اقدام کنید. مانند:

• فضای جستجو؛ مجموعه‌ای از تمام حالت‌های ممکن که قادر به انتخاب آن‌ها هستید.
• حالت شروع؛ یعنی جستجو در چه حالتی شروع می‌شود.
• آزمایش هدف؛ عملی که در نظر به جای توجه به هدف، حالت فعلی در نظر گرفته می‌شود.

راه‌حل برطرف سازی این مشکلات در مجموعه‌ای از اقدامات نهفته است که به آن‌ها نقشه یا برنامه گفته می‌شود. این نقشه‌ها حالت‌های ممکن و سریع را در انتقال از نقطه ابتدایی و رسیدن به هدف نشان می‌دهند.

الگوریتم‌های جستجو از دل این نقشه‌ها متولد می‌شوند. انواع جستجو در هوش مصنوعی در سه طبقه‌بندی جستجوی ناقص (Uninformed Search)، جستجوی کامل (Informed Search) و جستجوی محلی (Local Search) قرار می‌گیرد. هر کدام از آنها خود دارای دسته‌بندی‌های جزیی‌تر هستند که در ادامه به آ‌ن‌ها اشاره می‌کنیم.

جستجو در هوش مصنوعی از نوع Uninforemed

در این بخش الگوریتم‌ها جز در مورد گروه هدف و آنچه در تعریف مسئله ذکر شده است، اطلاعات دیگری را ارایه نمی‌دهند. در این حالت، نقشه راه در رسیدن به هدف از نقطه شروع تنها در دستور یا طول اقدامات تفاوت دارد. این نوع جستجو به جستجوی کور نیز شناخته می‌شود. انواع روش ها در این بخش عبارتند از:

1. عمق اول جستجو (Depth First Search ) یا DFS
2. عرض اول جستجو ( Breadth First Search ) یا BFS
3. هزینه یکنواخت جستجو (Uniform Cost Search) یا UCS

هر کدام از انواع جستجو در هوش مصنوعی در الگوریتم‌های زیر مشترک هستند.

• گراف مشکل در گره شروع S و گره هدف یا پایانی G؛
• استراتژی که شامل نحوه طی کردن گراف به منظور رسیدن به هدف G است؛
• حاشیه که به منظور ذخیره‌سازی تمام مسیرهای ممکن که از حالت کنونی به سمت G وجود دارد و توسط ساختار داده‌ها انجام می‌شود.
• درختی که در هنگام رسیدن به گره هدف مرحله به مرحله ایجاد می‌شود.
• نقشه یا برنامه راه‌حل که دنباله‌ای میان گره‌های S و G است.

عمق اول جستجو DFS

الگوریتمی است که به منظور عبور، تشکیل درخت جستجو یا ساختار داده گراف، ایجاد می‌شود. از گره S شروع و تا آنجا که امکان دارد در امتداد هر شاخه از درخت کاوش می‌کند. البته انتخاب برخی گره‌ها به عنوان شروع در گراف به صورت دلخواه انجام می‌شود.

مثال

در تصویر زیر با روش DFS چه حالت‌هایی به منظور جابه‌جایی و رسیدن از نقطه S به G وجود دارد؟

DFS در گراف بالا در درخت جستجو همواره عمیق‌ترین شاخه را به منظور رسیدن به هدف انتخاب می‌کند. بعد از اتمام کل گره‌های آن شاخه به شاخه بعد می‌رود. یعنی ابتدا از S به A می‌رود، سپس به B رفته و به جای انتخاب شاخه مستقیم‌تر، شاخه با گره C را انتخاب می‌کند و به هدف می‌رسد. در حالی که حتی راه آسان‌تری تنها بعد از گره S و با گذر از گره D جهت رسیدن به نقطه D وجود داشته است.

عرض اول جستجو BFS

این روش یکی از انواع جستجو در هوش مصنوعی به شمار می‌رود که در آن یک الگوریتم جهت عبور، جستجو در درخت یا ذخیره‌سازی ساختار داده‌های گراف ایجاد می‌شود.

کاوش از ریشه درخت یا گره‌های دلخواه که بستگی به کلید جستجو دارد، شروع می‌شود. قبل از حرکت، تمام گره‌های همسایه در عمق موجود بررسی می‌شوند. سپس حرکت به سمت بقیه گره‌ها در عمق‌های دیگر انجام می‌شود.

مثال

به عنوان مثال تصویر قبل را در نظر بگیرید. در روش BFS چه راه‌حلی به منظور حرکت از S و رسیدن به نقطه G وجود دارد؟

با توجه به آنچه در خصوص این روش بیان شد، کم‌عمق‌ترین شاخه به منظور رسیدن به هدف در این روش جستجو انتخاب می‌شود. یعنی ممکن است تمام شاخه‌ها تا انتها طی شود که کوتاه‌ترین مسیر مشخص شود.

بنابراین با توجه به تصویر اول و نکات گفته شده، شروع فرآیند از S، عبور از گره D و در نهایت رسیدن به نقطه G، راه‌حلی است که این روش برمی‌گزیند.

هزینه یکنواخت جستجو UCS

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

زبان دیگر معرفی UCS به شکل زیر نیز انجام می‌شود.

  cost(node) = cumulative cost of all nodes from root

  cost(root) = 0

مثال

نمونه قابل درک در این بخش سوالی است که در ابتدا به دنبال راه‌حل آن‌ها در شیوه‌های مختلف پرداخته شد. حال دوباره سوال یافتن بهترین راه جهت رسیدن از نقطه S به G مطرح می‌شود. در تصویر زیر هزینه عبور از هر گره مشخص شده است.

بنابراین بر اساس استراتژی روش UCS شاخه‌ای که در آن مجموعه گره‌ها کمترین هزینه را ایجاد کنند، انتخاب می‌شود. کاوش شروع شده و آنقدر تکرار می‌شود که منجر به انتخاب مسیر SABG می‌شود. هزینه‌ی نهایی این مسیر ۵ است.

جستجو در هوش مصنوعی از نوع Informed Search

در روش‌های بکاررفته در این نوع جستجو، الگوریتم‌هایی که اطلاعات هدف را در بردارند طراحی و اجرا می‌شوند. بنابراین جستجو به صورت کارآمدتری اتفاق می‌افتد. با بکارگیری یک روش اکتشافی یا heuristic جمع‌آوری اطلاعات در الگوریتم صورت می‌گیرد.

مواردی که ادامه نام برده و تعریف می‌شوند از الگوریتم‌های موجود در این دسته قرار می‌گیرند:

• جستجوی حریص (Greedy Search)
• جستجوی درخت A^* (A* Tree Search)
• جستجوی گراف A^* (A* Graph Search)

جستجوی اکتشافی از انواع جستجو در هوش مصنوعی است که کامل بوده و در این روش تخمین زده می‌شود که کدام مسیر به هدف نزدیک‌تر است.

به عنوان نمونه انتخاب نزدیک‌ترین مسیر بین دو شهر در هنگام سفر کمک می‌کند که زمان کمتری را در راه سپری کنید. در ادامه به بررسی نمونه‌های گفته شده می‌پردازیم.

جستجوی حریص یا GS

GS یکی از انواع جستجو در هوش مصنوعی است که توجه خود را در گره‌های نزدیک به گره هدف متمرکز می‌کند. این نزدیکی توسط کمیتی به نام heuristic تخمین زده و با h نشان داده می‌شود. هر چه مقدار این پارامتر کمتر باشد یعنی گره انتخاب شده به هدف نزدیک‌تر است.

بنابراین استراتژی این جستجو گزینش گره‌ها با پایین‌ترین مقدار h خواهد بود. به عنوان مثال به تصویر زیر توجه کنید، ابتدا با توجه به میزان h هر گره مسیر مناسب رسیدن از نقطه S به G را به روش GS تعیین کنید.

از نقطه S شروع و گره D را به دلیل h پایین‌تر نسبت به A انتخاب می‌کنیم. سپس با در نظر گرفتن مقادیر h، گره E بهترین گزینه پیش روی شما است. بنابراین به راحتی از E به هدف خود می‌رسید.

جستجوی درخت A*

ترکیب روش‌های جستجوی هزینه یکنواخت UCS با جستجوی حریص GS از نقاط قوت آن به حساب می‌آید. جمع کمیت g، هزینه جستجو، و h، عامل جدیدی را به نام f ایجاد می‌کند.

h در اینجا «هزینه پیش رو» نامیده می‌شود و مانند حالت قبل مسئولیت برآورد فاصله بین گره‌ها را با گره هدف بر عهده دارد. g نیز هزینه عقب‌مانده در نظر گرفته می‌شود و نشان‌دهنده‌ی هزینه تجمعی گره‌ها از گره G است.

این نوع جستجو زمانی بهترین عملکرد را خواهد داشت که h به منظور رسیدن به هدف، در تمام گره‌ها از هزینه‌های واقعی h^*، کمتر باشد. این ویژگی در A* با نام مقبولیت (admissibility) شناخته می‌شود. بنابراین استراتژی این روش یافتن گره‌ای با کمترین مقدار f است.

بنابراین با در نظر گرفتن تمامی عوامل، مسیر SDBEG با h=7 بهترین گزینه در این روش جستجو است.

جستجوی گراف A^*

جستجوی درخت A^* از انواع جستجو در هوش مصنوعی است که عملکرد خوبی دارد. به جز در زمان‌هایی که امکان بروز کاوش مجدد در شاخه‌های بررسی شده پیش می‌آید. این حالت هنگامی اتفاق می‌افتد که گره‌ای تکراری دو بار در شاخه‌های مختلف بسط داده می‌شود.

بنابراین ممکن است جستجو به طور مجدد در هر دو شاخه انجام و سبب اتلاف وقت شود. در جستجو به شیوه گراف A^* این عوامل را با اضافه کردن یک قانون حذف می‌کنند. طبق این قانون امکان بسط گره‌های مشابه بیش از یک بار وجود نخواهد داشت.

کمیت h در این شیوه زمانی بیشینه است که تفاوت هزینه‌های پیش رو h در بین دو گره A و B، کمتر یا برابر با کمیت g در هنگام رفتن از مسیر دو گره باشد. این ویژگی در شیوه جستجوی گراف A* با نام سازگاری (consistency) شناخته می‌شود. بنابراین شرطی که باید در نظر قرار داد، به شکل زیر بیان می‌شود:

به مثال قبل برگشته و با در نظر گرفتن تصویر، مسیر مناسب را با روش ذکر شده جستجو کنید. حل این سوال درست مانند شیوه قبل ولی با دقت بیشتری انجام می‌شود. حواس خود را متمرکز کرده و از بررسی دوباره گره‌های تکراری اجتناب کنید.

به روشنی خواهید دریافت که باز هم مسیر SDBCEG با هزینه ۷ راه‌حل جستجوی شما است.

جستجوی محلی Local

یکی از انواع جستجو در هوش مصنوعی LSA یا الگوریتم‌های جستجوی محلی است. این شیوه با دیدی آینده‌نگرانه شروع به فعالیت کرده و در نهایت یک راه‌حل محلی را انتخاب می‌کند. این شیوه قادر است حتی در صورت قطع ناگهانی فعالیت، راه‌حل معتبری را در هر زمان و قبل از اتمام بازگرداند.

انواع روش‌های موجود در این دسته بندی عبارتند از:

• تپه نوردی جستجو Hill-Climbing Search
• شعاع محلی جستجو Local Beam Search

تپه نوردی جستجو Hill-Climbing

این روش با بهره‌گیری از یک الگوریتم تکرار و بازگویی است که با یک راه‌حل دلخواه شروع می‌شود. بنابراین در ادامه روند خود سعی دارد که با استفاده از تغییر بخشی از راه‌حل فرضی، پاسخ سوال را پیدا کند. اگر این فرآیند تغییر منجر به راه‌حل بهتری شود، اضافه کردن این تغییر اضافی به عنوان جواب در نظر گرفته می‌شود.

بنابراین این روند تا زمانی که دیگر هیچ امید پیشرفتی وجود نداشته باشند، تکرار خواهد شد. با توجه به کد زیر، تابع تپه نوردی جستجو، رسیدن به ماکزیمم محلی معنا می‌شود. معایب این شیوه، کامل و بهینه نبودن الگوریتم آن است.

inputs: problem, a problem

local variables: current, a node

                 neighbor, a node

current <-Make_Node(Initial-State[problem])

loop

   do neighbor <- a highest_valued successor of current

      if Value[neighbor] ≤ Value[current] then

      return State[current]

      current <- neighbor

end

شعاع محلی جستجو Local Beam

در این الگوریتم تعداد حالت‌های k، در هر زمانی ایجاد می‌شوند. به عنوان نمونه در نقطه ابتدایی، انتخاب حالت به طور تصادفی صورت می‌گیرد. همچنین عملکرد آن‌ها به کمک توابع عینی بررسی می‌شود. اگر هر حالتی به مقدار بیشینه خود رسیده باشد، الگوریتم توقف خواهد کرد.

در غیر این صورت، حالت‌ها در مخزنی مانند استخر قرار می‌گیرند. بنابراین مخزن به طور عددی طبقه‌بندی شده و بالاترین حالت k به عنوان مقدار اولیه انتخاب می‌شود. این فرآیند تا زمانی که مقدار ماکزیمم حاصل نشود، ادامه می‌یابد.

در زیر کد شعاع محلی، بیان‌کننده یک پاسخ به منظور حل مشکل است.

کلام آخر

با توجه به موارد گفته شده با هردو الگوریتم DFS و BFS از انواع جستجو در هوش مصنوعی به مشکل خواهید برخورد. زیرا در صورت وجود نقشه‌های بزرگ‌تر و با گره‌های بیشتر، این الگوریتم‌ها عملکرد مناسبی ندارند. زیرا در روش DFS به دنبال شاخه‌های عمیق می‌گردد و زمان زیادی را صرف جستجو خواهد کرد که منجر به ایجاد فضای بیشتر ذخیره داده‌ها می‌شود.

همچنین روش BFS به دنبال کوتاه‌ترین شاخه از درخت می‌گردد که در گراف‌های بزرگ زمان زیادی صرف شده و ممکن است فضای حاشیه بیشتر از حد قابل قبول شود.

انواع جستجو در هوش مصنوعی مانند جستجوی حریص یا درخت و گراف A^* با ترکیب UCS ایجاد شده‌اند. البته گراف A^* به دلیل جلوگیری از بررسی مجدد گره‌های تکراری دارای ویژگی‌های بهینه‌تر و سرعت مناسب‌تری است.

با این حال در برخی بازی‌ها از روش‌های جستجوی محلی مانند تپه نوردی Hill-Climbing و شعاع محلی Local Beam استفاده می‌شود. مطالب این مقاله به بیان انواع جستجو در هوش مصنوعی و معایب و مزایای هر شیوه پرداخته است.