pseudocode de programmation dynamique pour Traveller Salesman

Question

il s'agit d'un pseudo-code de programmation dynamique pour TSP (Traveller Salesman Problem). J'ai compris sa sous-structure optimale mais je n'arrive pas à comprendre ce que fait le code entre parenthèses rouges.

Je ne demande pas quiconque d'écrire le code réel, j'ai juste besoin des explications sur ce qui se passe si je peux écrire mon propre .... merci :)

est ici un lien pour le pseudo-code, je couln 't téléchargé ici. http://www.imagechicken.com/viewpic.php?p=1266328410025325200&x=jpg

Answer 1

Voici un peu moins de pseudo-code mathématique. Je ne sais pas si cela va expliquer ce qui se passe, mais ça peut vous aider à le lire. Ce n'est pas un algorithme fonctionnel (beaucoup de := partout), donc je vais utiliser le pseudo-code Python.

# I have no idea where 'i' comes from. It's not defined anywhere 
for k in range(2,n): 
    C[set(i,k), k] = d(1,k) 
shortest_path = VERY_LARGE_NUMBER 
# I have to assume that n is the number of nodes in the graph G 
# other things that are not defined: 
# d_i,j -- I will assume it's the distance from i to j in G 
for subset_size in range(3,n): 
    for index_subset in subsets_of_size(subset_size, range(1,n)): 
     for k in index_subset: 
      C[S,k] = argmin(lambda m: C[S-k,m] + d(G,m,k), S - k) 
      shortest_path = argmin(lambda k: C[set(range(1,n)),k] + d(G,1,k), range(2,n)) 
return shortest_path 

# also needed.... 
def d(G, i, j): 
    return G[i][j] 
def subsets_of_size(n, s): # returns a list of sets 
    # complicated code goes here 
    pass 
def argmin(f, l): 
    best = l[0] 
    bestVal = f(best) 
    for x in l[1:]: 
     newVal = f(x) 
     if newVal < bestVal: 
      best = x 
      bestVal = newVal 
    return best 

Quelques notes:

1. L'algorithme source n'est pas complète. Au moins, sa mise en forme est bizarre dans la boucle interne, et elle rebondit k dans la deuxième argmin. Donc, tout est probablement faux. Je n'ai pas essayé d'exécuter ce code.
2. les arguments à range devraient probablement tous être augmentés de 1 puisque Python compte à partir de 0, et non de 1. (et en général compter de 1 est une mauvaise idée).
3. Je suppose que G est un dictionnaire de type {from: {to: length}}. En d'autres termes, une représentation de liste d'adjacence.
4. J'ai déduit que C est un dictionnaire de type {(set (int), int): int}. Je peux me tromper. J'utilise un set comme clés pour C. En vrai Python, vous devez d'abord convertir en frozen_set. La conversion est juste occupé, alors je l'ai laissé de côté.
5. Je ne me souviens pas des opérateurs set en Python. Je me souviens qu'il utilise | et & au lieu de + et -.
6. Je n'ai pas écrit subsets_of_size. C'est assez compliqué.