path_distance = lambda r,c: np.sum([np.linalg.norm(c[r[p]]-c[r[p-1]]) for p in range(len(r))])
two_opt_swap = lambda r,i,k: np.concatenate((r[0:i],r[k:-len(r) i-1:-1],r[k 1:len(r)]))

def two_opt(cities,improvement_threshold): # 2-opt Algorithm adapted from https://en.wikipedia.org/wiki/2-opt
    route = np.arange(cities.shape[0]) # Make an array of row numbers corresponding to cities.
    improvement_factor = 1 # Initialize the improvement factor.
    best_distance = path_distance(route,cities) # Calculate the distance of the initial path.

    while improvement_factor > improvement_threshold: # If the route is still improving, keep going!
        distance_to_beat = best_distance # Record the distance at the beginning of the loop.

        for swap_first in range(1,len(route)-2): # From each city except the first and last,
            for swap_last in range(swap_first 1,len(route)): # to each of the cities following,
                new_route = two_opt_swap(route,swap_first,swap_last) # try reversing the order of these cities
                new_distance = path_distance(new_route,cities) # and check the total distance with this modification.

                if new_distance < best_distance: # If the path distance is an improvement,
                    route = new_route # make this the accepted best route
                    best_distance = new_distance # and update the distance corresponding to this route.
        improvement_factor = 1 - best_distance/distance_to_beat # Calculate how much the route has improved.
    return route # When the route is no longer improving substantially, stop searching and return the route.

from math import radians,cos,sin

lat = cities2['lattitude'].map(radians)
lon = cities2['longitude'].map(radians)
x = lon.map(cos)*lat.map(cos)*6371
y = lon.map(cos)*lat.map(sin)*6371

cities2["lat_radians"] = lat
cities2["lon_radians"] = lon
cities2["x"] = x
cities2["y"] = y
cities2.head()

df = cities.copy()

scaler = MinMaxScaler(feature_range=(0, 100), copy=True)
scaled_df = scaler.fit_transform(df)
scaled_df = pd.DataFrame(scaled_df, columns=['x1', 'x2'])

cities = np.asarray(cities)

scaled = np.asarray(scaled_df)

route = two_opt(scaled,0.001)
route

I have one TSP problem, here I'm facing time complexity. How can I remove the for loop and how to reduce the time complexity?

Could anyone help to optimize it or ensure it can work on an increasingly large number of cities?

CodePudding user response：

Using the CPython interpreter for that is not efficient. Consider using a native language, a JIT like Numba, Cython or a natively compiled module that does that for you (if any). Using Numpy functions (like np.linalg.norm) on scalar items or very-small arrays is very inefficient (see this related post).

The TSP problem is NP-Hard so the best known algorithm known yet is exponential. Several decades of the best worldwide researchers failed so far to find a better algorithm that is not exponential (nor to prove P=NP which is considered to be rather wrong by researchers but they also failed to prove P!=NP yet). If the number of cities is big, I advise you to make use of an approximation (which can be computed in polynomial time).