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

إنشاء خوارزمية حل القوة المفرطة لمشكلة البائع المتجول

Creating a Brute-Force Solver for the Traveling Salesman Problem

تستخدم الدالة التالية خوارزمية حل القوة المفرطة لتعداد جميع الطرق الممكنة (التباديل) وإظهار أقصر مسار. وتقبل هذه الدالة مصفوفة المسافة وموقع الانطلاق والتوقف الذي تظهره الدالة ()create_problem_instance. لاحظ أن الحل الممكن لنسخة مشكلة البائع المتجول (TSP) هي تبديل مدن، يبدأ من مدينة startstop (الانطلاق والتوقف) ثم ينتهي إليها.

from itertools import permutations def brute_force_solver(dist_matrix, location_ids, startstop): # excludes the startstop location location_ids = location_ids - {startstop} # generate all possible routes (location permutations) all_routes = permutations(location_ids) best_distance = float('inf') # initializes to the highest possible number best_route = None # best route so far, initialized to None for route in all_routes: # for each route distance = 0 # total distance in this route curr_loc = startstop # current location for next_loc in route: distance += dist_matrix[curr_loc,next_loc] # adds the distance of this step curr_loc = next_loc # goes to the next location distance += dist_matrix[curr_loc,startstop] # goes to the startstop location if distance < best_distance: # if this route has lower distance than the best route best_distance = distance best_route = route # adds the startstop location at the beginning and end of the best route and returns return [startstop] + list(best_route) + [startstop], best_distance

تستخدم خوارزمية حل القوة المفرطة أداة ()permutations لإنشاء كل الطرق الممكنة. لاحظ أن موقع startstop (الانطلاق والتوقف) يُستبعد من التباديل؛ لأنه يجب أن يظهر دائمًا في بداية كل طريق ونهايته. فعلى سبيل المثال، إذا كانت لديك أربعة مواقع 0 و1 و2 و3، وكان الموقع 0 هو موقع startstop (الانطلاق والتوقف)، ستكون قائمة التباديل الممكنة كما يلي:

for route in permutations({1,2,3}): print(route)

(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)

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

288

--- SECTION: إنشاء خوارزمية حل القوة المفرطة لمشكلة البائع المتجول --- إنشاء خوارزمية حل القوة المفرطة لمشكلة البائع المتجول--- SECTION: Creating a Brute-Force Solver for the Traveling Salesman Problem --- Creating a Brute-Force Solver for the Traveling Salesman Problemتستخدم الدالة التالية خوارزمية حل القوة المفرطة لتعداد جميع الطرق الممكنة (التباديل) وإظهار أقصر مسار. وتقبل هذه الدالة مصفوفة المسافة وموقع الانطلاق والتوقف الذي تظهره الدالة ()create_problem_instance. لاحظ أن الحل الممكن لنسخة مشكلة البائع المتجول (TSP) هي تبديل مدن، يبدأ من مدينة startstop (الانطلاق والتوقف) ثم ينتهي إليها.--- SECTION: Python Code for Brute-Force Solver --- from itertools import permutations def brute_force_solver(dist_matrix, location_ids, startstop): # excludes the startstop location location_ids = location_ids - {startstop} # generate all possible routes (location permutations) all_routes = permutations(location_ids) best_distance = float('inf') # initializes to the highest possible number best_route = None # best route so far, initialized to None for route in all_routes: # for each route distance = 0 # total distance in this route curr_loc = startstop # current location for next_loc in route: distance += dist_matrix[curr_loc,next_loc] # adds the distance of this step curr_loc = next_loc # goes to the next location distance += dist_matrix[curr_loc,startstop] # goes to the startstop location if distance < best_distance: # if this route has lower distance than the best route best_distance = distance best_route = route# adds the startstop location at the beginning and end of the best route and returns return [startstop] + list(best_route) + [startstop], best_distanceتستخدم خوارزمية حل القوة المفرطة أداة ()permutations لإنشاء كل الطرق الممكنة. لاحظ أن موقع startstop (الانطلاق والتوقف) يُستبعد من التباديل؛ لأنه يجب أن يظهر دائمًا في بداية كل طريق ونهايته. فعلى سبيل المثال، إذا كانت لديك أربعة مواقع 0 و1 و2 و3، وكان الموقع 0 هو موقع startstop (الانطلاق والتوقف)، ستكون قائمة التباديل الممكنة كما يلي:--- SECTION: Python Code for Permutations Example --- for route in permutations({1,2,3}): print(route)--- SECTION: Output of Permutations Example --- (1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)2023 - 1447--- VISUAL CONTEXT --- **FIGURE**: Python Code for Brute-Force Solver Function Description: A Python code block defining the `brute_force_solver` function. It imports `permutations` from `itertools`. The function takes `dist_matrix`, `location_ids`, and `startstop` as arguments. It excludes the `startstop` location from `location_ids` to generate permutations of the remaining locations. It initializes `best_distance` to infinity and `best_route` to None. It then iterates through all possible routes, calculates the total distance for each route, including the return to `startstop`, and updates `best_distance` and `best_route` if a shorter route is found. Finally, it returns the best route (starting and ending with `startstop`) and its distance. Context: This code provides a practical example of implementing a brute-force algorithm to solve the Traveling Salesman Problem by generating and evaluating all possible permutations of locations.**FIGURE**: Python Code for Permutations Example Description: A Python code block demonstrating the use of the `permutations` function. It iterates through all permutations of the set `{1, 2, 3}` and prints each permutation. Context: This example illustrates how the `permutations` function generates all possible orderings of a given set of elements, which is a core component of the brute-force approach to the Traveling Salesman Problem.**FIGURE**: Output of Permutations Example Description: The text output showing all six possible permutations of the set `{1, 2, 3}`. Each permutation is enclosed in parentheses, with elements separated by commas. Data: The output lists the following permutations: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). Key Values: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) Context: This output visually confirms the result of the `permutations` function, showing all possible orderings for a small set, which helps in understanding the combinatorial nature of the Traveling Salesman Problem.