Klee – Minty текшесі - Википедия - Klee–Minty cube

Simle көлеңкелі әдісі үшін Klee Minty кубы.

The Кли-Минти кубы немесе Кли-Минти политопы (атымен Виктор Кли және Джордж Дж. Минти [де ]) Бұл бірлік гиперкуб айнымалы өлшем оның бұрыштары бұзылған. Кли мен Минти мұны көрсетті Джордж Дантциг Келіңіздер қарапайым алгоритм олардың «сығылған текшесінің» бір бұрышында инициалданған кезде нашар нашар өнімділікке ие. Үш өлшемді нұсқада қарапайым алгоритм және кросс-кросс алгоритмі ең нашар жағдайда барлық 8 бұрышқа барыңыз.

Атап айтқанда, көптеген оңтайландыру алгоритмдер үшін сызықтық оңтайландыру Klee-Minty кубына қолданған кезде нашар өнімділікті көрсетеді. 1973 жылы Кли мен Минти Дантцигтікі екенін көрсетті қарапайым алгоритм болған жоқ көпмүшелік уақыт алгоритмі олардың текшесіне қолданған кезде.[1] Кейінірек Klee-Minty текшесінің модификациялары басқаларға да нашар мінез-құлықты көрсетті негіз -айырбастау айналмалы алгоритмдер, сонымен қатар интерьерлік алгоритмдер үшін.[2]

Кубтың сипаттамасы

Klee-Minty кубы бастапқыда сызықтық теңсіздіктердің параметрленген жүйесімен, өлшемі параметрмен көрсетілген. Өлшем екі болғанда, «куб» сығылған квадрат болады. Өлшем үш болғанда, «текше» - қысылған текше. Алгебралық сипаттамалардан басқа «текше» суреттері пайда болды.[3][4]

Klee-Minty политопы берілген[5]

Бұл бар Д. айнымалылар, Д. басқа шектеулер Д. теріс емес шектеулер және 2Д. төбелер, а Д.-өлшемді гиперкуб жасайды. Егер максималды функция функциясы

егер симплекс алгоритмінің бастапқы шыңы бастау болса, онда Дантциг тұжырымдаған алгоритм барлық 2-ге кіредіД. ақыр соңында оңтайлы шыңға жететін шыңдар

Есептеудің күрделілігі

Klee-Minty кубы көптеген алгоритмдердің нәтижелерін талдау үшін пайдаланылды, ең нашар жағдайда да, орташа есеппен де. The уақыттың күрделілігі туралы алгоритм санын есептейді арифметикалық амалдар алгоритмге мәселені шешуге жеткілікті. Мысалға, Гауссты жою талап етеді тәртібі Д.3 амалдар, сондықтан полиномдық уақыттың күрделілігі бар дейді, өйткені оның күрделілігі а-мен шектелген кубтық көпмүше. Алгоритмдердің полиномдық-уақыттық күрделілігі жоқ мысалдары бар. Мысалы, Гауссты жоюды жалпылау деп аталады Бухбергердің алгоритмі оның күрделілігі үшін проблемалық деректердің экспоненциалды функциясы бар ( көпмүшелік дәрежесі және -ның айнымалылар саны көп айнымалы көпмүшеліктер ). Көрсеткіштік функциялар сайып келгенде полиномдық функцияларға қарағанда әлдеқайда тез өсетіндіктен, экспоненциалды күрделілік алгоритмнің үлкен есептерде баяу жұмыс істейтіндігін білдіреді.

Ең нашар жағдай

Үшөлшемді иллюстрация политоп бұл сызықтық бағдарламалауға арналған аймақ. Симплекс алгоритмі шетінен өтеді төбелер ол оңтайлы шыңға жеткенше. Көрсетілген жағдайда симплекс алгоритмі бес қадамды алады. Алайда, симплекс алгоритмі ең қиын жағдайда, кез-келген шыңға шығады, оның мүмкін болатын аймағы - Кли-Минти кубы, сондықтан қадамдар саны есептің өлшемімен геометриялық өседі.

Математикалық оңтайландыруда Klee-Minty кубы мысал бола алады ең нашар есептеу күрделілік көптеген алгоритмдер туралы сызықтық оңтайландыру. Бұл деформацияланған текше дәл 2-менД. бұрыштар өлшем  Д.. Кли мен Минти мұны көрсетті Дантцигтікі қарапайым алгоритм бұрыштардың барлығына барады (мазасызданған) текше өлшемдеД. ішінде ең жаман жағдай.[1][6][7]

Klee-Minty конструкциясының модификациялары ұқсас экспоненциалды көрсетті уақыттың күрделілігі сияқты қарапайым мүмкіндіктерді сақтайтын симплекстің басқа бұрылыс ережелері үшін Бланд ережесі.[8][9][10] Тағы бір модификация көрсеткендей кросс-кросс алгоритмі, бұл негізгі орындылықты сақтамайды, сонымен қатар өзгертілген Klee-Minty текшесінің барлық бұрыштарын аралайды.[7][11][12] Симплекс алгоритмі сияқты, кросс-кросс алгоритмі нашар жағдайда үш өлшемді текшенің барлық 8 бұрыштарын аралайды.

Төмендегі алгоритмдер

Klee-Minty текшесінің келесі модификациялары нашар өнімділікті көрсетті орталық жол- алгоритмдерді қадағалау сызықтық оңтайландыру үшін орталық жол текшенің әр бұрышына ерікті түрде жақындай түседі. Бұл «шыңды аңду» өнімділігі таңқаларлық, өйткені мұндай алгоритмдердің сызықтық оңтайландыру үшін полиномдық-уақыттық күрделілігі бар.[3][13]

Орташа жағдай

Кли-Минти кубы зерттеулерге шабыт берді жағдайдың орташа күрделілігі. Қажетті бұрылыстар кездейсоқ түрде жасалған кезде (және ең төмен шығу ережесі бойынша емес), Дантцигтің қарапайым алгоритмі қажет орта есеппен квадраттық түрде көптеген қадамдар (бұйрығы бойынша O (Д.2).[4]Симплекс алгоритмінің стандартты нұсқалары орташа алғанда қабылданадыД. текшеге арналған қадамдар.[14] Ол текшенің кездейсоқ бұрышында инициализацияланған кезде, кросс-кросс алгоритмі тек кіредіД. қосымша бұрыштар, дегенмен, Фукуда мен Намикидің 1994 жылғы мақаласында.[15][16] Симплекс алгоритмі де, крисс-кросс алгоритмі де үш өлшемді текшенің орта есеппен 3 қосымша бұрышына келеді.

Сондай-ақ қараңыз

Ескертулер

  1. ^ а б Klee & Minty (1972)
  2. ^ Деза, Антуан; Нематоллахи, Эйсса; Terlaky, Tamás (мамыр 2008). «Интерьерлік нүктелер әдісі қаншалықты жақсы? Klee-Minty текшелері итерация мен күрделіліктің шекараларын күшейтеді». Математикалық бағдарламалау. 113 (1): 1–14. CiteSeerX  10.1.1.214.111. дои:10.1007 / s10107-006-0044-x. МЫРЗА  2367063. (жазылу қажет). pdf нұсқасы профессор Дезаның басты бетінде.
  3. ^ а б Deza, Nematollahi & Terlaky (2008)
  4. ^ а б Гартнер және Зиглер (1994)
  5. ^ Гринберг, Харви Дж., Кли-Минти политопы симплекс әдісінің уақыт бойынша күрделілігін көрсетеді Денвердегі Колорадо университеті (1997) PDF жүктеу
  6. ^ Мурти (1983 ж.), 14.2 Есептеудің ең нашар күрделілігі, 434–437 бб.)
  7. ^ а б Терлаки және Чжан (1993)
  8. ^ Бланд, Роберт Г. (мамыр 1977). «Симплекс әдісі үшін жаңа ақырғы бұрылыс ережелері». Операцияларды зерттеу математикасы. 2 (2): 103–107. дои:10.1287 / moor.2.2.103. JSTOR  3689647. МЫРЗА  0459599.
  9. ^ Мурти (1983 ж.), 10.5 тарау, 331–333 б .; мәселе 14.8, б. 439) сипаттайды Бланд ережесі.
  10. ^ Мурти (1983 ж.), 14.3 есеп, б. 438; мәселе 14.8, б. 439) Бланд ережесінің ең ауыр күрделілігін сипаттайды.
  11. ^ Roos (1990)
  12. ^ Фукуда және Терлаки (1997)
  13. ^ Мегиддо және Шуб (1989)
  14. ^ Жалпы, қарапайым симплекс алгоритмі үшін қадамдардың күтілетін саны пропорционалдыД. ішінен кездейсоқ сызылатын бағдарламалық есептер үшін Евклид бірлік сферасы Боргвардт және дәлелдегендей Smale.

    Боргвардт (1987): Боргвардт, Карл-Хайнц (1987). Симплекс әдісі: Ықтималдық талдау. Алгоритмдер және комбинаторика (оқу және зерттеу мәтіндері). 1. Берлин: Шпрингер-Верлаг. xii + 268 бет. ISBN  978-3-540-17096-9. МЫРЗА  0868467.

  15. ^ Фукуда және Намики (1994), б. 367)
  16. ^ Фукуда және Терлаки (1997), б. 385)

Әдебиеттер тізімі

Сыртқы сілтемелер

Алгебралық сипаттамасы иллюстрациямен

Алғашқы екі сілтемеде алгебралық құрылым да, үш өлшемді Кли-Минти кубының суреті де бар:

Сызықтық жүйесі жоқ суреттер