|
#2
华少20132013-07-02 23:32
那我就先说哈我自己的算法，这样大家就可以放心交流了吧
 。我的邮箱好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秒的时间，会产生随机方向的变换，当然最糟糕的情况的时间花费为无限大。 |
疏散规则：
（1） 将教室离散成为大小相等的网格，每个同学在单位时间内只能移动一个网格或者保持不动，并且移动方向只能时上、下、左、右（如图2）；
（2） 如果某个同学选择的移动目标网格被其他同学占用，那么该同学选择等待；
（3） 如果多个同学同时竞争同一网格，随机选择其中一个同学占用该网格，其余同学保持不动；
（4） 同学不能移动到桌子占用的网格，并且只能通过出口处进行疏散；
（5） 当所有同学疏散完成后，算法结束。
（图在附件里）
图1
只有本站会员才能查看附件，请 登录
图2我自己想了个算法但想和大神讨论下，如果有想法的话欢迎发到我邮箱
