يا جماعة الخير، السلام عليكم ورحمة الله.
اسمحوا لي اليوم أن آخذكم في رحلة إلى الماضي القريب، إلى أحد المشاريع التي كادت أن تصيبني بالجلطة لولا لطف الله ثم ومضة من ذكاء الخوارزميات. كنا نعمل على تطوير نظام ملاحة لروبوت صغير ذاتي القيادة، مهمته توصيل الطرود داخل حرم جامعي كبير ومُعقّد. الفكرة كانت بسيطة، لكن الشيطان يكمن في التفاصيل، والتفاصيل هنا كانت “إيجاد أقصر وأسرع طريق”.
في البداية، وبكل سذاجة المبتدئين، قلنا: “بسيطة، بنستخدم خوارزمية بحث عادية زي الـ Breadth-First Search (BFS)”. وهكذا كان. أطلقنا الروبوت في بيئة المحاكاة، وأعطيناه أمراً بالانتقال من نقطة “أ” إلى نقطة “ب”. ما حدث بعد ذلك كان كوميدياً ومأساوياً في آنٍ واحد. بدأ الروبوت المسكين بالتحرك بشكل منهجي، مستكشفاً كل ممر وكل زاوية وكل تقاطع بنفس الأهمية، تماماً كشخص أعمى يتلمس طريقه في متاهة. إذا كان الهدف على يمينه، لكن هناك ممر طويل على يساره، كان يذهب ليستكشف الممر الأيسر بأكمله قبل أن يفكر حتى بالالتفات يميناً. كان المنظر مُحبطاً، والروبوت يبدو وكأنه “تايه في الطوشة” كما نقول بالعامية. كان يجد الطريق في النهاية، لكن بعد وقت طويل جداً وأداء كارثي.
في ذلك اليوم، ونحن نراقب المحاكاة الفاشلة، شعرتُ بذلك الإحساس الذي يعرفه كل مبرمج: جحيم البحث الأعمى. كنا نسير في كل الطرق الممكنة، على أمل أن نصل بالصدفة. هنا أدركت أننا بحاجة إلى “بصيرة”، بحاجة إلى شيء يخبر الخوارزمية: “يا عمي، الهدف من هناك، ركّز بحثك في ذلك الاتجاه!”. وهنا دخلت البطلة الحقيقية لقصتنا: خوارزمية A*.
لماذا البحث الأعمى كارثة حقيقية؟
قبل أن نغوص في تفاصيل A*، دعونا نفهم عدونا جيداً. خوارزميات البحث الأعمى (Blind Search) مثل البحث بالعرض أولاً (BFS) والبحث بالعمق أولاً (DFS) تُسمى “عمياء” لسبب وجيه: هي لا تملك أي معلومة عن الهدف سوى موقعه النهائي.
- BFS: تتوسع بشكل دوائر متحدة المركز من نقطة البداية. ستجد أقصر مسار من حيث “عدد الخطوات”، لكنها تتجاهل “تكلفة” هذه الخطوات. وهي تستكشف كل شيء على مسافة خطوة واحدة، ثم كل شيء على مسافة خطوتين، وهكذا. هذا يؤدي إلى استكشاف هائل لمناطق لا علاقة لها بالهدف.
- DFS: تغوص في مسار واحد حتى تصل إلى طريق مسدود، ثم تعود خطوة للوراء وتجرب مساراً آخر. هي سريعة في إيجاد أي حل (ليس بالضرورة الأقصر) ولكنها قد تتوه في مسارات طويلة جداً قبل أن تجد الطريق الصحيح.
تخيل أنك تبحث عن محل في سوق كبير. البحث الأعمى يعادل أن تبدأ من المدخل وتدخل كل محل في كل ممر بالترتيب، على أمل أن تجد محلك المنشود. طريقة تضمن لك إيجاده، لكنها ستستهلك يومك كله!
محاولة أولى للتحسين: خوارزمية Dijkstra
بعد فشلنا مع البحث الأعمى، كانت الخطوة المنطقية التالية هي استخدام خوارزمية Dijkstra. تُعتبر Dijkstra تطوراً كبيراً، فهي ليست “عمياء” تماماً، بل “حذرة”.
الفكرة الأساسية في Dijkstra هي أنها دائماً تستكشف المسار ذا التكلفة الأقل من نقطة البداية. هي تحتفظ بقائمة من العُقد (التقاطعات) التي لم تتم زيارتها بعد، وفي كل خطوة تختار العقدة التي يمكن الوصول إليها بأقل تكلفة إجمالية من البداية.
هذا رائع، أليس كذلك؟ نعم، لكنه ليس كافياً. مشكلة Dijkstra أنها لا تزال تفتقر إلى “الإحساس بالاتجاه”. قد تستمر في استكشاف مسارات رخيصة وقصيرة في الاتجاه المعاكس تماماً للهدف، فقط لأن تكلفتها الحالية من نقطة البداية منخفضة. هي مثل سائق يصر على سلوك الطرق الريفية القصيرة حتى لو كانت تأخذه بعيداً عن وجهته النهائية.
في مشروع الروبوت، تحسن الأداء قليلاً مع Dijkstra، لكن الروبوت كان لا يزال يقوم بحركات غير منطقية، مستكشفاً مناطق بعيدة عن الهدف قبل أن يلتفت أخيراً إلى الطريق الصحيح.
اللمسة السحرية: خوارزمية A* (A-Star)
وهنا يأتي دور A*. هذه الخوارزمية هي ببساطة عبقرية. لقد أخذت فكرة Dijkstra الذكية (النظر في التكلفة الفعلية من البداية) وأضافت إليها “لمسة سحرية”: تقدير تقريبي للتكلفة المتبقية للوصول إلى الهدف. هذا التقدير يسمى “الاستدلال” أو الـ Heuristic.
المعادلة التي غيرت كل شيء: f(n) = g(n) + h(n)
هذه المعادلة البسيطة هي قلب وروح خوارزمية A*. دعونا نفصّلها ببساطة:
g(n): هي التكلفة الفعلية للمسار الذي سلكناه من نقطة البداية إلى العقدة الحاليةn. هذا هو الجزء الذي تستخدمه Dijkstra. إنه يمثل “ما نعرفه على وجه اليقين”.h(n): هي التكلفة التقديرية (Heuristic) من العقدة الحاليةnإلى نقطة النهاية. هذا هو الجزء الذي يمنح A* “البصيرة”. إنه “تخميننا الذكي” أو “حدسنا” حول المسافة المتبقية.f(n): هي التكلفة الإجمالية التقديرية للمرور عبر العقدةnللوصول إلى الهدف. A* دائماً تختار استكشاف العقدة ذات القيمةf(n)الأقل.
بهذه الطريقة، توازن A* بين المسار الذي كان رخيصاً حتى الآن (g(n)) والمسار الذي يبدو واعداً للمستقبل (h(n)). إنها لا تنجرف وراء المسارات الرخيصة التي تبتعد عن الهدف، ولا تندفع بشكل أعمى نحو الهدف متجاهلة التكاليف الفعلية.
ما هو الـ Heuristic وكيف نختاره؟
الـ Heuristic هو “فن التخمين الذكي”. يجب أن يكون حساب هذا التخمين سريعاً جداً، ويجب أن يكون منطقياً. في مشاكل البحث عن المسار في الخرائط، أشهر نوعين هما:
- مسافة مانهاتن (Manhattan Distance): تُستخدم في الشبكات (grids) حيث يُسمح بالحركة فقط أفقياً وعمودياً (لا قطرياً). تحسب المسافة كأنك تمشي في شوارع مدينة نيويورك (مانهاتن). ببساطة هي:
|x1 - x2| + |y1 - y2|. - المسافة الإقليدية (Euclidean Distance): هي المسافة المستقيمة “كما يطير الغراب” (as the crow flies). تُستخدم عندما تكون الحركة القطرية مسموحة. معادلتها هي:
sqrt((x1-x2)^2 + (y1-y2)^2).
نصيحة من خبير: يجب أن يكون الـ Heuristic “مقبولاً” (Admissible)، وهذا يعني أنه لا يجب أن يبالغ في تقدير التكلفة الحقيقية أبداً. يجب أن يكون متفائلاً دائماً. إذا كان الـ Heuristic يبالغ في التقدير، قد تتسرع A* في سلوك مسار يبدو رخيصاً بشكل خاطئ، وتفوت المسار الأقصر الحقيقي. اختيار مسافة الخط المستقيم كـ Heuristic هو خيار آمن دائماً لأنه لا يوجد طريق أقصر من الخط المستقيم!
لنضع أيدينا في الكود: مثال عملي بلغة Python
الكلام النظري جميل، لكن دعونا نرى كيف تبدو A* في الواقع. إليك مثال بسيط لتطبيق الخوارزمية على شبكة ثنائية الأبعاد باستخدام لغة Python.
import heapq
class Node:
def __init__(self, parent=None, position=None):
self.parent = parent
self.position = position
self.g = 0
self.h = 0
self.f = 0
def __eq__(self, other):
return self.position == other.position
def __lt__(self, other):
return self.f 0:
# Get the current node (the one with the lowest f value)
current_node = heapq.heappop(open_list)
closed_list.add(current_node.position)
# Found the goal
if current_node == end_node:
path = []
current = current_node
while current is not None:
path.append(current.position)
current = current.parent
return path[::-1] # Return reversed path
# Generate children
children = []
for new_position in movements:
# Get node position
node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])
# Make sure within range
if node_position[0] > (len(grid) - 1) or node_position[0] (len(grid[0]) - 1) or node_position[1] open_node.g:
continue
# Add the child to the open list
heapq.heappush(open_list, child)
# --- مثال للاستخدام ---
if __name__ == '__main__':
grid = [[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # 0 = walkable, 1 = obstacle
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
start = (0, 0)
end = (7, 6)
path = astar(grid, start, end)
print(path)
في هذا الكود، استخدمنا `heapq` كـ Priority Queue لتخزين الـ `open_list`، مما يضمن أننا نسحب دائماً العقدة ذات أقل قيمة `f` بكفاءة عالية. الـ `closed_list` تمنعنا من إعادة استكشاف العقد التي زرناها بالفعل. جرب تشغيل الكود وستجد أنه يتجنب بذكاء الجدار (العوائق) ويجد مساراً فعالاً نحو الهدف.
نصائح من “الختيار”: متى وكيف تستخدم A*؟
بعد سنوات من التعامل مع هذه الخوارزمية، إليكم بعض النصائح العملية:
- الـ Heuristic هو الملك: جودة مسارك وسرعة البحث تعتمد كلياً على الـ Heuristic. إذا كان الـ Heuristic ضعيفاً جداً (مثل أن تكون قيمته دائماً صفراً)، ستتحول A* إلى Dijkstra. إذا كان جيداً، ستحصل على أداء مذهل.
- ليست للخرائط فقط: جمال A* يكمن في أنها خوارزمية بحث عامة. يمكنك استخدامها لحل أي مشكلة يمكن تمثيلها كمخطط (graph) تبحث فيه عن حل أمثل. مثلاً: حل الألغاز (مثل لغز الثمانية)، تخطيط المهام، وحتى في بعض تطبيقات معالجة اللغات الطبيعية.
- انتبه للذاكرة: في الخرائط الضخمة جداً (مثل ألعاب العالم المفتوح)، يمكن أن تصبح `open_list` و `closed_list` كبيرتين جداً وتستهلكان الكثير من الذاكرة. هناك متغيرات محسنة من A* مثل (Iterative Deepening A*) IDA* أو (Jump Point Search) JPS للتعامل مع هذه الحالات.
- عوالم متغيرة: A* الكلاسيكية مصممة للبيئات الثابتة حيث لا تتغير العوائق. إذا كنت تعمل في بيئة ديناميكية (مثل نظام ملاحة للسيارات يأخذ في الاعتبار الازدحام المروري المتغير)، ستحتاج إلى خوارزميات أكثر تقدماً مثل D* Lite.
الخلاصة: من البحث الأعمى إلى البصيرة الحاسوبية 💡
رحلتنا مع الروبوت الصغير تعلمنا درساً قيّماً. الانتقال من البحث الأعمى إلى A* لم يكن مجرد تغيير في الكود، بل كان تغييراً في الفلسفة. لقد انتقلنا من جعل الكمبيوتر “يجرب كل شيء” إلى إعطائه “حدساً” أو “بصيرة” توجهه. خوارزمية A* هي المثال المثالي على قوة الجمع بين ما نعرفه على وجه اليقين (التكلفة الفعلية g(n)) وتخميننا الذكي (التكلفة التقديرية h(n)).
الزبدة يا جماعة، في المرة القادمة التي تواجهون فيها مشكلة تتطلب البحث عن حل في فضاء واسع من الاحتمالات، لا تتركوها “عمياء”. فكروا… كيف يمكنني أن أعطي خوارزميتي قليلاً من البصيرة؟ كيف أمنحها Heuristic ذكياً؟ هذا السؤال الصغير يمكن أن يكون الفارق بين مشروع يرى النور ومشروع يبقى في جحيم البحث إلى الأبد.
أتمنى أن تكون هذه الرحلة مفيدة. والله ولي التوفيق.
