ᠪᠠᠩᠬᠢᠷ ᠤᠨ ᠠᠯᠭᠣᠷᠢᠲ᠋ᠮ

ᠴᠢᠯᠦᠭᠡᠲᠦ ᠨᠡᠪᠲᠡᠷᠬᠡᠢ ᠲᠣᠯᠢ — ᠸᠢᠺᠢᠫᠧᠳᠢᠶ᠎ᠠ ᠠᠴᠠ
ᠬᠠᠷᠠᠶᠢᠬᠤ: ᠤᠳᠤᠷᠢᠳᠬᠤ, ᠬᠠᠶᠢᠯᠲᠠ

ᠨᠥᠭᠡᠴᠡ ᠬᠤᠪᠢᠶᠠᠷᠢᠯᠠᠬᠤ ᠭᠷᠠᠹ ᠤᠨ ᠠᠯᠭᠣᠷᠢᠲ᠋ᠮ ᠢ ᠲᠥᠷᠥᠯ ᠪᠦᠷᠢ ᠶᠢᠨ ᠨᠥᠭᠡᠴᠡ ᠶᠢᠨ ᠣᠯᠠᠨ ᠲᠣᠬᠢᠶᠠᠯᠳᠤᠯ ᠤᠳ ᠲᠠᠢ ᠨᠥᠭᠡᠴᠡ ᠬᠤᠪᠢᠶᠠᠷᠢᠯᠠᠬᠤ ᠰᠢᠰᠲ᠋ᠧᠮ ᠳᠦ ᠠᠰᠢᠭᠯᠠᠬᠤ ᠲᠡᠶᠢᠮᠦ ᠴᠤ ᠲᠣᠬᠢᠷᠠᠮᠵᠢᠲᠠᠢ ᠪᠢᠰᠢ᠃ ᠬᠠᠷᠢᠨ ᠲᠦᠭᠵᠢᠷᠡᠯ ᠡᠴᠡ ᠵᠠᠶᠢᠯᠠᠰᠬᠢᠬᠤ ᠠᠯᠭᠣᠷᠢᠲ᠋ᠮ ᠨᠢ ᠡᠶᠢᠮᠦᠷᠬᠡᠦ ᠰᠢᠰᠲ᠋ᠧᠮ ᠳᠦ ᠲᠣᠬᠢᠷᠠᠮᠵᠢᠲᠠᠢ᠃ ᠭᠡᠪᠡᠴᠦ ᠨᠥᠭᠡᠴᠡ ᠬᠤᠪᠢᠶᠠᠷᠢᠯᠠᠬᠤ ᠭᠷᠠᠹ ᠤᠨ ᠰᠢᠰᠲ᠋ᠧᠮ ᠡᠴᠡ ᠦᠷ᠎ᠡ ᠳ᠋ᠦᠩ ᠪᠠᠭ᠎ᠠ ᠲᠠᠢ ᠪᠥᠭᠡᠳ ᠡᠨᠡ ᠠᠯᠭᠣᠷᠢᠲ᠋ᠮ ᠢ ᠥᠭᠡᠷ᠎ᠡ ᠪᠡᠷ 《ᠪᠠᠩᠬᠢᠷ ᠤᠨ ᠠᠯᠭᠣᠷᠢᠲ᠋ᠮ》 ᠭᠡᠵᠦ ᠨᠡᠷᠡᠯᠡᠳᠡᠭ᠃ ᠨᠥᠭᠡᠴᠡ ᠬᠤᠪᠢᠶᠠᠷᠢᠯᠠᠬᠤ ᠪᠠᠩᠬᠢᠷ ᠤᠨ ᠠᠯᠭᠣᠷᠢᠲ᠋ᠮ ᠨᠢ ᠲᠦᠭᠵᠢᠷᠡᠯ ᠡᠴᠡ ᠵᠠᠶᠢᠯᠠᠰᠬᠢᠬᠦ ᠳᠦ ᠬᠡᠷᠡᠭᠯᠡᠭᠳᠡᠳᠡᠭ᠃ ᠡᠨᠡ ᠨᠡᠷ᠎ᠡ ᠶᠢ ᠰᠣᠩᠭᠣᠭᠰᠠᠨ ᠰᠢᠯᠲᠠᠭᠠᠨ ᠭᠡᠪᠡᠯ ᠪᠠᠩᠬᠢ ᠨᠢ ᠪᠣᠯᠤᠮᠵᠢᠲᠤ ᠪᠡᠯᠡᠨ ᠮᠥᠩᠭᠥ ᠪᠡᠷ ᠪᠦᠬᠦ ᠬᠡᠷᠡᠭᠯᠡᠭᠴᠢᠳ ᠦᠨ ᠢᠶᠡᠨ ᠱᠠᠭᠠᠷᠳᠠᠯᠭ᠎ᠠ ᠶᠢ ᠬᠠᠩᠭᠠᠵᠤ ᠴᠢᠳᠠᠳᠠᠭ ᠦᠭᠡᠢ ᠤᠴᠢᠷ ᠠᠴᠠ ᠲᠥᠰᠥᠪ ᠢ ᠬᠠᠩᠭᠠᠬᠤ ᠶᠢᠨ ᠲᠤᠯᠠᠳᠠ ᠪᠠᠩᠬᠢᠨ ᠤ ᠡᠷᠦᠯᠲᠡ ᠶᠢᠨ ᠰᠢᠰᠲ᠋ᠧᠮ ᠳᠦ ᠠᠰᠢᠭᠯᠠᠳᠠᠭ᠃ ᠰᠢᠰᠲ᠋ᠧᠮ ᠳᠦ ᠰᠢᠨ᠎ᠡ ᠶᠠᠪᠤᠴᠠ ᠣᠷᠣᠵᠤ ᠢᠷᠡᠬᠦ ᠳᠦ ᠬᠡᠷᠡᠭᠴᠡᠭᠡ ᠲᠡᠢ ᠲᠥᠷᠥᠯ ᠪᠦᠷᠢ ᠶᠢᠨ ᠨᠥᠭᠡᠴᠡ ᠶᠢᠨ ᠲᠣᠬᠢᠶᠠᠯᠳᠤᠯ ᠤᠳ ᠤᠨ ᠬᠠᠮᠤᠭ ᠤᠨ ᠶᠡᠬᠡ ᠲᠣᠭ᠎ᠠ ᠶᠢ ᠵᠠᠷᠯᠠᠬᠤ ᠶᠣᠰᠣᠲᠠᠢ᠃ ᠡᠨᠡ ᠲᠣᠭ᠎ᠠ ᠨᠢ ᠰᠢᠰᠲ᠋ᠧᠮ ᠳ᠋ᠡᠬᠢ ᠨᠥᠭᠡᠴᠡ ᠨᠦᠭᠦᠳ ᠦᠨ ᠨᠡᠶᠢᠲᠡ ᠲᠣᠭ᠎ᠠ ᠶᠢ ᠬᠡᠲᠦᠷᠡᠭᠦᠯᠬᠦ ᠦᠭᠡᠢ᠃ ᠬᠡᠷᠡᠭᠯᠡᠭᠴᠢ ᠨᠥᠭᠡᠴᠡ ᠨᠦᠭᠦᠳ ᠦᠨ ᠲᠣᠬᠢᠷᠠᠨ ᠳᠤ ᠬᠦᠰᠡᠯᠲᠦ ᠭᠠᠷᠭᠠᠬᠤ ᠳᠤ ᠰᠢᠰᠲ᠋ᠧᠮ ᠡᠳᠡᠭᠡᠷ ᠨᠥᠭᠡᠴᠡ ᠨᠦᠭᠦᠳ ᠦᠨ ᠬᠤᠪᠢᠶᠠᠷᠢᠯᠠᠯᠲᠠ ᠶᠢ ᠴᠢᠭᠯᠡᠭᠦᠯᠵᠦ ᠠᠶᠤᠯ ᠦᠭᠡᠢ ᠲᠥᠯᠥᠪ ᠲᠦ ᠰᠢᠰᠲ᠋ᠧᠮ ᠢ ᠣᠷᠬᠢᠨ᠎ᠠ᠃ ᠲᠥᠰᠥᠪ ᠲᠦ ᠨᠥᠭᠡᠴᠡᠯᠡᠭᠳᠡᠭᠰᠡᠨ ᠪᠣᠯ ᠶᠠᠪᠤᠴᠠ ᠬᠠᠩᠭᠠᠯᠲᠠ ᠲᠠᠢ ᠨᠥᠭᠡᠴᠡ ᠵᠠᠷᠢᠮ ᠶᠠᠪᠤᠴᠠ ᠠᠴᠠ ᠴᠢᠯᠦᠭᠡᠯᠡᠬᠦ ᠬᠦᠷᠲᠡᠯ᠎ᠡ ᠬᠦᠯᠢᠶᠡᠳᠡᠭ᠃

ᠬᠡᠷᠪᠡ ᠪᠡᠶᠡᠯᠡᠪᠡᠯ ᠨᠥᠭᠡᠴᠡ ᠵᠠᠷᠤᠴᠠᠭᠤᠯᠤᠭᠳᠠᠳᠠᠭ᠂ ᠡᠰᠡᠷᠬᠦ ᠲᠣᠬᠢᠶᠠᠯᠳᠤᠯ ᠳᠤ ᠶᠠᠪᠤᠴᠠ ᠥᠭᠡᠷ᠎ᠡ ᠶᠠᠪᠤᠴᠠ ᠬᠠᠩᠭᠠᠯᠲᠠ ᠲᠠᠢ ᠨᠥᠭᠡᠴᠡ ᠬᠡᠪᠯᠡᠬᠦ ᠶᠢ ᠵᠥᠪᠰᠢᠶᠡᠷᠡᠬᠦ ᠶᠢ ᠬᠦᠯᠢᠶᠡᠬᠦ ᠱᠠᠭᠠᠷᠳᠠᠯᠭ᠎ᠠ ᠲᠠᠢ᠃ ᠲᠥᠷᠥᠯ ᠪᠦᠷᠢ ᠶᠢᠨ ᠥᠭᠭᠥᠭᠳᠡᠯ ᠦᠨ ᠪᠦᠲᠦᠴᠡ ᠨᠦᠭᠦᠳ ᠪᠠᠩᠬᠢᠷ ᠤᠨ ᠠᠯᠭᠣᠷᠢᠲ᠋ᠮ ᠢ ᠬᠡᠷᠡᠭᠵᠢᠭᠦᠯᠬᠦ ᠶᠢ ᠳᠡᠮᠵᠢᠳᠡᠭ᠃ ᠡᠨᠡ ᠥᠭᠭᠥᠭᠳᠡᠯ ᠦᠨ ᠪᠦᠲᠦᠴᠡ ᠨᠦᠭᠦᠳ ᠨᠢ ᠨᠥᠭᠡᠴᠡ ᠵᠠᠷᠤᠴᠠᠭᠤᠯᠤᠯᠲᠠ ᠶᠢᠨ ᠰᠢᠰᠲ᠋ᠧᠮ ᠦᠨ ᠮᠤᠵᠢ ᠶᠢ ᠺᠣᠳ᠋ ᠍ ᠢᠶᠠᠷ ᠱᠢᠹᠷᠯᠡᠳᠡᠭ (ᠺᠣᠳᠣᠯᠳᠠᠭ). ᠰᠢᠰᠲ᠋ᠧᠮ ᠳ᠋ᠡᠬᠢ ᠶᠠᠪᠤᠴᠠ ᠤᠨ ᠲᠣᠭ᠎ᠠ ᠶᠢ n, ᠨᠥᠭᠡᠴᠡ ᠶᠢᠨ ᠲᠥᠷᠥᠯ ᠦᠨ ᠲᠣᠭ᠎ᠠ ᠶᠢ m ᠭᠡᠵᠦ ᠲᠡᠮᠳᠡᠭᠯᠡᠶ᠎ᠡ᠃

  • Available (ᠪᠣᠯᠤᠮᠵᠢᠲᠤ).᠎ᠠ ᠸᠧᠺᠲ᠋ᠣᠷ ᠤᠨ m ᠤᠷᠲᠤ ᠨᠢ ᠨᠥᠭᠡᠴᠡ ᠪᠦᠷᠢ ᠶᠢᠨ ᠪᠣᠯᠤᠮᠵᠢᠲᠤ ᠲᠣᠭ᠎ᠠ ᠶᠢ ᠢᠯᠡᠷᠬᠡᠶᠢᠯᠡᠨ᠎ᠡ᠃ ᠬᠡᠷᠪᠡ Available[j] ᠨᠢ k- ᠲᠠᠢ ᠲᠡᠩᠴᠡᠭᠦᠦ ᠦᠶ᠎ᠡ ᠳᠦ Rj –ᠳ k ᠲᠣᠬᠢᠶᠠᠯᠳᠤᠯ ᠪᠣᠯᠤᠮᠵᠢ ᠲᠠᠢ᠃
  • Max (ᠬᠠᠮᠤᠭ ᠤᠨ ᠶᠡᠬᠡ). n x m ᠮᠠᠲᠷᠢᠼ ᠶᠠᠪᠤᠴᠠ ᠢ ᠬᠠᠮᠤᠭ ᠤᠨ ᠶᠡᠬᠡ ᠬᠡᠷᠡᠭᠴᠡᠭᠡᠲᠡᠢ ᠲᠣᠳᠣᠷᠬᠠᠶᠢᠯᠠᠭᠰᠠᠨ᠃ᠬᠡᠷᠪᠡ Max[i][j] ᠲᠡᠩᠴᠡᠭᠦᠦ k ᠦᠶ᠎ᠡ ᠳᠦ P ᠶᠠᠪᠤᠴᠠ ᠬᠠᠮᠤᠭ ᠤᠨ ᠶᠡᠬᠡ ᠳᠤ ᠪᠡᠨ k ᠲᠣᠬᠢᠶᠠᠯᠳᠤᠯ ᠭᠠᠷᠭᠠᠵᠤ ᠥᠭᠳᠡᠭ᠃
  • Allocation (ᠵᠠᠷᠤᠴᠠᠭᠤᠯᠤᠯᠲᠠ). n x m ᠮᠠᠲᠷᠢᠼ ᠨᠢ ᠶᠠᠪᠤᠴᠠ ᠲᠤ ᠪᠠᠶᠢᠷᠢᠯᠠᠭᠰᠠᠨ ᠲᠤᠬᠠᠢ ᠶᠢᠨ ᠲᠥᠷᠥᠯ ᠠᠷᠭ᠎ᠠ ᠶᠢᠨ ᠲᠣᠭ᠎ᠠ ᠶᠢ ᠲᠣᠳᠣᠷᠬᠠᠶᠢᠯᠠᠳᠠᠭ᠃ ᠬᠡᠷᠪᠡ Allocation[i][j] ᠲᠡᠩᠴᠡᠭᠦᠦ k ᠦᠶ᠎ᠡ ᠳᠦ ᠶᠠᠪᠤᠴᠠ Pi ᠨᠢ Rj ᠲᠥᠷᠥᠯ ᠳᠦ k ᠲᠣᠬᠢᠶᠠᠯᠳᠤᠯ ᠭᠠᠷᠭᠠᠵᠤ ᠥᠭᠳᠡᠭ᠃
  • Need (ᠱᠠᠭᠠᠷᠳᠠᠯᠭ᠎ᠠ). n x m ᠮᠠᠲᠷᠢᠼ ᠨᠢ ᠶᠠᠪᠤᠴᠠ ᠲᠤ ᠪᠠᠶᠢᠷᠢᠯᠠᠭᠰᠠᠨ ᠲᠤᠬᠠᠢ ᠶᠢᠨ ᠲᠥᠷᠥᠯ ᠠᠷᠭ᠎ᠠ ᠶᠢᠨ ᠲᠣᠭ᠎ᠠ ᠶᠢ ᠲᠣᠳᠣᠷᠬᠠᠶᠢᠯᠠᠳᠠᠭ᠃ ᠬᠡᠷᠪᠡ Need [i][j] ᠲᠡᠩᠴᠡᠭᠦᠦ k ᠦᠶ᠎ᠡ ᠳᠦ ᠶᠠᠪᠤᠴᠠ Pi ᠨᠢ ᠪᠡᠶᠡᠯᠡᠬᠦ ᠳᠦ Rj ᠲᠥᠷᠥᠯ ᠳᠦ k ᠍ ᠠᠴᠠ ᠣᠯᠠᠨ ᠲᠣᠬᠢᠶᠠᠯᠳᠤᠯ ᠭᠠᠷᠭᠠᠵᠤ ᠥᠭᠳᠡᠭ᠃

Need [i][j] = Max[i][j] - Allocation [i][j] ᠭᠡᠳᠡᠭ ᠢ ᠠᠩᠬᠠᠷᠤᠨ᠎ᠠ ᠤᠤ᠃

ᠥᠭᠭᠥᠭᠳᠡᠯ ᠦᠨ ᠪᠦᠲᠦᠴᠡ ᠨᠢ ᠬᠡᠮᠵᠢᠶ᠎ᠡ ᠪᠣᠯᠤᠨ ᠤᠳᠬ᠎ᠠ ᠪᠠᠨ ᠥᠭᠡᠷᠡᠴᠢᠯᠡᠵᠦ ᠪᠠᠶᠢᠳᠠᠭ᠃ ᠪᠠᠩᠬᠢᠷ ᠤᠨ ᠠᠯᠭᠣᠷᠢᠲ᠋ᠮ ᠢ ᠬᠢᠯᠪᠠᠷᠬᠠᠨ ᠢᠶᠠᠷ ᠢᠯᠡᠷᠬᠡᠶᠢᠯᠡᠬᠦ ᠳᠦ ᠳᠠᠷᠠᠭᠠᠬᠢ ᠲᠡᠮᠳᠡᠭᠯᠡᠭᠡ ᠶᠢ ᠪᠠᠲᠤᠳᠬᠠᠬᠤ ᠬᠡᠷᠡᠭᠲᠡᠢ᠃ ᠬ᠂ᠦ ᠸᠧᠺᠲ᠋ᠣᠷ ᠤᠳ n ᠤᠷᠲᠤ ᠲᠠᠢ᠃ ᠬ≤ᠦ ᠬ[i] ≤ᠦ[i] i=1,2,3,…᠃n . ᠵᠢᠱᠢᠶ᠎ᠡ ᠨᠢ: ᠬᠡᠷᠪᠡ ᠬ{1,7,3,2} ᠪᠠ Y{0,3,2,1} ᠦᠶ᠎ᠡ ᠳᠦ Y≤ X , Y<X ᠬᠡᠷᠪᠡ Y≤X Y≠X ᠪᠢᠳᠡ Allocation Need ᠮᠠᠲᠷᠢᠼ ᠤᠨ ᠮᠥᠷ ᠪᠦᠷᠢ ᠳᠦ ᠸᠧᠺᠲ᠋ᠣᠷᠣᠠᠷ ᠨᠢ ᠬᠠᠨᠳᠤᠬᠤ ᠪᠣᠯᠤᠮᠵᠢ ᠲᠠᠢ ᠪᠠ Allocation, Need –ᠡ ᠳᠦ ᠬᠠᠮᠢᠶᠠᠷᠤᠭᠤᠯᠵᠤ ᠪᠣᠯᠳᠠᠭ᠃ Allocation ᠸᠧᠺᠲ᠋ᠣᠷ ᠨᠢ Pi ᠶᠠᠪᠤᠴᠠ ᠲᠤ ᠭᠠᠷᠭᠠᠵᠤ ᠥᠭᠳᠡᠭ ᠠᠷᠭ᠎ᠠ ᠶᠢ ᠲᠣᠳᠣᠷᠬᠠᠶᠢᠯᠠᠳᠠᠭ᠃ Needi ᠸᠧᠺᠲ᠋ᠣᠷ ᠨᠢ Pi ᠶᠠᠪᠤᠴᠠ ᠪᠡᠶᠡᠯᠡᠬᠦ ᠶᠢ ᠬᠦᠰᠡᠭᠰᠡᠨ ᠨᠡᠮᠡᠯᠲᠡ ᠠᠷᠭ᠎ᠠ᠃

ᠠᠶᠤᠯ ᠦᠭᠡᠢ ᠪᠠᠶᠢᠳᠠᠯ ᠤᠨ ᠠᠯᠭᠣᠷᠢᠲ᠋ᠮ[ᠵᠠᠰᠠᠪᠤᠷᠢᠯᠠᠬᠤ | ᠺᠣᠳ᠋ ᠢᠶᠠᠷ ᠵᠠᠰᠠᠬᠣ]

ᠬᠠᠶᠢᠯᠲᠠ ᠠᠴᠠ ᠭᠠᠳᠠᠭᠤᠷ ᠪᠣᠯᠤᠨ ᠦᠢᠯᠡᠳᠦᠯ ᠦᠨ ᠰᠢᠰᠲ᠋ᠧᠮ ᠨᠢ ᠠᠶᠤᠯ ᠦᠭᠡᠢ ᠮᠤᠵᠢ ᠳᠤ ᠪᠠᠶᠢᠷᠢᠯᠠᠳᠠᠭ ᠦᠭᠡᠢ ᠠᠯᠭᠣᠷᠢᠲ᠋ᠮ ᠢ ᠢᠯᠡᠷᠬᠡᠶᠢᠯᠡᠬᠦ ᠪᠣᠯᠤᠮᠵᠢ ᠲᠠᠢ᠃ ᠡᠨᠡ ᠠᠯᠭᠣᠷᠢᠲ᠋ᠮ ᠨᠢ ᠳᠠᠷᠠᠭᠠᠬᠢ ᠪᠠᠶᠢᠳᠠᠯ ᠢᠶᠠᠷ ᠲᠣᠳᠣᠷᠠᠷᠬᠠᠶᠢᠯᠠᠭᠳᠠᠨ᠎ᠠ:


ᠳᠡᠭᠡᠷᠡᠬᠢ ᠠᠯᠭᠣᠷᠢᠲ᠋ᠮ ᠨᠢ ᠠᠶᠤᠯ ᠦᠭᠡᠢ ᠮᠤᠵᠢ ᠳᠤ ᠪᠠᠶᠢᠭ᠎ᠠ ᠴᠤ ᠭᠡᠰᠡᠨ n x m ᠦᠢᠯᠡᠳᠦᠯ ᠢ ᠲᠣᠳᠣᠷᠬᠠᠶᠢᠯᠠᠬᠤ ᠳᠠᠷᠠᠭᠠᠯᠠᠯ ᠢ ᠱᠠᠭᠠᠷᠳᠠᠳᠠᠭ᠃

ᠬᠦᠰᠡᠯᠲᠡ ᠶᠢᠨ ᠠᠯᠭᠣᠷᠢᠲ᠋ᠮ[ᠵᠠᠰᠠᠪᠤᠷᠢᠯᠠᠬᠤ | ᠺᠣᠳ᠋ ᠢᠶᠠᠷ ᠵᠠᠰᠠᠬᠣ]

ᠬᠦᠰᠡᠯᠲᠡ ᠨᠢ ᠠᠶᠤᠯ ᠦᠭᠡᠢ ᠪᠡᠷ ᠣᠯᠭᠣᠭᠳᠠᠭᠰᠠᠨ ᠲᠣᠬᠢᠶᠠᠯᠳᠤᠯ ᠤᠨ ᠠᠯᠭᠣᠷᠢᠲ᠋ᠮ ᠢ ᠲᠣᠳᠣᠷᠬᠠᠶᠢᠯᠠᠶ᠎ᠠ᠃ Request; ᠨᠢ ᠷ ᠶᠠᠪᠤᠴᠠ ᠤᠨ ᠬᠦᠰᠡᠯᠲᠡ ᠶᠢᠨ ᠸᠧᠺᠲ᠋ᠣᠷ ᠭᠡᠵᠦ ᠦᠵᠡᠶ᠎ᠡ᠃ ᠬᠡᠷᠪᠡ Request;[j] == k ᠦᠶ᠎ᠡ ᠳᠦ ᠷi ᠶᠠᠪᠤᠴᠠ ᠨᠢ Ri ᠲᠥᠷᠥᠯ ᠦᠨ k ᠲᠣᠬᠢᠶᠠᠯᠳᠤᠯ ᠪᠣᠯᠤᠨ᠎ᠠ᠃ ᠶᠠᠪᠤᠴᠠ ᠷ; ᠍ ᠪᠡᠷ ᠬᠢᠭᠳᠡᠭᠰᠡᠨ ᠬᠦᠰᠡᠯᠲᠡ ᠪᠠᠶᠢᠪᠠᠯ ᠳᠠᠷᠠᠭᠠᠬᠢ ᠦᠢᠯᠡᠳᠦᠯ ᠦᠳ ᠢ ᠬᠢᠨ᠎ᠡ:

ᠪᠢᠴᠢᠭᠡᠰᠦ