Келесі жоспарлау мәселесіне қандай да бір тәсілдер бар ма?

Мына мәселені қарастырайық: $ K $ тапсырмалары $ \ langle n_1, n_2, ..., n_K \ rangle $ беріледі. Әрбір тапсырма $ n_i $ екі параметрге сәйкес келеді:

  1. Аяқталу уақыты ($ t_i $) және
  2. Оны аяқтаудың утилитасы, $ u_i $. $ U_i $ - $ n_i $ тапсырмасын орындағаннан кейін алынған кірісті білдіретін скалярлық шамасы деп есептейік (біз марапатталған $ u_i $ after $ t_i $).

Барлық тапсырмалар қол жетімді және олардың арасындағы шектеулер жоқ. Біреуді іске қосқаннан кейін оны басқа біреуіне ауыстырудың алдында аяқтау керек. Жалпы табыс тұрақты және бұл $ U = \ sum \ limits_ {i = 1} ^ u_i $ тең екендігі анық. Бұл сыйлықтың $ T = \ sum \ limits_ {i = 1} ^ K t_i $ тең жалпы уақытында алынатыны анық.


Біз, бірақ, мүмкіндігінше көп пайдасын болжайтын $ K $ міндеттерінің жақсы орналасуын (немесе орналастырылуын) есептеуде мүдделіміз.


Екі жылдам сұрақ:

  1. Осы мәселеге белгілі тәсілдер қандай?
  2. Егер $ u_i $ тапсырманы аяқтаған кезде біз марапатталатын болсақ, уақыт өте келе функция ретінде анықталады?

Міне, осы мәселеге қатысты түсініктемелерді де қабылдайтын болар үшін, мәселені формальды негізде қоюға ерекше әрекет. Жауаптар міндетті түрде бірдей жолдармен жүру күтілмейді:

$ \ Pi: \ langle n_1, n_2, ..., n_K \ rangle $ арнайы шарты үшін $ X $ $ (0, T) $ интервалы бойынша қызметті ұсынатын кездейсоқ айнымалыны көрсетіңіз. $ X $ кездейсоқ айнымалы кездейсоқ айналымның $ x $ тең $ t \ leq T $ шамасына тең екендігін білдіреді. Бұл негіздеме оңтайландыруды білдіреді метриком тығыздығы функциясы жазылған аймақ болуы керек: $ F \ {\ pi, t} = p (X \ leq x, t) $ Екі $ f $ және $ F $ $ \ pi $ және $ t $, себебі әр мәселе әртүрлі қисықтарды және әртүрлі нәтижелердің әр түрлі мәндерін анықтайды.

Бұл біздің проблемамыздың келесі ресми түрде анықталуына әкеледі:


$ K $ тапсырмаларын $ \ langle n_1, n_2, ..., n_K \ rangle $ әрбір утилитасы бар білікті $ u_i $ және оны аяқтау үшін қажетті уақытты ескере отырып, $ t_i $ оңтайлы ауыспалы $ \ pi ^ * $ $ K $ $ арасында $ \ pi $ пуазбалық перестандарттардың арасында төмендегідей көбейтіледі:

$ \ sum \ limits_ {t = 1} ^ F F {\ pi, t} $


Көп рақмет,

0
Бұл өзгерісті қарастырайық: T уақытын ескере отырып, біз осы уақытта пайдасын барынша арттыруды қалаймыз, содан кейін мәселе 0-1 кнапак проблемасы сияқты, уақыт осында салмақ, T - қоржынның өлшемі және пайдалы қасиеті. Мәселе нашар NP-толық болып табылады, өйткені біз осы нұсқа үшін кнапкак сияқты бірдей динамикалық бағдарламалау тәсілін қолдануға болады. Менің ойымша, бұл жалпы жағдайға да байланысты. Егер $ u_i $ уақыт анықталған болса, қарапайым ашқарақтық алгоритм жұмыс істейді.
қосылды автор Saeed, көзі
Мен мұны қарадым және мұны ескеріп, бұрынғы түсініктеме жаздым. Пожалуйста, менің түсініктеме оқып, ол кнапкамен (өзіңіздің ойыңызша) байланысты емес деп ойлайсыз, егер менің пікірім әлі жарамсыз деп ойласаңыз, онда мен мысал боламын. Мен айтқанымның жалпы уақыты - бұл нөл мен жалпы уақыт аралығындағы уақыт (Уақыттың жалпы уақыты S, содан кейін $ 0 \ le T \ le S $). Бұл нақты қапшық, қапшықта жалпы салмағы мен жалпы мәнін білеміз, бірақ нақты салмақ үшін біз ең жақсы мәнді білмейміз.
қосылды автор Saeed, көзі
Карлос, сіз дұрыссыз, және менің бірінші түсініктемеңізді байқасаңыз, бұл өзгеріс деп айтқанмын (және екінші сұрағыңыз біріншіден сіздің сұрағыңызды түсіндірмеді), менің ойымша, тіпті белгілі бір уақыт ішінде бұл NP-толық, бұл ынталандырады мүмкін, жалпы агрегация тіпті қиын. Сондықтан мен оны жауап ретінде бермедім, себебі бұл шын мәнінде түпнұсқа емес, және мен жай ғана мәселені NP-қиын деп айтуға тырыстым және жай ғана полиномиальды алгоритм іздеген жағдайда, менің ойымша, многоцинома жоқ , бірақ сіз жалпы жағдайыңыз үшін, қапшық жұмыс істейтін сияқты динамикалық бағдарламалау болуы мүмкін.
қосылды автор Saeed, көзі
Менде жоғарыда айтылған ескертулерді дәлелдеу немесе жоққа шығару туралы ештеңе жоқ, себебі басқаша жауап беруді жоспарладым. Бірақ бөлшектік жағдайда біз жалпы біріктіруді қарапайым алгоритм арқылы оңтайландыра аламыз. (егер u уақыт бойынша тривиальды функция болса). Қалай болғанда да, кез-келген адам өзіңіздің проблемаңызды қапшық мәселесінің өзгеруімен қарастырған болуы мүмкін.
қосылды автор Saeed, көзі
@Saeed: жауап үшін рақмет! Барлық тапсырмалар орындалатындығын ескеріңіз. Қапшық мәселесі жоқ. Біз T жалпы уақытынан кейін жалпы U функциясына ие болатынын білеміз. Мәселе утилитаны уақтылы белгіленген функция ретінде максималды түрде арттыру болып табылады. Егер сіз оны ұнатсаңыз, әртүрлі алмасулар бірдей жалпы U және T, бірақ әртүрлі профильдер арқылы уақытты беретін бірнеше мысалды көре аламын. Әрқайсысының өз аумағы бар және біз ең үлкен аумақты беретін есептеу әдісін табуға тырысамыз.
қосылды автор Carlos Linares López, көзі
Сәлем, Саид! Көмектесу үшін тағы да рахмет. Мен шын мәнінде түсіндім, сіз кез-келген $ T $, $ 0 \ leq T \ leq S $ үшін қапшық мәселесінің уақытша нұсқасын есептеуді ұсынасыз, бұл нақты $ T $ үшін оңтайлы шешімдерді қамтамасыз етеді. Мен көрмеген нәрсе - бұл барлық нәрселердің қапшыққа сай келетін $ S $ кезінде оңтайлы шешім туралы не айтады? Ендеше, бізге пайдасы бар аймақ максималды түрде орындалатын міндеттердің ең жақсы тәртібі қызықтырады. Мен қапшық мәселесінің шешімі туралы ешқандай ақпарат көрмеймін. Мен не жоғалтып жатырмын?
қосылды автор Carlos Linares López, көзі
Эй Саид! Сен, әрине, дұрыс. Өкінішке орай, мен мәселені шешуге ұмтылдым :) Шындығында сіздің жауапыңыз көп мағынаға толы және сұрайтынымның себебі - біз байланысты жұмыстарға мүдделіміз. Бір қызығы, біз ештеңені таппадық! Көптеген рахмет
қосылды автор Carlos Linares López, көзі

Жауап жоқ

0