天使問(wèn)題,一個(gè)2006年才被證明的博弈難題!
2023-04-08 10:09 作者:取個(gè)響亮的昵稱竟然不行 | 我要投稿

當(dāng)k足夠大時(shí),惡魔需要在起始點(diǎn)之外 邏輯上建立墻派2r(園周長(zhǎng))×k半徑 的虛擬墻,才可阻擋
當(dāng)天使朝單方向移動(dòng),需要建立 派k×k/2–k的局部墻堵死天使
惡魔需要o(k2)級(jí)時(shí)間建造局部墻(只造一阻塞點(diǎn)的密鋪墻)
假設(shè)能堵住,o(r)> o( k2時(shí)間× k速度)
天使擋住后向左走兩次k距離( k足夠大),給了惡魔2次機(jī)會(huì),惡魔來(lái)不及在旁邊造墻
惡魔更換為視頻里砌墻的策略,并給予惡魔buff(簡(jiǎn)化計(jì)算),他只需要專心造一個(gè)局部墻就能獲得45度角的虛擬墻,這樣惡魔需要的時(shí)間還是o( k2)天使撞墻后,惡魔buff移除,天使向(k,–k)單方向移動(dòng)
天使移動(dòng)距離o(k),惡魔需要補(bǔ)充墻o(k2),從而讓天使不要離開(kāi)包圍圈,量級(jí)可知必定堵不住
標(biāo)簽: