Ես պետք է պատասխան [Այցելու (3.17.*.*) | Մուտք գործել ]
Բոլորը պատասխանները [ 1 ]
[Անդամ (365WT)]պատասխանները [Չինական ]
Ժամանակ :2017-11-24
Բոլոր հայտնի NP- ծանրակոչային ալգորիթմները ունեն արտոնյալ ռեժիմներ: Այնուամենայնիվ, երբեմն կան պոլիմերային ալգորիթմներ, եթե մենք փնտրում ենք «լավ», այլ ոչ թե օպտիմալ լուծում:
Հաշվի առնելով նվազագույնի խնդիրը եւ մոտարկման ալգորիթմը, մենք գնահատում ենք ալգորիթմը հետեւյալը. Նախ, օպտիմալ որոշումների ստորին սահմանը տալը, ապա համեմատել ալգորիթմի վազքի արդյունքը ստորին սահմանի հետ
Համեմատության համար: Մաքսիմալիզացման խնդրի համար առաջին հերթին տվեք վերին սահմանը եւ ապա համեմատեք ալգորիթմի վազքի արդյունքը վերին եզրով:
Մոտավոր ալգորիթմները ներառում են `նվազագույն ուղղահայաց ծածկույթ, ճանապարհորդող վաճառողի խնդիր, սահմանափակում եւ այլն:
Մինչ օրս բոլոր NP- ամբողջական խնդիրները պոլինոմիական ժամանակի ալգորիթմներ չունեն: Նման խնդիրների համար սովորաբար կարելի է հետեւել հետեւյալ ռազմավարությանը:
(1) Խնդրի միայն կոնկրետ դեպքերում լուծեք
(2) օգտագործելով դինամիկ ծրագրավորումը կամ մասնաճյուղը եւ լուծված մեթոդը
(3) լուծում հավանականության ալգորիթմի հետ
(4) Միայն մոտավոր լուծում
(5) Օգտագործեք ինհարիստական մեթոդ լուծելու համար
Եթե օպտիմալացման խնդրի օպտիմալ արժեքը c * է, խնդրի լուծման մոտավոր ալգորիթմի կողմից ստացված մոտավոր օպտիմալ լուծումների օբյեկտիվ գործառնական արժեքը c է,
Հարաբերական ալգորիթմի կատարողականության հարաբերակցությունը սահմանվում է որպես max (c / c *, c * / c): Ընդհանուր առմամբ, այս ցուցանիշի հարաբերակցությունը խնդրի ներածման չափի գործառույթն է
ρ (n), այսինքն, max (c / c *, c * / c) ＜= ρ (n): Հարաբերակցության ալգորիթմի հարաբերական սխալը սահմանվում է որպես Abs [(c-c *) / c *]: Եթե խնդրի մուտքագրման չափը n ունի ֆունկցիա ε (n), որ Abs [(c-c *) / c *] ＜= ε (n), ապա ε (n) մոտարկման ալգորիթմի հարաբերական սխալն է: Ρ (n )- ի եւ ε (n) հարաբերական սխալի միջեւ մոտավոր կատարողականության հարաբերակցությունը ակնհայտորեն հետեւյալն է
Հարաբերություններ. Ε (n) ≤ρ (n) -1.
版权申明 | 隐私权政策 | Հեղինակային իրավունք @2018 World հանրագիտարանային գիտելիքներ,
