94.Grexem algoritmi realizatsiyasini yozing Kofman - Grem algoritmi bu algoritmnomi bilan nomlangan Edvard G. Kofman, kichik va Ronald Grem, a elementlarini tartibga solish uchun qisman buyurtma qilingan to'plam darajalar ketma-ketligiga Algoritm tartibni ketma-ket ketma-ket keladigan element pastki darajaga berilishi va har bir sathda belgilangan kenglik chegarasidan oshmaydigan bir qator elementlar bo'lishi uchun tartibni tanlaydi. V. Qachon V = 2, bu aniq darajalarning mumkin bo'lgan minimal sonidan foydalanadi,[1] va umuman olganda u eng ko'p foydalanadi 2 − 2/V zarur darajadan ikki baravar ko'p.Coffman-Graham algoritmi bilan hal qilingan ish do'konini rejalashtirish muammosining versiyasida bitta to'plam berilgan. n ish joylari J1, J2, ..., Jn, ustunlik cheklovlari tizimi bilan birgalikda Jmen < Jj bu ishni talab qiladi Jmen ishdan oldin bajarilishi kerak Jj boshlanadi. Har bir ishni bajarish uchun birlik vaqtini olish kerak deb taxmin qilinadi. Rejalashtirish vazifasi ushbu ishlarning har birini tizimdagi vaqt oralig'iga tayinlashdir V bir xil protsessorlar, minimallashtirish yasash topshiriq (birinchi ish boshlanganidan yakuniy ish tugagunga qadar bo'lgan vaqt). Xulosa qilib aytganda, ustuvorlik cheklovlari ish joylarida qisman tartibni belgilaydi, shuning uchun muammoni ushbu qisman tartib elementlarini darajalarga (vaqt oraliqlariga) har bir vaqt oralig'ida ko'pi bilan ko'p ishlarga ega bo'ladigan tarzda belgilashning bir usuli sifatida o'zgartirish mumkin. protsessorlar (ko'pi bilan V ustunlik cheklovlarini hisobga olgan holda har bir darajadagi elementlar). Ushbu dastur Coffman va Graham uchun o'zlarining algoritmlarini ishlab chiqish uchun asl motivatsiya edi.[1][4] In qatlamli grafik chizish tomonidan belgilangan ramka Sugiyama, Tagava va Toda (1981)[5] kirish a yo'naltirilgan grafikva grafika chizmasi bir necha bosqichda qurilgan:[6][7] A teskari aloqa yoyi o'rnatilgan tanlangan va kirishni a ga aylantirish uchun ushbu to'plamning qirralari teskari yo'naltirilgan yo'naltirilgan asiklik grafik. Grafik tepalariga butun son berilgan y- har bir chekka uchun boshning tepa uchi tugaydigan vertikadan yuqori koordinataga ega bo'ladigan tarzda koordinatalarini eng ko'pi bilan V tepaliklar bir xil bo'lishadi y- muvofiqlashtirish. Dummy vertikalar har bir chetga kiritiladi, shunda bo'linadigan qirralarning barchasi chizilganning qo'shni darajalarida joylashgan tepalik juftlarini bog'laydi. Xuddi shu tepaliklarning har bir guruhi ichida y- koordinatali, tepaliklar buzilgan minimallashtirish uchun o'tish joylari soni natijada olingan rasmda va tepaliklar tayinlangan x- bu almashtirish bilan izchil koordinatalar. Grafaning tepalari va qirralari ularga berilgan koordinatalar bilan chiziladi. Ushbu doirada y-koordinatali topshiriq yana qisman tartiblangan to'plam elementlarini (grafaning tepalari, bilan.) guruhlashni o'z ichiga oladi erishish imkoniyati tepaliklar to'plamiga buyurtma berish) qatlamlarga (bir xil tepaliklar to'plamlari) y-koordinat), bu Kofman-Grem algoritmi bilan hal qilingan muammo.[6] Qatlam bosqichiga Kofman-Grem algoritmidan ko'ra muqobil yondashuvlar mavjud bo'lishiga qaramay, bu muqobillar umuman darajaning maksimal kengligi chegarasini o'z ichiga olmaydi yoki kompleksga tayanmaydi. butun sonli dasturlash protseduralar.[8] Keyinchalik mavhum ravishda, ushbu ikkala muammo ham kirish qisman tartiblangan to'plam va butun sondan iborat bo'lgan muammo sifatida rasmiylashtirilishi mumkin. V. Istalgan natija - bu qisman tartiblangan to'plam elementlariga butun sonli darajadagi raqamlarni belgilash, agar shunday bo'lsa x < y qisman tartibning tegishli elementlarining tartiblangan juftligi, berilgan raqam x tayinlangan sondan kichikroq y, eng ko'pi kabi V elementlarga bir-birlari bilan bir xil son beriladi va eng kichik va eng katta berilganlar orasidagi farqni minimallashtiradi.
