Homework 32 — Traveling Salesperson Problem heuristic

Due Sunday December 5

---

Files

• Module heuristic.py

• Tester test_heuristic.py

---

Your task

• Implement a stragegy that

---

Function consider( cities, tour, i1, i2 )

• Parameter cities is a list of points.

• Parameter tour is an arrangement of indices into cities.

• Parameters i1 and i2 are indices to tour

• The function performs the following actions

• Computes the cost c1 of the current tour.

• Performs a swap of the of tour elements at indices i1 and i2.

• Computes the cost c2 of the new tour.

• If c2 is less than c1, the function returns True. Otherwise, the function reswaps tour elements at indices i1 and i2 (thus, restoring the better solution) and returns False.

• The built-in tester should produce the following output

testing consider()

cities: [(281, 468), (515, 643), (738, 88), (530, 120), (410, 754)]

starting tour: [1, 0, 4, 3, 2]

i1: 2

i2: 4

consider( cities, tour, i1, i2 ): True

current tour: [1, 0, 2, 3, 4]

---

cities: [(281, 468), (515, 643), (738, 88), (530, 120), (410, 754)]

starting tour: [1, 0, 4, 3, 2]

i1: 1

i2: 3

consider( cities, tour, i1, i2 ): False

current tour: [1, 0, 4, 3, 2]

 

---