寻找拼图解决方案的算法
Che*_*ron 30 algorithm path collision-detection collision
我正在尝试制作一个游戏,玩家必须在游戏板上从头到尾找到自己的方式.![游戏板] [1]
如你所见,这个游戏板包含一堆红色的圆形障碍物.为了赢得比赛,玩家必须移除最少量的障碍物.所以我的问题是,我如何以编程方式找出要移除的最小障碍物,以释放路径？自由路径将被视为之间的空间,圆圈不重叠且不接触.
所以我真正需要的是要移除的最小圆圈量,我不需要实际的路径.是否有捷径可寻？
并且为了补充对该游戏板的理解,每个圆圈具有相同的半径,并且受到黑线的限制.
也没有必要沿直线移动.
Leo*_*nid 17
这是一个图论maximum flow问题.
假设每个圆都是图中的一个节点.另外引入2个特殊节点:TOP和BOTTOM.如果这些节点与TOP/BOTTOM侧相交,则将这些节点连接起来.如果圆相交,则将与圆相对应的节点相互连接.
现在您需要在此图中找到最小切割,将TOP作为源,将BOTTOM作为接收器,反之亦然.您可以使用Max-flow_min-cut_theorem来解决它.它所说的是Minimum-cut problem与Max-flow问题等价的.您可以Max-Flow problem在TopCoder上找到有关如何解决的详细信息.
由于我们只能通过每个节点一次,我们应该将节点转换为容量的有向边,其中每个节点具有节点内和节点外.max-flow算法将解决结果图上的问题,并考虑到我们正在删除圆而不是圆之间的连接这一事实.对于此问题,删除图形中的节点而不是边缘总是更好的决定,因为我们总是可以通过删除节点来删除任何边缘.另外删除节点可能导致删除多个边缘.
顺便说一句,在Uva Online Judge上也可以找到类似的问题.尝试在法官身上解决这个问题是个好主意,然后你就会确定你的解决方案是正确的.
对于图形转换,这样的事情可能会起作用.
如果两个圆重叠,则在两个圆之间做一个墙(蓝线).不要忘记添加顶部和底部边框.这会产生几个区域.这些将是图表的所有节点.
接下来,我们必须找到边缘,从一个节点到另一个节点的成本.拿两个相邻区域(共用一堵墙).然后通过蛮力,或者你想出的聪明方法,确定从这个区域移动到另一个区域的成本.如果删除圆圈,则表示删除了转到该圆圈的所有墙壁.如果这使得两个区域成为一个区域,则边缘的成本为1.如果需要移除两个圆(它们具有的所有墙)以组合这两个区域,则成本为2.等等.
绘制了一些边缘(绿色).我们必须从起始区域到结束区域.你现在有一个日常加权图.
我认为这可以改进很多,但我把它留作练习=)
在这种情况下,最小值为3.
警告,图片是手工绘制的,我确实忘记了几个墙壁,边缘和区域.仅用于说明目的.
