WEKO3
アイテム
ナップザック問題の分枝限定アルゴリズムのランダム化とその解析
https://ipsj.ixsq.nii.ac.jp/records/33759
https://ipsj.ixsq.nii.ac.jp/records/337596ccffd8c-cf23-4e4b-82e7-cc46c51f0417
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-MPS95004004.pdf (397.5 kB)
|
Copyright (c) 1995 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1995-11-17 | |||||||
| タイトル | ||||||||
| タイトル | ナップザック問題の分枝限定アルゴリズムのランダム化とその解析 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | An Analysis of Randomized Branch and Bound Algorithm of the Knapsack Problem | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 東京農工大学工学部電子情報工学科情報工学大講座 | ||||||||
| 著者所属 | ||||||||
| 東京農工大学工学部電子情報工学科情報工学大講座 | ||||||||
| 著者所属 | ||||||||
| 東京農工大学工学部電子情報工学科情報工学大講座 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science Tokyo University of Agriculture and Tecnology | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science Tokyo University of Agriculture and Tecnology | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science Tokyo University of Agriculture and Tecnology | ||||||||
| 著者名 |
福田, 和真
× 福田, 和真
|
|||||||
| 著者名(英) |
Kazuma, Fukuda
× Kazuma, Fukuda
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | ナップザック問題の1つである部分和問題を解く分枝限定アルゴリズムをランダム化して，その計算の手間を解析する．一般に，0?1変数をもつ問題に対する分枝限定アルゴリズムは，分枝操作において変数を次々と選んでは，それらの値が0の場合と1の場合に分けて問題をより小さな部分問題に分割する．本論文では，変数を選ぶ部分をランダム化したアルゴリズムを考察する．アルゴリズムの手間の評価は生成される部分問題の数について注目する．また，部分問題の限定操作が最小数しか行われない確率についても考察する． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | A randomized branch and bound algorithm for the subset-sum problem which is a special case of the knapsack problem is analized from the point of view of computational complexity. A branch and bound algorithm chooses variables successively, fixing each to value 0 or value 1 and thus deviding the original problem into smaller subproblems. This is called the branching process. In the present paper variables are chosen at random in the branching process. The computational complexity of our randomized algorithm is measured by the number of subproblems generated. The expected value of the mumber of subproblems is estimated and that of the probability that that worst case takes place is obtained. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN10505667 | |||||||
| 書誌情報 |
情報処理学会研究報告数理モデル化と問題解決（MPS） 巻 1995, 号 111(1995-MPS-004), p. 19-24, 発行日 1995-11-17 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
