资 源 简 介
应用背景一个旅行推销员是准备一个大的销售之旅。在他的家乡，提着手提箱，他将进行一次旅行，他的每一个目标城市被访问一次然后回家。鉴于城市之间的两两距离，在参观他们的最佳顺序是什么，从而减少整体的距离？为城市的1，……，N，推销员的故乡1，让a ； ；（dij）是城际间的距离矩阵。我们的目标是设计一个旅行的开始和结束在1，包括所有的其他城市是一次性的，并具有最低的总长度。图中显示了一个涉及五个城市的例子。 ；关键技术让我们马上进入DP。那么什么是适当的子问题求解TSP？在这种情况下，最明显的部分解决方案是一个旅游的初始部分。假设我们在市1的要求开始，参观了几个城市，现在在城市的什么信息是我们为了扩大这部分旅游需求？我们一定要知道，因为这将决定哪些城市未来最方便的访问。我们还需要知道所有访问的城市到目前为止，所以我们不要重复任何人。在这里，然后，是一个合适的子问题。
