非探索アルゴリズムによるn_queen問題の解法

• Item type: SIG Technical Reports(1)
• 公開日: 1990-05-24
• タイトル: 非探索アルゴリズムによるn_queen問題の解法
• タイトル / 言語: en
• タイトル: Non - Searching Algorithms for the n_Queen Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 電気通信大学電子情報学科
• 著者所属: 電気通信大学電子情報学科
• 著者所属: 電気通信大学電子情報学科
• 著者所属(英): en
• 著者所属(英): Dept. of Commun. & Systems, The Univ. of Electro - Communications
• 著者所属(英): en
• 著者所属(英): Dept. of Commun. & Systems, The Univ. of Electro - Communications
• 著者所属(英): en
• 著者所属(英): Dept. of Commun. & Systems, The Univ. of Electro - Communications
• 著者名: 山田, 義朗; 富田, 悦次; 高橋, 治久
• 著者名(英): Yoshiaki, Yamada; Etsuji, Tomita; Haruhisa, Takahashi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: n_queen問題は探索アルゴリズムの例題としてよく取上げられる。しかしながら、探索アルゴリズムは問題のサイズが大きくなると現実的な時間で解が得られないことが多い。ここでは、n_queen問題を解く2つの非探索アルゴリズムを提唱する。どちらのアルゴリズムも、モンテカルロ法による近似最大独立節点集合(）抽出アルゴリズムを基本にして効率化を行なったものである。計算機実験によりこれまでに20000 queen問題の解が得られており、アルゴリズムの効率の良さが伺える。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: An n_queen problem is one of typical problems which can be solved by searching methods. In many cases, the time required for such searching algorithms is very huge. In this note, we propose two non-searching algorithms for the n_queen problem that which are based upon a Monte-Carlo algorithm for finding a near-maximum independent set (MIS). We present some experimental results of these algorithms for up to 20000 queens.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10485570
• 書誌情報: 情報処理学会研究報告プログラミング（PRO）; 巻 1990, 号 44(1990-PRO-035), p. 87-92, 発行日 1990-05-24
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会