Voronoi博弈形式的競(jìng)爭(zhēng)選址問題的研究.pdf

1、本文主要討論最小鄰居化問題和鄰居最大化規(guī)則下Voronoi博弈形式的競(jìng)爭(zhēng)選址問題。
　　 最小鄰居化問題是指對(duì)平面中給定的n個(gè)點(diǎn)，選址放置k個(gè)新點(diǎn)使得在n+k個(gè)點(diǎn)的Voronoi圖中，所有的n個(gè)點(diǎn)都成為新點(diǎn)的鄰居，選址目標(biāo)是使k盡可能的小。一回合制鄰居最大化規(guī)則下Voronoi博弈形式的競(jìng)爭(zhēng)選址問題是指:有玩家A和玩家B各有n個(gè)點(diǎn)，A先在平面中選址放置n個(gè)點(diǎn)，之后B再選址放置自己的n個(gè)點(diǎn)，最后在2n個(gè)點(diǎn)的Voronoi圖中，有更

2、多對(duì)手的點(diǎn)成為自己鄰居的玩家獲勝，要求對(duì)博弈過程進(jìn)行分析并給出獲勝玩家的制勝策略。這種尋找最優(yōu)化選址的問題被稱為Voronoi博弈，屬于競(jìng)爭(zhēng)選址問題。
　　 本文通過考慮在局部上設(shè)置一個(gè)新點(diǎn)可使構(gòu)成一個(gè)Delaunay三角形的三個(gè)點(diǎn)成為此新點(diǎn)的鄰居，和設(shè)置一個(gè)新點(diǎn)可使構(gòu)成兩個(gè)相鄰Delaunay三角形的四個(gè)點(diǎn)成為此新點(diǎn)的鄰居來給出解決問題的基本思想。據(jù)此通過對(duì)n個(gè)點(diǎn)的Delaunay圖D的對(duì)偶圖Voronoi圖V進(jìn)行最小頂點(diǎn)覆蓋

3、求解和最大匹配求解的方法，獲得可使n個(gè)點(diǎn)全部成為鄰居而應(yīng)當(dāng)選址的位置，分別給出了一個(gè)至多需放置2n-h-2個(gè)點(diǎn)的近似算法，和至多需放置(7n-7-3h)/5個(gè)點(diǎn)的近似算法，其中h為D中凸包上點(diǎn)的個(gè)數(shù)。之后我們給出了一個(gè)性能較好的啟發(fā)式算法和其改進(jìn)算法，并通過實(shí)驗(yàn)對(duì)四種算法給出了實(shí)驗(yàn)驗(yàn)證，證明在一定情況下我們的算法的結(jié)果要優(yōu)于之前研究給出的算法。
　　 對(duì)一回合制鄰居最大化規(guī)則下的Voronoi博弈問題，我們根據(jù)四種新的算法和自我