Фюъѓьхэђ тчџђ шч ъ§јр яюшёъютющ ьрјшэћ. Рф№хё ю№шушэрыќэюую фюъѓьхэђр : http://lvk.cs.msu.su/~bahmurov/course_realtime/papers/balashov_TeorSist6_2007.pdf
Фрђр шчьхэхэшџ: Wed May 27 16:22:55 2015
Фрђр шэфхъёш№ютрэшџ: Sat Apr 9 23:15:08 2016
Ъюфш№ютър: ISO8859-5

№ёзцћ§№? њдї. §цљњ№? № ћ№ћ§цѕ? ќјњдзѓцї№?, 2007, < 6, т. 76-84

ћлтъвпмРи молб л лттову,млв уфв^ли
ќсє 681.3

дѓйљњ№§ѕ? ўљњѕ№њљздї№? њцєљѕцїсдх№ђ јњ№ јѓдї№њљздї№№ №їўљњѕдх№љїїљйљ љеѕцїд јљ єдїдѓќ ћ хцї§њдѓ№ёљздїї?ѕ ќјњдзѓцї№цѕ*
? 2007 ,,. з. з. ео?у,
ѕутн,, ѕйќ лп. ѕ. з. ѓупумуту,
јутъыфло , вн^л 28.05.07 ,,.

јл футъувмлл тфлтмлfl лмщуп^лумму,,у уЧпвм фу нмоы т ^вмъолбу,ммРп ыф,овмлвп , тутъ,в ,тъувммуи тлтъвпР воШму,,у ,впвмл пуквъ ЧРъШ ,Рfl,овм мвту,пвтълпутъШ ъвЧу,мли н лмщуп^луммупы уЧпвмы. з ъуп тоы~в мв,убпукму футъулъШ тфлтмлв, ыу,овъ,уflвв ,твп ъвЧу,млflп. з Чуъв фвоуквмР о,,улъпР ,ъупъл~втну,,у щуплу,млfl внупвм^ли фу лбпвмвмл ъвЧу,мли н лмщуп^луммупы уЧпвмы фу нмоы оfl уЧвтфв~вмлfl лi ту,пвтълпутъл. јл,ввмР вбыоШъъР нтфвлпвмъоШму,,у лттову,млfl уму,,у лб ттпуъвммРi о,,улъпу,.

з,ввмлв. з тутъ,в тфввовммРi ,тъувммРi тлтъвп воШму,,у ,впвмл (зћњз) оfl ,блпувитъ,лfl пвкы футлтъвппл ?луну лтфуоШбыътfl нмоР т ^вмъолбу,ммРп ыф,овмлвп, мфлпв пыоШълфовнтмРи нмо лмщуп^лумму,,у уЧпвм (ѕє№љ) [1]. њтфлтмлв лмщуп^лумму,,у уЧпвм оfl ънлi нмоу, тъулътfl, нн ф,лоу, тъъл~втнл, ~ъу fl,оflвътfl NP-ъымуи б~ви, фл~вп , воШмРi зћњз ~лтоу Чуъ оfl ,но~вмлfl , тфлтмлв утъл,,въ мвтнуоШнлi туъвм. јл щуплу,млл тфлтмлfl мвуЧiулпу ы~лъР,ъШ ^воРи fl ъвЧу,мли н лмщуп^луммупы уЧпвмы, , ъуп ~лтов тфв^лщл~втнлв оfl iлъвнъыР нумнвъмуи зћњз ъвiмуоу,,л~втнлв у,,мл~вмлfl м уЧпвм фу нмоы. зР~лтолъвоШмfl тоукмутъШ б~л футъувмлfl тфлтмлfl фл,улъ н мв,убпукмутъл флпвмвмлfl ъу~мРi о,,улъпу,, фуъупы м фнълнв лтфуоШбыътfl ,лтъл~втнлв о,,улъпР фомлу,млfl лмщуп^лумму,,у уЧпвм [2]. цтол лтфуоШбывпРи о,,улъп фомлу,млfl лмщуп^лумму,,у уЧпвм мв пуквъ тщуплу,ъШ тфлтмлв т ы~въуп ,твi ъвЧу,мли н лмщуп^луммупы уЧпвмы, Чывп ,,у,улъШ, ~ъу мЧу ъвЧу,мли fl,оflвътfl мвту,пвтълпРп. њбЧуъ~лны зћњз мвуЧiулпу ,мвтъл нувнъл,Р , ънуи мЧу. днъыоШм б~ ,ъупъл~втну,,у щуплу,млfl внупвм^ли фу лбпвмвмл мвту,пвтълпу,,у мЧу ъвЧу,мли. з Чуъв фвоуквмР о,,улъпР щуплу,млfl внупвм^ли фу лбпвмвмл мвту,пвтълпу,,у мЧу ъвЧу,мли н лмщуп^луммупы уЧпвмы оfl уЧвтфв~вмлfl лi ту,пвтълпутъл. јл,ввмР вбыоШъъР нтфвлпвмъоШму,,у лттову,млfl уму*

*

,,у лб фвоуквммРi о,,улъпу,, флпвмflвпу,,у , тутъ,в лмтъыпвмъоШмуи тлтъвпР ,ъупъл~втну,,у фомлу,млfl лмщуп^лумму,,у уЧпвм фу нмоы т ^вмъолбу,ммРп ыф,овмлвп [3, 4]. 1. љ,,млб^лfl лмщуп^лумму,,у уЧпвм фу нмоы т ^вмъолбу,ммРп ыф,овмлвп. 1.1. ќф,овмлв лмщуп^луммРп уЧпвмуп фу нмоы. ємо т ^вмъолбу,ммРп ыф,овмлвп фвтъ,оflвъ туЧуи уЧы ?лмы, н нуъууи фуно~вмР ЧумвмъР нмо. љлм лб Чумвмъу, fl,оflвътfl нумъуоовуп нмо, нуъуРи лмл^ллывъ ,тв уЧпвмР ммРпл пвкы Чумвмъпл л утывтъ,оflвъ нумъуоШ ытфв?мутъл уЧпвму,. ју~лв ЧумвмъР лтфуомflъ нупмР нумъуоов, му мв пу,,ыъ тпутъуflъвоШму лмл^ллу,ъШ уЧпвмР ммРпл. №мщуп^лfl фу нмоы фвввътfl , ,лв тууЧвмли, олъвоШмутъШ фвв~л нуъуРi лб,втъм фл футъувмлл тфлтмлfl. јвв~ы тууЧвмлfl фу нмоы Чывп мбР,ъШ Чуъуи. з тъъШв фвфуо,,вътfl, ~ъу нумъуоов щымн^лумлывъ фу товыви тiвпв. 1. з м~ов ЧуъР зћњз , нумъуоов б,,ыквътfl фу,,пп, тутъуflfl лб ^вфу~вн Чуъ. єкfl ^вфу~н фвтъ,оflвъ туЧуи ыфуflу~вммРи мЧу Чуъ, нуъуРв уокмР ,РфуомflъШтfl футову,ъвоШму. 2. з пупвмъ ,впвмл k*Lsc (,,в Lsc - бммРи фвлу, лбпвflвпРи , ънъi ЧуъР нмо1) нумъуоов м~лмвъ ,Рфуомвмлв ^вфу~нл Чуъ т мупвуп k л у,улъ в,,у у нум^. јвР,млв ъу,,у фу^втт мвуфытълпу. 3. јутов б,в?вмлfl ^вфу~нл Чуъ л у мтъыфовмлfl пупвмъ ,впвмл (k + 1)* Lsc), нумъуоов пу1

њЧуъ ,Рфуомвм фл ~тъл~муи щлммту,уи фувкнв њўў№ (,,мъ < 04-01-00556).

совв ,вбв Чывп т~лъъШ, ~ъу ,впfl лбпвflвътfl , ънъi ЧуъР нмо.

76

дѓйљњ№§ѕ? ўљњѕ№њљздї№? њцєљѕцїсдх№ђ јњ№ јѓдї№њљздї№№ ^вфу~н Чуъ вбв,

77

фу^лно
њлт. 1. ў,,пвмъ тфлтмлfl лмщуп^лумму,,у уЧпвм.

0

§

2ч§

3ч§

њлт. 2. слвнъл,мРв лмъв,оР Чуъ тууЧвмлfl.

квъ фу,ъулъШ ъв ЧуъР лб ^вфу~нл, ,Рфуомвмлв нуъуРi ЧРоу мвытфв?мРп, мфлпв лб-б фупвi , нмов. №мъв,о ,впвмл [k*Lsc; (k + 1)*Lsc мбР,вътfl фу^лноуп т мупвуп k (k = 0, 1, ... ), бм~вмлв Lsc - олмуи фу^лно. з мвнуъуРi фу^лноi пуквъ мв флтыътъ,у,ъШ мл умуи ^вфу~нл Чуъ. єупв фл,ввммуи ,Р?в тiвпР щымн^лумлу,млfl нумъуоов ,убпукмР ы,,лв тiвпР, нуъуРв бвтШ мв ттпъл,ътfl. јвоуквммРв о,,улъпР уфытнъ уЧуЧвмлв м мвнуъуРв лб ълi тiвп, , ъуп ~лтов м тiвпы т фвлул~втнуи Чуъуи нумъуоов нмо лол тiвпы Чвб ,,ыффлу,нл Чуъ , ^вфу~нл. 1.2. § вЧу,млfl н лмщуп^луммупы уЧпвмы фу нмоы. соfl ту,впвммРi зћњз iнъвм ^лнол~втнfl у,,млб^лfl ,Р~лтолъвоШму,,у фу^втт, фл нуъууи Чумвмъ нмо м нкуи лъв^лл т,ув,,у ^лно фу,,уъ,ол,въ фу^л ,РiумРi ммРi оfl фвв~л фу нмоы , ,лв уму,,у лол мвтнуоШнлi тууЧвмли [5]. §лфл~муи Чу~ви м,,ыбнуи оfl нмо fl,оflвътfl мЧу тууЧвмли, фвмбм~вммРi оfl фвлул~втнуи фвв~л; оfl нку,,у тууЧвмлfl бм олъвоШмутъШ л ъвЧывпfl ~тъуъ фвв~л. єумнвъмРв бм~вмлfl ммРi, ъмтолывпРв фу нмоы фл у~ввмуи фвв~в тууЧвмлfl, уфввоflътfl , фу^вттв щымн^лумлу,млfl зћњз. ћфв^лщлн iлъвнъыР нумнвъмуи зћњз бвъ мЧу ъвiмуоу,,л~втнлi у,,мл~вмли м тфлтмлв уЧпвм фу нмоы. совв Чывп ттпъл,ъШ товыли лi мЧу, флпвмflвпРи , воШмуи зћњз: 1) пнтлпоШму уфытълпув ~лтоу Чуъ , ^вфу~нв (овв - олм ^вфу~нл Чуъ); 2) пнтлпоШму уфытълпfl олъвоШмутъШ ^вфу~нл Чуъ (тыппмув ,впfl ,Рфуомвмлfl Чуъ лб ^вфу~нл); 3) олм фу^лно; 4) уоfl олмР фу^лно, бвбв,лу,ммfl оfl фу,ъумРi уЧпвму,; 5) пнтлпоШму уфытълпув уъноумвмлв ттъуflмлfl пвкы Чуъпл фу фвв~в уму,,у л ъу,,у кв тууЧвмлfl уъ фвлу ъу,,у тууЧвмлfl

(фвлу - ~лтоу, уЧъмув ~тъуъв фвв~л тууЧвмлfl). ї лт. 1 фунбм щ,,пвмъ тфлтмлfl лмщуп^лумму,,у уЧпвм, ,но~ли ,в ^вфу~нл Чуъ. њЧуъР уму,,у л ъу,,у кв тууЧвмлfl ,РвовмР улмну,уи ?ълiу,нуи. їЧу тууЧвмли л мЧу ъвiмуоу,,л~втнлi у,,мл~вмли м тфлтмлв , ту,уныфмутъл щуплыъ мЧу ъвЧу,мли н лмщуп^луммупы уЧпвмы фу нмоы. єкупы ъвЧу,мл , тутъ,в ъну,,у мЧу тууъ,вътъ,ывъ ~лтоу,fl iнъвлтълн - бм~вмлв ъвЧу,млfl. їфлпв, бм~вмлв ъвЧу,млfl "олм фу^лно" пуквъ ЧРъШ ,му 1000 (ънъу, нмо). ју лбпвмвмлвп ъвЧу,млfl Чывп фумлпъШ лбпвмвмлв в,,у бм~вмлfl. ївнуъуРв ъвЧу,млfl пу,,ыъ флмлпъШ ъуоШну ^воРв бм~вмлfl (мфлпв, пнтлпоШмfl олм ^вфу~нл Чуъ - фуоуклъвоШмРв ^воРв бм~вмлfl); ы,,лв ъвЧу,млfl - ,ввтъ,вммРв бм~вмлfl (мфлпв, бвбв,лу,ммfl уоfl олмР фу^лно - ,ввтъ,вммРв бм~вмлfl лб лфбум [0; 1)). 1.3. љЧfl тiвп фомлу,млfl лмщуп^лумму,,у уЧпвм фу нмоы т ^вмъолбу,ммРп ыф,овмлв п. јвв футъувмлвп тфлтмлfl ,Р~лтоflвътfl олм Lint лмъв,о фомлу,млfl, , ъв~вмлв нуъуу,,у тфлтмлв уокму ЧРъШ фуомутъШ уъЧуъму, л фу б,в?вмлл м~ъ товыfl лъв^лfl ,Рфуомвмлfl тфлтмлfl. єн ф,лоу, Lint фуо,,вътfl ,муи млпвмШ?впы уЧвпы нъмупы фвлуу, тууЧвмли. єкупы тууЧвмл туфутъ,оflвътfl мЧу лб Lint/T Чуъ фу в,,у фвв~в, ,,в T - фвлу тууЧвмлfl; i-и Чуъв, i = 1, ..., Lint/T, тууъ,вътъ,ывъ лвнъл,мРи лмъв,о [T*(i - 1); T*i), , ъв~вмлв нуъуу,,у Чуъ уокм ЧРъШ б,в?вм. ї лт. 2 фунбмР лвнъл,мРв лмъв,оР оfl мвтнуоШнлi футову,ъвоШмРi Чуъ уму,,у тууЧвмлfl. јл футъувмлл тфлтмлfl нкуи Чуъв уоквм ЧРъШ туфутъ,овм нумнвъмРи пупвмъ вв м~о. ё~ви о,,улъп фомлу,млfl лмщуп^лумму,,у уЧпвм fl,оflвътfl футъувмлв тфлтмлfl, ыу,овъ,уflв,,у товылп ытоу,лflп: 1) тфлтмлв ,но~въ ,тв ЧуъР ,твi тууЧвмли; 2) нкfl Чуъ ,Рфуомflвътfl , фввоi т,ув,,у лвнъл,му,,у лмъв,о; 3) туЧовмР ,тв ъвiмуоу,,л~втнлв у,,мл~вмлfl м тфлтмлв. 2. ё~ щуплу,млfl внупвм^ли фу лбпвмвмл ъвЧу,мли н лмщуп^луммупы уЧпвмы. 2.1. ў у п оШмfl футъму,н б~л щуплу,млfl внупвм^ли. јытъШ бм о,,улъп фомлу,млfl лмщуп^лумму,,у уЧпвм A л мЧу ъвЧу,мли н лмщуп^луммупы уЧпвмы (, ъуп ~лтов бм~вмлfl ,твi ъвЧу,мли). цтол о,,улъп A мв в?въ фл,ввммы ,

№ёзцћ§№? њдї. §цљњ№? № ћ№ћ§цѕ? ќјњдзѓцї№? < 6 2007

78

ео?у,

б. 1.3 б~ы футъувмлfl тфлтмлfl оfl мму,,у мЧу ъвЧу,мли, Чывп мбР,ъШ футовмли мвту,пвтълпРп уъмутлъвоШму о,,улъп д. цтол лтiумРи мЧу ъвЧу,мли н лмщуп^луммупы уЧпвмы мвту,пвтълп уъмутлъвоШму флпвмflвпу,,у о,,улъп фомлу,млfl, бЧуъ~лны зћњз товывъ лбпвмлъШ бм~вмлfl мвнуъуРi ъвЧу,мли лб ъу,,у мЧу оfl уЧвтфв~вмлfl в,,у ту,пвтълпутъл. зубпукмутъШ флпвмвмлfl ы,,у,,у о,,улъп фомлу,млfl , Чуъв мв ттпъл,вътfl; мвуЧiулпу уъпвълъШ, ~ъу ,РЧу о,,улъп фомлу,млfl л мтъуин в,,у м нумнвъмРи мЧу ъвiмуоу,,л~втнлi у,,мл~вмли fl,оflвътfl ъыувпнуи б~ви [2]. совв фу лбпвмвмлвп ъвЧу,млfl Чывп фумлпъШ лбпвмвмлв в,,у бм~вмлfl - мфлпв ы,вол~вмлв пнтлпоШмуи олмР ^вфу~нл Чуъ. ї фнълнв умл ъвЧу,млfl уфытълпу лбпвмflъШ , пнi мвнуъуРi лфбуму, (мфлпв, пнтлпоШмы олмы ^вфу~нл Чуъ), ы,,лв уокмР ЧРъШ туiмвмР (мфлпв, олъвоШмутъл л ~тъуъР фвв~л тууЧвмли). соfl бмРi ъвЧу,мли тоукмутъШ фъ^лл зћњз н лi лбпвмвмл бол~м, , т,flбл т ~вп лбпвмвмлв умлi ъвЧу,мли Чуовв фвфу~ълъвоШму, ~вп ы,,лi. јытъШ мвнуъуРв ъвЧу,млfl , тутъ,в бмму,,у мЧу уфытълпу лбпвмflъШ. ќфуflу~лп ъвЧу,млfl ън, ~ъуЧР ,м~ов тову,ол ъл ъвЧу,млfl, (фумыпвывп лi уъ 1 у NR), бъвп ,тв утъоШмРв (фумыпвывп лi уъ NR + 1 у MAXR). їЧууп бм~вмли ъвЧу,мли н лмщуп^луммупы уЧпвмы Чывп мбР,ъШ ,внъу, овпвмъпл нуъуу,,у fl,оflътfl бм~вмлfl ъвЧу,мли, л фуflун тову,млfl овпвмъу, тууъ,вътъ,ывъ мыпв^лл ъвЧу,мли. з,ввп щымн^л CompA(Y), уфввовммы м пмуквтъ,в ,тв,убпукмРi мЧуу, бм~вмли ъвЧу,мли н лмщуп^луммупы уЧпвмы л флмлпы бм~вмлfl: 1 - втол мЧу ту,пвтълп уъмутлъвоШму о,,улъп A; 0 - , фуъл,муп тоы~в. ўупоШмув фвтъ,овмлв ъвЧу,мли н лмщуп^луммупы уЧпвмы, мвуЧiулпув оfl пъвпъл~втнл тъу,,у,,у бмлfl щымн^лл CompA(Y), му , [6]. з,ввп товылв уЧубм~вмлfl: Ri - ъвЧу,млв т мупвуп i; init1, ..., initMAXR - бм~вмлfl ъвЧу,мли лб лтiуму,,у мвту,пвтълпу,,у мЧу; lim1, ..., limNR - бм~вмлfl, у нуъуРi уфытълпу лбпвмflъШ ъвЧу,млfl т мупвпл i = 1..NR (initi limi, i = 1..NR); INIT - ,внъу т овпвмъпл (init1, ..., initNR); LIM - ,внъу т овпвмъпл (lim1, ..., limNR); FIX - ,внъу т овпвмъпл (initNR+1, ..., initMAXR), тувкли бм~вмлfl ъвЧу,мли, лбпвмвмлв нуъуРi мвуфытълпу; X = (x1, ..., xNR) - ,внъу ъвнылi бм~вмли ъвЧу,мли, бм~вмлfl нуъуРi пукму лбпвмflъШ

(мфлпв, x1 пуквъ тууъ,вътъ,у,ъШ пнтлпоШму уфытълпуи олмв ^вфу~нл Чуъ); X FIX - ,внъу т овпвмъпл (x1, ..., xNR, initNR + 1, ..., initMAXR); бвтШ " " - уфв^лfl нумнъвм^лл ,внъуу,; INIT* = (INIT FIX) = (init1, ..., initMAXR) - ,внъу бм~вмли ,твi ъвЧу,мли лб лтiуму,,у мвту,пвтълпу,,у мЧу; LIM* = (LIM FIX) = (lim1, ..., limNR, initNR + 1, ..., initMAXR) - ,внъу бм~вмли ъвЧу,мли, , нуъууп ,тв ъвЧу,млfl, лбпвмвмлв нуъуРi уфытълпу, пнтлпоШму лбпвмвмР. ё~ы щуплу,млfl внупвм^ли фу лбпвмвмл мвту,пвтълпу,,у мЧу ъвЧу,мли н лмщуп^луммупы уЧпвмы Чывп ттпъл,ъШ , товыви футъму,нв. сму: 1) о,,улъп A тъъл~втну,,у фомлу,млfl лмщуп^лумму,,у уЧпвм; 2) мвту,пвтълпРи уъмутлъвоШму A мЧу бм~вмли ъвЧу,мли н лмщуп^луммупы уЧпвмы INIT* : CompA (INIT*) = 0 3) лмъв,оР, , нуъуРi уфытълпу ,Шлу,ъШ бм~вмлfl ъвЧу,мли: [initi; limi], i = 1..NR; 4) мупв ъвi ъвЧу,мли, лбпвмвмлв нуъуРi уфытълпу л бм~вмлfl нуъуРi уокмР ЧРъШ ^воу~лтовммРпл: {i1, ..., iNZ} (ik NR, k = 1..NZ); 5) ,вту,Рв нущщл^лвмъР, уъклв фвфу~ълъвоШмутъШ лбпвмвмлfl ъвЧу,мли: creli [ R+, i = 1..NR. §вЧывътfl: миъл , уфытълпРi лфбумi ънлв бм~вмлfl ъвЧу,мли, фл нуъуРi мЧу ъвЧу,мли Чывъ ту,пвтълпРп: CompA (X FIX) = 1; ѕлмлплблывпРи нлъвли (^вов,fl щымн^лfl): тыппмРи ",вт" лбпвмвмли Cost(X) = NR = crel i* |(xi - initi)/(limi - initi)|. i=1

ё~ пуквъ ЧРъШ фвтъ,овм , щупв б~л пъвпъл~втну,,у фу,,пплу,млfl [6]: minCost (X) X [ P, CompA(X FIX) = 1 xi [ Z, i [ {i1, ..., iNZ} xi [ R, i [ {1, ..., NR}\{i1,..., iNZ} ,,в P = [init1; lim1] ч ... ч [initNR ; limNR]. 2.2. д молб б~л щуплу,млfl внупвм^ли. јутъ,овммfl , б. 2.1 б~ уъмутлътfl н нотты лтнвъму-мвфвР,мРi б~ пъвпъл~втну,,у фу,,пплу,млfl т олмвимуи ^вов,уи щымн^лви. јлпвуп лтнвъму,,у уфълплблывпу,,у фпвъ пуквъ тоыклъШ пнтлпоШмfl олм ^вфу~нл Чуъ, мвфвР,му,,у фпвъ - уоfl олмР фу^лно, бвбв,лу,ммfl оfl фу,ъумРi уЧпвму,.

№ёзцћ§№? њдї. §цљњ№? № ћ№ћ§цѕ? ќјњдзѓцї№? < 6 2007

дѓйљњ№§ѕ? ўљњѕ№њљздї№? њцєљѕцїсдх№ђ јњ№ јѓдї№њљздї№№

79

љ,,мл~вмлв б~л X [ P fl,оflвътfl олмвимРп, ън нн P фвтъ,оflвъ туЧуи NR-пвмРи фоововфлфв. љ,,мл~вмлв CompA (X FIX) = 1 (овв - у,,мл~вмлв ту,пвтълпутъл) мволмвиму. д,ъуы мв лб,втъму молъл~втнув фвтъ,овмлв щымн^лл CompA оfl ,лтъл~втнлi о,,улъпу, A тъъл~втну,,у фомлу,млfl лмщуп^лумму,,у уЧпвм фу нмоы т ^вмъолбу,ммРп ыф,овмлвп (, ъуп ~лтов о,,улъпп лб [2]), ы~лъР,вв мЧуР ъвiмуоу,,л~втнлi у,,мл~вмли м уЧпвм , воШмРi зћњз (мфлпв, мЧу лб б. 1.2). ћову,ъвоШму, влмтъ,вммРп утъыфмРп тфутуЧуп ,Р~лтовмлfl бм~вмлfl щымн^лл CompA (Y) , уЧвп тоы~в утъвътfl футъувмлв тфлтмлfl фу мЧуы ъвЧу,мли Y фл фупул о,,улъп A. з уъвоШмРi тоы~fli оfl у^вмнл т,вiы лол тмлбы бм~вмлfl щымн^лл CompA пу,,ыъ ЧРъШ лтфуоШбу,мР фвоуквммРв , [7] молъл~втнлв ытоу,лfl ту,пвтълпутъл мЧуу, ъвЧу,мли оfl тiвпР т лмпл~втнлп фомлу,млвп уЧпвму,, нуъуРв т?лflъ ытоу,лfl, фвоуквммРв , [8]. ївуЧiулпу уъпвълъШ, ~ъу т щупоШмуи ъу~нл бвмлfl бм~вмлfl бол~мРi ъвЧу,мли лб уму,,у мЧу пу,,ыъ ЧРъШ мв ту,,оту,мР ы,, т ы,,уп. їфлпв, фл бммуи олмв фу^лно л утъъу~му ЧуоШ?уи олъвоШмутъл нку,,у тууЧвмлfl, олъвоШмутъШ ^вфу~нл Чуъ, ,но~ви пнтлпоШму уфытълпув ~лтоу Чуъ, пуквъ фв,Р?ъШ олмы фу^лно. з ъуп тоы~в фл щуплу,млл тфлтмлfl мв пу,,ыъ ЧРъШ футъувмР ^вфу~нл т пнтлпоШму уфытълпРп ~лтоуп Чуъ, ~ъу, ,ууЧв ,,у,уfl, мв лтно~въ ,убпукмутъл фуоы~вмлfl тфлтмлfl т туЧовмлвп ,твi ъвЧу,мли. з ммуи тъъШв ънлв мвту,,оту,ммРв мЧуР ъвЧу,мли т~лъътfl уфытълпРпл, л мв ,,улътfl млннлi уфуомлъвоШмРi у,,мл~вмли, уътвнлi ъл мЧуР. цтол бм~вмлfl ъвЧу,мли ъну,Р, ~ъу тфлтмлв б,вупу мв пуквъ ЧРъШ тщуплу,му млннлп о,,улъпуп (мфлпв, олм фу^лно пвмШ?в олъвоШмутъл уму,,у лб тууЧвмли), фууЧмРи мЧу бм~вмли ъвЧу,мли мв пуквъ ттпъл,ъШтfl , н~втъ,в в?вмлfl б~л щуплу,млfl внупвм^ли, футнуоШны м мвп мв ,Рфуомвму у,,мл~вмлв ту,пвтълпутъл. љътыътъ,лв молъл~втну,,у фвтъ,овмлfl оfl щымн^лл CompA, ,iуflви , щупыоы у,,мл~вмлfl ту,пвтълпутъл, мв фуб,уоflвъ флпвмflъШ оfl в?вмлfl футъ,овммуи б~л ,уитъ,вммРв пвъуР [6, 9]. соfl уфввовмлfl бм~вмлfl CompA мвуЧiулпу бъШ ,тв бм~вмлfl ъвЧу,мли (ъ.в. ,тв овпвмъР ,внъу X FIX), фуъупы оfl в?вмлfl б~л мвфлпвмлпР нумтъынъл,мРв о,,улъпР, футову,ъвоШму утъл,лв в?вмлв б~л (, ~тъмутъл, мвфлпвмлп пвъу ,въ,ви л ,,мл^). ћову,ъвоШму, оfl в?вмлfl б~л мвуЧiулпу флпвмflъШ фflпРв лъв^луммРв о,,улъпР [6].

2.3. ћ ы втъ,ылв ф уiуР н щуплу,мл внупвм^ли фу лбпвмвмл ъвЧу,мли н лмщуп^луммупы уЧпвмы. ћывтъ,ылв фуiуР [10, 11] н щуплу,мл внупвм^ли фу лбпвмвмл мвту,пвтълпРi ъвЧу,мли н лмщуп^луммупы уЧпвмы оfl ытъмвмлfl мвту,пвтълпутъл ъвЧу,мли улвмълу,мР м Чуъы т лмпл~втнлпл тiвппл фомлу,млfl лмщуп^лумму,,у уЧпвм, оfl нуъуРi тывтъ,ыъ молъл~втнлв ытоу,лfl ту,пвтълпутъл ъвЧу,мли [8, 12]. єн тнбму , б. 2.2, мвлб,втъмР молъл~втнлв ытоу,лfl ту,пвтълпутъл ъвЧу,мли н лмщуп^луммупы уЧпвмы уъмутлъвоШму ,лтъл~втнлi о,,улъпу, тъъл~втну,,у фомлу,млfl лмщуп^лумму,,у уЧпвм фу нмоы т ^вмъолбу,ммРп ыф,овмлвп. еуовв ъу,,у, кв оfl лмпл~втнлi тiвп фомлу,млfl мвлб,втъмР т?лвмлfl молъл~втнлi ытоу,ли ту,пвтълпутъл ъвЧу,мли, фуб,уоflлв , уЧвп тоы~в ы~лъР,ъШ ,олflмлв м ту,пвтълпутъШ мЧу ъвЧу,мли н лмщуп^луммупы уЧпвмы ъвiмуоу,,л~втнлi у,,мл~вмли лб б. 1.2. ћову,ъвоШму, оfl в?вмлfl футъ,овммуи , б. 2.1 б~л мвуЧiулпу тубъШ му,Рв о,,улъпР щуплу,млfl внупвм^ли, фувкл,лв Чуъы т ъвiмуоу,,л~втнлпл у,,мл~вмлflпл м уЧпвм л ы~лъР,лв тфв^лщлны флпвмflвпРi фл тъъл~втнуп фомлу,млл уЧпвм ,лтъл~втнлi о,,улъпу,. 3. до,,улъпР щуплу,млfl внупвм^ли. з бвов фл,ввмР фво,,впРв ,ъууп о,,улъпР в?вмлfl б~л щуплу,млfl внупвм^ли фу лбпвмвмл мвту,пвтълпу,,у мЧу ъвЧу,мли н лмщуп^луммупы уЧпвмы фу нмоы т ^вмъолбу,ммРп ыф,овмлвп. з н~втъ,в флпв мЧу ъвЧу,мли ттпъл,вътfl мЧу, ,,ввммРи , б. 1. љтоЧовмлвп ъвЧу,млfl Чывп мбР,ъШ ънув в,,у лбпвмвмлв, фл нуъууп оЧув тфлтмлв, ыу,овъ,уflвв ъвЧу,мл т лтiумРп бм~вмлвп, ыу,овъ,уflвъ л ъвЧу,мл т му,Рп бм~вмлвп. їфлпв, ы,вол~вмлв пнтлпоШмуи олмР ^вфу~нл Чуъ втъШ утоЧовмлв ъвЧу,млfl. №бпвмвмлв ъвЧу,млfl Чывп мбР,ъШ ытловмлвп, втол в,,у уЧъмув лбпвмвмлв fl,оflвътfl утоЧовмлвп. їфлпв, ы,вол~вмлв бвбв,лу,ммуи уол фу^лно - ытловмлв ъвЧу,млfl, футнуоШны ыпвмШ?вмлв ъуи уол - утоЧовмлв ъвЧу,млfl. јво,,впРв о,,улъпР фувкл,ъ лбпвмвмлв ъвЧу,мли, оfl нуъуРi уфввовмР фумflълfl ытловмлfl л утоЧовмлfl (мфлпв, ъвЧу,мли 1), 2), 4), 5) лб б. 1.2). совв Чывп т~лъъШ, ~ъу бв?вму лбпвмвмлв ъуоШну ънлi ъвЧу,мли. јл ъуп ытоу,лл ,тflнув уфытълпув лбпвмвмлв бм~вмли ъвЧу,мли лб мЧу INIT* fl,оflвътfl лi утоЧовмлвп, мЧу бм~вмли ъвЧу,мли LIM* (тп. б. 2.1) пуквъ

№ёзцћ§№? њдї. §цљњ№? № ћ№ћ§цѕ? ќјњдзѓцї№? < 6 2007

80

ео?у,

ЧРъШ фуоы~вм лб мЧу INIT* пнтлпоШму уфытълпРп утоЧовмлвп ,твi ъвЧу,мли. јутнуоШны бм~вмлfl ъвЧу,мли RNR + 1, ..., RMAXR щлнтлу,мР, ту,пвтълпутъШ мЧу X FIX уфввоflвътfl бм~вмлflпл ъвЧу,мли лб X, ъ.в. ъвi ъвЧу,мли, лбпвмвмлв нуъуРi уфытълпу. совв оfl нънутъл Чывп ,,у,улъШ, ~ъу мЧу бм~вмли ъвЧу,мли X ту,пвтълп (мвту,пвтълп), втол ту,пвтълп (мвту,пвтълп) мЧу X FIX. јво,,впРв о,,улъпР fl,оflътfl ,лтъл~втнлпл л ,Рфуомflъ фултн флЧолквмму,,у в?вмлfl б~л, футнуоШны фултн ъу~му,,у в?вмлfl ъвЧывъ , уЧвп тоы~в фуому,,у фввЧу нупЧлм^ли бм~вмли ъвЧу,мли лб уфытълпРi лфбуму,, ~ъу мвутълклпу , т,flбл т ,Ртунуи ,Р~лтолъвоШмуи тоукмутъШ футъувмлfl тфлтмлfl оfl воШмРi зћњз. 3.1. д о,,улъп т ,лтъл~втнлп ,РЧууп утоЧоflвпу,,у ъвЧу,млfl. їтъуflли о,,улъп , н~втъ,в м~оШму,,у флЧолквмлfl лтфуоШбывъ мвту,пвтълпРи мЧу бм~вмли ъвЧу,мли INIT л утывтъ,оflвъ фултн ту,пвтълпу,,у мЧу бм~вмли ъвЧу,мли, футову,ъвоШму утоЧоflfl уъвоШмРв ъвЧу,млfl. зiумРв ммРв: ,iумРв ммРв б~л щуплу,млfl внупвм^ли (тп. б. 2.1); dcost - плмлпоШму уфытълпув лбпвмвмлв Cost (X) м нкуи лъв^лл о,,улъп. зРiумРв ммРв: success - флбмн ытфв?мутъл б,в?вмлfl о,,улъп (мивм/мв мивм ту,пвтълпРи мЧу бм~вмли ъвЧу,мли); , тоы~в ытфв?му,,у б,в?вмлfl: ту,пвтълпРи мЧу бм~вмли ъвЧу,мли Xres : Xres [ P CompA (Xres FIX).

љтму,муи ^лно о,,улъп. љЧубм~лп ~ввб cur cur X = ( x 1 , ..., ( x NR ) ъвныли мЧу бм~вмли лбпвмflвпРi ъвЧу,мли. ћiвп утму,му,,у ^лно о,,улъп ,но~въ товылв ?,,л: 1) Xcur := INIT; 2) ,Р~лтолъШ бм~вмлв CompA (Xcur FIX), футъул, тфлтмлв фл фупул о,,улъп A; 3) втол CompA (Xcur FIX), ъу success := true; res := Xcur; б,в?лъШ Чуъы; X 4) ,РфуомлъШ ,лтъл~втны фу^выы choose_changes оfl ,РЧу лбпвмвмлfl бм~вмли ъвЧу,мли; 5) втол choose_changes б,в?отШ мвытфв?му, ъу success := false; б,в?лъШ Чуъы; 6) лбпвмлъШ мЧу Xcur , тууъ,вътъ,лл т вбыоШъъуп ,Рфуомвммуи м ?,,в 4 фу^выР choose_changes; 7) фввиъл н ?,,ы 2. ју^вы ,РЧу лбпвмвмли. ју^вы choose_changes ,Рфуомflвъ ,лтъл~втнли ,РЧу ъвЧу,млfl, бм~вмлв нуъуу,,у товывъ лбпвмлъШ , тъуумы утоЧовмлfl, ънкв ,Р~лтоflвъ лбпвмвмлв бм~вмлfl ъвЧу,млfl. јлпвмflвпfl , фу^выв ,лтълн лтфуоШбывъ туЧлвпы фл футъувмлл тфлтмлfl тъълтълны фу мы?вмл ъвЧу,мли н лмщуп^луммупы уЧпвмы Чуъпл, нуъуРв фл ,Рфуомвмлл о,,улъп A мв ыоутШ ,но~лъШ , тфлтмлв. јл футъувмлл тфлтмлfl оfl нку,,у ъвЧу,млfl Ri н лмщуп^луммупы уЧпвмы (i = 1..NR) ,Р~лтоflвътfl бм~вмлв viol(Ri) - пнтлпоШмув мы?вмлв ъвЧу,млfl Ri. ѕнтлпып Чввътfl фу пмуквтъ,ы U мв,но~вммРi , тфлтмлв Чуъ.
cur

viol(Ri) = max ok ( R i, u ) - init i , uU ,,в ok(Ri, u) - млЧуовв Чолбнув н initi бм~вмлв ъвЧу,млfl Ri, фл нуъууп мы?вмлfl ъу,,у ъвЧу,млfl Чуъуи u фл фуфРънв вв ,но~вмлfl , тфлтмлв мв фулбу?оу ЧР. з фу^вттв ЧуъР о,,улъп фомлу,млfl пуквъ ЧРъШ ,Рфуомвму мвтнуоШну мвытфв?мРi фуфРъун ,но~вмлfl , тфлтмлв ЧуъР u, нуъуРп тууъ,вътъ,ыъ бмРв бм~вмлfl ok(Ri, u); лб млi ънкв ,РЧлвътfl пнтлпоШмув. з фл,ввммуи млкв тiвпв фу^выР chjsse_changes ,лтъл~втнли ,РЧу лбпвмflвпу,,у ъвЧу,млfl ,Рфуомflвътfl м ?,,в 3. з [13] ттпуъвмР ы,,лв ,лмъР ,лтълн оfl ,РЧу лбпвмflвпу,,у ъвЧу,млfl. ?нтфвлпвмъоШмув лттову,млв м ммРi фу воШмуи зћњз фунбоу, ~ъу о,,улъп м утму,в фво,,впуи ,лтълнл фв,утiулъ ъл ,лмъР фу бм~вмл плмлплблывпу,,у нлъвлfl.

зубпукмутъШ мвытфв?му,,у б,в?вмлfl ЧуъР о,,улъп т,flбм т ъвп, ~ъу: пмуквтъ,у P пуквъ мв тувкъШ ту,пвтълпу,,у мЧу бм~вмли ъвЧу,мли; , тоы~в тывтъ,у,млfl , P ту,пвтълпу,,у мЧу бм~вмли ъвЧу,мли о,,улъп пуквъ в,,у мв уЧмыклъШ , т,flбл т мвфуомуъуи уЧiу P. ѕлмлплблывпРи нлъвли: Cost (X) ќтоу,лfl б,в?вмлfl. до,,улъп б,в?вътfl фл ,Рфуомвмлл iуъfl ЧР уму,,у лб товылi ытоу,ли: мивм ту,пвтълпРи мЧу бм~вмли ъвЧу,мли (ытфв?мув б,в?вмлв); , iув фултн в?вмлfl утъл,,мыъ мЧу бм~вмли ъвЧу,мли LIM. цтол утъл,,мыъ мЧу LIM л ум fl,оflвътfl ту,пвтълпРп, ъу о,,улъп б,в?вътfl ытфв?му.

№ёзцћ§№? њдї. §цљњ№? № ћ№ћ§цѕ? ќјњдзѓцї№? < 6 2007

дѓйљњ№§ѕ? ўљњѕ№њљздї№? њцєљѕцїсдх№ђ јњ№ јѓдї№њљздї№№

81

ћiвп фу^выР chjsse_changes товыfl: 1) тщуплу,ъШ пмуквтъ,у CAND ъвЧу,млинмлъу, м лбпвмвмлв, ,но~л, , CAND ъвЧу,млfl Ri, лбпвмвмлв нуъуРв уфытълпу л ,убпукму оШмви?вв утоЧовмлв (ъ.в. x i limi); 2) втол CAND = [, б,в?лъШ фу^выы мвытфв?му; 3) ,РЧъШ оfl лбпвмвмлfl ъвЧу,млв Ri лб CAND, лпввв млпвмШ?вв фу CAND уъол~мув уъ мыоfl бм~вмлв viol(Ri)*creli/|limi - initi| ; втол оfl ,твi ъвЧу,мли лб CAND ънув бм~вмлв ,му 0, ,РЧъШ оfl лбпвмвмлfl ъвЧу,млв Ri, лпввв млпвмШ?вв бм~вмлв ,вту,у,,у нущщл^лвмъ creli (ънуи ,РЧу пуквъ ЧРъШ твом, мфлпв, втол фл футъувмлл тфлтмлfl ЧРол мы?вмР ъуоШну ъв ъвЧу,млfl, лбпвмвмлв нуъуРi мв бcur в?вму лол оfl нуъуРi x i = limi); 4) ,Р~лтолъШ лбпвмвмлв оfl бм~вмлfl ,РЧмму,,у ъвЧу,млfl Ri фу щупыов incr i = min ( lim i - x
cur i cur

, d cos t * lim i - init i / crel i ) ;

5) втол Ri уфытнвъ ъуоШну ^воу~лтовммРв бм~вмлfl, уны,,олъШ incri ,,вi; 6) б,в?лъШ фу^выы ытфв?му. љЧутму,млв б,в?лпутъл о,,улъп. ју^вы chjsse_chnges фл нкуп ,Рбу,в ытъм,ол,въ оfl ,РЧмму,,у ъвЧу,млfl лбпвмвмлв мв пвмШ?вв, ~вп dcoct*|limi - initi|/creli. №тно~вмлв тутъ,оflвъ лбпвмвмлв, у,уflвв бм~вмлв Ri у limi. єкув лбпвмвмлв ъвЧу,млfl Ri флЧолквъ в,,у бм~вмлв н limi, футов утълквмлfl нуъуу,,у оШмви?вв лбпвмвмлв ъвЧу,млfl Ri мв фулб,улътfl. ћову,ъвоШму, о,,улъп б,в?лътfl мв Чуовв ~вп б

i = 1.. NR

crel i ------------- лъв^ли. d cos t

3.2. д о,,улъп т футову,ъвоШмРп тыквмлвп уЧотъл фултн. јытъШ бм мвнуъуРи ту,пвтълпРи мЧу бм~вмли ъвЧу,мли н лмщуп^луммупы уЧпвмы, овклi , лфбумi уфытълпу,,у лбпвмвмлfl. ?ъуъ мЧу пуквъ ЧРъШ овнлп уъ уфълпоШму,,у фу нлъвл плмлпоШмутъл Cost(X) - мфлпв мЧу LIM*. јытъШ C - мвнуъуfl нумтъмъ. з,ввп уЧубм~вмлв оfl пмуквтъ, мЧуу, бм~вмли ъвЧу,мли, м нуъуРi Cost(X) пвмШ?в ћ: P(C) = = {Y P|Cost(Y) < C}. јл,ввммРи , ммуп бвов о,,улъп фуоы~въ , н~втъ,в м~оШму,,у флЧолквмлfl ту,пвтълпРи мЧу бм~вмли ъвЧу,мли л ,Рфуомflвъ лъвъл,мРи фввiу н ту,пвтълпРп мЧуп, лпвлп пвмШ?лв бм~вмлfl Cost(X). ї нкуи i-и лъв^лл о,,улъп фу,улъ фултн ту,пвтълпу,,у мЧу бм~вмли ъвЧу,мли Xi м пмуквтъ,в P(Ci), ,,в Ci - нумтъмъ, щлнтлу,м-

мfl оfl ъвныви лъв^лл. їиfl Xi, о,,улъп фууоквъ тыквмлв уЧотъл фултн, лтфуоШбыfl м (i + 1)-и лъв^лл , н~втъ,в Ci+1 бм~вмлв Cost(Xi), пвмШ?вв, ~вп Ci. зiумРв ммРв: ,iумРв ммРв б~л щуплу,млfl внупвм^ли (тп. б. 2.1); dcost - плмлпоШму уфытълпув лбпвмвмлв Cost(X) м нкуи лъв^лл о,,улъп; м~оШмув флЧолквмлв - ту,пвтълпРи мЧу ъвЧу,мли Xsrc; Nest - ~лтоу мЧуу,-нмлъу,, уЧЧъР,впРi м нкуи лъв^лл. зРiумРв ммРв. їЧу ,РiумРi ммРi о,,улъп ,но~въ ту,пвтълпРи мЧу бм~вмли ъвЧу,мли Xres : Xres P CompA (Xres FIX). до,,улъп ,тв,, б,в?вътfl ытфв?му, фуъупы флбмн ытфв?мутъл б,в?вмлfl , тутъ, ,РiумРi ммРi мв ,iулъ. ѕлмлплблывпРи нлъвли: Cost(X). ќтоу,лfl б,в?вмлfl. до,,улъп б,в?вътfl, втол м у~ввмуи i-и лъв^лл мв ыоутШ фуоы~лъШ ту,пвтълпРи мЧу Xi, оfl нуъуу,,у ,Рфуомвму ытоу,лв (Cost(Xi - 1) - Cost(Xi) dcost). љтму,муи ^лно о,,улъп. з,ввп уЧубм~вмлfl: i - мупв лъв^лл о,,улъп; Ci - фуоуклъвоШмfl нумтъмъ, м i-и лъв^лл уфввоflfl пмуквтъ,у фултн в?вмли P(Ci); find_estimates(C, N) - фу^вы, фуоы~fl N бол~мРi мЧуу, ъвЧу,мли лб пмуквтъ, P(C); refin_compatible(X) - фу^вы мф,овмму,,у фултн, фвв,уflfl бммРи ту,пвтълпРи мЧу бм~вмли ъвЧу,мли X , ы,,уи ту,пвтълпРи мЧу Y ту бм~вмлвп Cost(Y), пвмШ?лп, ~вп Cost(X); find_compatible(X, C) - фу^вы мф,овмму,,у фултн, фвв,уflfl бммРи мвту,пвтълпРи мЧу бм~вмли ъвЧу,мли X , ту,пвтълпРи мЧу Y ту бм~вмлвп Cost(Y), мв фв,Р?лп C. совв фл,ввмР утму,мРв флм^лфР ЧуъР ълi фу^вы. ћiвп утму,му,,у ^лно о,,улъп товыfl: 1) ,РфуомлъШ лмл^лолб^л: X0 := := refine_comhatible(Xsrc); i := 1 2) у,,мл~лъШ уЧотъШ фултн в?вмли: Ci := := Cost(Xi - 1); 3) фуоы~лъШ пмуквтъ,у мЧуу,-нмлъу,: SETi := find_estimates(Ci, Nest); 4) ,РволъШ , пмуквтъ,в SETi фупмуквтъ, ту,пвтълпРi мЧуу, COMP_SETi л мвту,пвтълпРi мЧуу, INCOMP_SETi; 5) фуоы~лъШ пмуквтъ,у ту,пвтълпРi мЧуу, i COMP_ SET ref , ,Рфуомл, оfl нку,,у овпвмъ X COMP_SETi фу^выы refine_comhatible(X);

6 №ёзцћ§№? њдї. §цљњ№? № ћ№ћ§цѕ? ќјњдзѓцї№? < 6 2007

82

ео?у,

6) тщуплу,ъШ пмуквтъ,у ту,пвтълпРi мi Чуу, COMP_ SET fnd , ,Рфуомл, оfl нку,,у овпвмъ X INCOMP_SETi фу^выы i - dcost); find_comhatible(X, C 7) втол пмуквтъ,у RESi = COMP_ SET COMP_ SET Чуъы;
i ref i fnd

фытъув, ъу Xres := Xi-1; б,в?лъШ
i fnd

8) ,РЧъШ лб пмуквтъ, COMP_ SET
i ref

COMP_ SET , мЧу Xi т плмлпоШмРп бм~вмлвп щымн^лл Cost; 9) втол (Cost(Xi - 1) - Cost(Xi) < dcost), ъу Xres := := Xi - 1; б,в?лъШ Чуъы; 10) фввиъл н ?,,ы 2. ју^вы find_tstimates(C, N) ,Рфуомflвъ фултн N бол~мРi мЧуу, бм~вмли ъвЧу,мли м пмуквтъ,в P(C). з пнi фво,,впу,,у о,,улъп фомлывътfl флпвмflъШ , бол~мРi вв ,лмъ: 1) м утму,в тоы~иму,,у фултн т ,мупвмРп тфввовмлвп; 2) м утму,в тiвпР лплъ^лл уъкл,, [14]. з пнi ,лмъ 2 , н~втъ,в плмлплблывпуи ^вов,уи щымн^лл ,Ртъыфвъ ~лтоу Чуъ, мв ,но~вммРi , тфлтмлв, нуъуув футъувму фу ъвнывпы мЧуы бм~вмли ъвЧу,мли. §нуи ,РЧу ^вов,уи щымн^лл фуб,уоflвъ оfl ммуи фу^выР у,,мл~лъШтfl умлп уфълплблывпРп нлъвлвп (,ъуРп пу,,о ЧР ЧРъШ щымн^лfl Cost), ънкв уЧвтфв~лъШ тiулпутъШ фултн н ту,пвтълпРп мЧуп, м нуъуРi ^вов,fl щымн^лfl ,м мыо. з тоы~в, втол фу^выуи Чыыъ мивмР ту,пвтълпРв мЧуР, ыоы~?вмлв бм~вмлfl Cost м млi фу т,мвмл т C утъл,,вътfl б т~въ ,Рфуомвмлfl фултн м пмуквтъ,в P(C). ју^вы refine_compatible(X)утывтъ,оflвъ мф,овммРи фултн ту,пвтълпу,,у мЧу Y м пмуквтъ,в P(Cx) (,,в Cx = Cost(X)) т м~оШмРп ту,пвтълпРп флЧолквмлвп, ,мРп X. з футъви?вп ,лмъв фу^выР фултн ,ввътfl фу?,,у,у , мф,овмлл млтнуви?в,,у ыЧР,млfl Cost у фуоы~вмлfl мвту,пвтълпу,,у мЧу лол у утълквмлfl ,,мл^Р P; , н~втъ,в ,Рiуму,,у мЧу Y Чввътfl мЧу, фуоы~вммРи м фвфутовмвп ?,,в фултн. з тоы~в мвытфв?му,,у фултн фу^вы ,уб,въ мЧу X. д,ъууп ЧуъР фвоуквм fl т?лвмли ынбммуи ,Р?в тiвпР мф,овмму,,у фултн [13]. з фу^выв пуквъ ЧРъШ ънкв флпвмвм о,,улъп т ,лтъл~втнлп ,РЧууп ытлол,впу,,у ъвЧу,млfl, фвоуквммРи , [13].

ју^вы find_covpatible(X, C) волбывъ фултн ту,пвтълпу,,у мЧу Y м пмуквтъ,в P(C) т м~оШмРп мвту,пвтълпРп флЧолквмлвп, ,мРп X. љм Чуъвъ фу о,,улъпы т ,лтъл~втнлп ,РЧууп утоЧоflвпу,,у ъвЧу,млfl (уфлтм , б. 3.1) ту товылпл пулщлн^лflпл: 1) , н~втъ,в м~оШму,,у флЧолквмлfl Чввътfl мв мЧу INIT, мЧу X; 2) ,,улътfl уфуомлъвоШмув ытоу,лв б,в?вмлfl: втол , iув фултн в?вмлfl утъл,,мыъ мЧу ту бм~вмлвп Cost, фв,Р?лп C, фу^вы б,в?вътfl мвытфв?му. љЧутму,млв б,в?лпутъл о,,улъп. до,,улъп fl,оflвътfl б,в?лпРп, ~ъу товывъ лб тф,вол,утъл товылi ыъ,вквмли: 1) ~лтоу лъв^ли о,,улъп мв фв,Р?въ Cost(LIM)/dcost, футнуоШны Cost(INIT) = 0, оfl фввiу н нкуи у~ввмуи лъв^лл о,,улъп уокму ЧРъШ ,Рфуомвму ытоу,лв (Cost(Xi - 1) - - Cost(Xi) dcost); 2) м нкуи лъв^лл ,Рфуомflвътfl улм ,Рбу, фу^выР find_estimates л мв Чуовв Nest ,Рбу,у, фу^вы refin_compatible л find_cjmpatible; 3) нкfl лб ,РбР,впРi фу^вы fl,оflвътfl б,в?лпуи (уЧутму,млв ъу,,у т,уитъ, ,Рiулъ б пнл ммуи тъъШл). 4. ?нтфвлпвмъоШмув лттову,млв о,,улъп щуплу,млfl внупвм^ли. јл,ввп вбыоШъъР нтфвлпвмъоШму,,у лттову,млfl о,,улъп т ,лтъл~втнлп ,РЧууп утоЧоflвпу,,у ъвЧу,млfl, уфлтмму,,у , б. 3.1. №ттову,млв фу,улоутШ м мЧув тууЧвмли, фвмбм~вммуп оfl фвв~л фу нмоы ѕє№љ2 [1] , тутъ,в воШмуи Чуъу,уи зћњз. солм лмъв,о фомлу,млfl Lint ЧРо ,РЧм ,муи 1 000 000 пнт (1 т), футнуоШны плмлпоШмfl ~тъуъ тууЧвмли лб мЧу ,м 1 й^. љтму,мРв iнъвлтълнл мЧу тууЧвмли товылв: нуол~втъ,у тууЧвмли: 160; ~тъуъР тууЧвмли (й^): 1, 2, 5, 10; нуол~втъ,у Чуъ (лтiуfl лб Lint = 1 000 000 пнт): 650; б,,ыбн нмо (уъму?вмлв тыппмуи олъвоШмутъл Чуъ н олмв лмъв,о фомлу,млfl): 0.33. §вiмуоу,,л~втнлв у,,мл~вмлfl м тфлтмлв тууъ,вътъ,у,ол ынбммРп , б. 1.2. еРол бщлнтлу,мР бм~вмлfl товылi ъвЧу,мли н лмщуп^луммупы уЧпвмы: олм фу^лно: 2000 пнт;
2

§нъ нмо ѕє№љ лпввъ олъвоШмутъШ 1 пнт.

№ёзцћ§№? њдї. §цљњ№? № ћ№ћ§цѕ? ќјњдзѓцї№? < 6 2007

дѓйљњ№§ѕ? ўљњѕ№њљздї№? њцєљѕцїсдх№ђ јњ№ јѓдї№њљздї№№ §Чол^ 1. ём~вмлfl лбпвмflвпРi ъвЧу,мли н лмщуп^луммупы уЧпвмы §вЧу,млв, Ri RF MPE MCC ї~оШмув бм~вмлв, initi 0.5 0.01 1 ймл~мув бм~вмлв, limi 0 1 15

83

^лл Cost) в?вмлв Xopt б~л щуплу,млfl внупвм^ли. ју вбыоШъъп нку,,у нтфвлпвмъ ЧРо ,Р~лтовм бмутъШ бм~вмли ^вов,уи щымн^лл Cost м уфълпоШмуп в?вмлл Xopt л в?вмлл Xres, фуоы~вммуп уъ лттовывпу,,у о,,улъп. њвбыоШъъР нтфвлпвмъу, фл,ввмР , ъЧо. 2. єытл,уп ,РвовмР бм~вмлfl ъвЧу,мли лб Xres, уъол~мРв уъ бм~вмли лб Xopt. њвбыоШъъР фу,ввммРi нтфвлпвмъу, фунбР,ъ, ~ъу м ,РЧммуп флпвв уъноумвмлв бм~вмлfl ^вов,уи щымн^лл м вбыоШъъв ЧуъР о,,улъп уъ уфълпоШму,,у бм~вмлfl ^вов,уи щымн^лл мв фв,Р?въ 2% уъ уфълпоШму,,у бм~вмлfl. јл ъуп оfl лбпвмflвпу,,у ъвЧу,млfl т пнтлпоШмРп ,вту,Рп нущщл^лвмъуп о,,улъп ,Рвъ бм~вмлв, ту,фвв ту бм~вмлвп лб уфълпоШму,,у в?вмлfl. ївуЧiулпу уъпвълъШ, ~ъу , нтфвлпвмъв < 3 ,Р~лтовммув о,,улъпуп бм~вмлв MPE , 2 б уъол~вътfl уъ уфълпоШму,,у. ?ъу ,,у,улъ у ^вовтууЧбмутъл флпвмвмлfl н фуоы~вммупы в?вмл фу^выР, ,Рфуомflви ытловмлв уъвоШмРi лбол?мв утоЧовммРi ъвЧу,мли. ?ъу пуквъ ЧРъШ, мфлпв, фу^вы refine_compatible, уфлтммfl , б. 3.2. јл лттову,млл о,,улъп м лтныттъ,вмму тщуплу,ммРi мЧуi тууЧвмли (, ~тъмутъл, фл,ввммРi , [13]) ЧРоу ,Рfl,овму уъноумвмлв уъ уфълпоШму,,у в?вмлfl у 10% фу бм~вмл ^вов,уи щымн^лл Cost. јл ы,вол~вмлл ~лто лбпвмflвпРi ъвiмуоу,,л~втнлi у,,мл~вмли уъноумвмлв тъоу утъл,,ъШ 15-20%. ?ъу фуб,уоflвъ твоъШ ,Р,у у мвуЧiулпутъл флпвмвмлfl о,,улъпу,, ,Рфуомflлi футову,ъвоШмув ыпвмШ?вмлв бм~вмлfl ^вов,уи щымн^лл м ъвнывп флЧолквмлл, ънлi, нн фвоуквммРи , б. 3.2 о,,улъп т футову,ъвоШмРп тыквмлвп уЧотъл фултн. з н~втъ,в м~оШму,,у флЧолквмлfl оfl ънлi о,,улъпу, пу-

пнтлпоШмfl олъвоШмутъШ ^вфу~нл Чуъ: 2000 пнт; ~тъуъР л олъвоШмутъл тууЧвмли. ём~вмлfl товылi ъвЧу,мли ЧРоу уфытълпу лбпвмflъШ: 1) бвбв,лу,ммfl уоfl олмР фу^лно (уЧубм~вмлв: RF, уъ reserved fraction); 2) пнтлпоШму уфытълпув уъноумвмлв ттъуflмлfl пвкы Чуъпл уму,,у л ъу,,у кв тууЧвмлfl уъ фвлу ъу,,у тууЧвмлfl (уЧубм~вмлв: MPE, уъ maximum period error); 3) пнтлпоШму уфытълпув ~лтоу Чуъ , ^вфу~нв Чуъ (уЧубм~вмлв: MCJ, уъ maximum [number of] chained jobs). ї~оШмРв (мвту,пвтълпРв) бм~вмлfl ъвЧу,мли 1)-3) л ,,мл^Р лбпвмвмли ълi ъвЧу,мли ЧРол ,РЧмР тууъ,вътъ,вмму ъЧо. 1 ън, ~ъуЧР бм~вмлfl ъвЧу,мли лб мЧу LIM ЧРол ту,пвтълпРпл, бм~вмлfl лб мЧу INIT - мвту,пвтълпРпл. јпвъ dcost о,,улъп ЧРо флмflъ ,мРп 0.1. еРол фу,ввмР нтфвлпвмъР т бол~мРпл мЧупл ,вту,Рi нущщл^лвмъу, creli (тп. б. 2.1). соfl нку,,у мЧу нущщл^лвмъу, пвъууп фуому,,у фввЧу уфввоflоутШ уфълпоШмув (т плмлпоШмРп бм~вмлвп ^вов,уи щымн§Чол^ 2. њвбыоШъъР нтфвлпвмъу, їупв нтфвлпвмъ 1 RF MPE MCC 2 RF MPE MCC 3 RF MPE MCC Ri CRELi 10 10 10 10 100 1 10 1 100 x
res i

x

opt i

Cost(Xres) - Cost(Xopt) 0

Cost(Xopt) 5.63

0.33 0.09 3 0.33 0.08 11 0.31 0.31 2

0.33 0.09 3 0.33 0.08 10 0.31 0.15 2

0.07

11.11

0.16

11.08

№ёзцћ§№? њдї. §цљњ№? № ћ№ћ§цѕ? ќјњдзѓцї№? < 6 2007

6*

84

ео?у, 5. ?лтъуолму, ѕ.з. ѕвъуР л твтъ, щымн^лумоШму,,у ъвтълу,млfl ехзѕ-№зћ // §. ,ъууи зтвуттлитн. мы~м. нумщ. "ѕвъуР л твтъ, уЧЧуънл лмщуп^лл". ѕ.: №бъвоШтнли уъво щныоШъвъ ,Р~лтолъвоШмуи пъвпълнл л нлЧвмвълнл ѕйќ, 2005. ћ. 442-448. 6. ѕлмы ѕ. ѕъвпъл~втнув фу,,пплу,млв. §вулfl л о,,улъпР. ѕ.: їын, 1990. 7. ео?у, з.з. јувкн флмflълfl в?вмли фл футъувмлл ^лноу,,ппР уЧпвму, фу пыоШълфовнтмупы нмоы // §. ,ъууи зтвуттлитн. мы~м. нумщ. "ѕвъуР л твтъ, уЧЧуънл лмщуп^лл". ѕ.: №бъвоШтнли уъво щныоШъвъ ,Р~лтолъвоШмуи пъвпълнл л нлЧвмвълнл ѕйќ, 2005. ћ. 508-515. 8. Bate I.J. Scheduling and Timing Analysis for Safety Critical Real-Time Systems // Department of Computer Science. University of York, 1999. 9. №бпиоу, д.ў., ћуоуу, ѕ.з. ?лтовммРв пвъуР уфълплб^лл. ѕ.: ўлбпъолъ, 2005. 10. Stewart D.B., Arora G. A Tool for Analyzing and Fine Tuning the Real-Time Properties of an Embedded System // IEEE Trans. on Software Engineering. Issue 4. 2003. V. 29. 11. Park J., Ryu M., Hong S. et al. Rapid performance re-engineering of distributed embedded systems via latency analysis and k-level diagonal search // J. of Parallel and Distributed Computing. Issue 1. 2006. V. 66. 12. Pop T., Eles P., Peng Z. Schedulability Analysis for Distributed Heterogeneous Time / Event Triggered RealTime Systems // Proc. 15th Euromicro Conf. on RealTime Systems. Porto, Portugal, 2003. 13. ео?у, з.з. ўуплу,млв внупвм^ли фу лбпвмвмл ъвЧу,мли н лмщуп^луммупы уЧпвмы фл мв,убпукмутъл футъувмлfl ^лноу,,ппР уЧпвму, фу пыоШълфовнтмупы нмоы // §. §въШви пвкым. нумщ. "јоовоШмРв ,Р~лтовмлfl л б~л ыф,овмлfl" (њдћљ'2006). ѕ.: №јќ лп. з.д.§фвбмлну, њдї. 2006. ћ. 422-437. 14. єо?млну, д.з., єутъвмну з.д., ѕнлм ѕ.№. ћвтъ, нумтъылу,млfl лъв^луммРi о,,улъпу, оfl в?вмлfl б~ нупЧлмъумуи уфълплб^лл // №тныттъ,вммРи лмъвоовнъ. 2004. < 2. ћ. 91-95.

квъ ,РтъыфъШ в?вмлв, фуоы~вммув о,,улъпуп т ,лтъл~втнлп ,РЧууп утоЧоflвпу,,у ъвЧу,млfl. ёно~вмлв. јвоуквмР о,,улъпР щуплу,млfl внупвм^ли фу лбпвмвмл мвту,пвтълпРi ъвЧу,мли н лмщуп^луммупы уЧпвмы фу нмоы т ^вмъолбу,ммРп ыф,овмлвп оfl уЧвтфв~вмлfl лi ту,пвтълпутъл. јл,ввмР вбыоШъъР нтфвлпвмъоШму,,у лттову,млfl уму,,у лб о,,улъпу, м ммРi фу воШмуи зћњз. №ттову,млв фунбоу ,Ртуны щщвнъл,мутъШ о,,улъп фу нлъвл плмлпоШму,,у тыппму,,у лбпвмвмлfl бм~вмли лтiумРi ъвЧу,мли. до,,улъп т ,лтъл~втнлп ,РЧууп лбпвмflвпу,,у ъвЧу,млfl флпвмflвътfl , тутъ,в лмтъыпвмъоШмуи тлтъвпР ,ъупъл~втну,,у фомлу,млfl лмщуп^лумму,,у уЧпвм фу нмоы т ^вмъолбу,ммРп ыф,овмлвп [3, 4], лтфуоШбывпуи , фупР?овммутъл фл фувнълу,млл Чуъу,Рi зћњз оfl ,л^луммРi л путнлi нупфовнту,. ћфлтун олъвъыР
1. йутытъ,вммРи тъмъ њў "№мъвщвит п,,лтъоШмРи футову,ъвоШмРи тлтъвпР овнъуммРи пуыови" йљћ§ њ 52070-2003. 2. єутъвмну з.д., йыШflму, ц.ћ. до,,улъп футъувмлfl тфлтмли уЧпвму, фу ?лмв т ^вмъолбу,ммРп ыф,овмлвп л лттову,млв в,,у щщвнъл,мутъл // ју,,пплу,млв. 2005. < 6. ћ. 340-346. 3. ео?у, з.з., з,лму, ћ.з., йыШflму, ц.ћ. л . ћлтъвп ,ъупъл~втну,,у футъувмлfl ^лноу,,ппР уЧпвму, фу ?лмв т ^вмъолбу,ммРп ыф,овмлвп // §. ,ъууи зтвуттлитн. мы~м. нумщ. "ѕвъуР л твтъ, уЧЧуънл лмщуп^лл". ѕ.: №бъвоШтнли уъво щныоШъвъ ,Р~лтолъвоШмуи пъвпълнл л нлЧвмвълнл ѕйќ, 2005. ћ. 516-521. 4. Balashov V.V., Kostenko V.A., Smeliansky R.L. et al. A Tool System for Automatic Scheduling of Data Exchange in Real-Time Distributed Embedded Systems // Proc. Seventh IEEE Internat. Sympos. on Computer Networks (ISCN'06). Istanbul, Turkey, 2006.

№ёзцћ§№? њдї. §цљњ№? № ћ№ћ§цѕ? ќјњдзѓцї№? < 6 2007