五大常见算法策略之——回溯策略

# 回溯策略 回溯是五大常用算法策略之一，它的核心思想其实就是将解空间看作是一棵树的结构，从树根到其中一个叶子节点的路径就是一个可能的解，根据约束条件，即可得到满足要求的解。求解问题时，发现到某个节点而不满足求解的条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。下面通过几个例子来讨论这个算法策略。 ## 货郎问题 > 有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。（最后回到原来的城市），也就是说给一个无向带权图G