latex
المَعالِمِ هِيَ حَقائِقَ أَو أَفْعالٍ تُظْهِر فِي جَمِيعِ الحُلُولِ الصالِحَةِ لِمُشْكِلَةِ التَخْطِيطِ. لَقَد تَمَّ اِسْتِخْدامُها بِنَجاحٍ لِحِسابِ المَعايِيرِ الإِرْشادِيَّة الَّتِي تَوَجَّهَ البَحْثِ عَن خُطَّةٍ. نَحْنُ نَسْتَكْشِف تَوْسِيعاً لِهٰذا المَفْهُومُ مِن خِلالَ تَعْرِيفٍ “دَرَجَةِ الأَهَمِّيَّةِ” الجَدِيدَةِ الَّتِي تُساعِد فِي تَحْدِيدِ الحَقائِقِ أَو الأَفْعال الَّتِي تُظْهِر فِي مُعْظَمَ الخُطَطِ وَلٰكِن لَيِسَ فِي جَمِيعِ الخُطَطِ لِتَحْقِيقِ أَيّ هَدَفَ مُعَيَّنٍ. نِصْفِ طَرِيقَةِ لِحِسابِ هٰذِهِ الدَرَجَةِ وَاِسْتِخْدامَها كَمِعْيارٍ إِرْشادَيَّ فِي البَحْثِ عَن خُطَّةٍ. نُقارَن أَداءِ نَهْجنا تَجْرِيبِيّا مَعَ أَداءِ نَهْجٍ تَخْطِيطَيَّ قائِمٌ عَلَى المَعالِمِ وَالَّذِي يُعْتَبَر الأَحْدَثُ بِاِسْتِخْدامِ مَشاكِلَ التَخْطِيطِ المعياريه. بَيْنَما يُؤَدِّي المِعْيار القائِمِ عَلَى المَعالِمِ الأَصْلِيُّ إِلَى أَداءِ أَفْضَلَ فِي المَشاكِلِ الَّتِي تَحْتَوِي عَلَى مَعالِمُ مُحَدَّدَةٍ جَيِّداً، فَإِنَّ نَهْجنا يُحَسِّن الأَداءِ بِشَكْلٍ كَبِيرٍ فِي المَشاكِلِ الَّتِي تَفْتَقِر إِلَى المَعالِمِ غَيْرِ التافِهَة.
إِن اِسْتِخْدامِ الاِسْتِدْلالات لِتَوْجِيهِ البَحْثِ وَتَحْدِيدِ مِساحَةِ البَحْثِ هُوَ مُكَوِّن مُهِمٌّ فِي أَنْظِمَةِ التَخْطِيطِ الحَدِيثَةِ. هُناكَ أَدَبِيّاتِ مُؤَسَّسَةِ جَيِّداً مِن الطُرُقِ الَّتِي تُسْتَخْدَم الاِسْتِدْلالات لِتَحْسِينِ الكَفاءَة الحِسابِيَّة لِحِسابِ الخُطَطِ. وُجُودِ اِسْتِدْلال سَلِيم يُمْكِن حِسابِهِ بِسُرْعَةٍ يَجْعَل التَخْطِيطِ المساري فِي الفَضاءِ الأُقْلِيدِيّ أَكْثَرَ كَفاءَةِ بِكَثِيرٍ مِن مِساحاتٍ البَحْثِ المُجَرَّدَةِ المُسْتَخْدَمَةِ لِلتَخْطِيطِ المَهامّ. أَحَدُ الاِسْتِدْلالات الناجِحَةِ المُسْتَخْدَمَةِ لِلتَخْطِيطِ المَهامّ هُوَ عَدَدٍ “العَلاماتِ البارِزَةِ” الَّتِي لا تَزال بِحاجَةٍ إِلَى الوُصُولِ إِلَيها مِن حالَةِ مُعَيَّنَةٍ (Zhu2003, Hoffmann2004, Richter2010, Keyder2010)، حَيْثُ تَكُون العَلّامَةُ البارِزَةِ حَقِيقَةِ، أَو فِعْلٍ، أَو صِيغَةِ مَنْطِقِيَّةٍ عَلَى الحَقائِقِ وَ/أَو الأَفْعال، وَالَّتِي تَكُون مَوْجُودَةٌ فِي جَمِيعِ الحُلُولِ الصالِحَةِ (أَيّ تَسَلْسُلُ الأَفْعال) لِمُشْكِلَةِ التَخْطِيطِ. هٰذا يُؤَدِّي إِلَى تَفْضِيل الأَفْعال (فِي الخُطَطِ) الَّتِي تَكُون عَلامَةً بارِزَةٌ أَو تَحَقَّقَ واحِدَةٍ. وَمَعَ ذٰلِكَ، فَإِنَّ مُهِمَّةً حِسابِ جَمِيعِ العَلاماتِ البارِزَةِ لِمُشْكِلَةِ التَخْطِيطِ مُكَلَّفَةٍ؛ وَمِن المَعْرُوفُ أَنَّها مُكْتَمَلَةٍ الفَضاءِ الكُلِّيِّ (Porteous2001a). الأَنْظِمَةِ الَّتِي تَحَسُّب العَلاماتِ البارِزَةِ تُحَدِّد بِالتالِي مَجْمُوعَةِ فَرْعِيَّةٍ مِن العَلاماتِ البارِزَةِ الرَئِيسِيَّةِ، غالِباً بِاِسْتِخْدامِ نُسْخَةً مُرِيحَةٍ مِن مُشْكِلَةِ التَخْطِيطِ (Keyder2010)، وَلٰكِن تَكْلِفَةِ حِسابِ العَلاماتِ البارِزَةِ لا تَزال كَبِيرَةٍ.
أَحَدُ القُيُودِ الشائِعَةُ لِمُعْظَمِ النَهْجِ الَّتِي تَحَسُّب وَتُسْتَخْدَم العَلاماتِ البارِزَةِ لِتَوْجِيهِ التَخْطِيطِ هُوَ أَنَّ هٰذِهِ العَلاماتِ يَجِب أَنَّ تَكُون مَوْجُودَةٌ لِمَشاكِلِ التَخْطِيطِ قَيْدِ النَظَرِ. فِي العَدِيدَ مِن المَجالاتِ المُعَقَّدَةِ حَيْثُ تُوجَد طُرُقٍ مُتَعَدِّدَةِ مُمْكِنَةٍ لِلوُصُولِ إِلَى الهَدَفَ، قَد تَكُون العَلاماتِ البارِزَةِ البَسِيطَةِ (حَقِيقَةِ واحِدَةٍ) المَوْجُودَةِ تافِهه، أَيّ تِلْكَ المَوْجُودَةِ فِي مُواصَفاتِ الهَدَفَ أَو الَّتِي تَكُون صَحِيحَةٍ بِالفِعْلِ فِي الحالَةِ الأَوَّلِيَّةِ. بَيْنَما قَد تَكُون الصِيَغِ المَنْطِقِيَّةِ المُعَقَّدَةِ بِمَثابَةِ عَلاماتِ بارِزَةٌ، يُمْكِن أَنَّ يَكُون مِن الصَعْبِ حِسابِ وَاِسْتِخْدامِ هٰذِهِ الصِيَغِ المَنْطِقِيَّةِ فِي اِسْتِدْلال. النَهْجِ المَوْصُوف فِي هٰذِهِ الوَرَقَةَ يَتَجَنَّب هٰذا القَيْد مِن خِلالَ حِسابِ “دَرَجَةِ الصِلَةِ”، وَالَّتِي تَأْخُذ أَيْضاً فِي الاِعْتِبارِ قِيمَةَ تَحْقِيقِ الحَقائِقِ (أَو الأَفْعال) الَّتِي تُظْهِر فِي العَدِيدَ وَلٰكِن لَيِسَ جَمِيعِ الخُطَطِ الصالِحَةِ. الفَرْضِيَّة الأَساسِيَّةِ هِيَ أَنَّ هٰذِهِ المَعْلُوماتِ الإِضافِيَّة سَتُؤَدِّي إِلَى بَحَثَ أَكْثَرَ كَفاءَةِ عَن حَلٍّ صالِح لِمُشْكِلَةِ التَخْطِيطِ المُعْطاة. كَمُخَطَّط أَساسِيٌّ، نَسْتَخْدِم مُخَطَّطٍ لاما (Richter2010)، الَّذِي يَسْتَخْدِم مَزِيجاً مِن عَدَّ العَلاماتِ البارِزَةِ وَنِظامِ السُرْعَةِ الأَمامِيَّةِ (Hoffmann2001)، مَعَ أَقْصَرُ خُطَّةٍ مَوْجُودَةٌ بِاِسْتِخْدامِ بَحَثَ \(A^*\) المَوْزُون تَحْتَ شُرُوطٍ الاِسْتِرْخاء الحَذْف. وَقَد اِعْتَبَرَ الفَنِّ الحالِيَّ فِي مُسابَقاتِ التَخْطِيطِ لِأَكْثَرِ مِن عَقْدِ مِن الزَمانِ.
المُساهَمَةِ الرَئِيسِيَّةِ لِهٰذِهِ الوَرَقَةَ هِيَ تَعْرِيفٍ وَوَصَفَ نَهْجٍ لِحِسابِ اِسْتِدْلال جَدِيدٍ “دَرَجَةِ الصِلَةِ” (\(h_{\Xi})\). هٰذا الاِسْتِدْلال الَّذِي يُعَمِّم مفهوب العَلّامَةُ البارِزَةِ، الَّتِي يَجِب أَنَّ تَكُون صَحِيحَةٍ فِي نُقْطَةً ما فِي جَمِيعِ الخُطَطِ (تَحْتَ الاِسْتِرْخاء الحَذْف)، إِلَى الصِلَةِ، الَّتِي تُقِيم الحَقائِقِ أَو الأَفْعال وِفْقاً لِمَدَى ظُهُورِها فِي الخُطَطِ (أَيْضاً تَحْتَ الاِسْتِرْخاء الحَذْف). تُوَضِّح الشَكْلِ [fig:illustration] المَعْلُوماتِ الَّتِي نَهْدِف إِلَى اِلْتِقاطها مَعَ دَرَجَةِ الصِلَةِ، وَكَيْفَ تَرْتَبِط بِالعَلامات البارِزَةِ. لِتَسْهِيلِ المُقارَنَةِ مَعَ مُخَطَّطٍ لاما الأَساسِيُّ، نُحَدِّد تَرْكِيزنا عَلَى الحَقائِقِ كَكِيانات شَبِيهَةٍ بِالعَلامات البارِزَةِ. ثُمَّ نُوَضِّح مِن خِلالَ التَقْيِيم التَجْرِيبِيُّ الَّذِي يَشْمَل الأَفْرادِ وَمَجْمُوعاتٍ مِن مَشاكِلَ التَخْطِيطِ المعياريه أَنَّهُ بَيْنَما يُؤَدِّي الاِسْتِدْلال القائِمِ عَلَى العَلاماتِ البارِزَةِ الأَصْلِيَّةِ إِلَى أَداءِ أَفْضَلَ فِي المَشاكِلِ الَّتِي تَحْتَوِي عَلَى عَلاماتِ بارِزَةٌ مُحَدَّدَةٍ جَيِّداً، فَإِنَّ نَهْجنا القائِمِ عَلَى دَرَجاتٍ الصِلَةِ يُحَسِّن الأَداءِ بِشَكْلٍ كَبِيرٍ فِي المَشاكِلِ الَّتِي تَفْتَقِر إِلَى العَلاماتِ البارِزَةِ غَيْرِ التافِهَة.
تُنَظِّم بَقِيَّةِ هٰذِهِ الوَرَقَةَ عَلَى النَحْوِ التالِي. القِسْمِ [sec:rel-work] يَحْفِز نَهْجنا المُقْتَرَحِ مِن خِلالَ مُناقَشَةِ الأَعْمالِ ذاتِ الصِلَةِ. القِسْمِ [sec:definitions] يَصِف صِياغَةِ مُشْكِلَتنا وَالاِسْتِدْلالُ المُقْتَرَحِ، بَيْنَما القِسْمِ [sec:methods] يَصِف حِسابِ هٰذا الاِسْتِدْلال وَاِسْتِخْدامُهُ لِحِسابِ الخُطَطِ. النَتائِجِ التَجْرِيبِيَّة المَوْصُوفَة فِي القِسْمِ [sec:results] تُشَكِّل أَساسِ النِقاشُ حَوْلَ الخَطَواتِ التالِيَةِ فِي القِسْمِ [sec:discuss].
تَمَّ وَصَفَ المَعالِمِ كَوَسِيلَة لِلتَوْجِيه البِدائِيُّ فِي (Porteous2001a) وَتَمَّ تَطْوِيرها أَكْثَرَ فِي (Hoffmann2004)، كَاِمْتِداد لَتَرْتِيب الأَهْدافِ. سَعََوْا لِإِيجادِ وَتَرْتِيبُ الحَقائِقِ الَّتِي يَجِب تَحْقِيقِها فِي أَيّ خُطَّةٍ صالِحَةٌ. تَمَّ التَعامُلِ مَعَ هٰذا التَرْتِيبِ الجُزْئِيِّ لِلمَعالِمِ كَسِلْسِلَة مِن الأَهْدافِ الفَرْعِيَّةِ لِتَقْسِيمِ مُشْكِلَةِ التَخْطِيطِ إِلَى مَشاكِلَ فَرْعِيَّةٍ. عادَةً ما يَتِمّ العُثُورِ عَلَى المَعالِمِ بِاِسْتِخْدامِ رَسْمِ بَيانَيَّ لِلتَخْطِيطِ المَرِن (RPG) (Hoffmann2001)، الَّذِي يُؤَدِّي تَحْلِيلِ الوُصُولِ تَحْتَ شُرُوطٍ الاِسْتِرْخاء الحذفي وَيَتَطَلَّب خَطَواتٍ مُتَعَدِّدَةِ لِلتَحَقُّقِ مِن أَنَّ المَعالِمِ وَتَرْتِيبها سَلِيم.
اِسْتَخْدَمَ العَدِيدَ مِن الباحِثِينَ المَعالِمِ لِتَوْجِيهِ المُخَطِّطِينَ البَحْثِيَّيْنِ القائِمِينَ عَلَى البَياناتِ الإِرْشادِيَّة (Zhu2003,Helmert2006,Richter2008). وَقَد قامَ آخَرُونَ بِتَوْسِيعِ هٰذِهِ الفِكْرَةِ لِإِيجادِ خُطَطِ مِثْلِي مِن حَيْثُ التَكْلِفَةِ وَبَدَأُوا بِاِسْتِخْدامِ الأَفْعال وَالصِيَغِ الاقتراحيه لِلحَقائِق كَمَعالِم مُحْتَمَلَةٍ (Keyder2008,Karpas2009,Richter2010). يَسْتَخْدِم مُعْظَمُهُم عِدادِ المَعالِمِ البَيانِيّ، الَّذِي يُفْتَرَض أَنَّ كُلِّ مُعَلِّمٍ لَم يَتِمّ الوُصُولِ إِلَيهِ بُعْدَ سَيُكَلِّف فِعْلاً واحِداً. ثُمَّ يُعْطَى تَقْدِيرٍ المَسافَةِ إِلَى الهَدَفَ بِعَدَدٍ المَعالِمِ المُتَبَقِّيَةُ لِلعُثُور عَلَيها. كانَ هُناكَ بِعَضِّ العَمَلِ عَلَى البَياناتِ الإِرْشادِيَّة الَّتِي تُحافِظ عَلَى تَكالِيفِ الأَفْعال، وَتَأْخُذ فِي الاِعْتِبارِ الأَفْعال الَّتِي يُمْكِن أَنَّ تَحَقَّقَ عِدَّةٍ مَعالِمُ فِي آنٍ واحِدٍ (Helmert2009,Karpas2009). وَقَد اِسْتَكْشَفَت هٰذِهِ الأَوْراقِ وَغَيْرِها طُرُقاً أَكْثَرَ كَفاءَةِ لِتَحْدِيدِ العَدِيدَ مِن المَعالِمِ (Keyder2010).
أَسْتَكْشِف الباحِثُونَ طُرُقاً مُخْتَلِفَةٍ لِحِسابِ وَاِسْتِخْدامِ المَعالِمِ. مِثالٌ عَلَى ذٰلِكَ هُوَ تَرْجَمَةٍ الرُسُومِ البَيانِيَّةِ لِلتَخْطِيطِ المَرِن إِلَى رُسُومٍ بَيانَيْهِ AND/OR حَيْثُ تُعْتَبَر المَعالِمِ حُلُولاً فَرِيدَةٍ وَقُصْوَى يَتِمّ حِسابها بِاِسْتِخْدامِ طُرُقٍ بيلمان-فَوَرْد (Keyder2010). يَنْطَوِي تَطْبِيقِ الاِسْتِرْخاء الحذفي عَلَى مُشْكِلَةِ تَخْطِيطِ عَلَى فُقْدانِ المَعْلُوماتِ، وَيُمْكِن أَنَّ يُؤَدِّي إِلَى أَفْعالٍ أَو تَسَلْسُلات أَفْعالٍ مُسْتَحِيله فِي المُشْكِلَةِ الأَصْلِيَّةِ. إِحْدَى الطُرُقِ تَتَمَثَّل فِي التَخَلُّصِ مِن الشُرُوطِ السَلْبِيَّةِ وَالآثارِ مَعَ الحِفاظِ عَلَى المَعْلُوماتِ الَّتِي اِحْتَوَتْها (Haslum2009). مِن خِلالَ النَظَرِ فِي أَزْواج (\(m=2\))، أَو ثُلاثِيّات (\(m=3\)) أَو تَقارُنات أَكْبَرَ مِن الحَقائِقِ، يَتِمّ الحِفاظِ عَلَى مُتَطَلِّب تَحْقِيقِها فِي وَقْتٍ واحِدٍ، مِمّا يُؤَدِّي إِلَى مُشْكِلَةِ أَكْبَرَ \( \Pi^m \) خالِيَةً مِن الشُرُوطِ السَلْبِيَّةِ أَو الآثارِ. قامَ آخَرُونَ بِبِناءِ عَلَى هٰذِهِ الفِكْرَةِ (Keyder2010). نَظَراً لِأَنَّ حَجْمِ المُشْكِلَةِ يَنْمُو بِشَكْلٍ أَسَى مَعَ \(m\)، وَإِدْخال حَقائِقَ مُرَكَّبَةٌ جَدِيدَةٍ فِي المَجالِ يُطْرَح تَحَدِّياتٍ أُخْرَى، فَإِنَّ الطُرُقِ الَّتِي تُسْتَخْدَم المَعالِمِ غالِباً ما تُفَضِّل قُبُولِ القُيُودِ المَفْرُوضَةِ بِواسِطَةِ الاِسْتِرْخاء الحذفي.
لا يَزال هُناكَ عَمَلٍ جارَ عَلَى حِسابِ وَاِسْتِخْدامِ المَعالِمِ. يَشْمَل ذٰلِكَ حِسابِ المَعالِمِ بِاِسْتِخْدامِ تَعْرِيفات مَجالِ التَخْطِيطِ غَيْرِ المُؤَسَّسَةِ أَو “المَرْفُوعَةِ”، مِمّا يَسْمَح بِتَمْثِيلِ بِعَضِّ تَعْقِيداتٌ المَعالِمِ المُنْفَصِلَة فِي نِطاقِ التَأْسِيسات المُمْكِنَةِ (Wichlacz2022). كَما يَشْمَل اِسْتِخْدامِ المَعْلُوماتِ التَرْتِيبِيَّة لِحِسابِ بَيانٍ إِرْشادَيَّ جَدِيدٍ، مِمّا يُحَسِّن دِقَّته (Buchner2021). كَما يَتِمّ اِسْتِخْدامِ البَياناتِ الإِرْشادِيَّة المُسْتَنِدَةَ إِلَى المَعالِمِ فِي العَدِيدَ مِن المَجالاتِ ذاتِ الصِلَةِ مِثْلَ التَعَرُّفُ عَلَى الأَهْدافِ (Pereira2017,Vered2018) وَالتَخْطِيطِ المَشْرُوطِ (Maliah2018,Segovia-Aguas2022).
نَبْدَأ بِتَعْرِيف الرُمُوزَ وَبِعَضِّ المَفاهِيمِ المُسْتَخْدَمَةِ فِي هٰذِهِ الوَرَقَةَ، يَلِيه تَعْرِيفٍ لِلمِقْياس الاستدلالي لِلأَهَمِّيَّة الَّذِي اِقْتَرَحْناهُ.
تَعْرِف مُشْكِلَةِ التَخْطِيطِ الكلاسِيكِيَّةِ بِالثُنائِيّ (GNT2): \[\Pi = \langle F, A, I, G\rangle\] حَيْثُ \(F\) هِيَ مَجْمُوعَةِ مَحْدُودَةٍ مِن المَقُولات الأَرْضِيَّة الَّتِي تُمَثِّل الحَقائِقِ؛ \(A\) هِيَ مَجْمُوعَةِ مَحْدُودَةٍ مِن الأَفْعال؛ \(I\subseteq F\) هِيَ مَجْمُوعَةِ الحَقائِقِ الصَحِيحَةِ فِي الحالَةِ الاِبْتِدائِيَّةُ؛ وَ\(G \subseteq F\) هِيَ مَجْمُوعَةِ الحَقائِقِ الَّتِي تُمَثِّل الأَهْدافِ. الحالَةِ \(\sigma\) هِيَ مَجْمُوعَةِ مِن الحَقائِقِ الَّتِي تَكُون صَحِيحَةٍ فِي وَقْتٍ مُعَيَّنٍ. لِكُلِّ فِعْلٍ \(a \in A\) هُناكَ شُرُوطٍ مُسْبَقَةٍ \(pre(a)\) وَتَأْثِيرات \(ef\!f(a)\)، وَكُلُّ مِنها مُقَسَّم إِلَى مَجْمُوعاتٍ مِن الحَقائِقِ الإِيجابِيَّةِ وَالسَلْبِيَّة: \( pre^+(a), pre^-(a), ef\!f^+(a), ef\!f^-(a) \). إِذا كانَت الشُرُوطِ المُسْبَقَةِ الإِيجابِيَّةِ (السَلْبِيَّةِ) لِفِعْلِ ما صَحِيحَةٍ (خاطِئَةٍ) فِي حالَةِ مُعَيَّنَةٍ، فَإِنَّهُ يُمْكِن تَطْبِيقِهِ فِي تِلْكَ الحالَةِ: \[Applicable(a, \sigma) \iff \sigma \models pre^+(a)\cap\neg pre^-(a)\] عِنْدَ تَطْبِيقِ فِعْلٍ عَلَى حالَةِ يُمْكِن تَطْبِيقِهِ فِيها، فَإِنَّ الحالَةِ الناتِجَةِ تُعْطِي بِواسِطَةِ: \[Result(a, \sigma) \models \sigma \cup ef\!f^+(a) \setminus ef\!f^-(a)\] تَكُون سِلْسِلَةٍ الأَفْعال \([a_1 ... a_n]\) قابِلَةٍ لِلتَطْبِيقِ فِي حالَةِ إِذا كانَ كُلِّ فِعْلٍ قابِلٌ لِلتَطْبِيقِ فِي الحالَةِ الناتِجَةِ عَن السِلْسِلَة السابِقَةِ مِن الأَفْعال، أَيّ \( Applicable(a_1, \sigma), Applicable(a_2, Result(a_1, \sigma))\) وَهٰكَذا. نَتِيجَةَ تَطْبِيقِ سِلْسِلَةٍ الأَفْعال عَلَى حالَةِ يُمْكِن تَطْبِيقِها هِيَ نَتِيجَةَ تَطْبِيقِ كُلِّ فِعْلٍ فِي تِلْكَ السِلْسِلَة، أَيّ \( Result([a_1 ... a_n], \sigma) = Result(a_n, Result(a_{n-1}, ...Result(a_1, \sigma))\).
خُطَّةٍ\( \pi^\Pi\) لِمُشْكِلَةِ \( \Pi = \langle F, A, I, G\rangle\) هِيَ سِلْسِلَةٍ مِن الأَفْعال \([a_1 ... a_n]\) الَّتِي تَكُون قابِلَةٍ لِلتَطْبِيقِ فِي \(I\) وَتُؤَدِّي إِلَى حالَةِ تَكُون فِيها جَمِيعِ الحَقائِقِ فِي \(G\) صَحِيحَةٍ، أَيّ \(Result(\pi^\Pi, I) \models G\).
المُعَلِّمِ هُوَ تَعْرِيفٍ لَصِيغَة اِقْتِراحَيْهِ مِن الحَقائِقِ الَّتِي تَكُون صَحِيحَةٍ فِي نُقْطَةً ما خِلالَ تَنْفِيذِ جَمِيعِ الخُطَطِ الصالِحَةِ. بِسَبَبِ صُعُوبَةِ تَحْدِيدِ المَعالِمِ الاِخْتِيارِيَّة، تُسْتَخْدَم العَدِيدَ مِن أَنْظِمَةِ التَخْطِيطِ، بِما فِي ذٰلِكَ LAMA (Richter2010)، المَعالِمِ الحَقِيقِيَّةِ فَقَط. هٰذِهِ هِيَ الحَقائِقِ الفَرْدِيَّةِ الَّتِي يَجِب أَنَّ تَكُون صَحِيحَةٍ فِي نُقْطَةً ما خِلالَ تَنْفِيذِ جَمِيعِ الخُطَطِ الصالِحَةِ. كُلِّ حَقِيقَةِ فِي الهَدَفَ وَالحالَة الأَوَّلِيَّةِ هِيَ مُعَلِّمٍ، وَلٰكِنَّها ذاتِ فائِدَةٍ قَلِيلَةٍ لِلمُخَطَّطِ؛ وَتَعْرِف هٰذِهِ بِالمَعالِم السَطْحِيَّةُ. الحَقائِقِ الَّتِي يَجِب أَنَّ تَكُون صَحِيحَةٍ فِي نُقْطَةً ما غَيْرِ فِي بِدايَةِ أَو نِهايَةِ تَنْفِيذِ الخُطَّةِ تُعْتَبَر غَيْرِ سَطْحِيَّةٍ.
نَقْتَرِح فِي هٰذِهِ الوَرَقَةَ دَرَجَةِ أَهَمِّيَّةً تَنْطَبِق عَلَى كُلِّ مِن البِناءِ عَلَى الحَقائِقِ وَالإِجْراءات المُشابِهَة لِلمَعالِمِ. وَمَعَ ذٰلِكَ، لِتَسْهِيلِ الاِسْتِخْدامِ وَالمُقارَنَة مَعَ LAMA، نَحُدّ مُناقَشَتنا فِي هٰذِهِ الوَرَقَةَ عَلَى الحَقائِقِ.
يُمْكِن تَبْسِيطِ مُشْكِلَةِ التَخْطِيطِ الكلاسِيكِيَّةِ لِحِسابِ الإِرْشادات الَّتِي سَتُساعِد فِي حَلٍّ المُشْكِلَةِ الأَصْلِيَّةِ (Bonet2001, Hoffmann2001). إِحْدَى هٰذِهِ التَبْسِيطات هِيَ اِسْتِرْخاءِ الحَذْف، الَّذِي يُزِيل جَمِيعِ الشُرُوطِ السَلْبِيَّةِ وَالآثارِ السَلْبِيَّةِ مِن جَمِيعِ الأَفْعال. تُسْتَخْدَم تَبْسِيطه أُخْرَى غالِباً لَمَجالات التَخْطِيطِ الَّتِي تَحْتَوِي عَلَى أَهْدافٍ مُتَعَدِّدَةِ. عَلَى وَجْهِ التَحْدِيدِ، يَتِمّ تَعْدِيلِ المَجالِ بِإِضافَة فِعْلٍ \(achieveGoal\) الَّذِي لَهُ تَأْثِيرِ إِيجابِيٍّ واحِدٍ \(ef\!f^+(achieveGoal) = \{success\}\)، وَأَهْدافِ المُشْكِلَةِ كَشُرُوط مُسْبَقَةٍ \(pre^+(achieveGoal) = G\). ثُمَّ يَسْتَخْدِم \(success\) كَهَدَفٍ لِحِسابِ الإِرْشادات، مِمّا يَسْمَح بِالنَظَرِ فِي جَمِيعِ الأَهْدافِ مَعاً.
شَجَرَةَ هِيَ تَمْثِيلِ قِياسِيٌّ لَمَجال (وَتَغْيِيرات فِي المَجالِ) لِمُشْكِلَةِ تَخْطِيطِ. تَتَكَوَّن الشَجَرَة مِن عَقْدِ \(\underline{n}\) وَحَوافّ \(e\). عُقْدَةِ \(\underline{n} = \langle l, E \rangle\) تَتَكَوَّن مِن تَسْمِيَةِ \( label(\underline{n}) = l \in F\cup A\)، وَالَّتِي تُشِير إِلَى حَقِيقَةِ \(f\) أَو فِعْلٍ \(a\)، وَمَجْمُوعَةِ مِن الحَوافّ \(E\). حافَةِ \( e = (\underline{n} \rightarrow \underline{c})\) تَرْبِط عُقْدَةِ أَصْلِ \(\underline{n}\) بِعُقْدَةِ فَرْعِ \(\underline{c}\).
بِالنَظَرِ إِلَى حافَةِ \(e = (\underline{n} \rightarrow \underline{c})\)، فَإِنَّ الدالَّةِ \(parent(\underline{c})\) تُعْطِي \(\underline{n}\). الدالَّةِ \(children(\underline{n})\) تُعْطِي مَجْمُوعَةِ مِن العَقْدِ بِحَيْثُ لِكُلِّ عُقْدَةِ \(c\)، \( parent(\underline{c}) = \underline{n}\). جِذْرَ الشَجَرَة هُوَ العُقْدَة الوَحِيدَةُ بِدُونِ أَصْلِ، أَيّ \(parent(\underline{r}) = None\).
مُشْكِلَةِ التَخْطِيطِ المرتخيه لِلحَذْف \(\Pi = \langle F, A, I, G\rangle\) تُحَدِّد شَجَرَةَ \(T_\Pi\). عُقْدَةِ \(\underline{r}\) هِيَ جِذْرَ \(T_\Pi\) وَلَها \(label (\underline{r}) = achieveGoal\). عُقْدَةِ فِعْلٍ \(\underline{a}\)، أَيّ عُقْدَةِ تَسْمِيَتُها فِعْلٍ، لَها أَطْفالٍ تَسْمِياتهم هِيَ شُرُوطها المُسْبَقَةِ \(f \in pre(label(\underline{a}))\). عُقْدَةِ حَقِيقَةِ \(\underline{f}\) لَها أَطْفالٍ تَسْمِياتهم هِيَ أَفْعالٍ \(a\) بِحَيْثُ \(label(\underline{f}) \in ef\!f(a)\).
الدالَّةِ \(L(l)\) تَرْبِط تَسْمِيَةِ \(l\) بِعَقْدِ الشَجَرَة الَّتِي لَها هٰذِهِ التَسْمِيَة: \[\begin{aligned} \nonumber L(l) &= \{ \forall \underline{n} : label(\underline{n}) = l\} \\ \intertext{% مَسارِ عُقْدَةِ هُوَ تَسَلْسُلُ بَدِيلٍ مِن عَقْدِ الحَقائِقِ وَالأَفْعالِ الَّذِي يَتِمّ إِنْشاؤه بِإِضافَة أَصْلِ العُقْدَة الحالِيَّةِ حَتَّى يَتِمّ الوُصُولِ إِلَى الجَذْر: } \nonumber T_{\Pi}^{path}(\underline{n}) &= [\underline{n}, parent(\underline{n}), ..., \underline{r}] \\ \intertext{% النَسْل لَعَقَدَهُ $ \underline{n} $ هُم جَمِيعِ العَقْدِ الَّتِي لَها $ \underline{n} $ فِي مَسارِها: } \nonumber T_{\Pi}^{desc}(\underline{n}) &= \{\forall \underline{d}: \underline{n} \in T_{\Pi}^{path}(\underline{d}) \}\end{aligned}\] يَتِمّ اِسْتِثْناءِ الأَفْعال مِن أَطْفالٍ عُقْدَةِ حَقِيقَةِ \( \underline{f} \) إِذا ظَهَرَت أَيّ شُرُوطٍ مُسْبَقَةٍ لِذٰلِكَ الفِعْلِ كَتَسْمِيات عَلَى أَيّ عُقْدَةِ فِي \( path(\underline{f}) \). هٰذا يَمْنَع الدَوْراتِ، الَّتِي مِن شَأْنِها أَنَّ تُمَثِّل مُتَطَلَّباتِ غَيْرِ قابِلَةٍ لِلتَحْقِيقِ.
الهَدَفَ مِن القِياس الاستدلالي دَرَجَةِ الأَهَمِّيَّةِ هُوَ تَقْدِيرٍ مَدَى تَكْرارِ حَقِيقَةِ ما يَجِب أَنَّ تُصْبِح صَحِيحَةٍ فِي تَوْزِيعِ مُعَيَّنٍ لِلخُطَط الجُزْئِيَّةِ. نَسْتَخْدِم سُلُوكِ وَكِيلُ غَيْرِ حَتْمِيٌّ (NDA) لَتَعْرِيف هٰذا التَوْزِيعِ. شَجَرَةَ فَرْعِيَّةٍ \( S_{\Pi} \) مِن \( T_{\Pi} \)، تَتَكَوَّن مِن مَجْمُوعَةِ فَرْعِيَّةٍ مِن العَقْدِ فِي \( T_{\Pi} \) وَمَساراتها، مُخْتارَةٍ وِفْقاً للخوارزميه [alg:subtree]. تَطْبِيقِ تَسَلْسُلُ الإِجْراءاتِ المُمَثَّلَةِ بِمَسار كُلِّ عُقْدَةِ وَرَقَةً داخِلَ \( S_{\Pi} \) سَيُؤَدِّي إِلَى تَحْقِيقِ الهَدَفَ. وَبِالتالِي، قَد يُعْتَبَر \( S_{\Pi} \) خُطَّةٍ جُزْئِيَّةٍ تَحْتَ شُرُوطٍ الاِسْتِرْخاء الحذفي.
تَفْسِيرنا، الَّذِي نُتابِعه فِي هٰذِهِ الوَرَقَةَ، هُوَ أَنَّ اِحْتِمالَيْهِ عالِيَةٍ للتقاطها مِن قِبَلَ مِثْلَ هٰذا الوَكِيلَ غَيْرِ الحَتْمِيَّ تُشِير إِلَى أَنَّ حَقِيقَةِ ما لَها أَهَمِّيَّةً كَبِيرَةٍ لِتَحْقِيقِ الهَدَفَ. الحَقائِقِ الَّتِي تُظْهِر فِي جَمِيعِ الخُطَطِ الجُزْئِيَّةِ الَّتِي يُمْكِن أَنَّ تَقْتَطِف يَجِب أَنَّ تَكُون فِي جَمِيعِ الخُطَطِ، وَبِالتالِي هِيَ مَعالِمُ بارِزَةٌ.
لِتُمَثِّل دَرَجَةِ الصِلَةِ \( \Xi(l) \) اِحْتِمالِ أَنَّ يَتِمّ أَخَذَ عَيِّنَةً مِن عُقْدَةِ بِتَسْمِيَة \( l \) بِواسِطَةِ NDA: \[\begin{aligned} \nonumber \Xi(l) &= P \left( \exists \underline{l} \in S_{\Pi} | label(\underline{l}) = l \right)\end{aligned}\] لِتُمَثِّل دَرَجَةِ الصِلَةِ المَحَلِّيَّةِ \( \Xi(l, \underline{n}) \) اِحْتِمالِ أَنَّ يَتِمّ أَخَذَ عَيِّنَةً مِن عُقْدَةِ بِتَسْمِيَة \( l \) بِواسِطَةِ NDA، بِناءَ عَلَى أَنَّ العُقْدَة \( \underline{n} \) (وَبِالتالِي \( S_{\Pi}^{path}(\underline{n}) \)) قَد تَمَّ أَخَذَ عَيِّنَةً مِنها. \[\begin{aligned} \label{eqn:localrel} \Xi(l, \underline{n}) &= P \left( \exists \underline{l} \in S_{\Pi}^{desc}(\underline{n}) | label(\underline{l}) = l \right) \end{aligned}\] إِذا كانَت \( label(\underline{n}) \) حَقِيقَةِ، فَإِنَّ أَيّاً مِن أَطْفالها قَد يَتِمّ أَخَذَ عَيِّنَةً مِنهُ، وَقَد يَكُون لَدَيهِم عُقْدَةِ بِتَسْمِيَة \( l \) بَيِّنَ نَسْلهم: \[\begin{aligned} \nonumber \shortintertext{$ \texttt{if } label(n) \in F: $ } \nonumber \Xi(l, \underline{n}) &= \sum_{\underline{c} \in children(\underline{n})} P \left( \underline{c} \in S_{\Pi}^{desc}(\underline{n}) \right) \times \Xi(l, \underline{c}) \end{aligned}\] يَخْتار NDA طِفْلاً واحِداً مِن عُقْدَةِ حَقِيقَةِ بِالتَساوِي، وَهٰذا يَعْنِي: \[\begin{aligned} \label{eqn:XiFactBasic} \Xi(l, \underline{n}) &= \sum_{\underline{c} \in children(\underline{n})} \frac { \Xi(l, \underline{c}) } { \left| children(\underline{n}) \right| }\end{aligned}\] إِذا كانَت \( label(\underline{n}) \) عَمَلاً، فَسَيَتِمّ أَخَذَ عَيِّنَةً مِن جَمِيعِ أَطْفالها. وَبِالتالِي فَإِنَّ \(\Xi(l, \underline{n})\) هِيَ 1 ناقِصَ اِحْتِمالِ أَنَّ لا يَكُون لِأَيّ مِن نَسْلهم المَأْخُوذ عَيِّنَةً مِنهُ تَسْمِيَةِ \(l\): \[\begin{aligned} \nonumber \shortintertext{$ \texttt{if } label(n) \in A: $ } \label{eqn:XiActBasic} \Xi(l, \underline{n}) &= 1 - \prod_{\underline{c} \in children(\underline{n})} \left( 1 - \Xi(l, \underline{c}) \right)\end{aligned}\]
اِحْتِمالِ أَنَّ يَتِمّ اِخْتِيارِ العُقْدَة \(\underline{n}\) بِواسِطَةِ NDA، \(\xi(\underline{n}) = P(\underline{n} \in S_{\Pi})\) يَعْتَمِد عَلَى عَدَدٍ الخِياراتِ البَدِيلَةِ الَّتِي كانَ يُمْكِن اِتِّخاذُها بَدَلاً مِن تِلْكَ الَّتِي تَصِل إِلَى تِلْكَ العُقْدَة. سَيَتِمّ دائِماً اِخْتِيارِ جِذْرَ الشَجَرَة: \[\begin{aligned} \nonumber \xi(\underline{r}) &= \textnormal{1}\end{aligned}\] بَيِّنَ الفِعْلِ وَشُرُوطِهِ المُسْبَقَةِ، لا يُوجَد لَدَى NDA خِياراتٍ لَاِتِّخاذها، لُذّاً يَتِمّ نَقْلِ \( \xi \) دُونِ تَغْيِيرٍ: \[\begin{aligned} \nonumber \xi(\underline{f}) &= \xi(parent(\underline{f}))\end{aligned}\] يَخْتار NDA فِعْلاً واحِداً يُمْكِن أَنَّ يُوَفِّر حَقِيقَةِ مِن مَجْمُوعَةِ الأَفْعال الَّتِي تُشَكِّل \(children(f)\): \[\begin{aligned} \label{eqn:CCAct} \xi(\underline{a}) &= \frac{\xi(parent(\underline{a}))}{\left| children(parent(\underline{a})) \right|}\end{aligned}\] حَيْثُ \(\underline{r}\)، \(\underline{f}\)، \(\underline{a}\) هِيَ عَقْدِ الجَذْر، الحَقِيقَةِ، وَالفِعْل عَلَى التَوالِي.
أَدَّنِي سَلَف مُشْتَرَكٍ (LCA) لِعُقْدَتَيْنِ \(\underline{n}\) وَ \(\underline{m}\) هُوَ أَدَّنِي عُقْدَةِ فِي الشَجَرَة الَّتِي تَكُون سَلَفاً لَكَلَآ العُقْدَتَيْنِ: \[% \label{eqn:LCAdef} \nonumber LCA(\underline{n},\underline{m}) = \underset{\underline{i} \in T^{path}_{\Pi}(\underline{n}) \cap T^{path}_{\Pi}(\underline{m})}{argmax}(|T^{path}_{\Pi}(\underline{i})|)\] هٰذِهِ العَمَلِيَّةِ تَكُون تَجْمِيعَيْهِ وَيُمْكِن تَعْمِيمها عَلَى أَيّ عَدَدٍ مِن العَقْدِ.
بُعْدَ ذٰلِكَ، نِصْفِ مَنْهَجنا لِحِسابِ مِقْياسِ الأَهَمِّيَّةِ المُقْتَرَحِ. نَبْدَأ بِبَعْضِ الأَساسِيّات. سَيَتِمّ تَوْفِيرِ الكود المُسْتَخْدِمُ لِتَنْفِيذِ وَاِخْتِبارِ هٰذا عَلَى الرابط التالِي 1.
تَسْمَح لَنا المُعادَلَةَ [eqn:localrel] بِأَنَّ نَعْتَبِر الأَحْفاد لَعَقَدَهُ مُعَيَّنَةٍ بِشَكْلٍ مُسْتَقِلٍّ عَن الفُرُوعِ الأُخْرَى الناشِئَةِ مِن أَسْلافها. يُمْكِن تَطْبِيقِ هٰذا بِشَكْلٍ تَكْرارِي لِحِسابِ مِقْياسِ الأَهَمِّيَّةِ المَحَلِّيِّ لَجَذْر الشَجَرَة: \(\Xi(l, \underline{r}) = \Xi(l)\).
العِباراتِ التالِيَةِ صَحِيحَةٍ بِوُضُوحٍ، وَتَسْمَح لَنا بِتَجاهُلِ مِقْياسِ الأَهَمِّيَّةِ المَحَلِّيِّ \(\Xi(l, \underline{n})\) لِأَيّ عَقْدِ بِدُونِ أَحْفاد لَهُم \(label(\underline{n}) = l\): \[\begin{aligned} \shortintertext{ $\texttt{إِذا } label(\underline{n}) = l $ } \nonumber &\implies &\Xi(l, \underline{n}) =& 1 \shortintertext{ $ \texttt{إِذا } T^{desc}_{\Pi}(\underline{n}) \cap L(l) = \emptyset $ } \nonumber &\implies &\Xi(l, \underline{n}) =& 0\end{aligned}\] نَظَراً لَعَقَدَهُ \( \underline{n} \) وَأَحَدَ أَحْفادها بِحَيْثُ أَنَّ جَمِيعِ العَقْدِ الَّتِي تَحْمِل العَلّامَةُ \(l\) وَهِيَ حَفِيدَةُ لَواحِده هِيَ أَيْضاً حَفِيدَةُ لِلأُخْرَى: \[\begin{aligned} \shortintertext{$ \texttt{إِذا } T^{desc}_{\Pi}(\underline{n}) \cap L(l) = T^{desc}_{\Pi}(\underline{d}) \cap L(l) $ } \nonumber &\implies &\Xi(l, \underline{n}) =& P\left( \underline{d} \in S_{\Pi}^{desc}(\underline{n}) \right) &\times \Xi(l, \underline{d}) \\ \nonumber && =& P\left( \underline{d} \in S_{\Pi} | \underline{n} \in S_{\Pi} \right) &\times \Xi(l, \underline{d}) \\ \label{eqn:NodeToDesc} && =& \frac{\xi(\underline{d})}{\xi(\underline{n})} &\times \Xi(l, \underline{d})\end{aligned}\]
الآنَ، لِنُفَكِّر فِي المُعادَلَةَ [eqn:XiFactBasic] عِنْدَما يَكُون لِكُلِّ طِفْلٍ \(\underline{c}\) لَعَقَدَهُ حَقِيقَةِ \(\underline{f}\) سَلِيلُ واحِدٍ \(\underline{d}\) بِتَسْمِيَة \(label(\underline{d}) = l\): \[\begin{aligned} \nonumber \Xi(l, \underline{f}) =& \sum_{ \underline{c} \in children(\underline{f}) } \frac { \Xi(l, \underline{c}) } { \left| children(\underline{f}) \right| }\end{aligned}\] بِاِسْتِخْدامِ المُعادَلَةَ [eqn:CCAct]، يُمْكِن كِتابَتِها كَالتالِي: \[\begin{aligned} \nonumber =& \sum_{ \underline{c} \in children(\underline{f}) } \frac { \Xi(l, \underline{c}) } { \frac { \xi(\underline{f}) } { \xi(\underline{c}) } } \\ \nonumber =& \sum_{\underline{c} \in children(\underline{f})} \frac {\Xi(l, \underline{c}) \times \xi(\underline{c})} {\xi(\underline{f})}\end{aligned}\] بُعْدَ ذٰلِكَ، بِاِسْتِخْدامِ المُعادَلَةَ [eqn:NodeToDesc]، يُمْكِن إِعادَةِ كِتابَتِها كَالتالِي: \[\begin{aligned} \nonumber =& \sum_{ \substack { \underline{c} \in children(\underline{f}) \\ \underline{l}~\models T_{\Pi}^{desc}(\underline{c})~\cap~L(l) } } \frac { \frac { \xi(\underline{l}) } { \xi(\underline{c}) } \times \Xi(l, \underline{l}) \times \xi(\underline{c}) } { \xi(\underline{f}) } \\ \nonumber =& \sum_{ \underline{l}~\in~T_{\Pi}^{desc}(\underline{f})~\cap~L(l) } \frac { \xi(\underline{l}) } { \xi(\underline{f}) } \\ \label{eqn:XiFact} =& \frac { 1 } { \xi(\underline{f}) } \sum_{ \underline{l}~\in~T_{\Pi}^{desc}(\underline{f})~\cap~L(l) } \xi(\underline{l})\end{aligned}\] إِذا كانَ جَمِيعِ السُلالَة لَعَقَدَهُ \( \underline{d} \in T_{\Pi}^{desc}(\underline{n}) \) إِمّا بِتَسْمِيَة \(label(\underline{d}) = l\)، أَو هِيَ عقدات حَقِيقَةِ الَّتِي تَنْطَبِق عَلَيها المُعادَلَةَ [eqn:XiFact]، يُمْكِن تَكْرارِ هٰذِهِ العَمَلِيَّةِ، مِمّا يُؤَدِّي إِلَى إِلْغاءِ مَزِيدٍ مِن الحُدُودِ \( \frac{1}{\xi(\underline{c})} \). إِذا كانَ بِعَضِّ العَقْدِ بِتَسْمِيَة \(label(\underline{d_i}) = l\) لَها \( LCA(\underline{d_1},\underline{d_2}) = \underline{a} \) الَّتِي هِيَ فِعْلٍ (أَيّ، aLCA؛ أَنْظُر أَدَنّاهُ)، فَإِنَّ المُعادَلَةَ [eqn:NodeToDesc] لا تَنْطَبِق بَيِّنَ \( \underline{c_i} \) وَ \( \underline{d_i}\). سَتَنْطَبِق بَيِّنَ \( \underline{a_i} \) وَ \( \underline{c_i} \)، وَلٰكِن يَجِب حِسابِ \( \Xi(l,~\underline{a}) \) وِفْقاً لِلمُعادَلَة [eqn:XiActBasic]: \[\begin{aligned} \nonumber \Xi(l, \underline{f}) =& \frac { 1 } { \xi(\underline{f}) } \sum_{ \underline{l} \in fLCAs } \xi(\underline{l}) + \sum_{ \underline{a} \in aLCAs } \frac { \xi(\underline{a}) } { \xi(\underline{f}) } \times \Xi(l, \underline{a}) \\ \label{eqn:XiAnyFact} =& \frac { 1 } { \xi(\underline{f}) } \left( \sum_{ \underline{l} \in fLCAs } \xi(\underline{l}) \right. + \left. \sum_{ \underline{a} \in aLCAs } \xi(\underline{a}) \times \Xi(l, \underline{a}) \right)\end{aligned}\] حَيْثُ:
aLCAs - أَدُنَى جد مشَتَرَكَ لِلَأَفْعال: أَيّ عَقْدِ فِعْلٍ هِيَ الجِدِّ المُشْتَرَكِ الأَدْنَى لِأَيّ مَجْمُوعَةِ مِن \( L(l) \cap T_{\Pi}^{desc}(\underline{f})\)
fLCAs - أَدُنَى جد مشَتَرَكَ لِلَحَقائِق: أَيّ عَقْدِ بِتَسْمِيَة \( l \) الَّتِي تَتَفَرَّع مَساراتها عِنْدَ عَقْدِ الحَقائِقِ:
\(
fLCAs =
\left\{
\forall \underline{l} \in L(l) :
LCA(\underline{l}_i,\underline{l}_j) \in F \cap T_{\Pi}^{desc}(\underline{f})
\right\}
\)
يُمْكِن حِسابِ \(\Xi(l)\) مِن \(L(l)\) بِتَحْدِيدِ aLCAs، حِسابِ \(\Xi(l,\underline{c})\) لَأَطْفالهم المُباشِرِينَ بِالمُعادَلَة [eqn:XiAnyFact]، وَدَمْجهم وِفْقاً لِلمُعادَلَة [eqn:XiActBasic].
لِلمُشْكِلاتِ العَمَلِيَّةِ، \( T_{\Pi} \) قَد تَكُون كَبِيرَةٍ جِدّاً، مِمّا يَحُول دُونِ تَمْثِيلَها بِالكامِلِ. يُمْكِن العُثُورِ عَلَى حَدٍّ أَدَّنِي لِ \( \Xi(l) \) بِاِسْتِخْدامِ شَجَرَةَ مُسْتَكْشِفه جُزْئِيّاً \( \overline{T_{\Pi}} \). العَقْدِ الَّتِي لِ \( \xi(\underline{n}) \) قِيمَةَ صَغِيرَةٌ تُساهِم بِأَقَلِّ فِي \( \Xi(l) \)، وَتُوجَد بَعِيداً عَن الجَذْر، مِمّا يُؤَدِّي إِلَى تَقارُبٍ هٰذا الحَدِّ الأَدْنَى بِسُرْعَةٍ نَحْوَ الأَعْلَى كَلْماً تَمَّ اِسْتِكْشافٍ المِنْطَقَةِ القَرِيبَةِ مِن الجَذْر. نَسْتَخْدِم الخوارزميه [alg:exploration] لِأَخْذِ عَيِّناتٍ مِن \( \overline{T_{\Pi}} \) مِن \( T_{\Pi} \). عَتَبَةِ الاِسْتِكْشافِ \( \rho \) هِيَ تَقْدِيرٍ لَنِسْبَة كَمِّيَّةِ المَعْلُوماتِ المَوْجُودَةِ فِي الحُدُودِ مُقارَنَةً بِالشَجَرَة المُسْتَكْشِفَة. وَجَدْنا أَنَّ أَداءِ \( h_{\Xi} \) كَمِعْيارٍ لَيِسَ حَسّاسا لِلتَغْيِيرات الصَغِيرَةِ فِي قِيمَةَ \( \rho \). ما لَم يُذْكَر خِلافٍ ذٰلِكَ، نَسْتَخْدِم \( \rho = 0.2 \) فِي بَقِيَّةِ هٰذِهِ الوَرَقَةَ. يَضْمَن الشَرْطُ الأَوَّلِ فِي الحَلْقَةِ الخارِجِيَّةِ أَثْناءَ الخوارزميه [alg:exploration] أَنَّ الأَخْذِ بِالعَيْنات لا يَنْتَهِي مُبَكِّراً بِسَبَبِ تَقَلُّب مُصْطَلَحاته عِنْدَما تَكُون صَغِيرَةٌ.
لاحَظَ أَنَّ هٰذا الإِجْراءَ فِي أَخَذَ العَيْنات يَخْتَلِف عَن الأَخْذِ بِالعَيْنات الَّذِي يُؤَدِّيه ال NDA الاِفْتِراضِيّ. كُلّاً إِجْراءَيَّ الأَخْذِ بِالعَيْنات يَخْتارانِ الإِجْراءاتِ الَّتِي تُلَبِّي حَقِيقَةِ حُدُودِيَّةٍ عَشْوائِيّا، لٰكِنَّ ال NDA يَسْتَكْشِف جَمِيعِ الحَقائِقِ الَّتِي هِيَ شُرُوطٍ مُسْبَقَةٍ لِهٰذِهِ الإِجْراءاتِ، بَيْنَما يَخْتار إِجْراءِ الأَخْذِ بِالعَيْنات فِي الخوارزميه [alg:exploration] شَرْطاً مُسْبَقاً واحِداً. هٰذا يَضْمَن أَنَّ \( T_{\Pi} \) يَتِمّ أَخَذَ عَيِّناتٍ مِنها بِتَنَوُّع أَكْبَرَ دُونِ التَرْكِيزِ كَثِيراً عَلَى عَدَدٍ قَلِيلٍ مِن العَيْنات القَرِيبَةِ مِن الجَذْر الَّتِي تَتَفَرَّع عَلَى نِطاقِ واسِعٍ، مِمّا يُؤَدِّي إِلَى تَجاهُلُ أَشِقّائها.
لَقَد تَمَّ إِجْراءِ الكَثِيرَ مِن الأَبْحاثِ لِإِيجادِ أَقَلَّ سَلَف مُشْتَرَكٍ لَزَوْج مِن العَقْدِ فِي شَجَرَةَ. تَمَّت تَرْجَمَةٍ هٰذِهِ المُشْكِلَةِ إِلَى مُشْكِلَةِ حِسابِ اِسْتِعْلام الحَدِّ الأَدْنَى لِلمَدَى (Fischer2006). تَعْقِيدِ هٰذِهِ العَمَلِيَّةِ هُوَ \( O(h) \) لِمُعالَجَةِ الشَجَرَة مُسْبَقاً، حَيْثُ \(h\) هُوَ اِرْتِفاعِ الشَجَرَة، ثُمَّ \( O(1) \) لِكُلِّ اِسْتِعْلام عَن زَوْج مِن العَقْدِ. وَبِالتالِي، سَتُكَلِّف هٰذِهِ الطَرِيقَةِ \( O(h + n^2) \) لِإِيجادِ أَقَلَّ سَلَف مُشْتَرَكٍ لِكُلِّ زَوْج مِن العَقْدِ، حَيْثُ \(n\) هُوَ عَدَدٍ العَقْدِ الَّتِي نُرِيد إِيجادِ أَقَلَّ سَلَف مُشْتَرَكٍ لَها.
بَدَلاً مِن هٰذا الإِجْراءَ المُعْتَمَدُ، يُمْكِننا الاِسْتِفادَةِ مِن حَقِيقَةِ أَنَّ العَدِيدَ مِن أَقَلَّ الأَسْلاف المُشْتَرَكَةِ سَيَتِمّ مُشارَكَتِها بَيِّنَ أَزْواج مُتَعَدِّدَةِ؛ حَيْثُ يُوجَد فِي أَقْصَى الحالاتِ \(hn\) أَقَلَّ سَلَف مُشْتَرَكٍ فَرِيد. نَقُوم أَوَّلاً بِفَرْز العَقْدِ حَسَبَ مَساراتها (بِتَعْقِيد \(O(hn\log(n)) \) ). لا يُهِمّ التَرْتِيبِ، المُهِمِّ فَقَط أَنَّ العَقْدِ الَّتِي لَها نَفْسِ المَسارُ حَتَّى مَسافَةِ مُعَيَّنَةٍ مِن الهَدَفَ تَكُون فِي مَجْمُوعَةِ مُتَجاوِره، لُذّاً يَتِمّ مُعامَلَةِ العَقْدِ كَرُمُوزٍ فِي تَسَلْسُلُ (أَيّ المَسارُ الَّذِي يَبْدَأ عِنْدَ الهَدَفَ) وَيَتِمّ فَرْزُها أَبْجَدِيّا حَسَبَ تَسْمِياتها. يَتِمّ التَنَقُّلِ عَلَى طُولِ المَساراتِ المفروزه (بِأَسْوَأ تَعْقِيدِ حالَةِ \( O(hn) \))، وَالتَحَقُّقِ مِن الاِخْتِلافاتِ بَيِّنَ العَقْدِ فِي المَساراتِ (وَما إِذا كانَت عَقْدِ فِعْلِيَّةٍ أَم لا) المُتَجاوِرَة فِي تَرْتِيبَ الفَرْزِ يُنْتِج قائِمَةً مَرْتَبَةً مِن أَقَلَّ الأَسْلاف المُشْتَرَكَةِ الفِعْلِيَّةِ (aLCAs). يَتِمّ حِسابِ مَجْمُوعاتٍ مِن aLCAs مَرَّةً واحِدَةٍ لِكُلِّ حَقِيقَةِ، ثُمَّ يَتِمّ تَصْفِيَتها بِواسِطَةِ \(\sigma\) عِنْدَما يَحْتاج إِلَى حِسابِ \(h_{\Xi}(\sigma)\).
فِي أَيّ حالَةِ مُعَيَّنَةٍ \( \sigma \)، جَمِيعِ الحَقائِقِ فِي الحالَةِ \( f \in \sigma \) صَحِيحَةٍ وَلا تَحْتاج إِلَى تَحْقِيقِ مِن قِبَلَ المُخَطَّطِ. يَجِب أَلّا يَأْخُذ مِقْياسِ الصِلَةِ المُعْتَمَدُ عَلَى الحالَةِ لِتُسَمِّيه مُعَيَّنَةٍ، \( \Xi_{\sigma}(l) \)، فِي الاِعْتِبارِ أَجْزاءِ مِن \( \overline{T_{\Pi}} \) الَّتِي تَحَقَّقَ هٰذِهِ الحَقائِقِ عَلَى أَنَّها ذاتِ صِلَةٍ. يُمَثِّل مِقْياسِ الصِلَةِ المُطْبَقَ عَلَى حالَةِ \( \Xi_{\sigma}(l) \) اِحْتِمالِ أَنَّ يَتِمّ اِخْتِيارِ عُقْدَةِ بِتَسْمِيَة \( l \) بِواسِطَةِ NDA، إِذا تَوَقَّفَت عِنْدَ العَقْدِ الَّتِي هِيَ صَحِيحَةٍ فِي الحالَةِ \( \sigma \) (لِأَنَّها لا تَحْتاج إِلَى إِجْراءِ لَتَزْوِيدها). يَتِمّ حِسابِهِ وِفْقاً لِلمُعادَلاتِ [eqn:XiAnyFact] وَ [eqn:XiActBasic] المُطَبَّقَةِ عَلَى الشَجَرَة المَقْطُوعَةِ عِنْدَ العَقْدِ بِتَسْمِيات فِي \( \sigma \): \[\nonumber \overline{T_{\Pi}/\sigma} = \overline{T_{\Pi}} \left/ \bigcup_{\substack{ \forall \underline{f} \in L(f) \\ \forall f \in \sigma }} T^{desc}_{\Pi}(\underline{f}) \right.\] يَتِمّ العُثُورِ عَلَى هٰذا لِجَمِيعِ الحَقائِقِ، وَيَتِمّ حِسابِ المَنْهَجِيَّة لِحالَةِ كَما يَلِي: \[\nonumber h_{\Xi}(\sigma) = \sum_{l \in F} \Xi_{\sigma}(l)\] بِما أَنَّ مَنْهَجِيَّةً مِقْياسِ الصِلَةِ هِيَ مَجْمُوعُ الاِحْتِمالاتِ، \(h_{\Xi}(\sigma) \in \mathbf{R}\). مِن ناحِيَةٍ أُخْرَى، يَتَطَلَّب نِظامِ التَخْطِيطِ LAMA أَنَّ تَعُود المنهجيات بِقِيمَةِ صَحِيحَةٍ. لِلسَماحِ بِاِسْتِخْدامِ وَمُقارَنَة مَعَ LAMA، يَتِمّ تَقْرِيبِ \(h_{\Xi}(\sigma)\) إِلَى العَدَدَ الصَحِيحِ الأَقْرَبُ، لِلأَسَفِ فَقَد بِعَضِّ المَعْلُوماتِ فِي العَمَلِيَّةِ.
لَقَد قُمْنا بِتَقْيِيم التَجارِبِ التالِيَةِ:
يُعْتَبَر مِقْياسِ دَرَجَةِ الصِلَةِ S1 أَبْطَآ مِن مِقْياسِ عَدَّ العَلاماتِ البارِزَةِ S2 فِي حَلٍّ مُشْكِلاتِ التَخْطِيطِ القِياسِيَّةِ، وَلٰكِنَّهُ قادِرٌ عَلَى إِيجادِ خُطَّةٍ فِي مُعْظَمَ الأَوْقات؛ وَ
يُحَسِّن مِقْياسِ دَرَجَةِ الصِلَةِ S1 بِشَكْلٍ كَبِيرٍ القُدْرَةِ عَلَى إِيجادِ الخُطَطِ مُقارَنَةً بِمِقْياسِ عَدَّ العَلاماتِ البارِزَةِ S2 فِي المَجالاتِ الَّتِي لا تَحْتَوِي عَلَى عَلاماتِ بارِزَةٌ غَيْرِ تافِهه.
تَسْتَنِد الفَرْضِيَّة H1 إِلَى الفَهْمِ القائِل بِأَنَّهُ عِنْدَما يَتِمّ اِسْتِكْشافٍ الشَجَرَة بِالكامِلِ (أَيّ \( \overline{T_{\Pi}} = T_{\Pi} \))، سَتَحْصُل العَلاماتِ البارِزَةِ عَلَى دَرَجَةِ صِلَةٍ \( \Xi(l) = 1 \) وَالحَقائِقُ الَّتِي لا تُظْهِر فِي أَيّ خُطَطِ صالِحَةٌ سَتَحْصُل عَلَى دَرَجَةِ صِلَةٍ \( \Xi(l) = 0 \). بِمَعْنَى آخَرِ، يُوَفِّر اِسْتِخْدامِ مِقْياسِ دَرَجَةِ الصِلَةِ الوُصُولِ إِلَى جَمِيعِ المَعْلُوماتِ المُتاحَةِ لخوارزميه التَخْطِيطِ بِاِسْتِخْدامِ مِقْياسِ عَدَّ العَلاماتِ البارِزَةِ، مَعَ الأَخْذِ فِي الاِعْتِبارِ أَيْضاً مَعْلُوماتٍ إِضافِيَّةً حَوْلَ الحَقائِقِ ذاتِ الصِلَةِ وَلٰكِن غَيْرِ الأَساسِيَّةِ، مِمّا سَيُؤَدِّي إِلَى حِسابِ إِضافِيٍّ. الفَرْضِيَّة H2 صَحِيحَةٍ لِأَنَّهُ، بَيْنَما لَن يَكُون لَدَى مِقْياسِ عَدَّ العَلاماتِ البارِزَةِ S2 أَيّ عَلاماتِ بارِزَةٌ غَيْرِ تافِهه لِتَوْجِيهِ بَحْثُهُ، فَإِنَّ مِقْياسِ دَرَجَةِ الصِلَةِ S1 سَيَظَلّ يَمْتَلِك تُدْرَجا إِرْشادِيّا مَعْلُوماتِيّا لِلمُتابَعَة، مَعَ إِمْكانِيَّةَ قِيادَتِهِ إِلَى حُلُولٍ (أَفْضَلَ) لِمُشْكِلاتٍ التَخْطِيطِ.
تَمَّ تَقْيِيمِ هٰذِهِ الفرضيات بِاِسْتِخْدامِ بِنْيَةَ مُخَطَّطٍ لاما (Richter2010)، بِاِسْتِخْدامِ إِمّا مِقْياسِ دَرَجَةِ الصِلَةِ S1 أَو مِقْياسِ عَدَّ العَلاماتِ البارِزَةِ الحالِيَّ S2؛ اِسْتِخْدامِ S2 كانَ مِعْيارنا الأَساسِيُّ. يَسْتَخْدِم لاما إِجْراءِ بَحَثَ \(A^*\) المَوْزُون (بِاِسْتِخْدامِ الوَزْنِ الاِفْتِراضِيّ = 10) مَعَ أَحَدُ المَقايِيسِ (S1 أَو S2). تَمَّ تَقْيِيدِ جَمِيعِ البُحُوثِ بِحَدِّ أَقْصَى لِلذاكِرَة العَشْوائِيَّةِ يَبْلُغ 8GB. تَمَّت مُقارَنَةً أَدائهم فِي حَلٍّ جَمِيعِ المُشْكِلاتِ ال 674 المُحَدَّدَةِ فِي مُجَلَّدٍ الأَمْثِلَة لَمُسْتَوْدَع HSP2 (Bonet2001) وِفْقاً لِلمَقايِيسِ الادائيه التالِيَةِ:
نِسْبَةَ المُشْكِلاتِ الَّتِي تَمَّ حَلِّها/لَم يَتِمّ حَلِّها؛
الوَقْتِ المُسْتَغْرِق فِي البَحْثِ عَن خُطَّةٍ قِبَلَ العُثُورِ عَلَى واحِدَةٍ؛
عَدَدٍ الحالاتِ المُوسِعَةِ قِبَلَ العُثُورِ عَلَى خُطَّةٍ؛ وَ
طُولِ الخُطَّةِ المَوْجُودَةِ.
هٰذِهِ مَقايِيسِ مُعْتَرَف بِها جَيِّداً لَتَقْيِيم أَداءِ هٰذِهِ المُشْكِلاتِ التَخْطِيطِيَّة.
لَتَقْيِيم H2، قُمْنا بِإِنْشاءِ مُواصَفاتِ PDDL جَدِيدَةٍ لِلمَجالات الَّتِي لا تَحْتَوِي عَلَى مَعالِمُ بِاِسْتِثْناءِ الحَقائِقِ المَوْجُودَةِ فِي الهَدَفَ وَالحالَة الأَوَّلِيَّةِ. تَمَّ تَحْقِيقِ ذٰلِكَ مِن خِلالَ دَمْجِ زَوْج مِن المُشْكِلاتِ، \( \pi_1 \)، \( \pi_2 \) الَّتِي تَمَّ حَلِّها بِاِسْتِمْرارٍ بِاِسْتِخْدامِ كُلّاً الخُطَّتَيْنِ بِطَرِيقَةٍ تَمْنَع تَفاعُلهما. هٰذا يَضْمَن أَنَّ كُلِّ مُشْكِلَةِ جَدِيدَةٍ يُمْكِن حَلِّها بِواسِطَةِ 2 خُطَطِ عَلَى الأَقَلِّ لا تَتَداخَل فِيها الحَقائِقِ أَو الأَفْعال المَعْنِيَّةِ.
لَتَوْلِيد \( merged(\Pi_1, \Pi_2) \)، تَمَّ إِضافَةً تَسْمِيَةِ فَرِيدَةٍ لِكُلِّ مُشْكِلَةِ إِلَى جَمِيعِ العَناصِرِ المُحَدَّدَةِ بِالمَجال أَو المُشْكِلَةِ (الأَنْواع، الثَوابِتِ، المَفاهِيمِ، الأَفْعال، الأَشْياءَ) فِي كُلِّ مُشْكِلَةِ. هٰذا يَضْمَن عَدَمِ مُشارَكَةِ أَيّ عُنْصُرٍ اِسْماً مَعَ العَناصِرِ فِي المُشْكِلَةِ الَّتِي يَتِمّ دَمْجها مَعَها. إِذا لَم تُسْتَخْدَم مُشْكِلَةِ الأَنْواع، يَتِمّ تَطْبِيقِ نَوْعٍ جَدِيدٍ يَتَكَوَّن فَقَط مِن تَسْمِيَتُها الفَرِيدَة عَلَى جَمِيعِ الثَوابِتِ وَالأَشْياء داخِلَها. ثُمَّ تَتَأَلَّف المُشْكِلَةِ المُدْمَجَة الجَدِيدَةِ مِن جَمِيعِ العَناصِرِ المُسَمّاةَ مِن مُشْكِلَتَيَّ المَصْدَرُ، مَعَ التَعْدِيلاتِ التالِيَةِ:
يَتِمّ تَعْرِيفٍ فعلين جَدِيدَيْنِ:
\( a_1: pre(a_1) = G_1; ef\!f(a_1) = \{winning\}\)
\( a_2: pre(a_2) = G_2; ef\!f(a_2) = \{winning\}\).
تَحْتَوِي المُشْكِلَةِ المُدْمَجَة عَلَى هَدَفَ واحِدٍ:
\( G_{merged} = \{winning\}\)
تَمَّ إِنْشاءِ ما مَجْمُوعُهُ 500 مُشْكِلَةِ بِهٰذا الإِجْراءَ مِن خِلالَ اِخْتِيارِ زَوْج عَشْوائِيٍّ مِن المُشْكِلاتِ مِن مَجْمُوعَةِ تِلْكَ الَّتِي تَمَّ حَلِّها بِشَكْلٍ فَرْدِيٌّ بِواسِطَةِ S1 وَ S2. البَرْنامَجِ المُسْتَخْدِمُ لِهٰذا غَيْرِ قادِرٌ عَلَى التَعامُلِ مَعَ PDDL الَّذِي، عَلَى الرَغْمِ مِن أَنَّهُ صالِح، لا يَتْبَع بِعَضِّ الاِتِّفاقِيّات. كَلْماً حَدَثَ هٰذا، تَمَّ اِخْتِيارِ زَوْج جَدِيدٍ عَشْوائِيّا لِلتَقْيِيم التَجْرِيبِيُّ.
مِن بَيِّنَ 674 مُشْكِلَةِ تَخْطِيطِ فِي مُسْتَوْدَع أُمَثِّله HSP2، تُظْهِر الجَدْوَلُ [tab:standardsolvefail] عَدَدٍ المُشْكِلاتِ الَّتِي تَمَّ حَلِّها بِاِسْتِخْدامِ كُلِّ مِن الإِسْتراتِيجِيّات (أَيّ، S1، S2) مَعَ مُخَطَّطٍ LAMA. لاحَظَ أَنَّ S2 قَدَّمَ أَداءِ أَفْضَلَ وَلٰكِن S1 تَمَكَّنَ مِن إِيجادِ خُطَطِ لِمُعْظَمِ المُشْكِلاتِ الَّتِي حَلِّها S2.
| تَمَّ حَلِّها بِواسِطَةِ | S1 | S2 | كُلاهما | لا أَحَدُ |
|---|---|---|---|---|
| عَدَدٍ المُشْكِلاتِ | 273 | 370 | 261 | 147 |
لِلمُشْكِلاتِ الَّتِي تَمَّ حَلِّها بِواسِطَةِ كُلّاً الإِسْتراتِيجِيَّتَيْنِ:
المُتَوَسِّطِ النِسْبِيّ بَيِّنَ أَوْقاتِ البَحْثِ (ث) لِ \(\textbf{S1}/\textbf{S2} = 951.34 \pm 3303.31\)؛
المُتَوَسِّطِ النِسْبِيّ بَيِّنَ عَدَدٍ الحالاتِ المُوسِعَةِ لِ \(\textbf{S1}/\textbf{S2} = 6.86 \pm 29.53\)؛ وَ
المُتَوَسِّطِ النِسْبِيّ بَيِّنَ طُولِ الخُطَّةِ المَوْجُودَةِ لِ \(\textbf{S1}/\textbf{S2} = 1.13 \pm 0.29\).
هٰذِهِ النَتائِجِ كانَت ضِمْنَ الخُطُوطِ المُتَوَقَّعَةِ وَتُدَعِّم بِقُوَّةٍ الفَرْضِيَّة H1.
مِن بَيِّنَ 500 مُشْكِلَةِ تَمَّ تَوْلِيدها وِفْقاً لِلإِجْراء المُوَضِّح فِي القِسْمِ [sec:lmfgeneration]، يُلَخِّص الجَدْوَلُ [tab:mergedsolvefail] عَدَدٍ المُشْكِلاتِ الَّتِي تَمَّ حَلِّها بِاِسْتِخْدامِ كُلِّ مِن الإِسْتراتِيجِيّات (S1, S2) بِاِسْتِخْدامِ مُخَطَّطٍ LAMA. لاحَظَ أَنَّ الأَداءِ كانَ أَفْضَلَ بِاِسْتِخْدامِ S1 مُقارَنَةً ب S2.
| تَمَّ الحَلِّ بِواسِطَةِ | S1 | S2 | كُلاهما | لا أَحَدُ |
|---|---|---|---|---|
| عَدَدٍ المُشْكِلاتِ | 335 | 122 | 108 | 151 |
تُظْهِر النَتائِجِ أَنَّ S1 قَد تَمَّ قِياسه عَلَى أَنَّهُ أَفْضَلَ بِكَثِيرٍ مِن S2 وِفْقاً لَمَقايِيس الأَداءِ M2، M3، وَ M4 لِغالِبِيَّةِ هٰذِهِ المُشْكِلاتِ المُدْمَجَة. S2 فَشَلِ فِي حَلٍّ مُعْظَمَ هٰذِهِ الفِئَةِ مِن المُشْكِلاتِ. بِالنِسْبَةِ لِلمُشْكِلاتِ الَّتِي تَمَّ حَلِّها بِواسِطَةِ كُلّاً الإِسْتراتِيجِيَّتَيْنِ:
المُتَوَسِّطِ النِسْبِيّ بَيِّنَ أَوْقاتِ البَحْثِ (ث) لِ \(\textbf{S1}/\textbf{S2} = 123.08 \pm 295.25\)؛
المُتَوَسِّطِ النِسْبِيّ بَيِّنَ عَدَدٍ الحالاتِ المُوسِعَةِ لِ \(\textbf{S1}/\textbf{S2} = 0.64 \pm 1.77\)؛ وَ
المُتَوَسِّطِ النِسْبِيّ بَيِّنَ طُولِ الخُطَّةِ المَوْجُودَةِ لِ \(\textbf{S1}/\textbf{S2} = 2.17 \pm 2.40\).
هٰذِهِ النَتائِجِ تَدْعَم بِقُوَّةٍ فَرْضِيَّةَ H2.
المُخَطَّطِ لا يَتَأَثَّر بِالتَغْيِيراتِ الصَغِيرَةِ فِي \(\rho\). يُظْهِر أَنَّ اِسْتِكْشافٍ المَزِيدِ مِن الشَجَرَة (أَيّ التَوَقُّفِ عِنْدَما يَتِمّ الوُصُولِ إِلَى نِسْبَةَ أَقَلَّ بَيِّنَ المَعْلُوماتِ فِي الحُدُودِ وَ\( \overline{T_{\Pi}} \)) لا يُحَسِّن مِن قُدْرَةِ \( h_{\Xi} \) عَلَى حَلٍّ المُشْكِلاتِ. بِاِسْتِخْدامِ ذاكِرَةِ الوُصُولِ العَشْوائِيِّ الإِضافِيَّة، يَجْعَل مِن الصَعْبِ عَلَى المُخَطَّطِ حَلٍّ المُشْكِلاتِ ضِمْنَ حُدُودِ ذاكِرَةِ الوُصُولِ العَشْوائِيِّ الخاصَّةِ بِهِم.
تُوَفِّر النَتائِجِ التَجْرِيبِيَّة بِعَضِّ الرُؤَى المُثِيرَةِ لِلاِهْتِمامِ. تَحَسُّب دَرَجَةِ الصِلَةِ لَشَجَره مُسْتَكْشِفه بِالكامِلِ (\( \overline{T_{\Pi}} = T_{\Pi} \)) عَلَى أَنَّها عَدَدٍ الحَقائِقِ الَّتِي تُعْتَبَر مَعالِمُ لِلخُطَط المُنْطَلِقَة مِن \( \sigma \) (حَيْثُ \( \Xi_\sigma(l) = 1\))، مُضافا إِلَيها الصِلَةِ المَحْسُوبَة لَحَقائِق أُخْرَى. فِي حالَةِ مُشْكِلاتِ التَخْطِيطِ القِياسِيَّةِ، بِالإِضافَةِ إِلَى استغراق وَقْتٍ أَطْوَلِ لِحِسابِ وَاِسْتِخْدامِ هٰذِهِ المَعْلُوماتِ الإِضافِيَّة، يَبْدُو أَنَّ اِسْتِخْدامِ الإِرْشادِ المُقْتَرَحِ مِن قَبِلَنا يُعِيق قُدْرَةِ المُخَطَّطِ عَلَى إِيجادِ خُطَّةٍ ضِمْنَ الحُدُودِ المَوارِدِ المَفْرُوضَةِ. تَفْسِيرنا لِذٰلِكَ هُوَ أَنَّ الحَقائِقِ ذاتِ الصِلَةِ وَلٰكِن لَيِسَت ضَرُورِيَّةٌ، الَّتِي يَكُون لَها \( \Xi_\sigma(l) \) عالِياً وَلٰكِن أَقَلَّ مِن 1، تَوَجَّهَ المُخَطَّطِ نَحْوَ خُطَطِ مُتَنافِسه مُحْتَمَلَةٍ. هٰذا “التَشْتِيت” يُؤَدِّي إِلَى إِيجادِ خُطَطِ تَتَضَمَّن عَناصِرِ مِن خُطَطِ جُزْئِيَّةٍ أُخْرَى كانَ مِن المُمْكِنِ أَنَّ يَجِدها، مِمّا يُؤَدِّي إِلَى خُطَطِ أَطْوَلِ. فِي المُشْكِلاتِ الَّتِي يَكُون فِيها تَداخُلٌ أَقَلَّ بَيِّنَ الخُطَطِ المُحْتَمَلَةِ، يَكُون النِسْبَةِ بَيِّنَ طُولِ الخُطَطِ (عِنْدَما يَجِد كُلّاً مِن S1 وَ S2 خُطَّةٍ) أَكْبَرَ. الخُطَطِ الَّتِي وَجَدَها S1 فِي المُشْكِلاتِ الخالِيَةِ مِن المَعالِمِ تَحْتَوِي عَلَى أَفْعالٍ مِن كُلّاً المُشْكِلَتَيْنِ المَصْدَرُ، بَيْنَما الخُطَطِ الَّتِي وَجَدَها S2 لا تَفْعَل ذٰلِكَ. المَعْلُوماتِ المشتته تَزِيد أَيْضاً مِن تَكْلِفَةِ الاِسْتِكْشافِ (M2 وَ M3)، مِمّا يُؤَدِّي إِلَى زِيادَةِ عَدَدٍ المُشْكِلاتِ الَّتِي لا يُمْكِن حَلِّها ضِمْنَ حُدُودِ المَوارِدِ (RAM).
بِالنِسْبَةِ لِلمُشْكِلاتِ الخالِيَةِ مِن المَعالِمِ، يُمْكِن لِ S2 فَقَط أَنَّ يُخْبَر أَنَّ خُطَّةٍ جُزْئِيَّةٍ قَد تَكُون جَيِّدَةٍ عِنْدَما يَجِد أَحَدُ حَقائِقَ الهَدَفَ. حَتَّى ذٰلِكَ الحِينِ، يَبْحَث عَلَى سَطْحِ مُسَطَّح، مِمّا يَزِيد المَسافَةِ مِن الحالَةِ الأَوَّلِيَّةِ فِي جَمِيعِ الاِتِّجاهاتِ. بِالمُقابِلِ، S1، أَيّ الإِرْشادِ المُقْتَرَحِ لِدَرَجَةِ الصِلَةِ، قادِرٌ عَلَى تَسَلُّقِ سَطْحِ مَعْلُوماتِي يُوَجِّهه نَحْوَ الخُطَطِ المُحْتَمَلَةِ. نَظَراً لِأَنَّ S1 يُكافِئ المُخَطَّطِ لِإِيجادِ حَقائِقَ ذاتِ صِلَةٍ بِخُطَط بَدِيلَةٍ، وَلٰكِن قَد تَكُون مُنْفَصِلَةٍ، فَإِنَّهُ يَمِيل إِلَى تَضْمِينِ بِعَضِّ الأَفْعال فِي الخُطَّةِ النِهائِيَّةِ الَّتِي لَم تُساهِم فِي تَحْقِيقِ الهَدَفَ. نَعْتَقِد أَنَّ هٰذا يُفَسِّر سَبَبُ إِيجاده لَخُطَط أَطْوَلِ مِن S2، خاصَّةٍ فِي المُشْكِلاتِ المَعْرُوفَةِ بِأَنَّها قابِلَةٍ لِلحَلِّ بِخُطَط مُنْفَصِلَةٍ. هٰذا هُوَ مُنْتِجٍ غَيْرِ مَقْصُود مِن الطَرِيقَةِ الَّتِي تَمَّ بِها إِنْشاءِ هٰذِهِ المَجالاتِ وَقَد لا يَكُون الحالِ فِي المُشْكِلاتِ الَّتِي تَمَّ إِنْشاؤها بِطُرُقٍ أُخْرَى.
بِشَكْلٍ عامَ، المُلاحَظَةُ الرَئِيسِيَّةِ هِيَ أَنَّ إِرْشاد دَرَجَةِ الصِلَةِ الخاصِّ بِنا قادِرٌ عَلَى تَوْجِيهِ مُخَطَّطٍ LAMA نَحْوَ حَلٍّ فِئَةٌ مِن مُشْكِلاتِ التَخْطِيطِ الَّتِي يَكُون فِيها عَدَّ العَلاماتِ غَيْرِ فَعّالٌ. يَأْتِي ذٰلِكَ عَلَى حِسابِ كَوْنُهُ أَكْثَرَ تَكْلِفَةِ لِلحِساب، وَأَداء أَسْوَأ فِي المُشْكِلاتِ القِياسِيَّةِ. لِذٰلِكَ، يُمْكِن تَوْصِيَته فَقَط عَلَى فِئَةٌ المُشْكِلاتِ الَّتِي يَتَفَوَّق فِيها؛ تِلْكَ الَّتِي لَدَيها عَدَدٍ قَلِيلٍ أَو لا تُوجَد عَلاماتِ غَيْرِ تافِهه. لاحَظَ، مَعَ ذٰلِكَ، أَنَّ العَلاماتِ يَتِمّ تَحْدِيدِها قِبَلَ أَنَّ تَبْدَأ إِجْراءاتِ بَحَثَ الخُطَّةِ، مِمّا يَعْنِي أَنَّ هُناكَ طَرِيقَةِ سَهْلَةً وَطَبِيعِيّه لِلاِسْتِفادَةِ مِن كُلّاً الإِرْشادَيْنِ: أَخْتِر عَدَّ العَلاماتِ فِي المُشْكِلاتِ الَّتِي تَحْتَوِي عَلَى عَلاماتِ مُحَدَّدَةٍ جَيِّداً، وَاِسْتَخْدَمَ إِرْشاد دَرَجَةِ الصِلَةِ الخاصِّ بِنا لِلمُشْكِلاتِ الَّتِي تَحْتَوِي فَقَط عَلَى عَلاماتِ تافِهه. فِي الأَعْمالِ المُسْتَقْبَلِيَّةِ، نَأْمَل فِي اِسْتِكْشافٍ هٰذِهِ الرُؤَى بِشَكْلٍ أَكْبَرَ مَعَ مُشْكِلاتِ تَخْطِيطِ إِضافِيَّةً (وَأَكْثَرُ تَعْقِيداً).