[算法] 大草原装路灯算法 求解

CuiRong 发布于 2012/08/08 11:13
阅读 728
收藏 1
一片大草原上有若干人家, 现在要安装若干灯,照亮所有人家,已知人家坐标和灯光半径 80 ,最少要 多少 盏灯。下面是dropbox上的demo

https://dl-web.dropbox.com/u/335315/outlink/lightallhouse.html

目前算法的思想是以房屋为中心灯光半径为半径做圆,相交部分就是插路灯的可能地点

计算采用递归,取最短的分支,但是在处理抢夺分支的时候遇到麻烦,太TMD复杂了,如果直接递归 100!太庞大了,求分析。
加载中
0
中山野鬼
中山野鬼
地址连不上。你的题目不清晰。。。
CuiRong
CuiRong
原题是:一片大草原上有若干人家, 现在要安装若干灯,照亮所有人家,已知人家坐标表M和灯光半径r ,问最少需要多少盏灯? 试试https://www.dropbox.com/u/335315/outlink/lightallhouse.html ,用chrome看,里面有canvas;还是不行的话我下面贴代码
0
CuiRong
CuiRong
<!DOCTYPE HTML>
<html>
<head>
<meta charset="utf-8">
<title>house & light</title>
<style type="text/css">
body{font:normal 12px/2 Arial, Helvetica, sans-serif; color:#181416; padding: 0; margin: 0; overflow: hidden;}
#top{ position: absolute; top:0; left: 0; right: 0; border-bottom: solid 1px #ccc; background: rgba(255,255,255,.5); padding: 0 10px}
.focus{color: #39f; background:#f4f4f4; border-radius:3px; padding: 2px 4px; font-size: 15px}
.info{ color: #aaa; padding: 5px; float: right}
</style>
</head>

<body>
	<div id="top">
	<div class="info">按键 Backspace 撤销操作</div>
	一片大草原上有若干人家,
现在要安装若干灯,照亮所有人家,已知人家坐标和灯光半径 <span id="Radius" class="focus">80</span> ,最少要 <span id="result" class="focus"></span> 盏灯。 </div>

<canvas id="canvas" width="800" height="500">Fallback content, in case the browser does not support Canvas.</canvas>
<script type="text/javascript">
//momofiona 大草原算法解1
;(function(){
  var canvas=document.getElementById("canvas"),
  Radius=document.getElementById("Radius"),
  resultText=document.getElementById("result");
  var cxt=canvas.getContext("2d"),
  houses=[[487,269],[600,308]],
  r=80,result=[],
  draw=function(o,i){
	cxt.fillStyle="#000";
	//cxt.fillRect(o[0]-2,o[1]-2,4,4);
	cxt.fillText(i+1+" ["+o+"]", o[0]+10 ,o[1]);
	cxt.beginPath();
	cxt.arc(o[0],o[1],4,0,Math.PI*2,true);
	cxt.closePath();
	cxt.fill();
	cxt.beginPath();
	cxt.arc(o[0],o[1],r,0,Math.PI*2,true);
	cxt.closePath();
	cxt.fillStyle="rgba(51,153,255,0.1)";
	cxt.fill();
	},
  //避免发生线段交叉
  nocross=function(arr){
  	arr.sort(function(a,b){return a[1]<b[1]});
  	var v=arr[0];
  	arr.map(function(x){
  		x.ac=Math.atan2(x[1]-v[1],x[0]-v[0]);
  		return x;
  	});
  	arr.sort(function(a,b){
  		return a.ac<b.ac
  	});
  	return arr;
  },
  //为所有队伍确立队伍关系网,
  drawline=function(arr){
	cxt.strokeStyle="rgba(51,153,255,0.5)";
	cxt.lineWidth=1;
  	for(var i=0,l;l=arr[i];i++){
  	  if(l.length==1) continue;
  	  if(l.length>3) l=nocross(l);
  	  cxt.beginPath();
  	  cxt.moveTo(l[0][0],l[0][1])
  	  for(var j=0,k;k=l[j];j++){
  	  	cxt.lineTo(k[0],k[1]);
  	  }
	  cxt.lineTo(l[0][0],l[0][1]);
	  cxt.stroke();
  	}
  },
  drawall=function(){
  		clear();
  		for(var i=0,l=houses.length;i<l;i++) draw(houses[i],i);
  		arrange([],houses.slice());
  	    resultText.innerHTML=result.length;
  	    drawline(result);
  	},
  clear=function(){cxt.clearRect(0,0,canvas.width,canvas.height);};
  canvas.onclick=function(e){
		//r=parseInt(Radius.innerHTML)||r;
		houses.push([e.pageX-this.offsetLeft,e.pageY-this.offsetTop]);
		drawall();
		};
  document.onkeydown=function(e){
  	if(e.keyCode==8){
  		houses.pop();
  		drawall();
  		return false;
  	  };
    };
  window.onresize=function(){
  	canvas.width=document.documentElement.clientWidth;
  	canvas.height=document.documentElement.clientHeight;
  	drawall();
    };
  var getDistance=function(a,b){
	return Math.sqrt(Math.pow(a[0]-b[0],2)+Math.pow(a[1]-b[1],2));
	};
  //house是否和hk有公共的相交区域,已知hk相交
  var circle=function(h,k,house){
  	var l=getDistance(h,k);//两圆心距离
  	var d=Math.sqrt(r*r-l*l/4)// 圆交点到l的距离
  	var x=[(k[0]+h[0])/2,(k[1]+h[1])/2] //l中心点
  	var _x=(k[1]-h[1])/l*d;//圆交点相对X x偏移量
  	var _y=(k[0]-h[0])/l*d;
  	return getDistance([x[0]-_x,x[1]+_y],house)<r||getDistance([x[0]+_x,x[1]-_y],house)<r
    };
  //house是否符合group招募条件
  //符合的返回true,否则false
  var recruit=function(group,house){
		for(var i=0,h;h=group[i];i++){
			//如果出现不想交的house则立刻判定失败
			if(getDistance(h,house)>r*2) return false;
			for(var j=0,k;k=group[j];j++){
				if(i>=j) continue;
				if(!circle(h,k,house)) return false;
			}
		}
		return true;
		};
  //返回抢夺到的队员,默认为完全抢夺,去掉部分抢夺分支
  var grab =function(group,house){
		for(var i=0,h;h=group[i];i++){
			//如果出现不相交的house则立刻判定失败
			if(getDistance(h,house)>r*2) return false;
			for(var j=0,k;k=group[j];j++){
				if(i>=j) continue;
				if(!circle(h,k,house)) return false;
			}
		}
		return true;
		};
	//对返回结果进行递归,
	//抢夺分支:(新增独立分支,与自助、招募分支互不影响)对于不符合某队伍招募条件的house,有权利把该队伍中和自己可组队的house抢夺过来成立新队伍
	//自助分支:当没有被任何队伍招募时自己建队伍的分支
	//招募分支: 当被某个队伍招募成功时产生的分支
	//assembly  这里是所有最终集合的可能组合[[house,house],[house]]
	//houses   	[house,house,...]
	//house  	一间房屋
  function arrange(assembly,houses){
	  var house=houses.shift();
	  //组队完成
	  if(!house){
	  	console.log("result ==> ",assembly.length,JSON.stringify(assembly));
	  	//把队伍最少的分组方案复制给result
	  	if(result.length==0||assembly.length<result.length){
	  		result=assembly;
	  	}
	  	return false;
	  }
	  //第一次assembly=[]
	  if(assembly.length==0){
	  	result.length=0;
	  	arrange([[house]],houses);
	  	return false;
	  }
	  //招募分支
	  for(var i=0,k=0,l=assembly.length;i<l;i++){
		if(recruit(assembly[i],house)){
			k=1;
			var _assembly=assembly.slice();
			_assembly[i].push(house);
			arrange(_assembly,houses);
			return false;
		}else{
			k
		}
	  }
	  //自助分支
	  if(k==0){
	  	assembly.push([house]);
	  	arrange(assembly,houses);
	  }
	}
  //首次draw
  window.onresize();
})();
</script>
</body>
</html>


中山野鬼
中山野鬼
你这种代码,能跑快,就是天才了。。。。
0
中山野鬼
中山野鬼

哦。总算看到到了。这个是个图论的题目。你可以参考找找。递归只是计算方式的一种。不是重点。有一种做法是对整个平面图做整数值化。然后对整个平面图的任何一个点,计算到各个房屋的最短距离。这个图像处理里有方法。如同类似你说的做圆一样。

但我不认为,以房子为重心求路灯点的方式。我更认为,比较任意点是否适合做潜在路灯点的方式来处理。这样计算机处理算法更简单,速度更快。你可以分尺度。逐步提高分辨率,而且显然,每次提高分辨率,只是对潜在点的区域处理。而更多的非潜在点被排除在外。

中山野鬼
中山野鬼
回复 @CuiRong : 和邻接都没关系。就是个二维图,无非一开始你可以3X3的。如果有个左上角4个格子里一个房子都没有。你何必要在提高分辨率下,处理最左上角的格子呢?哈。。。
CuiRong
CuiRong
以房子为中心做邻接矩阵的方式不合适,没办法就用递归了。谢谢你的提示,我研究下你的方法
0
adler
adler

引用来自“中山野鬼”的答案

哦。总算看到到了。这个是个图论的题目。你可以参考找找。递归只是计算方式的一种。不是重点。有一种做法是对整个平面图做整数值化。然后对整个平面图的任何一个点,计算到各个房屋的最短距离。这个图像处理里有方法。如同类似你说的做圆一样。

但我不认为,以房子为重心求路灯点的方式。我更认为,比较任意点是否适合做潜在路灯点的方式来处理。这样计算机处理算法更简单,速度更快。你可以分尺度。逐步提高分辨率,而且显然,每次提高分辨率,只是对潜在点的区域处理。而更多的非潜在点被排除在外。

两位不同处就是求潜在路灯点的方式不同,各有利弊吧。如果草原面积比较大且住户分散,整体划分的方式数学运算简单,但不见得总体运算量会小,尤其此时住户少,但路灯半径稍大的时候,每次提高分辨率,排除的区域很少;而画圆取重叠区域为潜在路灯点的方式数学运算复杂,好处就是只需面对住户区域而不是整个草原,运算速率取决于用户数量和密度,尤其在用户密度比较大的时候运算开销很大。个人观点,如果当做算法学习题目,两种方法都可以,尤其后者,能写出来都NB的..如果不是练习,视情况而定吧,个人倾向鬼先生的方法,有两个原因:一是普遍情况下住户住宿都比较集中的;二是这个方式确实比较简单..个人看法
中山野鬼
中山野鬼
如果以房屋为处理对象,数学公式复杂。类似问题我以前求解过。实际工程上的,往往越简单的,计算越快,并非说计算步骤少了,肯定更多,而是更贴近计算机硬件的计算方式而已。所以更快。
返回顶部
顶部