<< 上一主题 | 下一主题 >>

投票 交易 悬赏 活动

青木风亮 (枯木) 定远侯谏议大夫 组别 翰林学士 级别 平西将军 好贴 3 功绩 521 帖子 2357 编号 12000 注册 2004-7-18 家族 泡泡营

#1 发表于 2007-5-17 18:50 资料 主页 文集 短消息 只看该作者 求教一个问题 给出一个10x10的矩形网格场地，在这块场地上尽可能多地用1x1的方形（建筑物）进行填充。这些方形至少要与一个空置的单元相邻，所有这些空置的单元必须是连通的。        这个问题反映了在矩形场地上放置建筑物的问题，在确保每个建筑物单元都是可以通过道路到达的情况下（也可以看作形成连通的院落），保证最高的建筑密度。 上图是10x10的情况下的三种最优方案 最多可以放置61个建筑单元 我把这个问题推广到mxn做了一下 if(m>n){   swap(m,n); } //如果m>n则交换m,n的值 k=m div 3;l=m mod 3;sky=(n mod 3)*l; //整除 取余 乘积 switch(sky){ case 1:A=1; case 2:A=2; case 4:A=3; } //1x1--A=1;1x2--A=2;2x2--A=3; min=n+(m+n-3*k+2)(k-1)+((n-3(k-1)) div 3)*(l+1)+A; //这个是满足条件的最小的道路网长度 这个是我用旋转放置的方法得到的yy公式，我感觉是对的，也没发现什么问题，但是我不会证明，也没想到更简单的表达方式，各位达人能不能推导一下（或者纠正我的错误），下面还要想枚举出各种可能情况的算法，目前打算用上面那个做启发函数作图形覆盖，或者用遗传算法生成，头痛，大家有空就提提思路吧 [ 本帖最后由 青木风亮 于 2007-5-17 19:48 编辑 ] [广告] 《精忠报国岳飞传完整版》火热发布

天宫公主 (司徒家的颖颖) 虞国公主 ★ 组别 限制发言用户 级别 大将军 好贴 6 功绩 517 帖子 11552 编号 1037 注册 2004-10-25 来自 天津 家族 司徒实业

#2 发表于 2007-5-20 14:03 资料 主页 短消息 只看该作者 可以在 m x n 上做一个 random tree，然后挑出元素最多的。 [广告] 《精忠报国岳飞传完整版》火热发布

投票 交易 悬赏 活动

当前时区 GMT+8, 现在时间是 2025-2-8 06:21
京ICP备2023018092号 轩辕春秋 2003-2023 www.xycq.org.cn