CAN RATS SOLVE A SIMPLE VERSION OF THE TRAVELING SALESMAN PROBLEM

Whereas correct tours through the radial arm maze are almost equally long, free choice mazes with multiple goals scattered in an open field allow the animal to select the shortest one from a multitude of correct tours. Thirteen rats were trained (at 10 trials per day) to visit an array of cylindrical feeders in an open field (40 x 100 cm) with reward available only when visiting the last feeder of the set. In Expt. 1 with eight feeders arranged in five different configurations the rats made after 10 days of training 1 error in the first 8 choices and incidence of errorless trials was about 20%. In Expt. 2, the use of six feeders in a rectangular (A) or double triangle (B) configuration increased the incidence of errorless trials to 60%. Expt. 3 showed that performance in the 6-feeder maze was significantly impaired by 6 mg/kg ketamine or 0.25 mg/kg scopolamine but not by lower dosages of these drugs. Tours generated on errorless trials (each feeder visited only once) during 10 days of Expt. 2 were analyzed. Six places can be visited in 6! = 720 different closed tours the lengths of which (in arbitrary units) range from 6.00 to 10. 12 for A and from 6.83 to 10.47 for B. Whereas random generation of correct routes yielded only 5% of the shortest tours, they were clearly preferred by rats (41% in A and 45% in B). The apparent proficiency of rats in this optimization problem is probably not due to cognitive comparison of the possible correct routes but rather to following a simple rule 'Always go to the nearest not yet visited feeder'.