Pa-20䝕䞊䝍䝬䜲䝙䞁䜾䜢⏝䛔䛯䠎䠌䠍䠍ᖺ䠕᭶䠐᪥㑣ᬛᕝὶᇦ䛻䛚䛡䜛ᅵ◁⅏ᐖⓎ⏕䛻ಀ䜟䜛㔜せせᅉ䛾ᢕᥱ㻌㻌኱つᶍᅵ◁⅏ᐖᑐ⟇◊✲ᶵᵓ㸦࿴ḷᒣ┴㸧       ‫ۑ‬ᆏཱྀṊᘯ࣭すᒸᜏᚿ࣭⟄஭࿴⏨࣭⚟⏣࿴ᑑ኱つᶍᅵ◁⅏ᐖᑐ⟇◊✲ᶵᵓ㸦ᅜ❧◊✲㛤Ⓨἲேᅵᮌ◊✲ᡤ㸧              ᮌୗ⠜ᙪ ኱つᶍᅵ◁⅏ᐖᑐ⟇◊✲ᶵᵓ㸦ᅜᅵ஺㏻┬㏆␥ᆅ᪉ᩚഛᒁ኱つᶍᅵ◁⅏ᐖᑐ⟇ᢏ⾡ࢭࣥࢱ࣮㸧⏣୰೺㈗
ओ࢚࢖ࢺ᪥ᮏᢏ⾡㛤Ⓨ                           ྈ⇃඾Ꮚ࣭ᾏཎⲮ୍⌧ ᅜᅵ஺㏻┬ᅜᅵᢏ⾡ᨻ⟇⥲ྜ◊✲ᡤ㸯㸬ࡣࡌࡵ࡟  ᖺ  ᭶ࡢྎ㢼  ྕ㸦௨ୗࠕྎ㢼  ྕࠖ࡜࠸࠺㸧࡛࿴ḷᒣ┴㑣ᬛ຾ᾆ⏫ෆࡢ㑣ᬛᕝὶᇦ࡛ࡣ㸪⥲㞵㔞 ੈ㸪᫬㛫㞵㔞  ੈࢆ㉸࠼ࡿ㝆㞵࡟ࡼࡾ㸪ከᩘࡢᅵ◁⅏ᐖࡀⓎ⏕ࡋࡓࠋᅵ◁⅏ᐖࡢⓎ⏕༴㝤ᗘࢆᢕᥱࡍࡿࡓࡵ࡟ࡣ㸪ᆅᙧࡸᆅ㉁㸪㝆㞵ᣦᶆ࡞࡝ᅵ◁⅏ᐖࡢⓎ⏕࡜㛵㐃ᛶࡢ㧗࠸⣲ᅉࡸㄏᅉࢆᢕᥱࡍࡿࡇ࡜ࡀᚲせ࡛࠶ࡿࠋ ࡑࡇ࡛㸪ᮏ◊✲࡛ࡣྎ㢼  ྕ࡟ࡼࡾ㑣ᬛᕝὶᇦ࡛Ⓨ⏕ࡋࡓᅵ◁⅏ᐖࢆᑐ㇟࡟ࢹ࣮ࢱ࣐࢖ࢽࣥࢢᡭἲࡢ㸯ࡘ࡛࠶ࡿࣛࣇ㞟ྜࢆ⏝࠸࡚㸪ᆅᙧ࣭ᆅ㉁ࡸ㝆㞵࡞࡝ᅵ◁⅏ᐖⓎ⏕࡟㛵㐃ᛶࡢ῝࠸㔜せᅉᏊࡢᢳฟࡸⓎ⏕᮲௳ཬࡧ㠀Ⓨ⏕᮲௳ࡢ᳨ウࢆ⾜ࡗࡓࠋ ㄪᰝ⟠ᡤࡢ㑣ᬛᕝὶᇦࡣὶᇦ㠃✚ NP㸪ὶ㊰ᘏ㛗ࡀ⣙ NP㸪Ἑᗋ໙㓄ࡣ ࡛࠶ࡿࠋᆅ㉁ⓗ≉ᚩ࡜ࡋ࡚ࡣ⇃㔝ᒙ⩌࡟ⰼᓵᩬᒾࡀ㈏ධࡋ࡚㸪Ἶᒾୖ࡟ᓴ㗹ࢆᙧᡂࡋࡓᆅᇦ࡛࠶ࡾ㸪ྎ㢼  ྕࡢ㞟୰㇦㞵࡟ࡼࡾ⾲ᒙᔂቯ࣭ᅵ▼ὶࡀከᩘⓎ⏕ࡋ኱つᶍ࡞⿕ᐖࡀ⏕ࡌࡓὶᇦ࡛࠶ࡿࠋ㸰㸬᳨ウ᪉ἲ㸰㸯ࣛࣇ㞟ྜࡢᴫせ ࣛࣇ㞟ྜࡣࢹ࣮ࢱ࣐࢖ࢽࣥࢢᡭἲࡢ୍ࡘ࡛࠶ࡾ㸪 ᖺ࡟࣏࣮ࣛࣥࢻࡢィ⟬ᶵᏛ⪅ =G]LVĄDZ3DZODN ࡟ࡼࡗ࡚ᥦၐࡉࢀࡓࡶࡢ  ࡛㸪ࡑࡢᇶᮏᴫᛕࡣ㢮ู࡜㏆ఝ࡛࠶ࡾ㸪ࢹ࣮ࢱ࣮࣋ࢫࡢศ㞳ᛶࢆపୗࡉࡏࡎ࡟ዴఱ࡟⡆⣙໬࡛ࡁࡿ࠿
࡜࠸࠺Ⅼ࡟୺║ࡀ⨨࠿ࢀ࡚࠸ࡿࠋࣛࣇ㞟ྜࡢ୺࡞ᶵ⬟࡜ࡋ࡚ࡣ㸪ࢹ࣮ࢱ࣮࣋ࢫࡢ⦰⣙࡜࣮ࣝࣝࡢᢳฟࡀ࠶ࡿࠋࣛࣇ㞟ྜࡢᴫᛕࢆᅗ ࡟♧ࡍࠋ౛࠼ࡤᩳ㠃໙㓄࡜ᩳ㠃㧗ࡢせᅉࢆࡑࢀࡒࢀ  ࡘࡢ࢝ࢸࢦࣜ࡟ศ๭ࡋ࡚㸪⅏ᐖࡢⓎ⏕ࡋࡓὶᇦ ‫ۑ‬༳ ࡜㠀Ⓨ⏕ࡢὶᇦ ‫ە‬༳ ࢆศ㢮ࡋࡓሙྜࢆ⪃࠼ࡿࠋ⅏ᐖࡢⓎ⏕࡜㠀Ⓨ⏕ࢆ⪃࠼ࡿࡇ࡜ࡣ㸪Ⓨ⏕ࡍࡿ⟠ᡤ࡜㠀Ⓨ⏕ࡢ⟠ᡤࢆศ㞳ࡍࡿࡇ࡜࡛࠶ࡾ㸪ࣛࣇ㞟ྜ࡛ࡣᅗ ࡢⓑⰍࡢ⠊ᅖࡢࡼ࠺࡟ྠ୍࢝ࢸࢦࣜෆࡀⓎ⏕ࡲࡓࡣ㠀Ⓨ⏕ࡢࡳࡢࢹ࣮ࢱ࡛ᵓᡂࡉࢀ࡚࠸ࡿࡼ࠺࡞ࢹ࣮ࢱࢆᩚྜࢹ࣮ࢱ࡜࿧ࡧ㸪⅊ⰍࡢࢭࣝࡣⓎ⏕࣭㠀Ⓨ⏕ࡀΰᅾࡋ࡚࠸ࡿࡶࡢࢆ▩┪ࢹ࣮ࢱ࡜࿧ࢇ࡛࠸ࡿࠋ඲ࢹ࣮ࢱᩘ࡟ᑐࡍࡿᩚྜࢹ࣮ࢱࡢᏑᅾ๭ྜࢆᩚྜᗘ࡜࿧ࢇ࡛࠾ࡾ㸪ᩚྜᗘࡀ㧗ࡃ࡞ࡿࡼ࠺࡞せᅉࡣ㔜せせᅉ࡛࠶ࡿ࡜ゝ࠼ࡿࠋࡲࡓ㸪⦰⣙࡜ࡣ㸪౛࠼ࡤ㸪ᅗ ࡢ౛ࡢࡼ࠺࡟ᆅᙧ᮲௳  ࢆ㝖࠸࡚⪃࠼࡚ࡶ㸪⅏ᐖࡢⓎ⏕ཬࡧ㠀Ⓨ⏕࡟ࡣ㛵ಀ࡞࠸࡜࡞ࡿ࡜㸪ࢹ࣮ࢱ࣮࣋ࢫୖ࡛ࡣᆅᙧ᮲௳  ࡣ┬␎ࡍࡿࡇ࡜ࡀ࡛ࡁࡿ࡜࠸࠺⪃࠼᪉࡛࠶ࡿࠋṧࡾࡢᆅᙧ᮲௳ 㸪ᆅᙧ᮲௳  ࡣ⅏ᐖࡢⓎ⏕࣭㠀Ⓨ⏕ࢆ⪃࠼ࡿୖ࡛ࡢ㔜せせᅉ࡛࠶ࡿ࡜࠸࠺ࡇ࡜࡟࡞ࡿࠋ㸰㸰ᮏ◊✲࡟⏝࠸ࡓࢹ࣮ࢱᮏ◊✲࡛ࡣ㑣ᬛᕝὶᇦෆࢆ P ࣓ࢵࢩࣗ࡟༊ศࡋ㸪ࡑࢀࢆホ౯༢఩࡜ࡋ࡚ᩳ㠃ᔂቯ➼ࡢ⠊ᅖ࠿ࡽⓎ⏕࣭㠀Ⓨ⏕ࢆ༊ศࡍࡿ࡜ࡶ࡟㸪࣮ࣞࢲ࣮㞵㔞ィ࡟ࡼࡿ㞵㔞࣓ࢵࢩࣗࢹ࣮ࢱ࡟ᇶ࡙ࡃ▷ᮇ㹼㛗ᮇࡢ㞵㔞ࡸࡑࢀࡽ㉸㐣☜⋡ᖺ㸪ᩳ㠃᪉఩ࡸഴᩳᗘ࡞࡝ࡢᆅᙧせᅉ㸪ᆅ㉁༊ศ㸪✵୰㟁☢Ἴ᥈ᰝ⤖ᯝ➼ࡢィ  せᅉ࡟ࡘ࠸࡚ࡑࢀࡒࢀ 㹼 ࡢ࢝ࢸࢦࣜ࡟ศ㢮ࡋࡓࠋ⅏ᐖࡢⓎ⏕࡜㛵㐃ᛶࡢప࠸せᅉᅗ㸫 ࣛࣇ㞟ྜ࡟࠾ࡅࡿࢹ࣮ࢱ࣮࣋ࢫ⦰⣙ࡢ࢖࣓࣮ࢪᅗ㸫 ࣛࣇ㞟ྜࡢᴫᛕ- 426 -࡞࠾㸪✵୰㟁☢Ἴ᥈ᰝ⤖ᯝ࡟ࡘ࠸࡚ࡣᆅ୰ࡢỈศ㔞ࡸᆅ㉁ᵓ㐀ࡢኚ໬Ⅼ➼ࢆ⾲ࡍᣦᶆ࡜ࡋ᳨࡚ウᑐ㇟࡟ຍ࠼ࡓࠋࡲࡓ㸪ὶᇦෆ࡛  ᖺࡢᔂቯⓎ⏕⟠ᡤࡢุㄞ⤖ᯝࢆඖ࡟㸪ホ౯༢఩ࡢ P ࣓ࢵࢩࣗࢆⓎ⏕࡜㠀Ⓨ⏕࡟ศ㢮ࡋ㸪ࢹ࣮ࢱ࣮࣋ࢫࢆసᡂࡋࡓࠋࡑࡢࢹ࣮ࢱ࣮࣋ࢫ࡟ᇶ࡙࠸࡚㸪ࣛࣇ㞟ྜࢆ⏝࠸࡚ᅵ◁⅏ᐖⓎ⏕ࡢⓎ⏕ཬࡧ㠀Ⓨ⏕࡜㛵ಀࡢ῝࠸࡜⪃࠼ࡽࢀࡿせᅉࢆ  㡯┠ࡢせᅉࡢ୰࠿ࡽᢳฟࡍࡿ ⾲ ࡜࡜ࡶ࡟㸪Ⓨ⏕ཬࡧ㠀Ⓨ⏕᮲௳ࢆồࡵࡓࠋ㸱㸬㑣ᬛᕝὶᇦ࡟࠾ࡅࡿᩳ㠃ᔂቯࡢⓎ⏕࣭㠀Ⓨ⏕࡟࠾ࡅࡿ㔜せせᅉࣛࣇ㞟ྜ࡟ࡼࡿゎᯒࡢ⤖ᯝ㸪 せᅉࡢ࠺ࡕ  せᅉࡢ⤌ࡳྜࢃࡏ࡛ᩚྜᗘࡀ⣙ 㸣ࡢ⢭ᗘ࡛Ⓨ⏕࣭㠀Ⓨ⏕ࢆศ㞳ྍ⬟࡜࡞ࡗࡓࠋᢳฟせᅉ࡜ࡋ࡚ࡣ㸪ࠕᩳ㠃᪉఩ࠖ㸪ࠕ᥋㇂㠃ᕪࠖ㸪ࠕ㇂ᐦᗘࠖࡀ࡝ࡢ⤌ࡳྜࢃࡏࡢሙྜ࡟࠾࠸࡚ࡶᢳฟࡉࢀ࡚࠾ࡾ㸪ḟ࠸࡛ࠕ⣼✚ゎᯒ㞵㔞ࠖ㸪ࠕ᥋ᓠ㠃ᕪࠖࡀከࡃᢳฟࡉࢀࡿ⤖ᯝ࡜࡞ࡗࡓࠋ
⾲ せᅉ࡜せᅉᩘࡈ࡜ࡢᢳฟせᅉࡢ⤌ࡳྜࢃࡏ୍ぴ⾲せᅉᩘ␒ྕᩚྜᗘᩳ㠃᪉఩ᆅ㉁༊ศഴᩳᗘ᥋ᓠ㠃ᕪ᥋㇂㠃ᕪ㇂ᐦᗘ䠎䠑䖃䖃䖃䖃㻠䖃䖃䖃䖃䖃䖃䖃㻣䖃䖃䖃䖃䖃䖃䖃䖃㻤䖃䖃䖃䖃㻠䖃䖃䖃䖃䖃䖃䖃㻣䖃䖃䖃䖃䖃䖃䖃䖃㻤㻡㻙㻝㻡㻙㻞㻡㻙㻟㻡㻙㻠 ᥇⏝ᩘ㻢㻙㻝㻢㻙㻞㻢㻙㻟㻢㻢㻙㻠㻢㻙㻡㻢㻙㻢㻢㻙㻣 ᥇⏝ᩘ㻣㻙㻝㻣㻙㻞㻣㻙㻟㻣㻙㻠㻣㻣㻙㻡㻣㻙㻢㻣㻙㻣㻣㻙㻤 ᥇⏝ᩘ㻡㻥㻜㻚㻜㻥㻜㻥㻜㻚㻝㻡㻠㻥㻜㻚㻟㻠㻤㻥㻜㻚㻠㻣㻢㻥㻠㻚㻡㻟㻜㻥㻠㻚㻡㻟㻜㻥㻠㻚㻡㻟㻜㻥㻠㻚㻢㻡㻥㻥㻠㻚㻣㻞㻟㻥㻠㻚㻣㻞㻟㻥㻠㻚㻤㻡㻞㻥㻢㻚㻣㻝㻤㻥㻢㻚㻣㻝㻤㻥㻢㻚㻣㻝㻤㻥㻢㻚㻣㻝㻤㻥㻢㻚㻣㻤㻟㻥㻢㻚㻣㻤㻟㻥㻢㻚㻣㻤㻟㻥㻢㻚㻣㻤㻟㻙䖃䖃䖃䖃㻠䖃䖃䖃䖃䖃䖃䖃㻣䖃䖃䖃䖃䖃䖃䖃䖃㻤䖃㻜㻜䖃㻝䖃䖃䖃䖃㻜㻝䖃䖃㻡䖃䖃䖃䖃㻜㻞䖃䖃䖃㻢ゎᯒ㞵㔞䠍䠌ศ㻜ゎᯒ㞵㔞䠍᫬㛫㻜ゎᯒ㞵㔞䠎䠐᫬㛫㻜ゎᯒ㞵㔞䠏䠒᫬㛫㻜ゎᯒ㞵㔞䠐䠔᫬㛫㻜ゎᯒ㞵㔞⣼✚䖃䖃䖃䖃㻠䖃☜⋡ᖺ䠍᫬㛫☜⋡ᖺ䠎䠐᫬㛫☜⋡ᖺ䠏䠒᫬㛫㻝㻝☜⋡ᖺ㑣ᬛ䠍᫬㛫ᅵ◁⅏ᐖ㆙ᡄ᝟ሗᅵተ㞵㔞ᣦᩘẚ᢬ᢠ್⾲㠃ẚ᢬ᢠ್㟁᥈䠍ḟᚤศ㟁᥈䠍ḟᚤศ῝䛥㟁᥈䠎ḟᚤศ㟁᥈䠎ḟᚤศ῝䛥䠍ḟᚤศ࿘㎶ᕪศ㻜㻜㻜㻜㻜㻜㻜㻜㻜㻜㻜㻜㻜㻜㻜䖃䖃㻝䖃㻝㻝䖃㻜㻜㻜䖃䖃䖃䖃䖃㻢䖃䖃䖃䖃䖃䖃䖃䖃䖃㻞㻜㻜㻜䖃䖃㻣㻞䖃㻝䖃䖃㻞㻜㻜㻜㻜㻜㻜㻜䖃㻝䖃䖃䖃䖃䖃䖃䖃䖃䖃䖃䖃䖃䖃㻜☜⋡ᖺ⣼✚䖃䖃㻜☜⋡ᖺ䠐䠔᫬㛫㻝㻠㻞㻜㻜㻜㻜㻜㻜㻜㻜㻢㻜䖃㻞㻜㸲㸬⪃ᐹᮏ◊✲࡟࠾࠸࡚ᩳ㠃᪉఩ࡀ㑅ᐃࡉࢀࡓ⌮⏤࡜ࡋ࡚㸪せᅉศᯒ⤖ᯝࡼࡾ༡ᮾ࣭༡࣭༡すྥࡁᩳ㠃࡟࠾࠸࡚⾲ᒙᔂቯࡢⓎ⏕๭ྜࡀ㧗ࡃ࡞ࡗ࡚࠾ࡾ㸪ࡇࢀࡣ㑣ᬛᕝὶᇦࡀ఩⨨ࡍࡿ⣖ఀ༙ᓥࡀ  ᖺྎ㢼  ྕࡢ୰ᚰ㐍㊰࠿ࡽᮾഃ࡟఩⨨ࡋ࡚࠸ࡓࡇ࡜࡟ࡼࡗ࡚༡ഃᩳ㠃ࡀ‵ࡗࡓ✵Ẽࡢ┤ᧁࢆཷࡅ㝆㞵㔞ࡀከࡃ࡞ࡗࡓࡇ࡜ࡀཎᅉ࡛࠶ࡿ࡜᥎ᐹࡉࢀࡿࠋࡲࡓ㸪ࠕ᥋㇂㠃ᕪࠖ㸪ࠕ㇂ᐦᗘࠖࡣඹ࡟⌧ᆅᙧ࡟⮳ࡿ㐣⛬ࡢ౵㣗ࡢ⤖ᯝࢆ⾲⌧ࡍࡿᣦᶆ࡛࠶ࡾ㸪㔜せせᅉ࡜ࡋ࡚㑅ᐃࡉࢀࡿࡇ࡜࡟▩┪ࡣ࡞࠸࡜⪃࠼ࡽࢀࡿࠋ
୍⯡ⓗ࡟▷ᮇ㞵㔞ᣦᶆ࡜ࡢ㛵ಀࡀ῝࠸࡜⪃࠼ࡽࢀࡿ⾲ᒙᔂቯࢆ᳨ウᑐ㇟࡜ࡋ࡚࠸ࡿ࡟ࡶ࠿࠿ࢃࡽࡎ㸪⣼✚ゎᯒ㞵㔞ࡸ  ᫬㛫㞵㔞ࡢ㉸㐣☜⋡ᖺࡀከࡃ㑅ᐃࡉࢀ࡚࠸ࡿࡇ࡜࡟ࡘ࠸࡚ࡣ㸪ୖ✵㞵㔞ࢆほࡋ࡚࠸ࡿゎᯒ㞵㔞࡜ᐇ㝿࡟ᆅୖ࡛㝆ࡿ㞵㔞࡜ࡢ㐪࠸ࡀᙳ㡪ࡋࡓྍ⬟ᛶࡀ࠶ࡿࡇ࡜ࡲࡓ㸪㝈ࡽࢀࡓ᳨ウᑐ㇟⠊ᅖ࡛ࡣ㝆㞵ᣦᶆ࡟኱ࡁ࡞ᕪࡀ࡞࠿ࡗࡓࡓࡵ࡛࠶ࡿ࡜᥎ᐹࡉࢀࡿࠋࡲࡓ㸪 せᅉ࡛✵୰㟁☢Ἴ᥈ᰝ  ḟᚤศ῝ࡉ ᆅ㉁ࡢኚ໬Ⅼࡀ⾲ࢀࡿ῝ᗘ ࡀせᅉ࡜ࡋ࡚ᢳฟࡉࢀ࡚࠸ࡿࡀ㸪せᅉศᯒࡢ⤖ᯝ࡛ࡣ᭱ࡶὸ࠸࢝ࢸࢦࣜࡢⓎ⏕⋡ࡀ᭱ࡶ㧗ࡃ࡞ࡗ࡚࠸࡞࠸ࡶࡢࡢ㸪ẚ㍑ⓗὸ࠸⠊ᅖࡢ࢝ࢸࢦࣜ 㹼P ࡟ᔂቯⓎ⏕࣓ࢵࢩࣗࡀ㞟୰ࡋ࡚࠾ࡾ㸪᮲௳࡟ࡼࡗ࡚ࡣ㸪ᆅ⾲௜㏆ࡢࢹ࣮ࢱࡀྲྀᚓࡋ࡟ࡃ࠸ሙྜࡀ࠶ࡿ࡜࠸࠺✵୰㟁☢Ἴ᥈ᰝࡢᛶ㉁࠿ࡽ⪃࠼ࡿ࡜᳨ウ⤖ᯝ࡜▩┪ࡋ࡚࠸࡞࠸ࠋ
ཧ⪃ᩥ⊩ 3DZODN=㸸Rough Sets, International Journal of computer and Information Sciences, Vol.11, pp.341-356, 19822) ᾏཎⲮ୍࣭ᮌୗ⠜ᙪ࣭௒᳃┤⣖࣭➉ᮏ኱᫛࣭ྈ⇃඾Ꮚ㸸ࣛࣇ㞟ྜ࡟ࡼࡿ῝ᒙᔂቯⓎ⏕ࡢ㔜せせᅉ࡜Ⓨ⏕࣭㠀Ⓨ⏕᮲௳ࡢᢳฟ㸪◁㜵Ꮫ఍ㄅ㸪Vol. 70㸪No. 1㸪2017㸦ᥖ㍕ணᐃ㸧- 427 -