Jaki jest skuteczny algorytm rozwiązywania łamigłówek Jigshaw?

Question

Wczoraj właśnie grałem w Jigshaw Puzzle i zastanawiałem się, jaki algorytm byłby dla niego rozwiązany.

jak człowiek, które następnie etapy gdzie:

1. oddzielny wszystkie elementy w 3 częściach, jednolitego płaską krawędzią, podwójne płaską krawędzią i bez krawędzi przy wszystkich.
2. Oddzielne kawałki płaską krawędzią, tak jak byłyby narożniki obrazu
3. oddzielnych elementów pojedynczej krawędzi, jak to tworzą 4 krawędzi końcowych obrazów
4. Wreszcie, przedmioty bez krawędzi będzie tworzyła wewnętrzną obrazu.
5. Dopasuj kolor i fragmenty obrazu, aby połączyć elementy.

Zastanawiam się, jaki byłby skuteczny algorytm, który sprawnie poradzi sobie z tą układanką i jaką bazę danych zapewni optymalne, wydajne rozwiązanie.

Dzięki.

Answer 1

Rozwiązywanie takich problemów może być zwodniczo skomplikowane, szczególnie jeśli nie ma ograniczeń co do rozmiaru i złożoności układanki.

Oto moje przemyślenia na temat podejścia do pisania programu do rozwiązania takiej łamigłówki.

Istnieją cztery główne fragmenty informacji, które można wykorzystać indywidualnie i wspólnie jako wskazówki do rozwiązywania puzzli:

1. Informacje kształt każdego z kawałków (jak wyglądają ich krawędzie)
2. informacje o kolorze każdego z elementów (sąsiednie elementy będą generalnie gładkie)
3. Informacja o orientacji każdego elementu (gdzie mogą znajdować się krawędzie płaskie i narożne)
4. Ogólny rozmiar i liczba sztuk określają ogólne wymiary o f układanki

Więc jaki rodzaj informacji będzie program zostanie dostarczony - załóżmy, że każdy kawałek układanki jest niewielki prostokątny obraz z informacjami przejrzystości używane do identyfikacji części puzzle, które stanowią nie-prostokątne krawędzie .

Z tego względnie łatwo zidentyfikować cztery elementy narożne (w typowej układance). Mają one dokładnie dwie krawędzie, które mają płaskie kontury (patrz mapa konturu poniżej).

Następnie chciałbym uzyskać informacje na temat kształtu każdej z czterech krawędzi łamigłówki. Ta informacja może być użyta do zbudowania adjacency matrix wskazującej, które elementy pasują do siebie.

Teraz możemy przycinać matrycę przyległości, aby zidentyfikować tylko te elementy, które mają gładkie przejścia kolorów w sąsiedniej konfiguracji. Jest to nieco skomplikowane, ponieważ wymaga poziomu dopasowania rozmytego - ponieważ nie każda granica pikseli do pikseli musi mieć płynne przejścia kolorów.

Używając czterech oryginalnych elementów narożnych, powinniśmy teraz odtworzyć wymiary i pozycje wszystkich elementów układanki.

Dogodną strukturą danych do przedstawiania kształtów krawędzi może być mapa konturowa - zasadniczo zbiór liczb całkowitych reprezentujących przyrostowe delty w odległości od przeciwnej strony obrazu do ostatniego nieprzezroczystego piksela w każdym z czterech boków obrazu kawałek układanki. Pasujące elementy powinny mieć odwzorowane kontury lustrzane.

Answer 2

Zakładając, że nie dostaniesz się do jakiejkolwiek wizji komputerowej, byłoby bardzo małe różnice w przeszukiwaniu całej przestrzeni problemowej, tj. Próbowanie każdego fragmentu, aż jeden pasuje, i powtarzanie. Główną optymalizacją byłoby nie próbowanie tego samego utworu w tym samym miejscu, jeśli wiesz, że nie pasuje. Części boczne/narożne składają się stosunkowo z niewielu części i prawdopodobnie nie można ich było brać pod uwagę przy jakiejkolwiek większej optymalizacji.

Struktura danych prawdopodobnie byłaby podobna do macierzy haszującej, w której można by szybko sprawdzić, czy już wypróbowano element w danej pozycji.

Łatwą optymalizacją, która obejmuje wizje komputerowe, byłoby wypróbowanie kawałków w każdej pozycji po sortowaniu sztuk według stopnia, w jakim ich średni kolor pasuje do sąsiednich pozycji.

To tylko ze szczytu mojej głowy oczywiście.

Answer 3

Upewnij się, że skanujesz część męską/żeńską elementu - spowoduje to zmniejszenie połowy o połowę.

Answer 4

Nie sądzę, że ludzki sposób byłby pomocny w implementacji - komputer może oglądać wszystkie utwory wiele razy na sekundę i nie widzę (dużej) wygranej, kategoryzując elementy w rogu, krawędzi i Wewnętrzne kawałki, zwłaszcza, że ​​są tylko trzy kategorie i mają bardzo różne rozmiary.

Biorąc pod uwagę zestaw obrazów wszystkich elementów, spróbuję wyprowadzić prosty deskryptor dla każdego kawałka lub krawędzi. Deskryptor musi zawierać informacje o szorstkim kształcie i kolorze kawałka lub czterech krawędziach. Biorąc pod uwagę układankę złożoną z 1000 elementów, istnieją 4000 krawędzi i zawsze dwie muszą być równe (ignorując granicę układanki). W konsekwencji deskryptor musi być w stanie odróżnić 2000 krawędzi wymagających co najmniej 11 bitów.

Dzielenie jednego kawałka na wzór szachownicy 3 x 3 z dziewięcioma polami daje trzy kolory na brzeg - z ośmioma bitami na kanał mamy już 72 bity. Najpierw sugerowałem zmniejszenie rozdzielczości kolorów, ale nie wydaje się to dobrym pomysłem - na przykład błękitne niebo może naprawdę czerpać korzyści z wysokiej rozdzielczości kolorów. Zauważ, że obliczenie kolorów prawdopodobnie wymaga oddzielenia kawałka od tła i próby wyrównania krawędzi do osi poziomej i pionowej.

W bardzo jednolitych obszarach, takich jak błękitne niebo, informacja o kolorze prawdopodobnie nie będzie wystarczająca do znalezienia dobrych dopasowań i wymagane będą dodatkowe informacje geometryczne. Próbowałbym opisać kształt krawędzi przez jego curvature lub miarę pochodną. Może próbkowane od dziesięciu do dwudziestu punktów za krawędź. To prawdopodobnie znów polega na separacji tła i wyrównaniu krawędzi.

Wreszcie komputer może wykonać część łatwą - porównaj wszystkie pary deskryptorów krawędzi i znajdź najlepsze pasujące elementy. Najprawdopodobniej proces ten powinien być kontrolowany, aby stał się bardziej lokalny zamiast prostego, najlepszego dopasowania, ponieważ gdy kiedykolwiek znajdziesz kąt (Prawidłowe angielskie słowo? Mam na myśli trzy elementy w kształcie litery L.) masz dwa krawędzie ograniczające kawałek do znalezienia i można wcześnie wyśledzić, jeśli nie można znaleźć dobrego dopasowania (co wskazuje na popełniony błąd lub twardą układankę).

Answer 5

Przechodząc przez to, pomyślałem o interesującym rozwiązaniu, które rozwiązuje to przy rosnących kosztach w serii kroków.

1. Oddziel wszystkie puzzelki na zestawy dwóch. Sprawdź, czy pasują do siebie. Jeśli nie, spróbuj innego kawałka, którego jeszcze nie widziałeś. Jeśli tak, włóż zestaw do właściwego stosu. Powtarzaj, dopóki wszystkie zestawy dwóch nie znajdą dopasowania.

2. Z właściwego stosu połącz zestaw dwójek, aby utworzyć zestaw z zestawami dwójek, tj. {{1,2}, {5,6}}. Sprawdź, czy przynajmniej jeden kawałek układanki z jednego zestawu dwóch pasuje do co najmniej innego elementu układanki z drugiego zestawu dwóch. Jeśli nie, spróbuj innego zestawu dwóch, których jeszcze nie widziałeś. Jeśli tak, połącz oba zestawy w jeden zestaw czterech w prawidłowej orientacji z kawałkiem, który pasowałeś do siebie i ustaw połączony zestaw na prawidłowym stosie. Powtarzaj, aż wszystkie zestawy czterech zostaną znalezione.

3. Powtórz te czynności, aż do ostatniego problemu, w którym zestaw n/2 zostanie połączony z zestawem n/2.

Niezadowalające, jaki byłby czas obliczeń.