Блог

У меня есть список из 12 городов, связанных друг с другом без исключения. Единственное, что вызывает беспокойство, — это время в пути. Здесь указано название каждого города. Матрица расстояний (представляющая время в пути в минутах) между парами городов находится здесь.

Как я могу узнать, сколько городов я могу посетить при определенном бюджете на поездку (скажем, 800 минут) из города происхождения (это может быть любой из 12).

Вы не можете посетить один и тот же город дважды во время поездки, и вам не нужно беспокоиться о возвращении к месту своего происхождения. Я не могу превысить свой бюджет на поездки.

 import numpy as np
from scipy.spatial import distance_matrix
from sklearn.cluster import AgglomerativeClustering


def find_cities(dist, budget):     # dist: a 12x12 matrix of travel time in minutes between city pairs; budget: max travel time allowed for the trip (in mins)

    assert len(dist) == 12        # there are 12 cities to visit and each one has a pairwise cost with all other 11 citis 

    clusters = []                 # list of cluster labels from 1..n where n is no of cities to be visited  

    dists = [0]   [row[1:] for row in dist]       # start-to-start costs have been excluded from the distances array which only contains intercity distances     
    linkage = 'complete'             # complete linkage used here because we want an optimal solution i.e., finding minimum number of clusters required  

    ac = AgglomerativeClustering(affinity='precomputed', linkage=linkage, compute_full_tree=True)          # affinity must be precomputed or function otherwise it will use euclidean distance by default !!! 
                        # compute full tree ensures that I get all possible clustesr even if they don't make up entire population! This is needed so that I can determine how many clusters need to be created given my budget constraints below  

    Z = ac.fit_predict(dists).tolist()   # AgglomerativeClustering.fit_predict returns list of cluster labels for each city 

    while budget >= min(dists):          # while my budget is greater than the minimum intercity travel cost, i.e., I can still visit another city
        if len(set(Z)) > 1:              # at least 2 clusters are needed to form a valid tour so continue only when there are more than one cluster left in Z
            c1 = np.argmax([sum([i==j for j in Z]) for i in set(Z)])      # find which clustes has max no of cities associated with it and that will be the next destination (cities within this cluster have same label as their parent cluster!)          # numpy argmax returns index of maximum value along an axis; here we want to know which group has most elements! 
            c2 = [j for j,val in enumerate(Z) if val == Z[c1]][0]         # retrieve first element from the group whose parent is 'cluster' returned by previous line      

            clusters  = [c2   1]                             ## add new destination found into our trip plan/list "clusters" after converting its city id back into integer starting from 1 instead of 0 like array indices do!!              
            dists  = [dist[c1][c2]]                           ## update total distance travelled so far based on newly added destination ... note: distances between two adjacent cities always equals zero because they fall under same cluster
            budget -= dists[-1]                               ## update travel budget by subtracting the cost of newly added destination from our total budget 

        else: break   # when there is only one city left in Z, then stop! it's either a single city or two cities are connected which means cost between them will always be zero!              

    return clusters   # this is a list of integers where each integer represents the id of city that needs to be visited next! 
    
def main():

    with open('uk12_dist.txt','r') as f:      ## read travel time matrix between cities from file           ## note: 'with' keyword ensures file will be closed automatically after reading or writing operation done within its block!!! 
        dist = [[int(num) for num in line.split()] for line in f]       ## convert text data into array/list of lists using list comprehension; also ensure all data are converted into int before use!        

    with open('uk12_name.txt','r') as f:      ## read names of 12 cities from file              ## note: 'with' keyword ensures file will be closed automatically after reading or writing operation done within its block!!! 
        name = [line[:-1].lower().replace(" ","") for line in f]          ## remove newline character and any leading/trailing spaces, then convert all characters to lowercase; also make sure there's no space between first and last name (which results in empty string!) otherwise won't match later when searching distances!!

    budget = 800                             # max travel budget allowed (in mins) i.e., 8 hrs travelling at 60 mins per km which means I can cover about 800 kms on a full tank!                   

    print(find_cities(dist,budget), "n")     ## print(out list of city ids to visit next!
    print("Total distance travelled: ", sum(dist[i][j] for i, j in enumerate([0] find_cities(dist,budget))), "n" )     # calculate total cost/distance travelled so far by adding up all distances between cities visited so far - note index '0' has been added at start because 0-2 is same as 2-0 and it's not included in find_cities() output above !

    while True:
        try:                                ## this ensures that correct input from user will be obtained only when required!!              
            budget = int(raw_input("nEnter your travel budget (in minutes): "))   # get new travel budget from user and convert into integer before use!!! 
            
            if budget <= 800: break          ## stop asking for valid input only when the value entered by user isn't greater than 800 mins or 8 hrs !!                              

        except ValueError:                   ## catch exception raised due to invalid data type; continue asking until a valid number is given by user!!                     
            pass

    print(name[find_cities(dist,budget)[1]],"->",name[find_cities(dist,budget)[2]],"-> ...",name[find_cities(dist,budget)[-1]] )## print out the city names of cities to visit next!

    return None

if __name__ == '__main__': main()