矩形に四角形を重ならないようにランダムな位置に配置するアルゴリズム

Question

とあるサイズの矩形に四角形を重ならないようにランダムな位置に配置するアルゴリズムを探しています。

以下の画像のようなものを想定しています。
青い四角形をランダムに配置しています。

こういったアルゴリズムがあるという情報だけで構いません。ご存知の方がいらっしゃれば教えていただきたいです。
追記：ある程度速度が速い方法を探しています。

(個人的に考えたのは、図形詰め込みアルゴリズム(参考：Pythonによる図形詰込みアルゴリズム入門)を用いて詰め込んでから、かさならないようにランダムで動かすという手法です・・・もっと綺麗にできる手法があると思い質問を投稿させていただきました。)

Answer 1

（貼られている絵の様子から，四角形はグリッドに沿う位置に配置するのだと思って以下を書きます）

まず，「ランダム」を度外視して，「全ての四角形を枠内に置ける配置パターンを見つける手続き」を考える．
この手続きは，ほうっておけば（置けるパターンを見つけてもそこで止めなければ）全ての配置パターンを探索するだろう．

↓

これに対して「ランダム」を導入するとしたら…

• 前記の「探索」の順序は，何らかの秩序立ったルールに従っているだろうが，

この探索順序をランダムに決定すればよいのではないか．

• あるいは，「K番目に見つけた置けるパターンを解とする」こととしてKを乱数で決めればよいのではないだろうか．

…といった，至極単純な話をまず思いつくけれども，そんな話ではいかんのでしょうか？

Comments

[rtag]

ある程度速度を求めているので、すべての四角形の配置パターンを処理するのは難しいですが、
ある程度配置パターンを求めてから、特定番目の配置パターンを解とするという手法はとても参考になりました。ありがとうございました！

[fana]

実際に想定している問題の規模(?)とか，このような力技な(?)方法だと速度の面で問題がある等の懸念事項等を質問文内にて述べておくと良いように思いまする．

Answer 2

すでに、ご存じかもしれませんが

組み合わせ最適化と呼ばれるジャンルのものでしょうか。

直接的なアルゴリズムは知らないのですが、キーワードとしては、組み合わせ最適化、アルゴリズムで
いろんな情報が得られると思います。

Comments

[rtag]

組み合わせ最適化に関しまして調べていきたいと思います！
ありがとうございました！