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

for i in I: # for each item if x[i].x == 1: # if the item was selected print('item', i, 'was selected') # updates the total weight and value of the solution total_weight += weights[i] total_value += values[i] print('total weight', total_weight) print('total value', total_value)

item 0 was selected item 2 was selected item 3 was selected item 5 was selected total weight 34 total value 65

مشكلة البائع المتجول Traveling Salesman Problem

مشكلة البائع المتجول (TSP) - Traveling Salesman Problem) من المشكلات الأخرى التي يمكن حلها ببرمجة الأعداد الصحيحة المختلطة، وهي مشكلة مألوفة تُعنى بتحديد أقصر مسار يمكن أن يسلكه بائع متجول لزيارة مدن معينة مرة واحدة، دون أن يكرر زيارة أي منها، ثم يعود للمدينة الأصلية، ويصور الشكل 5.7 نسخة من هذه المشكلة.

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

تُمثل كل دائرة (عقدة) مدينة أو موقعاً يجب زيارته، وهناك حافة تربط بين موقعين إذا كان من الممكن السفر بينهما، ويُمثل الرقم الموجود على الحافة التكلفة (المسافة) بين الموقعين. في هذا المثال، تم ترقيم المواقع وفقاً لترتيبها في الحل الأمثل للمشكلة. وتكون التكلفة الإجمالية للطريق 1 ← 2 ← 4 ← 3 ← 1 تساوي 80 = 10 + 25 + 30 + 15. وهو أقصر طريق ممكن لزيارة كل مدينة مرة واحدة فقط والعودة إلى نقطة البداية. توجد تطبيقات عملية لمشكلة البائع المتجول في الخدمات اللوجستية، والنقل، وإدارة الإمدادات والاتصالات، فهي تنتمي إلى عائلة أوسع من مشكلات تحديد الطريق التي تشمل أيضاً مشكلات شهيرة أخرى موضحة فيما يلي:

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

تتضمن مشكلة تحديد مسار المركبات (Vehicle Routing Problem) إيجاد الطرق المثلى لأسطول من المركبات لتوصيل السلع أو الخدمات لمجموعة من العملاء في ظل تقليل المسافة الإجمالية المقطوعة إلى الحد الأدنى، وتشمل تطبيقاتها الخدمات اللوجستية وخدمات التوصيل وجمع النفايات.

تتضمن مشكلة الاستلام والتسليم (Pickup and Delivery Problem) إيجاد الطرق المثلى للمركبات لكي تستلم (تُحمّل أو تُركب) وتُسلم (تُوصل) البضائع أو الأشخاص إلى مواقع مختلفة، وتشمل تطبيقاتها خدمات سيارات الأجرة، والخدمات الطبية الطارئة، وخدمات النقل الجماعي.

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

286

وزارة التعليم Ministry of Education 2025 - 1447

for i in I: # for each item if x[i].x == 1: # if the item was selected print('item', i, 'was selected') # updates the total weight and value of the solution total_weight += weights[i] total_value += values[i] print('total weight', total_weight) print('total value', total_value)item 0 was selected item 2 was selected item 3 was selected item 5 was selected total weight 34 total value 65--- SECTION: مشكلة البائع المتجول --- مشكلة البائع المتجول Traveling Salesman Problemمشكلة البائع المتجول (TSP) - Traveling Salesman Problem) من المشكلات الأخرى التي يمكن حلها ببرمجة الأعداد الصحيحة المختلطة، وهي مشكلة مألوفة تُعنى بتحديد أقصر مسار يمكن أن يسلكه بائع متجول لزيارة مدن معينة مرة واحدة، دون أن يكرر زيارة أي منها، ثم يعود للمدينة الأصلية، ويصور الشكل 5.7 نسخة من هذه المشكلة.الأمثلة الواردة في مخطط مشكلة البائع المتجول متصلة اتصالاً تاماً، فهناك حافة تصل كل زوج من العقد بالآخر.تُمثل كل دائرة (عقدة) مدينة أو موقعاً يجب زيارته، وهناك حافة تربط بين موقعين إذا كان من الممكن السفر بينهما، ويُمثل الرقم الموجود على الحافة التكلفة (المسافة) بين الموقعين. في هذا المثال، تم ترقيم المواقع وفقاً لترتيبها في الحل الأمثل للمشكلة. وتكون التكلفة الإجمالية للطريق 1 ← 2 ← 4 ← 3 ← 1 تساوي 80 = 10 + 25 + 30 + 15. وهو أقصر طريق ممكن لزيارة كل مدينة مرة واحدة فقط والعودة إلى نقطة البداية. توجد تطبيقات عملية لمشكلة البائع المتجول في الخدمات اللوجستية، والنقل، وإدارة الإمدادات والاتصالات، فهي تنتمي إلى عائلة أوسع من مشكلات تحديد الطريق التي تشمل أيضاً مشكلات شهيرة أخرى موضحة فيما يلي:شكل 5.7: نسخة على مشكلة البائع المتجول تتضمن مشكلة تحديد مسار المركبات (Vehicle Routing Problem) إيجاد الطرق المثلى لأسطول من المركبات لتوصيل السلع أو الخدمات لمجموعة من العملاء في ظل تقليل المسافة الإجمالية المقطوعة إلى الحد الأدنى، وتشمل تطبيقاتها الخدمات اللوجستية وخدمات التوصيل وجمع النفايات.تتضمن مشكلة الاستلام والتسليم (Pickup and Delivery Problem) إيجاد الطرق المثلى للمركبات لكي تستلم (تُحمّل أو تُركب) وتُسلم (تُوصل) البضائع أو الأشخاص إلى مواقع مختلفة، وتشمل تطبيقاتها خدمات سيارات الأجرة، والخدمات الطبية الطارئة، وخدمات النقل الجماعي.تتضمن مشكلة جدولة مواعيد القطارات (Train Timetabling Problem) إيجاد جداول زمنية مثالية للقطارات في شبكة سكك الحديد في ظل تقليل نسبة التأخير إلى الحد الأدنى وضمان الاستخدام الفعال للموارد، وتشمل تطبيقاتها النقل بالسكك الحديدية والجدولة.2025 - 1447--- VISUAL CONTEXT --- **DIAGRAM**: شكل 5.7: نسخة على مشكلة البائع المتجول Description: A network diagram representing the Traveling Salesman Problem. It shows four circular nodes, labeled 1, 2, 3, and 4, representing cities or locations. These nodes are interconnected by lines (edges) representing possible travel routes. Each edge has a numerical label indicating the cost or distance between the connected nodes. The connections and costs are: Node 1 to Node 2 (20), Node 1 to Node 4 (10), Node 1 to Node 3 (15), Node 2 to Node 4 (25), Node 2 to Node 3 (35), and Node 3 to Node 4 (30). The diagram illustrates a complete graph where every node is directly connected to every other node. Table Structure: Headers: N/A Rows: Calculation needed: not applicable Data: The diagram visually represents a graph where nodes are cities and edges are routes with associated costs. The text describes an optimal path 1 → 2 → 4 → 3 → 1 with a total cost of 80 (10 + 25 + 30 + 15). Key Values: Nodes: 1, 2, 3, 4, Edge 1-2: 20, Edge 1-4: 10, Edge 1-3: 15, Edge 2-4: 25, Edge 2-3: 35, Edge 3-4: 30 Context: This diagram serves as a visual representation of the Traveling Salesman Problem, illustrating the concept of nodes (cities) and weighted edges (travel costs/distances) that are central to the problem's definition and solution. It is directly referenced in the accompanying text to explain the problem's structure and an example optimal path.