| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 735 人关注过本帖
标题:大家一起解决下这个算法吧
只看楼主 加入收藏
华少2013
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2013-6-30
结帖率:0
收藏
已结贴  问题点数:20 回复次数:3 
大家一起解决下这个算法吧
假设针对某间教室,试设计一算法模拟同学下课后疏散离开教室的过程(如图1,四周为墙壁,灰色长条区域为课桌,黑色实心圆代表同学)。疏散过程中考虑2个因素影响:(1)每个同学首先选择最近的出口进行疏散;(2)当该出口聚集了大量同学形成拥塞,这时可能考虑离次近的出口进行疏散。这两方面的权重分别为0.7和0.3。

疏散规则:
(1)    将教室离散成为大小相等的网格,每个同学在单位时间内只能移动一个网格或者保持不动,并且移动方向只能时上、下、左、右(如图2);
(2)    如果某个同学选择的移动目标网格被其他同学占用,那么该同学选择等待;
(3)    如果多个同学同时竞争同一网格,随机选择其中一个同学占用该网格,其余同学保持不动;
(4)    同学不能移动到桌子占用的网格,并且只能通过出口处进行疏散;
(5)    当所有同学疏散完成后,算法结束。
(图在附件里)
         
图1      
图片附件: 游客没有浏览图片的权限,请 登录注册
                           图2
我自己想了个算法但想和大神讨论下,如果有想法的话欢迎发到我邮箱
搜索更多相关主题的帖子: 课桌 影响 
2013-06-30 23:05
华少2013
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2013-6-30
收藏
得分:0 
那我就先说哈我自己的算法,这样大家就可以放心交流了吧。我的邮箱好582797956@
目录
1最初设计
   If-else版设计 (X)
   扫雷版设计 (X)
2设计改进
   队列与遍历版设计
3最短路径算法
  广度优先搜索算法
4实现方案


最初设计(if-else)
(1)思考顺序
1先判断离前后门三条轴线的距离,因无法斜向行走,故只要到达三条轴线即可。[1]
2可以几乎排除向左走的可能,见最短路径判断法。
3前后和拥挤的权重比为0.7比0.3,故在判断时优先考虑距离。
4图中前后门宽度不一样,故前门的权重大于后面。
5把教室划分为前后,但因第4条所述,前后划分不等。

[1]关于三条轴线
 

(2)基本AI设定
1.方案设计图(if-else判断)

 

总共执行3次循环,与1次函数的迭代算法,编程较为困难,这只是单纯的走迷宫法(顺着右边走的方法),并无法算出最短路径,也无从得到最优算法,此方案否决。



最初设计(扫雷版)
(1)    将教室离散成相等的小方格,并采用扫雷的计数方法,判断周围障碍与人的数量,数字和越大,就说明密度越高,因该回避该区域
(2)    初始可采用数组的方式,对数进行记载,可以方便的编程,且快速计算出密度。

 
一个目标可使总数加4,当全图的数字和相等于初始障碍物的和时,算法结束。

但因无法判断人与障碍物,就算使用特定标识,几乎无法建立最短路径算法,至少我办不到,且每当一个运动时会改变5个数字,并且还要知道路径周围的障碍,故否决。

队列与遍历设计

设计思路
(1)    将教室离散成相等的小方格,设置一位数组,并建立Point方法,确认坐标。
(2)    共有三种物品状态,人,桌,地面,设计Block类(基本单元格)
Static class Block
{
      public  const  byte Land = 0;  // 地面
   public  const  byte Desk= 2;  // 桌
   public  const  byte Man= 6;  // 人
}

(3)    建立方法,获取数据状态,完成准备工作
const  string  mask = "-+#%xX()";  
  
 public  static  char GetChar( ushort block)
      {
        return mask[block & 0x07];
      }

    public  static  byte GetByte( char block)
     {
       return ( byte)mask.IndexOf(block);
     }
 
       public  static  void CleanAllMark(ushort[,] bb)
      {
         for  ( int  i = 0; i < bb.GetLength(0); i++)
          for  ( int  j = 0; j < bb.GetLength(1); j++)
            bb[i, j] &= 0x07;
      }
       public  static  void Mark(ref ushort block,  int  value)
      {
         block |= ( ushort)(value << 3);
       }
   
        public  static  int  Value( ushort block)
       {
          return block >> 3;
       }



最短路径算法
广度优先搜索算法
(1)    共两种方式,一是从人找出口,二则从出口找人,遍历全组,且搜索所有的节点(不重复),在每个分支处做下标记排入队列,在之后又从这出发,再次搜索,一直到找到人或出口时停止算法。如果未找到,返回错误的布尔值。
(2)    此方法不使用递归,而是循环,全部搜索,而不具有判断经验。
(3)    详细视图
 
但是这样时间复杂度为(N*N-1)/2+N-1,同时这也是最短路径的情况,但如果图再大一些,时间复杂度会急剧上升,所以因改进算法。

算法改进

(1)    将所标记的数,进行压缩,按倍数压缩,如(1,2,3,4,5,6,7,8,9)化为(1,2,3,1,2,3,1,2,3)只保留3个数来记录路径,因为来时的一个方向除开,剩下只有3个方向足够了。可减少内存占用量。

 

(2)    算法表达式 C#
  static  bool Seek(byte[,] map, Point to, out  int  value)
     {
      Queue<Point> q =  new Queue<Point>();
       Block.Mark( ref map[to.Y, to.X], 1);  
       Point nbr = Point.Empty; 60        
for  (; ; )
       {
         value = Block.Value(map[to.Y, to.X]) % 3 + 1;  
 
        for  ( int  i = 0; i < offsets.Length; i++)         
 {
          nbr = Fcl.Add(to, offsets[i]);  
         if  (Block.IsMan(map[nbr.Y, nbr.X]))  
break ;  
           if  (Block.IsBlank(map[nbr.Y, nbr.X]))  
           {
                     Block.Mark( ref map[nbr.Y, nbr.X], value);
     q.Enqueue(nbr);
           }
        }
        if  (Block.IsMan(map[nbr.Y, nbr.X]))  break ;  
        if  (q.Count == 0)  return false;
       to = q.Dequeue();  
      }
      return true;  
     }
}
}
如果找到返回最短路径长度,没有返回长度为0,具体如下
1=>2=>3=>1=>2=>3
 =>3=>1=>2=>3=>1=>2=>3
=>1=>2=>3
=>2=>3=>1=>2=>3
              按红绿蓝的顺序,黑为障碍,呈中心扩散开,不断增大,直到查遍全部的路径
 
               
实现方案
(1)    如之前所述,计算出到门的最短路径长度,再利用之前的权重比,将较拥挤的长度乘以0.7,再与另一个门的最短路径相比,再作判断。
(2)    拥挤情况,如果按一个接一个的状况,对单体的时间会有影响,但总时间不会产生变化(全部单体最短路径情况下),无需再考虑占位的问题。
(3)    基于数组与VSM的绑定结合,可开发可视演算程序。
(4)    可以不考虑最糟糕的情况,撤离时一定会发生慌乱,有3~4秒的时间,会产生随机方向的变换,当然最糟糕的情况的时间花费为无限大。
2013-07-02 23:32
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:20 
有一个最大的问题就是,这些人是自己随机走,还是我来给他规定?

比如110(1-人,0-空), 对左1来说,他无路可走,除非右1向右移动,所以如果他们自己走,会有两种结果(101 011)

但是如果我规定,那就只有1种,让右1先走(011)

也就是一个先后问题


[fly]存在即是合理[/fly]
2013-07-06 00:30
华少2013
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2013-6-30
收藏
得分:0 
回复 3楼 azzbcc
我想定义一个随机变量,由电脑随机分配。来判断人是向左还是向右。先判断是否四周都有阻碍,若有则不动,只有一个方向就走哪个方向,有两个方向就想刚才说的就随机分配个(0,1).0则向左,1向右可以吧?还有就是有3个,4个方向的时候我就判断人距离哪个门的距离近,再判断是怎么走。
你就当行得通吗?
2013-07-09 14:40
快速回复:大家一起解决下这个算法吧
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.020502 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved