البحث بالعرض BFS: أقل عدد حواف وشجرة السوابق لإعادة المسار

عدد الحواف لا كلفة الطريق

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

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

كما لا نطلب مجرد معرفة هل عقدتان في المجموعة نفسها. نحتاج بداية محددة، ومسافة منها، ومسارًا يحقق هذه المسافة. يمكن أن تكون مجموعات الاتصال صحيحة مع غياب معلومات تكفي لإعادة طريق معين. لذلك نحفظ سوابق الاكتشاف ونراجع كل انتقال في الطريق الناتج مقابل الحواف الأصلية، بدل استنتاج المسار من تسمية مجموعة فقط.

[1]

سبع عقد وعقدة غير قابلة للوصول

نؤلف رسمًا بعقد A وB وC وD وE وF وG. الحواف غير الموجهة هي A مع B، وA مع C، وB مع D، وC مع D، وC مع E، وD مع F، وE مع F. نمثل كل حافة في قائمتي جيران طرفيها، أما G فقائمة جيرانها فارغة. هذه بيانات محلية من تأليف المقال، لا شبكة مواصلات أو أجهزة فعلية.

نبدأ من A. نصل مباشرةً إلى B وC بخطوة واحدة. ومنهما نصل إلى D وE بخطوتين، ثم إلى F بثلاث. لا توجد حافة تصل G بهذا الجزء من الرسم، لذلك لا تصل إليها عملية البداية من A. وجود G في قائمة العقد لا يوجب أن تكون ضمن نتائج المسافات؛ التصريح بالعقدة يختلف من الوصول إليها.

الرسم الرئيسي يضع A في الطبقة صفر، وB وC في الأولى، وD وE في الثانية، وF في الثالثة، مع G خارج الطبقات القابلة للوصول. نكتب هذا بوضوح كي لا يصبح فراغ حقل G مسافة صفرًا أو دليلًا على أنها لم تكن في الإدخال. المسافة صفر تخص A نفسها لأنها البداية، لا كل عقدة لم يظهر لها طريق.

الطابور وأول اكتشاف

نضع A وحدها في الطابور ونحفظ مسافتها صفرًا وسابقها None. حين نخرجها من بداية الطابور، نراجع جيرانها بالترتيب B ثم C. كلاهما جديد، فنحفظ له المسافة واحدًا والسابق A، ثم نضيفه إلى نهاية الطابور. تصبح قائمة الانتظار B ثم C، ونفصل هذا الترتيب عن ترتيب أسماء العقد أبجديًا.

نخرج B، ونرى A المكتشفة مسبقًا فلا نضيفها، ثم نكتشف D من B بمسافة اثنين. يصبح الطابور C ثم D. بعد إخراج C، نرى A وD مكتشفتين، ونكتشف E فقط بمسافة اثنين وسابق C. يصبح الطابور D ثم E. معرفة D وقت إدخالها للطابور منعت إدخالها مرة أخرى من C.

نخرج D فنكتشف F بمسافة ثلاثة وسابق D، ويصبح الطابور E ثم F. إخراج E لا يعيد اكتشاف F، ثم تنتهي قراءة F دون عقدة جديدة وينتهي الطابور. النتيجة تحفظ مسافات ست عقد، ولا تدخل G. كل تغيير في الحالة يمكن تتبعه من قائمة الجيران المعلنة، لا من حافة تخيلناها بعد مشاهدة الرسم.

لماذا نسجل قبل الإدخال للطابور؟

في المثال، يصل المرشح D من B ثم من C. إذا لم نعلن اكتشاف D إلا عند إخراجها، فقد يعيد C إضافتها وهي ما زالت تنتظر دورها. كودنا يحفظ المسافة والسابق أولًا ثم يضيف العقدة، فتدل عضويتها في قاموس distance على أنها اكتشفت، سواء كانت قيد الانتظار أو اكتمل فحصها.

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

ونفس الفحص يمنع إعادة البداية عند رؤية حافة راجعة من B إلى A. كما يتعامل مع دورة أو تكرار اسم جار أو حافة عقدة إلى نفسها في نطاقنا، لأن العقدة المكتشفة لا تدخل مرة جديدة من تلك الحالة. لا نستعمل وجود دورة سببًا لتوقع بحث لا ينتهي تلقائيًا؛ نراجع سياسة الاكتشاف التي نفذها الكود بالفعل.

لماذا يكون أول اكتشاف بأقل عدد خطوات؟

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

لذلك لا يظهر لاحقًا طريق أقصر إلى D بعد اكتشافها بخطوتين في المثال. لو كان لها طريق من خطوة واحدة من A، لكنا وجدناها في جيران A عند البداية، وهو غير موجود في بياناتنا. وفي الحالة العامة لهذا المرور، طريق أقصر يمر بسابق في طبقة أقرب، وكان فحص ذلك السابق سيقدم العقدة قبل اكتشاف أطول يدعي أنه الأول.

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

شجرة السوابق ليست كل حواف الرسم

السابق لكل عقدة في نتيجتنا هو A للبداية الفرعية B وC، ثم B لـD، وC لـE، وD لـF، ولا سابق فعليًا للبداية A. هذه روابط الاكتشاف التي تكفي للعودة من كل هدف قابل للوصول إلى البداية. تحتوي خمس روابط بين ست عقد قابلة للوصول، بينما الرسم الأصلي يحتوي سبع حواف غير موجهة.

الحافتان C مع D وE مع F موجودتان في الأصل، لكنهما ليستا رابطتي سابق في هذه النتيجة. لم تحذف عملية البحث هاتين الحافتين من الإدخال، ولم تقل إنهما غير صالحتين. اختارت سبب الاكتشاف الأول فقط لكل عقدة. لذلك لا نستعمل previous سجلًا كاملًا للرسم أو قائمة بكل البدائل التي كانت متاحة أثناء المرور.

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

إعادة مسار من A إلى F

نبدأ من F ونتبع السوابق: السابق D، وقبله B، وقبله A، ثم None التي تميز نهاية الرجوع عند البداية في عقدنا. يجمع الكود هذه الهويات بترتيب الرجوع، ثم يعكسها ليعرض A ثم B ثم D ثم F. عدد الهويات أربعة، لكن عدد الحواف بينها ثلاثة، وهو المسافة المخزنة لـF.

نراجع كل زوج متتالٍ في المسار؛ A مع B وB مع D وD مع F كلها حواف أصلية. كما نراجع البداية والهدف وعدد الانتقالات. حفظ ثلاثة في حقل distance لا يثبت وحده أن قائمة أسماء عشوائية تحقق هذا العدد؛ نحتاج توافق الشاهد مع الرسم ومع الهويات التي ادعى أنه يصلها.

وللهدف A نفسها يعيد المسار A وحدها، بطول حواف صفر، دون الحاجة إلى حافة ذاتية. أما G فلا تظهر في قاموس المسافات، فيعيد مساعد المسار None. هذه الحالة لا تعيد قائمة فارغة بوصفها طريقًا من A إلى G؛ لا يوجد شاهد وصول في الرسم الذي عالجناه من هذه البداية.

ترتيب الجيران يغير الشاهد لا المسافة

نعكس ترتيب قوائم الجيران في نسخة من الرسم الأصلي، دون إضافة حافة أو حذفها. تبدأ A بعرض C قبل B، فيتغير ترتيب انتظار بعض العقد. في هذه النسخة يعيد مساعد المسار إلى F الطريق A ثم C ثم E ثم F بدل A ثم B ثم D ثم F. كلاهما يحتوي ثلاث حواف ويحقق مسافة F نفسها.

تظل مسافات A وB وC وD وE وF كما كانت، لأن أقصر عدد خطوات لم يتغير بتغيير ترتيب عرض الجيران. لكن سوابق الاكتشاف الأول يمكن أن تختلف عند وجود عدة طرق قصيرة. لا نطالب بظهور قائمة أسماء واحدة في كل ترتيب إدخال إذا لم يحدد عقدنا سياسة تفاضل أخرى بين الشواهد المتساوية.

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

عرض الرسم بالحجم الكامل

مسار واحد ليس جميع المسارات القصيرة

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

في الأصل يمكن الوصول إلى F عبر A ثم B ثم D ثم F، أو A ثم C ثم D ثم F، أو A ثم C ثم E ثم F. جميعها ثلاث حواف. السابق الوحيد F من D لا يضع الطريق عبر E ضمن نتيجة مساعدنا، وسابق D من B لا يحتفظ بالطريق عبر C إلى D. هذه حدود تمثيل مفرد، لا نفي لصحة البدائل.

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

[2]

الكود الأصلي وعقد التصريح بالعقد

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

تستعمل deque للطابور، وتحفظ distance وprevious عند أول اكتشاف، ثم تستكمل المرور على كل ما يمكن الوصول إليه من البداية. مساعد path_to يتوقع نتيجة سليمة من هذه الدالة ويعيد مسارًا أو None إذا لم يجد الهدف في قاموس المسافات. القواميس المعادة قابلة للتعديل في Python؛ لا ننسب للمساعد فحصًا يصلح سوابق غيرها المستدعي يدويًا.

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

from collections import deque


def bfs_paths(graph, start):
    adjacency = {node: tuple(neighbors) for node, neighbors in graph.items()}
    if any(not isinstance(node, str) or not node for node in adjacency):
        raise ValueError("nonempty text vertices required")
    for neighbors in adjacency.values():
        if any(node not in adjacency for node in neighbors):
            raise ValueError("every neighbor must be declared")
    if start not in adjacency:
        raise KeyError(start)
    distance = {start: 0}
    previous = {start: None}
    waiting = deque([start])
    while waiting:
        node = waiting.popleft()
        for neighbor in adjacency[node]:
            if neighbor not in distance:
                distance[neighbor] = distance[node] + 1
                previous[neighbor] = node
                waiting.append(neighbor)
    return {"distance": distance, "previous": previous}


def path_to(result, target):
    if target not in result["distance"]:
        return None
    path = []
    node = target
    while node is not None:
        path.append(node)
        node = result["previous"][node]
    return tuple(reversed(path))

الاتجاه والأوزان يغيران السؤال

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

وفي مثال موزون مستقل، نضع انتقالًا مباشرًا من S إلى T بقيمة 9، وانتقال S إلى U بقيمة 1 ثم U إلى T بقيمة 1. البحث بوصف كل حافة خطوة يختار الطريق المباشر إلى T لأنه خطوة واحدة، لكن مجموع القيم في الطريق ذي خطوتين هو 2 مقابل 9. هذا يفصل أقل عدد حواف من أقل مجموع أوزان.

لم تدخل تلك الأوزان في كودنا أصلًا، فلا يمكن أن نزعم أنه عظم أو قلل مجموعها. الأعداد هنا قيم تعليمية مؤلفة، وليست أسعارًا أو زمن سفر فعليًا. إذا أراد السؤال وزنًا أو قيد اتجاه أو حواجز، نثبت البيانات والمعيار والطريقة التي تعالجه، بدل إطلاق كلمة أقصر على نتيجة حسبت عدد انتقالات فقط.

المجهول وغير القابل للوصول والفارغ

الهدف G عقدة معلومة لكنها غير قابلة للوصول من A. والاسم Z ليس عقدة في رسمنا أصلًا. يعيد path_to None في الحالتين إذا مررنا له هذين الاسمين، لأنه يفحص وجود الهدف في distance فقط. لذلك يجب على المستدعي فحص التصريح بالهوية في الرسم إذا احتاج الفصل بين هدف غير معروف وهدف معروف لم نجد له طريقًا.

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

ونراجع حافة ذاتية أو جارًا متكررًا أو دورة صغيرة من A إلى B ثم A. سياسة الاكتشاف قبل الإدخال للطابور تمنع إضافة العقد المكتشفة مرة أخرى، فتبقى المسافات المعلنة سليمة في هذه الحالات المؤلفة. لا نستعمل None عددًا أو نضع صفرًا لكل غياب؛ نحتفظ بالمعاني المختلفة كي لا يتحول نقص معلومة إلى مسافة صحيحة مزعومة.

مرجع الاسترخاء المستقل

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

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

ونضيف رسمنا ذي سبع عقد، ونسخة الجيران المعكوسة، وحالات الدورة والتكرار والهدف المجهول والبداية المرفوضة. الفحوص محدودة بالبيانات التي نفذناها، ولا تعني أن كل رسم خارجي صرح بعلاقاته بصورة صحيحة. نجاح التنفيذ وحسن تمثيل المصدر سؤالان مختلفان؛ نحفظ ما فحصناه كي يمكن مراجعة كل ادعاء في نطاقه.

بطاقة النتيجة والنسخة

يمكن وصف نتيجة الأصل ببطاقة: البداية A، وكل حافة خطوة واحدة، وجيران ثابتون بالترتيب المعلن، ومسافات الطبقات صفر وواحد واثنان وثلاثة، وG مصرح بها لكنها خارج الوصول. نكتب طريق F الشاهد A ثم B ثم D ثم F، ونذكر أن شجرة السوابق لا تحفظ جميع حواف الرسم أو كل الطرق القصيرة.

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

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