次の問題: 与えられたのは任意の多角形です。所定の半径の最小数の円で 100% 覆われている必要があります。
注: 1) 当然、円は重なる必要があります。2) 任意のポリゴンの問題を解決しようとしています。しかし、CONVEX ポリゴンのソリューションも高く評価されています。3) 私が知る限り、この問題は NP 困難 (セット カバー問題の最小サイズ セット カバーを見つけるためのアルゴリズム) です。選択: U = 多角形および S1...Sk = 任意の中心を持つ円。
私の解決策：私 はすでにいくつかの論文を読み、自分でいくつかのことを試しました. 私が思いついた最も有望なアイデアは、実際、同じ半径の円で任意の領域をカバーするで既に示したものでした。
ですから、自分の考えをすぐに説明してから、質問を絞り込むのが最善だと思います。
写真は、私が何をしているかについてすでにかなり良いアイデアを与えてくれます
IDEA と問題の定式化 1. 対応する六角形で円を近似し、R2 全体、つまり十分に大きな領域をテッセレーションします。キーワードは六角形に最も近いパッケージングです。(シアン … テッセレーション、赤のドット、シアンの六角形の中心) 2. このテッセレーション領域の中央にポリゴンを配置し、ポリゴンを覆うために必要な六角形の数を計算します。
次の例では、各ステップで N を「カウント」した後、ポリゴンをステップごとに移動することで、ポリゴンをカバーするために必要な六角形の数である N を最小化しようとしています。
問題を解決する： それが（私にとって）難しいときです。この問題を適切に解決するオプティマイザーは知りません。ポリゴンを少し動かして変化を観察しないとすべて終了するからです。
私の解決策は次のとおりです。 まず、これは周期的な問題であることに注意してください。1. ポリゴンは、六角形の 3*r (辺の長さ = 半径 r) の周期で水平方向 x に移動できます。2. ポリゴンは、六角形の r^2+r^2-2*r r cos(2/3*pi) の周期で垂直方向 y に移動できます。3. ポリゴンは 2/3*pi の周期で phi 回転できます。
つまり、最適な解を見つけるには、可能な解の有限領域を検索する必要があります。つまり、(x,y,phi) のステップサイズを選択し、考えられるすべての解を力ずくで計算して、最適解を選択します。
質問の改善 1) 問題は知的に定式化されていますか? 現在、できるだけ小さな六角形を計算する必要があるように、非常に小さな領域のみをテッセレーションするアルゴリズムに取り組んでいます。2) 問題を解決するためのよりインテリジェントなオプティマイザーはありますか? 3) 最後に: 検索する適切なキーワードがわからないとは思わないので、適切な文献を見つけるのも困難です。誰かが私に文献を提供してくれれば、それも大いに感謝します。
実際、私が試した他のことについて続けることもできますが、私の質問を読むだけで午後全体を過ごしたいと思う人は誰もいないと思います。
それについて考えるのに時間をかけるすべての人に前もって感謝します。
マット
PS i は私のアルゴリズムを matlab に実装します