旅行售货员问题（回溯法，深度优先搜索）_清风er的博客_旅行售货员问题回溯法

1 问题描述

2 算法分析

该题利用回溯法求解，此时需要确定解空间的类型：我们可以知道该解空间为一棵排列树。我们假设初始的一条路线为x，x中的值为 1，2，3，……，n，表示该路线为由城市1依次经过城市2、3……到n后再回到城市1（当然是假设该路线存在）。如果不存在的话，我们只需改变一下这个排列的排列方式，再进行判断，所以可想而知，我们可以知道该解空间是一棵排列树。该题利用回溯法求解，此时需要确定解空间