Consider the rollout algorithm for the traveling salesman problem using as base heuristic the nearest neighbor method, whereby we start from some simple path and at each iteration, we add a node that does not close a cycle and minimizes the cost of the enlarged path (see the paragraph following the description of the rollout algorithm iteration in Section 10.5). Write a computer program to apply this algorithm to the problem involving Hamilton's 20-node graph (Exercise 1.35) for the case where all arcs have randomly chosen costs from the range [0, 1]. For node pairs for which there is no arc, introduce an artificial arc with cost randomly chosen from the range [100, 101]. Compare the performances of the rollout algorithm and the nearest neighbor heuristic, and compile relevant statistics by running a suitable large collection of randomly generated problem instances. Verify that the rollout algorithm performs at least as well as the nearest neighbor heuristic for each instance (since it is sequentially consistent).