Compute and display the traveling salesman problem solution with coordinate points using the Held-Karp algorithm. -- 2

The aim of this project is to solve a traveling salesman problem, optimally if the number of points is at most 15, and approximate the solution beyond that. Your program has two input modes: if it gets started with a command line argument, then that is the file which contains the points, with two coordinates per line. The coordinates are integers in the range 0 to 500. If the program gets started without a command line argument, then you can enter points interactively by mouseclick (left mouseclick enters a point, a right mouseclick ends the input phase).

After you have all the points, you compute and display a TSP solution. If the number of points is at most fifteen, you use the Held-Karp algorithm to compute the optimum TSP tour. If the number is greater than fifteen, you sort the points according to the first coordinate, divide the set into groups of at most fifteen, and solve each group optimally; after that, you find the optimal connection between the groups. You connect the groups in their left-to-right sequence, so you try for each edge pipi±i in one group and qiqi+i in the next, what the distance is if you replace pipi+1, qiqj+1 by piqi+i, pi+iqj or by piqi,pi+igi-o. You use again the xlib system to open a window and draw the results; draw the points black, and the lines in a color. Print the total length of the tour to stdout.

The attached files is a sample program that uses xlib, which this program should model.

C 프로그래밍

프로젝트 ID: #12504926

프로젝트 소개