基于C语言的创新实践——第三课、第四课——最小生成树、平面点集的凸包
上节课迷宫地图生成的方法:
把迷宫分成00-15这16个区域,然后把所有墙都堵上,再拆墙。
随机拆墙:
总墙数(3*4)*2=24
对着24面墙进行打乱(类似扑克洗牌)。即对1-24数列进行。每次从这个打乱的数列中取出一个数,准备拆除对应的墙。之所以说是准备,是因为拆之前要判断一下是否会出现拆掉某面墙后出现多条路的情况(出现开阔地),如果会,就不拆这面墙,继续看数列中的下一个数对应的墙。
本节内容:最小生成树(Minimun Spanning Tree)
典型贪心算法 Greedy Algorithm
某些情况下,局部最优能导出全局最优
(即,当确认只有一个极大值时,极大值就是最大值)
相关问题
现根据某些规则选择一个点集,求出其最小生成树,使得它确定是总最小生成树的一部分,然后再扩展。(某些规则是必要的,否则部分点集的最小生成树不一定是总最小生成树的一部分)。
GENERIC-MST
A就是最小生成树
不断地加入轻边即可
注意左侧数据区别
作业:
需求分析
算法设计
程序设计
第四课 二维点集的凸包
特征描述:
应用:
类似于游戏的命中判定、碰撞箱。
题目的标准定义
如何提高效率:
1、已经判断出不可能是极点的的应不再参与循环。
2、序号123的点、231的点、312的点都会作为三角形参与判断,这是冗余的