Open Access 話題の記事
列挙の基本と基礎的なアルゴリズム
Vol.95 No.6pp.477-483
発行日:2012/06/01
Online ISSN:2188-2355
Print ISSN:0913-5693
種別:小特集 広がる列挙の技術──列挙による問題解決アプローチ──
専門分野:
キーワード:
列挙アルゴリズム, 遅延, 分割法, グレイコード, 逆探索法,
Free本文:PDF(452.5KB)
あらまし:
列挙問題とは,与えられた条件を満たすものを漏れなく,重複なく出力する問題である.本稿では,列挙問題を解くためのアルゴリズム設計技法として基礎的なものを紹介する.まず,列挙アルゴリズムの効率の良さの測り方を導入する.その後で,部分集合列挙問題を例題として,分割法,グレイコード,逆探索法という三つの設計技法を紹介する.最後に,効率の良い列挙アルゴリズムを設計することが難しい列挙問題とその理由について言及する.