مشكلة البائع المتجول مع قيود الاتصال - كتاب الذكاء الإصطناعي - الصف 12 - الفصل 1 - المملكة العربية السعودية

تشمل الصيغة الكاملة لمشكلة البائع المتجول نوعًا إضافيًا آخرًا من القيود لضمان حساب الطرق المتصلة، ففي نسخة مشكلة البائع المتجول الواردة في الشكل 5.8 يُفترض أن الموقع 0 هو موقع الانطلاق والتوقف. في هذا المثال، أقصر طريق ممكن هو 0 ← 3 ← 4 ← 1 ← 2، بمسافة سفر إجمالية قدرها 24. ولكن عند وجود قيد اتصال سيكون هناك حل صحيح آخر يشمل طريقين غير متصلين هما: 0 ← 3 ← 4 ← 0 و 1 ← 2. وهذا الحل المتمثل في وجود طريقين يمثل قيود الوصول والمغادرة التي تم تعريفها في المقطع البرمجي السابق؛ لأن كل موقع يدخل له ويخرج منه مرة واحدة فقط، ولكن هذا الحل غير مقبول لمشكلة البائع المتجول. يمكن فرض حل يشمل طريقًا واحدًا متصلاً بإضافة متغير القرار y_i لكل موقع i، وستحافظ هذه المتغيرات على ترتيب زيارة كل موقع في الحل.

شكل 5.8: نسخة مشكلة البائع المتجول

# adds a decision variable for each location y = [solver.add_var(var_type = INTEGER) for i in location_ids]

على سبيل المثال، إذا كان الحل هو: 0 ← 3 ← 4 ← 1 ← 2 ← 0، فستكون قيم y كما يلي: 2 = y_1، 3 = y_2، 0 = y_3، 1 = y_4، والموقع 0 هو موقع الانطلاق والتوقف، ولذلك لا تؤخذ قيمة y الخاصة به بعين الاعتبار. يمكن استخدام متغيرات القرار الجديدة هذه لضمان الاتصال من خلال إضافة قيد جديد لكل انتقال i ← j لا يشمل موقع startstop (الانطلاق والتوقف).

# adds a connectivity constraint for every transition that does not include the startstop for (i, j) in product(location_ids - {startstop}, location_ids - {startstop}): # ignores transitions from a location to itself if i != j: solver += y[j] - y[i] >= (N+1) * x[i, j] - N

إذا كانت 1 = x_ij وتم إدراج هذا الانتقال i ← j في الحل، فإن المتباينة الواردة في الأعلى تصبح 1 + y[i] >= y[j]، ومعنى ذلك أن المواقع التي ستُزار لاحقًا لا بد أن تكون قيمة y الخاصة بها أعلى، بالإضافة إلى قيود الوصول والمغادرة. وسيكون الطريق الذي لا يشمل موقع الانطلاق والتوقف صحيحًا فقط إذا: • بدأ وانتهى بالموقع نفسه؛ لضمان أن يكون لكل موقع وصول واحد ومغادرة واحدة فقط. • خصصت قيم y أعلى لكل المواقع التي ستُزار لاحقًا؛ لأن y[j] يجب أن تكون أكبر من y[i] لكل الانتقالات التي تم إدراجها في الطريق. ويؤدي هذا أيضًا إلى تجنب إضافة الحافة نفسها من اتجاه مختلف، على سبيل المثال: i ← j و j ← i. ولكن إذا كان الموقع يمثل بداية الطريق ونهايته، فلا بد أن تكون قيمة y الخاصة به هي أكبر وأصغر من قيم كل المواقع الباقية في الطريق. ونظرًا لاستحالة هذا الأمر، فستؤدي إضافة قيد الاتصال إلى استبعاد أية حلول بها طرق لا تشمل موقع الانطلاق والتوقف.

وزارة التعليم 291 2025 - 1447

تشمل الصيغة الكاملة لمشكلة البائع المتجول نوعًا إضافيًا آخرًا من القيود لضمان حساب الطرق المتصلة، ففي نسخة مشكلة البائع المتجول الواردة في الشكل 5.8 يُفترض أن الموقع 0 هو موقع الانطلاق والتوقف. في هذا المثال، أقصر طريق ممكن هو 0 ← 3 ← 4 ← 1 ← 2، بمسافة سفر إجمالية قدرها 24. ولكن عند وجود قيد اتصال سيكون هناك حل صحيح آخر يشمل طريقين غير متصلين هما: 0 ← 3 ← 4 ← 0 و 1 ← 2. وهذا الحل المتمثل في وجود طريقين يمثل قيود الوصول والمغادرة التي تم تعريفها في المقطع البرمجي السابق؛ لأن كل موقع يدخل له ويخرج منه مرة واحدة فقط، ولكن هذا الحل غير مقبول لمشكلة البائع المتجول. يمكن فرض حل يشمل طريقًا واحدًا متصلاً بإضافة متغير القرار y_i لكل موقع i، وستحافظ هذه المتغيرات على ترتيب زيارة كل موقع في الحل.--- SECTION: شكل 5.8: نسخة مشكلة البائع المتجول --- شكل 5.8: نسخة مشكلة البائع المتجول# adds a decision variable for each location y = [solver.add_var(var_type = INTEGER) for i in location_ids]على سبيل المثال، إذا كان الحل هو: 0 ← 3 ← 4 ← 1 ← 2 ← 0، فستكون قيم y كما يلي: 2 = y_1، 3 = y_2، 0 = y_3، 1 = y_4، والموقع 0 هو موقع الانطلاق والتوقف، ولذلك لا تؤخذ قيمة y الخاصة به بعين الاعتبار. يمكن استخدام متغيرات القرار الجديدة هذه لضمان الاتصال من خلال إضافة قيد جديد لكل انتقال i ← j لا يشمل موقع startstop (الانطلاق والتوقف).# adds a connectivity constraint for every transition that does not include the startstop for (i, j) in product(location_ids - {startstop}, location_ids - {startstop}): # ignores transitions from a location to itself if i != j: solver += y[j] - y[i] >= (N+1) * x[i, j] - Nإذا كانت 1 = x_ij وتم إدراج هذا الانتقال i ← j في الحل، فإن المتباينة الواردة في الأعلى تصبح 1 + y[i] >= y[j]، ومعنى ذلك أن المواقع التي ستُزار لاحقًا لا بد أن تكون قيمة y الخاصة بها أعلى، بالإضافة إلى قيود الوصول والمغادرة. وسيكون الطريق الذي لا يشمل موقع الانطلاق والتوقف صحيحًا فقط إذا: • بدأ وانتهى بالموقع نفسه؛ لضمان أن يكون لكل موقع وصول واحد ومغادرة واحدة فقط. • خصصت قيم y أعلى لكل المواقع التي ستُزار لاحقًا؛ لأن y[j] يجب أن تكون أكبر من y[i] لكل الانتقالات التي تم إدراجها في الطريق. ويؤدي هذا أيضًا إلى تجنب إضافة الحافة نفسها من اتجاه مختلف، على سبيل المثال: i ← j و j ← i. ولكن إذا كان الموقع يمثل بداية الطريق ونهايته، فلا بد أن تكون قيمة y الخاصة به هي أكبر وأصغر من قيم كل المواقع الباقية في الطريق. ونظرًا لاستحالة هذا الأمر، فستؤدي إضافة قيد الاتصال إلى استبعاد أية حلول بها طرق لا تشمل موقع الانطلاق والتوقف.2025 - 1447--- VISUAL CONTEXT --- **DIAGRAM**: شكل 5.8: نسخة مشكلة البائع المتجول Description: A network diagram representing an instance of the Traveling Salesperson Problem. It shows 6 nodes labeled 0, 1, 2, 3, 4, 5. Node 0 is the starting and stopping point. The nodes are connected by edges with associated weights (distances/costs). Data: The diagram illustrates a graph with nodes and weighted edges. The nodes are: 0, 1, 2, 3, 4, 5. The edges and their weights are: (0,2,5), (0,3,3), (0,4,7), (1,2,5), (1,3,5), (1,4,6), (2,4,4), (3,4,5). Key Values: Nodes: 0, 1, 2, 3, 4, 5, Edge (0,2) weight: 5, Edge (0,3) weight: 3, Edge (0,4) weight: 7, Edge (1,2) weight: 5, Edge (1,3) weight: 5, Edge (1,4) weight: 6, Edge (2,4) weight: 4, Edge (3,4) weight: 5 Context: This diagram visually represents the problem described in the text, showing the locations (nodes) and the connections (edges) with their associated costs or distances (weights) for the Traveling Salesperson Problem. It is used to explain the constraints and decision variables in the context of finding an optimal path.