In real-life cases, like collecting balls scattered on a tennis court, humans are solving the Euclidean Traveling Salesman Problem (E-TSP) represented not by the actual positions of the balls, but by the perceived ones. The percept of the problem is a result of visual reconstruction based on retinal images in the observer's eyes. Because the reconstruction is not likely to be perfect, the input is corrupted with errors. As a result, the optimal solution for the perceived problem may not be optimal for the original one. We tested a pyramid and the Concorde algorithms on orthographic images of E-TSP. The algorithms solved not the original problems, but the projected ones, so the foreshortening of the image produced by the orthographic projection was as the source of input errors. TSP problems with 6, 10, 20, 50 and 100 cities were used. The tour, represented by the order of cities, produced by each algorithm for the projected problem was used to determine the solution error for the original problem. With small problems, the solution error produced by the pyramid algorithm was, in most cases, not greater than that of Concorde. With larger problems, Concorde outperformed the pyramid algorithm in most cases, but the difference in performance was small. These results suggest that in the presence of input errors, approximating algorithms may be preferable because they produce solutions quickly and the solution error may be comparable to that of an algorithm that produces optimal solutions. |