2024-03-29T03:34:43Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000105912022-10-21T05:24:51Z00581:00625:00631
Selected Sequence-Pairのための効率的な隣接解生成手法An Efficient MOVE Operation for Selected Sequence-Pairjpn論文http://id.nii.ac.jp/1001/00010591/Journal Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=10591&item_no=1&attribute_id=1&file_no=1Copyright (c) 2005 by the Information Processing Society of Japan情報数学東京農工大学工学教育部電子情報工学専攻東京農工大学工学教育部電子情報工学専攻東京農工大学工学教育部電子情報工学専攻藤吉, 邦洋児玉, 親亮清田, 紘司n個の矩形のパッキングを長さn の順列の対で表現するsequence-pairに対して,近年,隣接交差と呼ばれる部分列の数をn-「√4n-1」 以下に制限した“selected sequence-pair”が提案された.これはsequence-pairと同様にどんな矩形パッキングでも表現可能であるという特長を持ちながら,矩形数の線形時間で,その示唆する制約の下での左下詰めパッキングを得ることができるという優れた特長を持つ.しかし,隣接解やその生成法が提案されていなかったため,Simulated Annealing法などと組み合わせてのパッキング探索に用いることができなかった.そこで本稿では,selectedsequence-pairでの到達可能性を保証できる隣接解と,その効率的な生成方法を提案し,計算機実験によってその効率の良さを確認する.Recently “selected sequence-pair” was proposed, which is a sequence-pair with n?「√4n?1」 or less sub-sequences called adjacent cross (n is the number of rectangles). In addition to the merit that it can represent any packing, it has a superior feature that a bottom left corner packing can be obtained under the constraints imposed by itself in linear time of the number of rectangles. However, as a method of generating adjacent solution was not proposed, it was impossible to use selected sequence-pair for search of packing by combining with Simulated Annealing, etc. In this paper, we propose adjacent solution which can guarantee reachability in selected sequence-pair and a procedure to generate an adjacent solution and then we confirm its efficiency by experiments.AN00116647情報処理学会論文誌467171117222005-07-151882-77642009-06-29