穷举法解决最小成本分配问题 - 算法分析与设计实验

"这篇文档是关于使用穷举法解决算法问题的一个实验报告，涉及的具体问题是寻找一种总成本最小的任务分配方案。实验中使用了C++编程语言，通过Visual Studio 2019在Windows 10环境下进行。实验旨在理解和掌握穷举法，了解其局限性，并通过编写程序和上机调试来验证解决方案的正确性。" 在这个实验中，穷举法被用于找到一个最佳的任务分配策略，使得所有人的任务分配成本之和达到最小。穷举法，也称为枚举法，是一种基础的搜索策略，它尝试列举所有可能的解决方案，然后从中选取最优的一个。在本实验中，这个策略体现在对每个人可能选择的任务进行遍历，通过递归函数`Jie`来实现。 程序的核心在于`Jie`函数，该函数接受一个参数`s`表示当前正在考虑分配任务的人。如果`s`超过了总人数`n`，则意味着所有人的任务都已经分配完毕，此时会比较当前的总成本`sum`与已知的最小成本`cost`，如果`sum`更小，则更新`cost`。对于每个人，穷举所有可能的任务（由`for`循环实现），如果当前任务已被分配（`visit[i]!=0`），则跳过；否则，标记该任务已被分配，累加成本，然后递归地处理下一个人。递归返回后，回溯并取消当前任务的分配，减去相应成本。 实验的输入是每个人执行每个任务所需的成本矩阵，输出是最小的总成本。样例输入给出了一个9x9的成本矩阵。在实验过程中，还需要编写程序，上机调试，设计新的测试用例来验证程序的正确性，并撰写实验报告，包含实验目的、任务、环境、步骤、结果分析和总结。 穷举法虽然直观易懂，但其主要局限性在于效率低下。当可能的解决方案数量巨大时，穷举法可能会变得极其耗时，甚至无法在合理的时间内完成计算。例如，当任务和人员数量增加时，这个问题的空间复杂度会迅速增长，导致计算时间呈指数级增长。因此，在实际应用中，通常需要结合其他优化策略，如剪枝、动态规划或贪心算法，以提高算法效率。