W3Schools 線上編輯器 - W3Schools 教學

Python

Java

from itertools import permutations

def calculate_distance(route, distances):
    total_distance = 0
    for i in range(len(route) - 1):
        total_distance += distances[route[i]][route[i + 1]]
    total_distance += distances[route[-1]][route[0]]
    return total_distance

def brute_force_tsp(distances):
    n = len(distances)
    cities = list(range(1, n))
    shortest_route = None
    min_distance = float('inf')
    
    for perm in permutations(cities):
        current_route = [0] + list(perm)
        current_distance = calculate_distance(current_route, distances)
        
        if current_distance < min_distance:
            min_distance = current_distance
            shortest_route = current_route
    
    shortest_route.append(0)
    return shortest_route, min_distance

distances = [
    [0, 2, 2, 5, 9, 3],
    [2, 0, 4, 6, 7, 8],
    [2, 4, 0, 8, 6, 3],
    [5, 6, 8, 0, 4, 9],
    [9, 7, 6, 4, 0, 10],
    [3, 8, 3, 9, 10, 0]
]

route, total_distance = brute_force_tsp(distances)
print("Route:", route)
print("Total distance:", total_distance)

#Python

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define NUM_CITIES 6

void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

int calculateDistance(int *route, int distances[NUM_CITIES][NUM_CITIES]) {
    int totalDistance = 0;
    for (int i = 0; i < NUM_CITIES; i++) {
        totalDistance += distances[route[i]][route[(i + 1) % NUM_CITIES]];
    }
    return totalDistance;
}

void copyArray(int *source, int *destination, int length) {
    for (int i = 0; i < length; i++) {
        destination[i] = source[i];
    }
}

void permute(int *array, int start, int end, int distances[NUM_CITIES][NUM_CITIES], int *shortestRoute, int *minDistance) {
    if (start == end) {
        int currentDistance = calculateDistance(array, distances);
        if (currentDistance < *minDistance) {
            *minDistance = currentDistance;
            copyArray(array, shortestRoute, NUM_CITIES);
        }
    } else {
        for (int i = start; i < end; i++) {
            swap((array + start), (array + i));
            permute(array, start + 1, end, distances, shortestRoute, minDistance);
            swap((array + start), (array + i)); // backtrack
        }
    }
}

int main() {
    int distances[NUM_CITIES][NUM_CITIES] = {
        {0, 2, 2, 5, 9, 3},
        {2, 0, 4, 6, 7, 8},
        {2, 4, 0, 8, 6, 3},
        {5, 6, 8, 0, 4, 9},
        {9, 7, 6, 4, 0, 10},
        {3, 8, 3, 9, 10, 0}
    };

int route[NUM_CITIES], shortestRoute[NUM_CITIES];
    for (int i = 0; i < NUM_CITIES; i++) {
        route[i] = i;
    }

int minDistance = INT_MAX;
    permute(route, 0, NUM_CITIES, distances, shortestRoute, &minDistance);

printf("Shortest Route: ");
    for (int i = 0; i < NUM_CITIES; i++) {
        printf("%d ", shortestRoute[i]);
    }
    // Ensure to print the return to the starting city for completeness
    printf("%d", shortestRoute[0]);
    printf("\nTotal Distance: %d\n", minDistance);

return 0;
}

// C

import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static int calculateDistance(ArrayList<Integer> route, int[][] distances) {
        int totalDistance = 0;
        for (int i = 0; i < route.size() - 1; i++) {
            totalDistance += distances[route.get(i)][route.get(i + 1)];
        }
        totalDistance += distances[route.get(route.size() - 1)][route.get(0)];
        return totalDistance;
    }

public static void bruteForceTSP(int[][] distances) {
        int n = distances.length;
        ArrayList<Integer> cities = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            cities.add(i);
        }
        ArrayList<Integer> shortestRoute = new ArrayList<>();
        int minDistance = Integer.MAX_VALUE;
        
        ArrayList<ArrayList<Integer>> allPerms = generatePermutations(cities);
        for (ArrayList<Integer> perm : allPerms) {
            ArrayList<Integer> currentRoute = new ArrayList<>();
            currentRoute.add(0);
            currentRoute.addAll(perm);
            int currentDistance = calculateDistance(currentRoute, distances);
            
            if (currentDistance < minDistance) {
                minDistance = currentDistance;
                shortestRoute = new ArrayList<>(currentRoute);
            }
        }
        
        shortestRoute.add(0);
        System.out.print("Route: ");
        for (int city : shortestRoute) {
            System.out.print(city + " ");
        }
        System.out.println("\nTotal Distance: " + minDistance);
    }

public static ArrayList<ArrayList<Integer>> generatePermutations(ArrayList<Integer> list) {
        if (list.size() == 0) {
            ArrayList<ArrayList<Integer>> result = new ArrayList<>();
            result.add(new ArrayList<>());
            return result;
        }
        
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        int firstElement = list.remove(0);
        ArrayList<ArrayList<Integer>> recursiveReturn = generatePermutations(list);
        for (ArrayList<Integer> li : recursiveReturn) {
            for (int i = 0; i <= li.size(); i++) {
                ArrayList<Integer> temp = new ArrayList<>(li);
                temp.add(i, firstElement);
                result.add(temp);
            }
        }
        return result;
    }

public static void main(String[] args) {
        int[][] distances = {
            {0, 2, 2, 5, 9, 3},
            {2, 0, 4, 6, 7, 8},
            {2, 4, 0, 8, 6, 3},
            {5, 6, 8, 0, 4, 9},
            {9, 7, 6, 4, 0, 10},
            {3, 8, 3, 9, 10, 0}
        };

bruteForceTSP(distances);
    }
}

//Java