Voronoi博弈形式的競爭選址問題的研究.pdf

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

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

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