4ᨭᕝ࠿ࡽࡢᅵ◁౪⤥࡟ᑐࡍࡿᮏᕝࡢᛂ⟅        ᰴᘧ఍♫ࢽ࣮ࣗࢪ࢙ࢵࢡ㸸‫ۑ‬ᰩ⏣ᫀ༤ࠊ኱ᮏ㞝஧ࠊ஝ ဴஓࠊ୕ᾆಙ୍ࠊỤ㢌㐍἞ዉⰋ┴㧗⏣ᅵᮌ஦ົᡤᕤົㄢ㸸▼ᕝ ᝅࠊዉⰋ┴ᅵᮌ㒊㸸኱ගᘯဴࡣࡌࡵ࡟ᨭᕝ࠿ࡽࡢᅵ◁౪⤥࡟ᑐࡍࡿᮏᕝࡢ࢖ࣥࣃࢡࢺࡣ

QoldQbr (1 Qm / Qbr )          㸦㸧ᨭᕝ࠿ࡽࡢᅵ◁౪⤥ࡀ␗ᖖ࡟ቑຍࡋࡓሙྜ࠶ࡿ࠸

ࡇࡇ࡟ Qold 㸸0ROG ࡢὶ㔞 Qbr 㸸ᨭᕝࡢὶ㔞 Qm 㸸ࡣ↓ࡃ࡞ࡿࡼ࠺࡞᮲௳ୗ࡛㢧ⴭ࡟࡞ࡿࡤ࠿ࡾ࡛࡞ࡃ

ᮏᕝࢲ࣒ᆅⅬࡢὶ㔞ࠋὶ㔞ẚࢆὶᇦ㠃✚ẚ࡛⾲ࡋ᭦ᮏᕝ࡟࠾ࡅࡿὥỈὶ㔞ࡀᛴῶࡍࡿࡼ࠺࡞ሙྜ࡟ࡶ㢧࡟ᘧ㸦㸧ࢆ༢఩ᖜὶ㔞࡟ኚ᥮ࡍࡿ࡜

ⴭ࡟⌧ࢀࡿࠋࡇࡢ✀ࡢ࢖ࣥࣃࢡࢺࡣ┤᥋ⓗ࡟ࡣἙᗋኚືࡸἙᗋᮦᩱࡢኚ໬ࡢࡼ࠺࡞ᙧ࡛⌧ࢀࡿࠋ≉࡟ᮏq old[(1 Am / Abr ) / Bm ]Qbr     㸦㸧ᕝࡢὥỈὶ㔞ࡀᛴῶࡍࡿࡼ࠺࡞ሙྜ࡟ࡣᨭᕝ࠿ࡽࡇࡇ࡟ Am 㸸ࢲ࣒ᆅⅬࡢὶᇦ㠃✚ Abr 㸸ᨭᕝࡢὶᇦࡢᅵ◁౪⤥ࡀ⥆ࡃ㝈ࡾ୰ᑠὥỈ࡛࠶ࡗ࡚ࡶᮏᕝࡢ㠃✚ Bm 㸸0ROG ࠶ࡿ࠸ࡣ 0QHZ ࡢᕝᖜࠋᘧ㸦㸧ࡣࢲἙᗋୖ᪼ࡸἙᗋᮦᩱࡢኚ໬ࡀ㢧ⴭ࡟㉳ࡇࡿࡣࡎ࡛࠶࣒ᘓタᚋ࡟࠾࠸࡚ࡣ Amࡿࠋࡇࡢࡼ࠺࡞⌧㇟ࡀᅵ◁ฎ⌮ィ⏬࡟࠾ࡅࡿ㘽࡜࡞ࡿࡼ࠺࡞ὶᇦࡀᏑᅾࡋ࡚࠸ࡿࠋᮏ◊✲ࡣࡇࡢࡼ࠺࡞ὶᇦࡢᅵ◁ฎ⌮ィ⏬࡟㛵ࡍࡿ᝟ሗࢆᚓࡿࡇ࡜ࢆ┠ⓗ࡜ࡋ࡚⾜ࡗ࡚࠸ࡿࡶࡢ࡛࠶

q new0 ࡛࠶ࡿ࠿ࡽ

Qbr / Bm             㸦㸧༢఩ᖜὶ◁㔞࡜ࡋ࡚ qb ~ࡢࡶࡢࢆ᥇⏝ࡍࡿ࡜

ࡗ࡚ࡇࡇ࡛ࡣࡑࡢ୍⎔࡜ࡋ࡚ዉⰋ┴໭ᒣᕝ࡜ࡑࡢᨭᕝụ㒓ᕝࢆᑐ㇟࡜ࡋ࡚ᮏᕝ࡟ᑐࡍࡿụ㒓ᕝ࠿

q b ~ sgd 3~ sgd 3ࡽࡢᅵ◁౪⤥ࡢᙳ㡪ࢆㄪ࡭࡚࠸ࡿࠋ
ᮏᕝὶ㔞ࡢᛴῶ࡟క࠺ᅵ◁㍺㏦≉ᛶhisdࡇࡇ࡟ q b 㸸༢఩ᖜὶ◁㔞 sᅗ㸫 ࡣ௒ᅇᑐ㇟࡜ࡋ࡚࠸ࡿἙ㐨ࡢᶍᘧᅗ࡛࠶ࡿࠋ
ࡇࡇ࡟0 ࡣᮏᕝ໭ᒣᕝ% ࡣᨭᕝụ㒓ᕝ࡛࠶ࡿࠋ
 0ROG ࡣụཎࢲ࣒ᘓタ௨๓ࡢἙ㐨࡛࠶ࡾࡑࢀࡲ࡛
ࡢὶỈ࡜ὶ◁࡟ࡼࡗ࡚ᙧᡂࡉࢀࡓἙ㐨≉ᛶࢆ᭷ࡋ࡚     㸦㸧/1㸸Ỉ୰ẚ㔜g 㸸㔜ຊຍ㏿ᗘ d 㸸⢏ᚄ h 㸸Ỉ῝ i 㸸໙㓄ࠋᘧ㸦㸧ࢆ༢఩ᖜὶ㔞ࢆ⏝࠸࡚♧ࡏࡤq b ~ sgd 3 ( sd ) n 3 / 5 i 7 / 10 q 3 / 5     㸦㸧࠸ࡓࡣࡎ࡛࠶ࡿࠋࢲ࣒ᘓタᚋὥỈࡣవỈྤࢆ㏻ࡌ࡚ᘧ㸦㸧㸦㸧㸦㸧ࡼࡾ 0ROG࡜ 0QHZ ࡟࠾ࡅࡿὶ0ROG ࡢୗὶ࡟ὶࡉࢀࡿࡼ࠺࡟࡞ࡗࡓࠋࡑࡢࡓࡵ⌧◁⬟ຊࡢẚࡣἙᗋᮦᩱࡢ⢏ᚄࡸ໙㓄ࡀኚࢃࡽ࡞࠸

ᅾ0QHZ ࡣᨭᕝ % ࠿ࡽࡢὶỈ࡜ὶ◁ࡢࡳࢆὶࡍὶ㊰࡜ࡍࢀࡤḟᘧ࡛⾲ࡉࢀࡿࠋ

࡟࡞ࡗ࡚࠸ࡿࠋࡑࡇ࡛ࡲࡎࡶ࡜ࡶ࡜ 0ROG ࡢἙ㐨≉ᛶࢆᣢࡗ࡚࠸ࡓἙ㐨ࡀᮏᕝ࠿ࡽࡢὥỈ࡜ὶ◁ࡀ೵Ṇࡉࢀࡓ⤖ᯝ࡝ࢇ࡞ኚ໬ࢆ♧ࡍࡢ࠿⡆༢࡞ゎᯒ࡟q bnew / qbold[1 /(1 Am / Abr )]3 / 5     㸦㸧

0QHZ ࡟࠾࠸࡚ࡣᨭᕝࡢὥỈ࡜ὶ◁ࡢࡳࡀ౪⤥ࡉࢀࡿࡀࡇࢀࢆ 0QHZ ࡛㍺㏦ࡍࡿࡓࡵࡢ໙㓄ࡢ᮲௳ࡣࡼࡗ࡚ㄪ࡭࡚ࡳࡿࠋᘧ㸦㸧ᘧ㸦㸧࠾ࡼࡧ Br q brMBm q bm ࡞࡝ࡢ᮲௳ࡼࡾḟᘧࡢࡼ࠺࡟࡞ࡿࠋ

i new / i br ( Bm / Bbr ) 2 (36SLOOZD\䝎䝮㻌

M

B0ROGRU0QHZᅗ㸫 ᑐ㇟Ἑ㐨ࡢᶍᘧᅗࢲ࣒ᘓタ௨๓ࡢ 0ROG ࡢὶ㔞ࡣ5) / 7      㸦㸧ࡇࡇ࡟ inew 㸸0QHZ ࡢᖹ⾮໙㓄 i br 㸸ྜὶⅬ㏆ഐࡢᨭᕝࡢ໙㓄 Br 㸸ྜὶⅬ㏆ഐࡢᨭᕝࡢᕝᖜ࡛࠶ࡿࠋ
ୖ㏙ࡢᘧ㸦㸧࠾ࡼࡧ㸦㸧ࢆ⏝࠸࡚ࢲ࣒࡟ࡼࡿὥỈὶ㔞ࡀ࢝ࢵࢺࡉࢀࡓࡇ࡜࡟ࡼࡗ࡚ᮏᕝࡢὶ◁⬟ຊࡸἙᗋ໙㓄ࡀ࡝ࡢࡼ࠺࡟࡞ࡿ࠿ぢ࡚ࡳࡿࠋィ⟬࡟ᚲせ࡞ᨭᕝụ㒓ᕝ࠾ࡼࡧᮏᕝࡢㅖ㔞ࡣḟࡢ࡜࠾ࡾ࡛

㪄㩷㪙㪄㪈㪇㪇㩷㪄࠶ࡿࠋ

i br 0.01  B br 30 㹫 Abr 㸻NP A m 354 NP
B m 150 㹫ࠋỤ㢌࣭ᐑᮏ࣭ఀ⸨ࡢὶ◁◁㔞ᘧ㸯㸧ࢆཧ
⪃࡟
5 / 2 ࡜ࡋ࡚ࡇࢀࡽࢆᘧ    ࡟௦ධࡍࡿ࡜ḟࡢࡼ࠺࡞⤖ᯝࡀᚓࡽࢀࡿࠋ

q bnew / q bold

0.022  ཬࡧ i new / ibrr

1.58 ࡇࢀࡽࡣ⌧ᅾࡢᮏᕝἙ㐨ࡢᅵ◁㍺㏦㏦⬟ຊࡀඖࡢἙ㐨ࡢ  ࣃ࣮ࢭࣥࢺ⛬ᗘ࡛࠶ࡗ࡚ᨭᕝᕝ࠿ࡽ౪⤥ࡉࢀࡿᅵ◁ࢆᖹ⾮ ≧ែ࡛㍺㏦ࡍࡿࡓࡵࡵ࡟ ࡣᨭᕝࡢ ಸࡢ໙㓄ࡀᚲせ࡛࠶ࡿࡇ࡜ࢆ♧ࡋࡋ࡚࠸ࡿࠋ஦ᐇḟ❶࡛♧ࡍࡼ࠺࡟ 0QHZ ࡟࠾࠸࡚ࡣᛴ⃭⃭࡞ᅵ◁ሁ✚ࡀ㉳ࡇࡗ࡚࠸ࡿࠋᅵ◁౪⤥࡟ᑐࡍࡿᮏᕝࡢᛂ⟅

㸦6W1R ࡣᅗ㸫 ࢆཧ↷ὶ◁◁ࡢ⢏ᗘศᕸࡣィ⟬್㸧ᅗ㸫 ึᮇἙᗋᮦᩱ࠾ࡼࡧὶ◁ࡢ⢏ᗘศᕸୖ㏙ࡢゎᯒ࡟ࡼࡗ࡚ᮏᕝࡢὶ㔞ࡀ࢝࢝ࢵࢺࡉࢀࡓ᫬ᮏᕝ࡟ᑐࡍࡿᨭᕝ࠿ࡽࡢᅵ◁౪⤥⤥ࡢᙳ㡪ࡣᮏᨭᕝࡢὶᇦ㠃✚ẚཬࡧᕝᖜẚ࡟౫Ꮡࡍࡍࡿࡶࡢࡢ࠿࡞ࡾ㢧ⴭ࡟⌧ࢀࡿࡇ࡜ࡀ♧ࡉࢀࡓࠋࡑࡑࡇ࡛ᐇ㝿ࡢὶ㔞᫬⣔ิἙ㐨≉ᛶཬࡧἙᗋᮦᩱ࡟㛵㛵ࡍࡿࢹ࣮ࢱࢆ⏝࠸࡚ΰྜ◁ࢆᑐ㇟࡜ࡋࡓ୍ḟඖࡢࡢὶ◁࣭Ἑᗋኚືࣔࢹࣝ࡟ࡼࡿࢩ࣑࣮ࣗࣞࢩࣙࣥࢆ
ࢆ⾜࠸ᨭᕝ࠿ࡽࡢᅵ◁౪⤥࡟ᑐࡍࡿᮏᕝࡢᛂ⟅ࢆㄪ࡭࡚ࡳࡿࠋ ィ⟬㡿ᇦࡣᅗ㸫 ࡟♧ࡍᮏᨭᕝࡢྜὶⅬࢆୖὶ➃࡜ࡍࡿ NP ࡢ༊㛫࡛࠶ࡿࠋἙ㐨ᙧ≧ࡣ ᖺ ᭶࠾ࡼࡧ  ᖺ  ᭶࡟ᐇ ࡉࢀ࡚࠸ࡿࠋྂ࠸᪉ࡢࢹ࣮ࢱࢆึᮇ᮲௳࡜ࡋ࡚⏝࠸ ᖺ  ᭶ࡢἙᗋ㧗ࢆண ࡋ࡚࠸ࡿࠋࡇࡢ᫬ὶ◁㔞ὶ◁ཬཬࡧἙᗋᮦᩱ
ࡢ⢏ᗘศᕸࡶண ࡋ࡚࠸ࡿࠋᅗ㸫 ࡣἙᗋᮦᩱࡢ⢏ᗘศᕸࡢึᮇ᮲௳࡛࠶ࡿࠋ        㸦౪⤥ᅵ◁ࡢ⥲㔞㸸ᤲὶ◁㸻
Pᾋ㐟◁㸻Pࠊὶฟᅵ◁ࡢ⥲㔞㸸ᤲὶ◁㸻Pᾋ㐟◁㸻
P࢛࢘ࢵࢩ࣮ࣗࣟࢻ㸻P㸧ᅗ㸫 ᨭᕝࡢᅵ◁౪⤥࡟ࡼࡿࡿᮏᕝࡢἙᗋኚືィ⟬⤖ᯝ

6W ࡢࡶࡢࡣィ⟬ୖὶ➃㏆ഐࡢࡶࡢ
ࡢ࡛6W ࡣୗὶ➃㏆ഐࡢࡶࡢ࡛࠶ࡿࠋᅗ࡟ࡣᚋ㏙ࡍࡍࡿὶ◁ࡢ⢏ᗘศᕸ࡟㛵ࡍࡿィ⟬⤖ᯝࡶ♧ࡉࢀ࡚࠸ࡿࠋ࡛࠶ࡿࠋᅗ࡟ࡣᅗ㸫 ࡣἙᗋ㧗࡟㛵ࡍࡿィ⟬⤖ᯝ࡛ィ⟬ᮇ㛫࡟࠾ࡅࡿ⥲౪⤥ᅵ◁㔞࡜ࡑࡢࡢὶฟᅵ◁㔞ࡶ♧ࡉࢀ࡚࠾ࡾᨭᕝ࠿ࡽ౪⤥ࡉࢀࡿᅵᅵ◁ࡢ࡯࡜ࢇ࡝ࡣィ⟬༊㛫࡟ሁ✚ࡋ࡚࠸ࡿࡇ࡜ࡀࢃ࠿࠿ࡿࠋࡇࡢࡇ࡜ࢆᛕ㢌࡟Ἑᗋኚືࡢ⤖ᯝࢆࡳࡿ࡜ἙἙᗋୖ᪼ࡣୖὶᇦ࡛㢧ⴭ࡟ࡳࡽࢀࡿࡀࡑࢀ௨እࡢ㡿㡿ᇦ࡛ࡣἙᗋࡣ࠶ࡲࡾື࠸࡚࠸࡞࠸ࡇ࡜ࡀࢃ࠿ࡿࠋࡇࡇࢀࡽࡢࡇ࡜ࡼ࠾ࢃࡾ࡟ ᮏᕝࡢὶ㔞ࡀᛴῶࡍࡿ࡜ࡁὶ◁࣭Ἑᗋኚື࡟ᑐࡍࡿᅵ◁౪⤥ࡢᙳ㡪ࢆ⌮ㄽⓗ࡟࡟ணࡋࡇࢀࢆᩘ್ࢩ࣑࣮ࣗࣞࢩࣙࣥ࡟ࡼࡗ࡚☜࠿࠿ࡵࡓࠋ௒ᚋᮏሗ࿌࡛♧ࡋࡓࡼ࠺࡞⡆༢࡞ゎᯒἲ࡜ᩘᩘ್ゎᯒࢆే⏝ࡍࡿࡇ࡜࡟ࡼࡗ࡚ᅵ◁ฎ⌮ィ⏬࡟ᑐᑐࡍࡿ᭷⏝࡞᝟ሗࢆ࠸࠿࡟ᚓ࡚࠸ࡃ࠿᳨ウࢆ῝ࡵࡿᡤᡤᏑ࡛࠶ࡿࠋཧ⪃ᩥ⊩⊩㸸 ୡ⣖ࡢἙᕝᏛ ❶ ⰱ⏣࣭Ụ㢌࣭୰ᕝ㸦㸧ࡾィ⟬㡿ᇦ࠿ࡽὶฟࡋ࡚࠸ࡿὶ◁ࡣἙᗋᮦᩱࡢ୰࠸ࡿࡶࡢ࡜᥎ᐹࡢᑠࡉ࠸ࡶࡢࡀ㑅ᢥⓗ࡟㍺㏦ࡉࢀ࡚࠸
ࡉࢀࡿࠋࡇࡢࡇ࡜ࢆࡳࡿࡓࡵᅗ㸫 ࡟ࡣ
ࡣ 6W ㏆ഐࡢὶ◁ࡢ⢏ᗘศᕸࢆᥖ㍕ࡋ࡚࠸ࡿࠋࡇࢀࡼࡾὶ◁ࡣἙᗋᮦᩱࡢ⣽࠿࠸ࡶࡢ࠿ࡽ࡞ࡗ࡚࠸ࡿࡇ࡜ࡀࢃ࠿ࡿࠋ㪄㩷㪙㪄㪈㪇㪈㩷㪄ி㒔኱Ꮫฟ∧఍㸬