限られたスペースに部屋を配置するアルゴリズムに関するヘルプ

Question

私は小さな家の設計プロジェクトに取り組んでいます。その最も重要な部分の1つは、ユーザーが彼の部屋をどのようにしたいかに関する情報を与えることができるセクションです（例えば、 10x10メートルの家、3x3のリビングルーム、3x3のキッチン、2つの4x5のベッドルーム、4x2のバスルーム）を備え、プログラムは要求された条件に従って家の地図を生成する。

今のところ、マップを描画することを心配していません。重複しないように部屋を配置するだけです（はい、出力はかなり醜いことがあります）。私は既にいくつかの検索を行い、私が欲しいものがpacking problemと非常に似ていることを発見しました。この問題はかなりうまく処理されますが（NP完全な問題ですが）、algorithmsです。

しかし、私はさらに1つの制限がありました。たとえば、ユーザーは部屋間に「リンク」を指定できます。たとえば、部屋にはバスルームに「ドア」があり、リビングルームには直接キッチンなど（つまり、部屋を並べて配置する必要があります）、これが複雑になる場所です。

私はNP問題を設定したいと思うので、良い実装をするためのヒントを求めていますが、必ずしも最適な実装ではありません。私が持っているアイデアは、部屋間の関係を表すためにグラフを使用することですが、私はこの新しい制約に合わせて既存のパッキングアルゴリズムをどのように適応させることができないのかを知ることはできません。誰でも助けてくれますか？

Answer 1

完全な答えはありませんが、私はヒントを持っています：planar graphと呼ばれる接続の制約があります。そうでない場合は、単話の家では解決できません）。最終的なソリューションの部屋は、dual of the constraint graphのエッジで囲まれた領域に対応するので、次に行う必要があるのは、デュアルを取って、サイジングの制約に合わせて交差を導入せずにそのエッジの形状を調整することです。制約グラフで「外側」を表す頂点を導入し、それがデュアルで囲まれていないことを確認する必要があります。また、すべての部屋が確実に接続されるように制約グラフにエッジを追加する必要があります（廊下などの部屋を追加するなど）。

Answer 2

thisが面白いかもしれません。 これは、パラディオ地方のヴィラを建設するための文法です。

あなたの問題にそのようなものを適用するには、ランダムに構成し、ランダムに変更してシミュレーテッドアニーリングアルゴリズムを使用する方法があります。