lab1/src/ptsm.cpp
/* using recursive DFS to find the best solution. */
using recursive DFS to find the best solution.
using recursive DFS to find the best solution .
void dfs(
    int** matrix, 
    const int& num_cities, 
    int current_layer, 
    int previous_city, 
    int current_city, 
    int current_distance, 
    int visited_cities, 
    int& min_distance, 
    int* current_route, 
    int* best_route 
) 
{
    current_route[current_layer] = current_city;
    current_distance += matrix[previous_city][current_city];
    int min_distance_holder = INT32_MAX;
    #pragma omp atomic read 
    min_distance_holder = min_distance;
    if (current_distance >= min_distance_holder) {
        return;
    }
    if (current_layer == num_cities - 1) {
        #pragma omp critical 
        {
            if (current_distance < min_distance) {
                min_distance = current_distance;
                for (int i = 0; i < num_cities; i++) {
                    best_route[i] = current_route[i];
                }
            }
        }
    } else {
        visited_cities |= (1 << current_city);
        for (int i = 1; i < num_cities; i++) {
            if (!(visited_cities & (1 << i))) {
                dfs(
                    matrix, 
                    num_cities, 
                    current_layer + 1, 
                    current_city, 
                    i, 
                    current_distance, 
                    visited_cities, 
                    min_distance, 
                    current_route, 
                    best_route 
                );
            }
        }
    }
}
void dfs ( int * * matrix , const int & num_cities , int current_layer , int previous_city , int current_city , int current_distance , int visited_cities , int & min_distance , int * current_route , int * best_route ) { current_route [ current_layer ] = current_city ; current_distance += matrix [ previous_city ] [ current_city ] ; int min_distance_holder = INT32_MAX ; #pragma  omp atomic read  min_distance_holder = min_distance ; if ( current_distance >= min_distance_holder ) { return ; } if ( current_layer == num_cities - 1 ) { #pragma  omp critical  { if ( current_distance < min_distance ) { min_distance = current_distance ; for ( int i = 0 ; i < num_cities ; i ++ ) { best_route [ i ] = current_route [ i ] ; } } } } else { visited_cities |= ( 1 << current_city ) ; for ( int i = 1 ; i < num_cities ; i ++ ) { if ( ! ( visited_cities & ( 1 << i ) ) ) { dfs ( matrix , num_cities , current_layer + 1 , current_city , i , current_distance , visited_cities , min_distance , current_route , best_route ) ; } } } }
using recursive DFS to find the best solution.
using recursive DFS to find the best solution .
// the distance matrix; shared and only read operations are used // number of cities; shared and only read operations are used // how many cities, including the current one, have been visited // the id of previous city visited // the id of current city visited // the current total distance so far // indicator of visited cities, using bit manipulation // minimum distance so far; shared and put inside critical section // array of current path // array of the best path found so far; shared and put inside critical section // update the route and distance so far // abandon the current search if the distance is already greater than the minimum // use atomic read here // if we have visited all the cities, and the distance so far is smaller // update the minimum distance inside critical section // also update the best route inside critical section // if we have not visited all the cities, should continue to visit the next one // update the visited cities in the indicator // traverse the following cities // if the city chosen has not been visited, recursively run DFS // same distance matrix // same number of cities // we have visited one more city // the current city should become the previous one for next round // the next city // current distance has been updated // visited cities have been updated // same minimum distance // current route has been updated // same best route