墨尔本大学COMP90038和复杂性作业辅导

　　COMP90038 - IT -算法和复杂性-分配帮助

　　我们来做个游戏。或者，更精确地说，设计和分析一些可能在简单的二维游戏中使用的算法。

　　图1:一个小的游戏场景示例。敌人(ai控制)玩家以蓝色显示。人类玩家的固定位置由红十字标记。考虑一个在二维网格上玩的游戏，其笛卡尔坐标范围为(−M, M)…(M, M)。图1描述了一个游戏板，其中M = 4。游戏包含固定数量的N个由ai控制的敌方玩家。每个玩家(包括人类的球员,每个敌人AI)位于任意但固定位置(x, y),即为−M≤x y≤M和M−≤≤M .人类玩家可以执行某些攻击,伤害某个范围内的所有敌方玩家的人类的球员。为了避免使用昂贵的乘法和平方根运算进行计算，我们将使用一个位于人类玩家周围的平方来近似这个范围。

　　具体地说,鉴于一些固定约束b, b 0≤≤M,如果人类玩家位于位置(px, py),那么所有敌人球员,或在境内的左下侧的角落(px−b, py−b)和是谁的右上角(px + b, py + b)受到攻击的影响。图1描述了一个边界b = 1.5的示例框。

　　1. 实现一个Θ(1)函数来确定敌人的位置(x, y) affectedm由玩家的攻击,给球员的位置(px, py):函数是影响((px, py), (x, y), b)

　　2. 假设(现在)敌方玩家的位置存储在一个未排序的数组A[0]中…(N−1)。下面的函数使用分而治之的方法来标记所有受到玩家攻击影响的敌方玩家。标记由标记函数实现，其细节并不重要。(注:下面的除法是整数除法，也就是取到最接近的整数)函数MarkAffected((px, py)， A, b)函数markaffect ((px, py)， A, 0, N−1,b)函数markaffect dc ((px, py)， A, lo, hi, b)如果lo = hi，则if IsAffected((px, py)， A[lo]， b) then Mark(A[lo]) else mid←lo + (hi−lo)/2 markaffect teddc ((px, py)， A, lo, mid, b) markaffect teddc ((px, py)， A, mid + 1, hi, b)

　　解释最外面的“if/else”测试的目的。特别地，假设我们删除了“if lo = hi”行和“else”行。用不超过一段的篇幅解释这将如何影响算法。

　　3.考虑下面的递归关系。哪一个最好地描述了markaffect dc函数的最差基复杂度，它的输入大小是n = hi−lo + 1，它的基本操作是调用IsAffected和Mark?证明你的答案不超过一段文字。

　　T(1) = 1 T(n) = 2T(n/2)

　　T(1) = 2T(n) = 2T(n/2) + 2

　　T(1) = 0 T(n) = 2T(n/2)

　　T(1) = 2T(n) = 2T(n/2)

　　4. 用望远镜(又名替换)获得一个封闭的形式为您选择的递推关系,从而证明MarkAffectedDC算法的最坏情况下的复杂性Θ(n)。

　　5. 我们能做得更好吗?回想一下人类玩家在某个固定位置(px, py)。你的任务是计算出如何排序数组A，以便需要标记的敌人ai可以在log(N)时间内被识别。

　　具体来说,完成以下比较函数排序时将使用的ar -雷a, (x1, y1)和(x2, y2)是两个点从数组的函数应该返回true,如果它认为第一点是小于或等于第二,否则,返回false。你的函数可以使用玩家的坐标(px, py)作为全局变量，也就是说，你可以在你的函数中引用px和py。

　　6. 现在,假设该数组排序使用你的比较函数,实现一个算法的最坏情况的复杂性在Θ(log (N)),确定哪些应该标记数组元素。你的函数应该以边界b为参数，也可以以玩家的coor(px, py)为参数。

　　7. 在最坏的情况下，需要标记多少个元素?因此，一个算法的最坏情况复杂度是多少?用大符号来表达你的答案。

　　8. 最坏的情况是相当悲观的。平均而言，我们可能会认为敌人的ai是均匀分布在整个棋盘上的。设d为棋盘上边界b(即宽度和高度各为2b)框内或框边所含敌人ai的期望个数。为了简单起见，我们将注意力限制在完全包含在baord游戏中的盒子上。

　　考虑一个算法,给定数组排序根据你的比较函数,及其——表示“状态”的行为MarkAffected上面首先使用Θf (log (N))