以下は検索よりも優れていると思いますが、検索に基づいているため、最初にそれについて説明します。
探す
基本的な検索をさまざまな方法で効率的にすることができます。
まず、可能な配置を効率的に列挙する必要があります。ファームを配置できる最初の位置に相対的なシフト数を格納することで、これを行うと思います。下から (ルートの近く)。したがって、(0) は一番下の行の左側にある単一の農場になります。(1) ファームが 1 つ右にシフトしたことになります。(0,0) は 2 つのファームになります。最初は (0) として、2 番目は最初の位置で上方向にスキャンできます (2 行目、最初のファームに接触)。(0,1) は 2 番目のファームを 1 つ右にします。等
次に、可能な限り効率的に剪定する必要があります。そこでは、スマートだがコストのかかることと、ばかげているが高速なこととの間のトレードオフがあります。愚かだが速いのは、すべてのファームに到達できるかどうかをチェックする、ルートからのフラッド フィルです。1 つのファームを追加するときに、増分方式でそれを行う方法を考える方が賢明です。たとえば、ファームがカバーする最小値よりも小さいセルを以前のフラッド フィルに依存できることがわかっています。さらに賢明なのは、重要な道路 (別の農場への一意のアクセス) を特定し、何らかの方法でそれらを「保護」することです。
第三に、より高いレベルでできる追加の微調整があるかもしれません。たとえば、対称グリッドを解決し (対称性を使用して、同じパターンをさまざまな方法で繰り返さないようにする)、どのソリューションが実際のグリッドと一致しているかを確認する方がよい場合があります。役立つかもしれないが、どのように機能するかはわかりませんが、農場ではなく道路に集中するという別のアプローチがあります。
キャッシング
秘伝のタレはこちら。私が説明した検索は、左から右へのスキャンで、下からスペースにファームを「埋めます」。
ここで、ほぼ最適な分布でスペースがいっぱいになるまで検索を実行したと想像してください。その解決策を改善するには、ほとんど最初に戻って、「底近く」のいくつかのファームを再配置する必要があるかもしれません。上のスペースを再入力するために検索を続行する必要があるため、これはコストがかかります。
ただし、農場の周囲の「境界」が以前の配置と同じである場合は、検索全体を繰り返す必要はありません。最適な方法でその境界の上をすでに「埋めて」いるからです。そのため、「特定の境界の最良の結果」によってキャッシュし、それらのソリューションを簡単に検索できます。
境界の説明には、境界の形状とルートへのアクセスを提供する道路の位置を含める必要があります。それだけです。
