用探索（穷举）法求解货郎担问题

1．设计内容：

货郎担问题又称推销员问题,是组合数学中的一个著名问题?求解四个城市的货郎担问题,距离关系如下：

1到2、3、4城的距离分别为6、7、9

2到1、3、4城的距离分别为8、9、7

3到1、2、4城的距离分别为5、8、8

4到1、2、3城的距离分别为6、5、5

当推销员从1城出发,经过每个城市一次且仅一次,最后回到1城,问按照怎样的路线走,使总的行程距离最短.

2．设计要求：

（1）给出求解算法；

（2）编程实现此算法；

（3）以图形化界面各城市间及各城市间的路径和距离；

（4）给出时间复杂度分析.