本文共 1304 字，大约阅读时间需要 4 分钟。

某售货员要到若干城市去推销商品，已知各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后

回到住地的路线，使总的路程最短。

解题思路：先对所有城市全排列 ，再计算每条路径的花费，取最小值。

int MinCost = Integer.MAX_VALUE; // 花费	/**	 * @param route 路线花费	 * @param city  城市编号	 * @param cost  每条路线的花费	 * @param cityNumlist  路线的城市编号	 * @param k   起始位置	 * @param m   结束位置(该题目假设由终止位置可直达起点)	 * @return 总花费最小的路线顶点	 */	ArrayList
   
     bakctrack(int[][] route, int[] city, int cost, ArrayList
    
      cityNumlist, int k, int m)	{		int i = 0;		// 产生nums[k:m]的所有排列		if (k == m)		{			for (i=1; i<=m; i++)			{				cost += route[city[i-1]][city[i]];			}						// 再加上返回路径			cost += route[city[m]][city[0]];						if (cost < MinCost)			{				MinCost = cost;				if (cityNumlist != null)					cityNumlist.clear(); // 清空原来的编号				for (int j=0; j<=m; ++j)				{					cityNumlist.add(city[j]+1); // 将城市编号放入集合中				}			}			cost = 0;		}		else		{			// 还有多少个元素待排列，递归产生排列			for (i=k; i<=m; i++)			{				swap(city, i, k);				bakctrack(route, city, cost, cityNumlist, k+1, m);				swap(city, i, k);			}		}		return cityNumlist;	}			// 交换元素	public void swap(int[] nums, int i, int j)	{		int tmp = nums[i];		nums[i] = nums[j];		nums[j] = tmp;	}		public ArrayList
     
       smallCost(int[][] route, int[] city)	{		ArrayList
      
        cityNum = bakctrack(route, city, 0, new ArrayList<>(), 0, city.length-1);		return cityNum;	}
      
     
    
   

转载地址：http://vcpoi.baihongyu.com/