Frage Füllen Sie das Gitter mit Quadraten, die alle durch freien Raum verbunden sind


Ich habe ein Raster mit x Feldern. Dieses Raster sollte mit so viel Quadraten (nennen wir sie "Farmen") der Größe 2x2 (so dass jede Farm 4 Felder groß ist) gefüllt werden. Jede Farm muss mit einem bestimmten Feld ("root") über "roads" verbunden sein.

Ich habe eine Art Brute-Force-Algorithmus geschrieben, der jede Kombination von Farmen und Straßen ausprobiert. Jedes Mal, wenn eine Farm im Grid platziert wird, überprüft der Algorithmus, ob die Farm über den A * -Algorithmus eine Verbindung zur Root hat. Es funktioniert sehr gut auf kleinen Gittern, aber auf großen Gittern ist es zu zeitaufwendig.

Hier ist ein kleines bereits gelöstes Gitter

http://www.tmk-stgeorgen.at/algo/small.png

Blaue Quadrate sind die Farmen, rote Quadrate sind freier Platz oder "Straßen" und das gefüllte rote Quadrat ist das Wurzelfeld, zu dem jede Farm eine Verbindung benötigt.

Ich muss dieses Gitter lösen:

http://www.tmk-stgeorgen.at/algo/grid.png

Gibt es einen schnellen Standardalgorithmus, den ich verwenden kann?


17
2018-06-25 10:55


Ursprung


Antworten:


Ich denke, das Folgende ist besser als eine Suche, aber es basiert auf einer Suche, also werde ich das zuerst beschreiben:

Suche

Sie können eine grundlegende Suche auf verschiedene Arten effizient machen.

Zuerst müssen Sie die möglichen Anordnungen effizient aufzählen. Ich denke, ich würde dies tun, indem ich die Anzahl der Verschiebungen relativ zur ersten Position speichern würde, in der eine Farm platziert werden kann, beginnend von unten (nahe der Wurzel). so (0) wäre eine einzelne Farm links von der unteren Zeile; (1) wäre diese Farm nach rechts verschoben; (0,0) wären zwei Betriebe, zuerst als (0), zweiter an der ersten Position, mögliches Scannen aufwärts (zweite Linie, erste Farm berührend); (0,1) würde die zweite Farm rechts haben; etc.

Zweitens müssen Sie so effizient wie möglich beschneiden. da ist es ein Kompromiss zwischen intelligenten, aber teuren Dingen und dummen, aber schnellen Dingen. dumm aber schnell wäre eine Flutfüllung von der Wurzel, die überprüft, ob alle Farmen erreichbar sind. Klüger würde herausfinden, wie man das schrittweise macht, wenn man eine Farm hinzufügt - man weiß beispielsweise, dass man sich auf frühere Flood-Fills-Zellen verlassen kann, die kleiner sind als der kleinste Wert, den die Farm abdeckt. Noch schlauer wäre es, zu erkennen, welche Straßen kritisch sind (einzigartiger Zugang zu einer anderen Farm) und diese "zu schützen".

drittens, es kann zusätzliche Verbesserungen geben, die Sie auf einer höheren Ebene tun können. Zum Beispiel könnte es besser sein, nach einem symmetrischen Gitter zu suchen (und Symmetrie zu verwenden, um zu vermeiden, dass das gleiche Muster auf verschiedene Arten wiederholt wird) und dann zu überprüfen, welche Lösungen mit dem Gitter übereinstimmen, das Sie tatsächlich haben. Ein anderer Ansatz, der nützlich sein könnte, aber dass ich nicht sehen kann, wie man Arbeit macht, ist, sich eher auf die Straße als auf die Farmen zu konzentrieren.

Zwischenspeichern

Hier ist die geheime Soße. Die Suche, die ich beschrieben habe, füllt Farmen in den Raum von unten nach rechts.

Stellen Sie sich nun vor, dass Sie die Suche bis zu dem Punkt ausgeführt haben, an dem der Speicherplatz voll ist, mit einer nahezu optimalen Verteilung. Es kann sein, dass, um diese Lösung zu verbessern, man fast bis zum Anfang zurückgehen muss, um einige Farmen "ganz unten" neu anzuordnen. das ist teuer, weil Sie dann die Suche fortsetzen müssen, um den Raum oben wieder zu füllen.

Sie müssen jedoch nicht die gesamte Suche wiederholen, wenn die "Grenze" um die Farmen mit einer früheren Anordnung übereinstimmt. weil Sie diese Grenze bereits auf optimale Weise "ausgefüllt" haben. Sie können also nach "bestem Ergebnis für eine gegebene Grenze" cachen und diese Lösungen einfach nachschlagen.

Die Grenzbeschreibung muss die Form der Grenze und die Positionen von Straßen enthalten, die Zugang zur Wurzel bieten. das ist alles.


1
2018-06-25 23:57



Hier ist etwas Rohes in Haskell, das wahrscheinlich von Optimierung, Memoisierung und besseren Heuristiken profitieren könnte ...

Die Idee ist, mit einem Gitter zu beginnen, das alle Farm und Straßen darauf platzieren, beginnend mit der Wurzel und erweitert von dort. Die Rekursion verwendet eine Basisheuristik, bei der die Kandidaten aus allen benachbarten geraden Zweiblocksegmenten entlang der gesamten Straße ausgewählt werden und nur dann, wenn sie die Anforderung erfüllen, dass das Hinzufügen des Segments die Anzahl der mit der Straße verbundenen Betriebe erhöht. s (überlappende Segmente werden nur als ein Block statt zwei hinzugefügt).

import qualified Data.Map as M
import Data.List (nubBy)

-- (row,(rowLength,offset))
grid' = M.fromList [(9,[6])
                  ,(8,[5..7])
                  ,(7,[4..8])
                  ,(6,[3..9])
                  ,(5,[2..10])
                  ,(4,[1..11])
                  ,(3,[2..10])
                  ,(2,[3..9])
                  ,(1,[4..7])]

grid = M.fromList [(19,[10])
                   ,(18,[9..11])
                   ,(17,[8..12])
                   ,(16,[7..13])
                   ,(15,[6..14])
                   ,(14,[5..15])
                   ,(13,[4..16])
                   ,(12,[3..17])
                   ,(11,[2..18])
                   ,(10,[1..19])
                   ,(9,[1..20])
                   ,(8,[1..19])
                   ,(7,[2..18])
                   ,(6,[3..17])
                   ,(5,[4..16])
                   ,(4,[5..15])
                   ,(3,[6..14])
                   ,(2,[7..13])
                   ,(1,[8..11])]

root' = (1,7) --(row,column)
root = (1,11) --(row,column)

isOnGrid (row,col) =
  case M.lookup row grid of
    Nothing -> False
    Just a  -> elem col a

isFarm (topLeftRow,topLeftCol) =
  and (map isOnGrid [(topLeftRow,topLeftCol),(topLeftRow,topLeftCol + 1)
                    ,(topLeftRow - 1,topLeftCol),(topLeftRow - 1,topLeftCol + 1)])

isNotOnFarm tile@(r,c) farm@(fr,fc) =
  not (elem r [fr,fr - 1]) || not (elem c [fc, fc + 1])

isOnFarm tile@(r,c) farm@(fr,fc) =
  elem r [fr,fr - 1] && elem c [fc, fc + 1]

farmOnFarm farm@(fr,fc) farm' =
  or (map (flip isOnFarm farm') [(fr,fc),(fr,fc + 1),(fr - 1,fc),(fr - 1,fc + 1)])                 

addRoad tile@(r,c) result@(road,(numFarms,farms))
  | not (isOnGrid tile) || elem tile road = result
  | otherwise = (tile:road,(length $ nubBy (\a b -> farmOnFarm a b) farms',farms'))
    where
      newFarms' = filter (isNotOnFarm tile) farms
      newFarms = foldr comb newFarms' adjacentFarms
      farms' = newFarms ++ adjacentFarms
      comb adjFarm newFarms'' =
        foldr (\a b -> if farmOnFarm a adjFarm || a == adjFarm then b else a:b) [] newFarms''
      adjacentFarms = filter (\x -> isFarm x && and (map (flip isNotOnFarm x) road)) 
                        [(r - 1,c - 1),(r - 1,c),(r,c - 2),(r + 1,c - 2)
                        ,(r + 2,c - 1),(r + 2,c),(r + 1,c + 1),(r,c + 1)]

candidates result@(road,(numFarms,farms)) = 
  filter ((>numFarms) . fst . snd) 
  $ map (\roads -> foldr (\a b -> addRoad a b) result roads) 
  $ concatMap (\(r,c) -> [[(r + 1,c),(r + 1,c - 1)],[(r + 1,c),(r + 1,c + 1)]
                         ,[(r,c - 1),(r + 1,c - 1)],[(r,c - 1),(r - 1,c - 1)]
                         ,[(r,c + 1),(r + 1,c + 1)],[(r,c + 1),(r - 1,c + 1)]
                         ,[(r - 1,c),(r - 1,c - 1)],[(r - 1,c),(r - 1,c + 1)]
                         ,[(r + 1,c),(r + 2,c)],[(r,c - 1),(r,c - 2)]
                         ,[(r,c + 1),(r,c + 2)],[(r - 1,c),(r - 2, c)]]) road

solve = solve' (addRoad root ([],(0,[]))) where
  solve' result@(road,(numFarms,farms)) =
    if null candidates'
       then [result]
       else do candidate <- candidates'
               solve' candidate
   where candidates' = candidates result

b n = let (road,(numFarms,farms)) = head $ filter ((>=n) . fst . snd) solve
      in (road,(numFarms,nubBy (\a b -> farmOnFarm a b) farms))

Ausgabe, kleines Raster:
Format: (Straße / n, (numFarms, Farmen))

*Main> b 8
([(5,5),(5,4),(6,6),(4,6),(5,6),(4,8),(3,7),(4,7),(2,7),(2,6),(1,7)]
,(8,[(2,4),(3,8),(5,9),(8,6),(6,7),(5,2),(4,4),(7,4)]))
(0.62 secs, 45052432 bytes)

Diagram (O's are roads):

     X
    XXX
   XXXXX
  XXXOXXX
 XXOOOXXXX
XXXXXOOOXXX
 XXXXXOXXX
  XXXOOXX
   XXXO

Ausgabe, großes Raster:
Format: (Straße / n, (numFarms, Farmen))

*Main> b 30
([(9,16),(9,17),(13,8),(13,7),(16,10),(7,6),(6,6),(9,3),(8,4),(9,4),(8,5)
 ,(8,7),(8,6),(9,7),(10,8),(10,7),(11,8),(12,9),(12,8),(14,9),(13,9),(14,10)
 ,(15,10),(14,11),(13,12),(14,12),(13,14),(13,13),(12,14),(11,15),(11,14)
 ,(10,15),(8,15),(9,15),(8,14),(8,13),(7,14),(7,15),(5,14),(6,14),(5,12)
 ,(5,13),(4,12),(3,11),(4,11),(2,11),(2,10),(1,11)]
,(30,[(2,8),(4,9),(6,10),(4,13),(6,15),(7,12),(9,11),(10,13),(13,15),(15,13)
     ,(12,12),(13,10),(11,9),(9,8),(10,5),(8,2),(10,1),(11,3),(5,5),(7,4),(7,7)
     ,(17,8),(18,10),(16,11),(12,6),(14,5),(15,7),(10,18),(8,16),(11,16)]))
(60.32 secs, 5475243384 bytes)

*Main> b 31
still waiting....

1
2018-06-26 23:26



Ich weiß nicht, ob diese Lösung Ihre Anzahl an Farmen maximiert, aber Sie können versuchen, sie auf eine normale Art und Weise zu setzen: Sie können sie horizontal oder vertikal zuweisen. Sie können 2 Spalten (oder Zeilen) zusammenhalten, um die bestmögliche Dichte von Farmen zu erzielen. Sie sollten nur darauf achten, dass 1 Abstand oben / unten (oder links / rechts) bleibt.

Wenn Sie keine weitere Spalte (Zeile) hinzufügen können, überprüfen Sie, ob Sie einige Farmen in der Nähe des Gitters platzieren können.

Ich wünschte, es könnte dir helfen!


0
2018-06-25 13:01