1.回溯算法介绍
1.来源
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。
用回溯算法解决问题的一般步骤：
1、 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。
2 、确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。
3 、以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。
确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。 [2]
2.基本思想
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。八皇后问题就是回溯算法的典型，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数，剪去一些不可能到达 最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。
2.代码介绍
/**
* 当输入门票数为5时会优先排列团体票
*
*/
public int getPeopleCount() {
switch (typeDescription) {
case "团体票":
return 5;
default:
return 1;
}
}
/**
* 回溯算法计算所有可能的门票组合，这些组合满足不超过给定预算且总人数等于指定人数的条件。
* @param ticketTypeDao Dao对象，用于访问门票类型数据。
* @param scanner 用于接收用户输入的Scanner对象。
*/
private static void calculateAllPossibleTicketCombinations(TicketTypeDao ticketTypeDao, Scanner scanner) {
// 提示用户输入预算并读取输入
System.out.print("请输入预算：");
double budget = scanner.nextDouble();
// 处理换行符，以便下一次输入可以正常读取
scanner.nextLine();
// 提示用户输入需要购票的人数并读取输入
System.out.print("请输入购票人数：");
int numberOfPeople = scanner.nextInt();
scanner.nextLine(); // 消耗换行符
// 通知用户程序正在计算可能的组合
System.out.println("正在计算所有可能的票价组合，请稍候...");
// 从DAO获取所有门票类型信息
List<TicketType> ticketTypes = ticketTypeDao.getAllTicketTypes();
// 初始化用于存储所有可能组合的列表
List<List<TicketType>> allCombinations = new ArrayList<>();
// 调用递归方法findCombinations来找出所有可能的门票组合
findCombinations(ticketTypes, budget, numberOfPeople, new ArrayList<>(), allCombinations, 0, 0);
// 打印找到的所有可能的门票组合（最多打印1000条）
System.out.println("\n所有可能的票价组合（当结果数量过大时只显示前1000条）：");
int combinationNumber = 1;
for (List<TicketType> combination : allCombinations) {
// 使用Stream API计算当前组合的总价和总人数
double totalPrice = combination.stream().mapToDouble(TicketType::getPrice).sum();
int totalPeople = combination.stream().mapToInt(TicketType::getPeopleCount).sum();
// 如果当前组合的总价不超过预算且总人数等于指定人数，则打印这个组合
if (totalPrice <= budget && totalPeople == numberOfPeople) {
System.out.println("组合 " + combinationNumber++ + "：");
for (TicketType ticketType : combination) {
// 打印组合中每个门票类型的描述、价格和适用人数
System.out.println(" - " + ticketType.getTypeDescription() +
" (￥" + ticketType.getPrice() + ", " +
ticketType.getPeopleCount() + "人)");
}
System.out.println(" 总价：￥" + totalPrice);
System.out.println(" 总人数：" + totalPeople);
}
}
// 如果没有找到任何符合条件的组合，则打印提示信息
if (combinationNumber == 1) {
System.out.println("没有找到符合条件的票价组合。");
}
}
/**
* 递归方法，用于找出所有可能的门票组合，这些组合满足不超过给定预算且总人数等于指定人数的条件。
*
* @param ticketTypes 所有可用门票类型的列表。
* @param budget 用户设定的预算限制。
* @param numberOfPeople 用户需要购买的门票总人数。
* @param currentCombination 当前正在构建的门票组合。
* @param allCombinations 用于存储所有找到的有效门票组合的列表。
* @param start 当前递归搜索的起始索引，用于跳过已经考虑过的门票类型。
* @param foundCombinations 已找到的有效门票组合数量，用于限制搜索结果的数量，避免结果过多。
*/
private static void findCombinations(List<TicketType> ticketTypes, double budget, int numberOfPeople,
List<TicketType> currentCombination, List<List<TicketType>> allCombinations,
int start, int foundCombinations) {
// 如果找到的组合数量已经达到1000个，或者超出了限制，停止进一步搜索
if (foundCombinations >= 1000) {
return;
}
// 计算当前组合中所有门票类型的人数总和
int currentPeopleCount = currentCombination.stream().mapToInt(TicketType::getPeopleCount).sum();
// 如果当前组合的人数已经超过了用户指定的总人数，则没有必要继续搜索这个分支
if (currentPeopleCount > numberOfPeople) {
return;
}
// 如果当前组合的人数等于用户指定的总人数，将当前组合添加到所有有效组合的列表中
// 并且递增已找到的组合数量
if (currentPeopleCount == numberOfPeople) {
allCombinations.add(new ArrayList<>(currentCombination)); // 添加一个当前组合的副本
foundCombinations++; // 递增找到的组合数量
return; // 退出当前递归调用
}
// 遍历门票类型列表，从start指定的索引开始，尝试将每种门票类型添加到当前组合中
for (int i = start; i < ticketTypes.size(); i++) {
TicketType ticketType = ticketTypes.get(i);
// 如果预算充足，考虑将当前门票类型添加到组合中
if (budget >= ticketType.getPrice()) {
// 将当前门票类型添加到组合中
currentCombination.add(ticketType);
// 递归调用findCombinations，尝试添加列表中的下一个门票类型
// 并更新预算为扣除当前门票价格后的剩余预算
findCombinations(ticketTypes, budget - ticketType.getPrice(),
numberOfPeople, currentCombination,
allCombinations, i + 1, foundCombinations);
// 回溯步骤：从当前组合中移除最后添加的门票类型，回到上一个状态
currentCombination.remove(currentCombination.size() - 1); // 回溯
}
}
}3.使用 “回溯算法”来生成所有可能的购票组合。
回溯算法用于列举所有可能的门票组合，以找出在限定预算和人数条件下的所有有效组合。回溯算法是一种通过递归来实现的搜索算法，尝试所有可能的解决方案，直到找到满足条件的答案。具体作用：
-
生成组合：
findCombinations方法通过递归生成所有可能的门票组合。它从空组合开始，逐步添加不同类型的门票。 -
剪枝：如果当前组合的总人数已经超过了用户指定的人数，或者在添加新的门票类型后超出了预算，递归将停止当前路径的搜索，这是一种剪枝操作，可以减少不必要的计算。
-
记录有效组合：当找到一个满足条件的组合（即总人数等于用户指定的人数）时，将其添加到
allCombinations列表中。如果找到了1000个或更多的有效组合，将停止搜索以避免结果过多。 -
回溯：在递归调用结束后，通过从当前组合中移除最后添加的门票类型（
currentCombination.remove(currentCombination.size() - 1)），算法回溯到上一个状态，然后尝试添加下一个门票类型。 -
避免重复：虽然代码中没有直接实现避免重复组合的逻辑，但通过递归的剪枝和停止条件，可以在一定程度上避免生成明显不可能满足条件的组合。
-
输出结果：在递归搜索结束后，遍历
allCombinations列表，输出所有找到的有效组合及其详细信息。 -
限制搜索范围：通过在
findCombinations方法中使用foundCombinations参数，算法可以控制搜索的范围，一旦找到足够数量的组合，就停止搜索。
