一個(gè)藝術(shù)畫(huà)廊看守問(wèn)題的啟發(fā)式算法.pdf

1、藝術(shù)畫(huà)廊問(wèn)題來(lái)源于人們的現(xiàn)實(shí)生活，已經(jīng)吸引了越來(lái)越多的學(xué)者對(duì)其進(jìn)行研究。如今，它在現(xiàn)實(shí)生活的很多領(lǐng)域中都有著重要的應(yīng)用。由于求任一簡(jiǎn)單多邊形所需看守的最少數(shù)目”這一算法是NP-難的，所以人們嘗試著給出求簡(jiǎn)單多邊形所需看守?cái)?shù)目相對(duì)比較優(yōu)的算法。本文提出了大部分具有k個(gè)凹點(diǎn)的簡(jiǎn)單多邊形所需看守?cái)?shù)目的一個(gè)啟發(fā)式算法，一般情況下，此看守?cái)?shù)目要要優(yōu)于k。因此，無(wú)論在理論上還是在實(shí)際應(yīng)用中，對(duì)其研究都具有一定的意義。主要研究?jī)?nèi)容如下： (1

2、)由藝術(shù)畫(huà)廊定理可知，對(duì)于任意的多邊形Pn，其最小看守?cái)?shù)為|n/3|。在研究多邊形所需監(jiān)視器的數(shù)目中，多邊形中的凹點(diǎn)起著非常重要的作用。由于對(duì)絕大多數(shù)的具有k個(gè)凹點(diǎn)的簡(jiǎn)單多邊形來(lái)說(shuō)，k臺(tái)監(jiān)視器并不是最優(yōu)的。所以，通過(guò)分析簡(jiǎn)單多邊形的剖分及其算法，從凹點(diǎn)的角度出發(fā)，提出簡(jiǎn)單多邊形的M形剖分以及M形剖分的算法，并在此剖分及其算法的基礎(chǔ)上給出了藝術(shù)畫(huà)廊看守問(wèn)題的啟發(fā)式算法，得出大部分具有七個(gè)凹點(diǎn)的簡(jiǎn)單多邊形需要的看守?cái)?shù)目G，滿(mǎn)足|k/2|≤G