問(wèn)答題

【簡(jiǎn)答題】什么是算法A對(duì)于實(shí)例I的近似比、A的絕對(duì)近似比和漸進(jìn)近似比？

答案：算法A對(duì)于實(shí)例I的近似比（ratio factor）=RA（I）=max{A（I）/OPT（I），OPT（I）...

你可能感興趣的試題

問(wèn)答題

【簡(jiǎn)答題】引入NP-完全性概念有什么意義？

答案：如果存在一臺(tái)DTM在多項(xiàng)式時(shí)間里接受某個(gè)NP-C語(yǔ)言，則所有NP類語(yǔ)言均可找到DTM在多項(xiàng)式時(shí)間里接受，從而有P=NP。...

問(wèn)答題

【簡(jiǎn)答題】什么是NP-完全性語(yǔ)言？什么是NP-完全性問(wèn)題？什么是NP-hard問(wèn)題？

答案：