COMP90038 - IT -算法和復(fù)雜性-分配幫助

　　我們來(lái)做個(gè)游戲?；蛘?，更精確地說(shuō)，設(shè)計(jì)和分析一些可能在簡(jiǎn)單的二維游戲中使用的算法。

　　圖1:一個(gè)小的游戲場(chǎng)景示例。敵人(ai控制)玩家以藍(lán)色顯示。人類玩家的固定位置由紅十字標(biāo)記。考慮一個(gè)在二維網(wǎng)格上玩的游戲，其笛卡爾坐標(biāo)范圍為(?M, M)…(M, M)。圖1描述了一個(gè)游戲板，其中M = 4。游戲包含固定數(shù)量的N個(gè)由ai控制的敵方玩家。每個(gè)玩家(包括人類的球員,每個(gè)敵人AI)位于任意但固定位置(x, y),即為?M≤x y≤M和M?≤≤M .人類玩家可以執(zhí)行某些攻擊,傷害某個(gè)范圍內(nèi)的所有敵方玩家的人類的球員。為了避免使用昂貴的乘法和平方根運(yùn)算進(jìn)行計(jì)算，我們將使用一個(gè)位于人類玩家周圍的平方來(lái)近似這個(gè)范圍。

　　具體地說(shuō),鑒于一些固定約束b, b 0≤≤M,如果人類玩家位于位置(px, py),那么所有敵人球員,或在境內(nèi)的左下側(cè)的角落(px?b, py?b)和是誰(shuí)的右上角(px + b, py + b)受到攻擊的影響。圖1描述了一個(gè)邊界b = 1.5的示例框。

　　1. 實(shí)現(xiàn)一個(gè)Θ(1)函數(shù)來(lái)確定敵人的位置(x, y) affectedm由玩家的攻擊,給球員的位置(px, py):函數(shù)是影響((px, py), (x, y), b)

　　2. 假設(shè)(現(xiàn)在)敵方玩家的位置存儲(chǔ)在一個(gè)未排序的數(shù)組A[0]中…(N?1)。下面的函數(shù)使用分而治之的方法來(lái)標(biāo)記所有受到玩家攻擊影響的敵方玩家。標(biāo)記由標(biāo)記函數(shù)實(shí)現(xiàn)，其細(xì)節(jié)并不重要。(注:下面的除法是整數(shù)除法，也就是取到最接近的整數(shù))函數(shù)MarkAffected((px, py)， A, b)函數(shù)markaffect ((px, py)， A, 0, N?1,b)函數(shù)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”測(cè)試的目的。特別地，假設(shè)我們刪除了“if lo = hi”行和“else”行。用不超過(guò)一段的篇幅解釋這將如何影響算法。

　　3.考慮下面的遞歸關(guān)系。哪一個(gè)最好地描述了markaffect dc函數(shù)的最差基復(fù)雜度，它的輸入大小是n = hi?lo + 1，它的基本操作是調(diào)用IsAffected和Mark?證明你的答案不超過(guò)一段文字。

　　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. 用望遠(yuǎn)鏡(又名替換)獲得一個(gè)封閉的形式為您選擇的遞推關(guān)系,從而證明MarkAffectedDC算法的最壞情況下的復(fù)雜性Θ(n)。

　　5. 我們能做得更好嗎?回想一下人類玩家在某個(gè)固定位置(px, py)。你的任務(wù)是計(jì)算出如何排序數(shù)組A，以便需要標(biāo)記的敵人ai可以在log(N)時(shí)間內(nèi)被識(shí)別。

　　具體來(lái)說(shuō),完成以下比較函數(shù)排序時(shí)將使用的ar -雷a, (x1, y1)和(x2, y2)是兩個(gè)點(diǎn)從數(shù)組的函數(shù)應(yīng)該返回true,如果它認(rèn)為第一點(diǎn)是小于或等于第二,否則,返回false。你的函數(shù)可以使用玩家的坐標(biāo)(px, py)作為全局變量，也就是說(shuō)，你可以在你的函數(shù)中引用px和py。

　　6. 現(xiàn)在,假設(shè)該數(shù)組排序使用你的比較函數(shù),實(shí)現(xiàn)一個(gè)算法的最壞情況的復(fù)雜性在Θ(log (N)),確定哪些應(yīng)該標(biāo)記數(shù)組元素。你的函數(shù)應(yīng)該以邊界b為參數(shù)，也可以以玩家的coor(px, py)為參數(shù)。

　　7. 在最壞的情況下，需要標(biāo)記多少個(gè)元素?因此，一個(gè)算法的最壞情況復(fù)雜度是多少?用大符號(hào)來(lái)表達(dá)你的答案。

　　8. 最壞的情況是相當(dāng)悲觀的。平均而言，我們可能會(huì)認(rèn)為敵人的ai是均勻分布在整個(gè)棋盤(pán)上的。設(shè)d為棋盤(pán)上邊界b(即寬度和高度各為2b)框內(nèi)或框邊所含敵人ai的期望個(gè)數(shù)。為了簡(jiǎn)單起見(jiàn)，我們將注意力限制在完全包含在baord游戲中的盒子上。

　　考慮一個(gè)算法,給定數(shù)組排序根據(jù)你的比較函數(shù),及其——表示“狀態(tài)”的行為MarkAffected上面首先使用Θf (log (N))