Algorithms For Dummies

 

   

  PART 5 

 Challenging Difficult Problems

        for idx,dist in enumerate(D[0][1:])}

cities = D.shape[0]

for subset_size in range(2, cities):

    # Here we define the size of the subset of cities

    new_memo = dict()

    for subset in [frozenset(comb) | {0} for comb in

                   combinations(range(1, cities),

                                subset_size)]:

        # We enumerate the subsets having a certain subset

        # size

        for ending in subset - {0}:

            # We consider every ending point in the subset

            all_paths = list()

            for k in subset:

                # We check the shortest path for every

                # element in the subset

                if k != 0 and k!=ending:

                    length = memo[(subset-{ending},k)][0

                                        ] 

+ D[k][ending]

                    index  = memo[(subset-{ending},k)][1

                                            ] 

+ [ending]

                    all_paths.append((length, index))

            new_memo[(subset, ending)] = min(all_paths)

    # In order to save memory, we just record the previous

    # subsets since we won't use shorter ones anymore

    memo = new_memo

# Now we close the cycle and get back to the start of the

# tour, city zero

tours = list()

for distance, path in memo.values():

    distance 

+= D[path[-1],0]

    tours.append((distance, path

+[0]))

# We can now declare the shortest tour

distance, path = min(tours)

print ('Shortest dynamic programming tour is: %s, %i kms'

       % (path, distance))

Shortest dynamic programming tour is:

 [0, 1, 3, 2, 4, 0], 80 kms

---

CHAPTER 16