|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 最 ： [さい] 1. (n,pref) the most 2. the extreme ・ 最小 ： [さいしょう] 【名詞】 1. smallest 2. least ・ 極 ： [きょく, ごく] 1. (adv,n) quite 2. very ・ 極大 ： [きょくだい] (adj-na,n) maximum ・ 問 ： [もん] 【名詞】 1. problem 2. question ・ 問題 ： [もんだい] 【名詞】 1. problem 2. question ・ 題 ： [だい] 1. (n,vs) title 2. subject 3. theme 4. topic
最小極大マッチング問題（さいしょうきょくだいマッチングもんだい）は、与えられたグラフ ''G'' の極大マッチングの中で大きさが最小のものを見つける問題。NP困難な問題であることが知られている。 この問題に対しては、最大マッチング問題の解を求めるアルゴリズムを適用することで、近似度2 の解が得られることは容易に示すことができるが、近似度が 2 を下回るアルゴリズムは知られていない。また、2003年には、P=NP が成り立たないとき、近似度が 7/6 より良い近似アルゴリズムが存在しないことが示された。 == 関連項目 == * NP完全問題 * 計算複雑性理論 * グラフ理論 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「最小極大マッチング問題」の詳細全文を読む スポンサード リンク
|