1 问题内容与目的要求
求解最优化问题的算法通常需要经过一系列的步骤，在每个步骤都面临多种选择。对于许多最优化问题，使用动态规划算法求最优解显得大材小用，可以使用更简单、更高效的算法。贪心算法就是这样的算法，它在每一步都做出当时看起来最佳的选择。也就是说能找到最优解的最优化问题。贪心算法并不能保证得到最优解，但对很多问题确实可以求得最优解。
贪心方法是一种强有力的算法设计方法，可以很好的解决很多问题。采用贪心策略设计的算法就有很多，包括最小生成树的Prim算法和Kruskal算法、单源最短路径的Dijkstra算法，以及集合覆盖问题的Chvatal贪心启发式算法。
本课题的目的是设计一个程序，来帮助房主完成装修新房子这项颇为复杂的工程的室内电线的布局，具体内容如下：
首先，墙壁上插座的位置是固定的，插座间需要有电线相连，而且要布置得整齐美观，即要求每条线都与至少一条墙边平行，且嵌入四壁或者地板（不能走屋顶）。
房主要求知道，要将所有插座连通，自己需要买的电线最短长度。
参考文档和完整的文档和源码下载地址：
网友评论