| 講演名 | 1993/11/19 区分的線形抵抗回路のすべての解を求める効率的なアルゴリズム 山村 清隆, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本論文では、区分的線形抵抗回路のすべての解を求める簡単で効率的なアルゴリズムを提案する.このアルゴリズムは前回提案したアルゴリズムの改良版で,簡単な符号テストを施行して解が存在しない線形領域を除去することにより,線形方程式の求解回数を大幅に減少させるものである.しかし線形領域の数は一般に天文学的数字であるので,すべての線形領域上でテストを行なうことは膨大な計算時間を必要とする.本論文では,符号テストを複数個の線形領域からなる超直方体に適用できるよう拡張し,分岐限定法のアイデアを符号テストに採り入れることにより,計算時間を飛躍的に短縮できることを示す.例えば,線形領域数100兆の問題を解くのに,前回提案したアルゴリズムでは300年以上かかるのに対し,新しいアルゴリズムでは数十分で解を求めている. |
| 抄録(英) | An efficient algorithm is presented for finding all solutions of piecewise-lineax resistive circuits.In this algorithm,a simple sign test is performed to eliminate many linear regions that do not contain a solution.This makes the number of simultaneous linear equations to be solved much smaller.This test,in its original form,is applied to each linear region;but this is time- consuming because the number of linear regions is generally very large.In this paper,it is shown that the sign test can be applied to super-regions consisting of adjacent linear regions.Therefore, many linear regions are discarded at the same time,and the computational efficiency of the algorithm is substantially improved.The branch-and-bound method is used in applying the sign test to super-regions.Some numerical examples are given,and it is shown that all solutions are computed very rapidly.The proposed algorithm is simple,efficient,and can be easily programmed. |
| キーワード(和) | 区分的線形抵抗回路 / 全解探索問題 / 符号テスト / 分離性 / 分岐限定 法 |
| キーワード(英) | piecewise-linear resistive cirouit / all solution / sign test / separability / branch-and-bound method |
| 資料番号 | NLP93-58 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NLP |
|---|---|
| 開催期間 | 1993/11/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Nonlinear Problems (NLP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 区分的線形抵抗回路のすべての解を求める効率的なアルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Finding All Solutions of Piecewise-Linear Resistive Circuits |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 区分的線形抵抗回路 / piecewise-linear resistive cirouit |
| キーワード(2)（和/英） | 全解探索問題 / all solution |
| キーワード(3)（和/英） | 符号テスト / sign test |
| キーワード(4)（和/英） | 分離性 / separability |
| キーワード(5)（和/英） | 分岐限定 法 / branch-and-bound method |
| 第 1 著者 氏名（和/英） | 山村 清隆 / Kiyotaka Yamamura |
| 第 1 著者 所属（和/英） | 群馬大学工学部情報工学科 Department of Computer Science,Faculty of Engineering,Gunma University |
| 発表年月日 | 1993/11/19 |
| 資料番号 | NLP93-58 |
| 巻番号（vol） | vol.93 |
| 号番号（no） | 335 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |