Search algorithms in Artificial Intelligence - Depth-first search (DFS)

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph.

A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Trémaux as a strategy for solving mazes.
In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with either discrete or continuous values.

Although search engines use search algorithms, they belong to the study of information retrieval, not algorithmics.

The appropriate search algorithm often depends on the data structure being searched, and may also include prior knowledge about the data. Search algorithms can be made faster or more efficient by specially constructed database structures, such as search trees, hash maps, and database indexes.

search algorithms are algorithms which solve the search problem, namely, to retrieve information stored within some data structure, or calculated in the search space of a problem domain, either with discrete or continuous values.

Based on the search problems we can classify the search algorithms into uninformed (Blind search) search and informed search (Heuristic search) algorithms.

In Artificial Intelligence, Search techniques are universal problem-solving methods. Rational agents or Problem-solving agents in AI mostly used these search strategies or algorithms to solve a specific problem and provide the best result. Problem-solving agents are the goal-based agents and use atomic representation. In this topic, we will learn various problem-solving search algorithms.

Search Algorithm Terminologies:
A search problem can have main factors:
• Search Space: Search space represents a set of possible solutions, which a system may have.
• Start State: It is a state from where agent begins the search.
• Goal test: It is a function which observe the current state and returns whether the goal state is achieved or not.
Objective functions: to determine the movements.


خوارزميات البحث في الذكاء الاصطناعي - بحث بالعمق أولا

بحث العمق أولاً هي خوارزمية لاجتياز أو البحث في شجرة أو هياكل بيانات الرسم البياني. تبدأ الخوارزمية في العقدة الجذرية (اختيار بعض العقد التعسفية كعقدة جذر في حالة الرسم البياني) وتستكشف قدر الإمكان على طول كل فرع قبل التراجع. هناك حاجة إلى ذاكرة إضافية ، عادةً ما تكون مكدسًا ، لتتبع العقد المكتشفة حتى الآن على طول فرع معين مما يساعد في التراجع عن الرسم البياني.

تمت دراسة نسخة من البحث المتعمق أولاً في القرن التاسع عشر بواسطة عالم الرياضيات الفرنسي تشارلز بيير تريمو كاستراتيجية لحل المتاهات.

في علوم الكمبيوتر ، تعد خوارزمية البحث خوارزمية مصممة لحل مشكلة البحث. تعمل خوارزميات البحث على استرداد المعلومات المخزنة ضمن بنية بيانات معينة ، أو محسوبة في مساحة البحث في مجال المشكلة ، إما بقيم منفصلة أو مستمرة.

على الرغم من أن محركات البحث تستخدم خوارزميات البحث ، إلا أنها تنتمي إلى دراسة استرجاع المعلومات ، وليس الخوارزميات.

غالبًا ما تعتمد خوارزمية البحث المناسبة على بنية البيانات التي يتم البحث عنها ، وقد تتضمن أيضًا معرفة مسبقة بالبيانات. يمكن جعل خوارزميات البحث أسرع أو أكثر كفاءة من خلال هياكل قواعد البيانات المُنشأة خصيصًا ، مثل أشجار البحث وخرائط التجزئة وفهارس قواعد البيانات.

خوارزميات البحث هي خوارزميات تحل مشكلة البحث ، وهي استرداد المعلومات المخزنة ضمن بعض هياكل البيانات ، أو المحسوبة في مساحة البحث في مجال المشكلة ، إما بقيم منفصلة أو مستمرة.

بناءً على مشكلات البحث ، يمكننا تصنيف خوارزميات البحث إلى خوارزميات البحث غير المستنير (البحث الأعمى) والبحث المستنير (البحث الإرشادي).

في الذكاء الاصطناعي ، تعتبر تقنيات البحث طرقًا عالمية لحل المشكلات. استخدم الوكلاء العقلانيون أو وكلاء حل المشكلات في الذكاء الاصطناعي في الغالب استراتيجيات أو خوارزميات البحث هذه لحل مشكلة معينة وتقديم أفضل نتيجة. عوامل حل المشكلات هي العوامل القائمة على الهدف وتستخدم التمثيل الذري. في هذا الموضوع ، سوف نتعلم العديد من خوارزميات البحث لحل المشكلات.

مصطلحات خوارزمية البحث:
يمكن أن يكون لمشكلة البحث عوامل رئيسية:
• مساحة البحث: تمثل مساحة البحث مجموعة من الحلول الممكنة ، والتي قد يكون لدى النظام.
• حالة البدء: وهي حالة يبدأ منها الوكيل البحث.
• اختبار الهدف: وهي وظيفة تراقب الوضع الحالي وترجع ما إذا كانت حالة الهدف قد تحققت أم لا.
الوظائف الموضوعية: تحديد الحركات.