Znajdowanie kształtów w szyku 2D, a następnie optymalizacja

Właśnie dostałem pozwolenie na zdjęcie ... Poniższy obraz z mojej gry pokazuje niektóre zaciemnione bloki, które zostały rozpoznane jako część kształtu litery „T”. Jak widać, kod przyciemnił bloki czerwonymi plamami i nie widział kształtów „T” z zielonymi konturami.

Mój kod zapętla się przez x / y, zaznacza bloki jako używane, obraca kształt, powtarza, zmienia kolor, powtarza.

Zacząłem próbować naprawić to sprawdzanie z wielką obawą. Obecny pomysł polega na:

• wykonaj pętlę przez siatkę i zanotuj wszystkie wystąpienia wzorca (NIE zaznaczaj bloków jako używane) i umieszczaj je w tablicy
• ponownie zapętlić siatkę, tym razem zauważając, które bloki są zajęte przez które wzorce, a zatem które są zajęte przez wiele wzorców.
• ponownie zapętlając siatkę, tym razem zauważając, które wzory blokują które wzory

Tyle wydaje się słuszne ... Co mam teraz zrobić?

Myślę , że musiałbym

• wypróbuj różne kombinacje sprzecznych kształtów, zaczynając od tych, które najpierw przeszkadzają w większości innych wzorów. Jak podejść do tego?
• użyj rozumowania, które mówi, że mam 3 sprzeczne kształty zajmujące 8 bloków, a kształty to 4 bloki każdy, dlatego mogę mieć maksymalnie dwa kształty.

(Zamierzam również uwzględnić inne kształty i prawdopodobnie będzie ważenie punktów, które należy wziąć pod uwagę, przechodząc przez kształty będące w konflikcie, ale może to być inny dzień)

Nie sądzę, że to problem z pakowaniem pojemników, ale nie jestem pewien, czego szukać. Mam nadzieję, że to ma sens, dziękuję za pomoc

EDYCJA Pomimo jasności pytania, wydaje się, że wszyscy rozumieli, tak,

Chcę znaleźć maksymalne kształty „T” w każdym kolorze

(ponieważ gdybym dał ci punkty za dwa, a ty zrobiłeś trzy, byłbyś trochę zirytowany)

Zobaczę, czy dobrze to zrozumiałem, czerwone bloki oznaczone są na niebiesko, a algorytm znalazł kształt litery T i oznaczył je na czerwono, czy to prawda? Twoim celem jest znalezienie jak największej liczby kształtów T z blokami tego samego koloru, mam nadzieję, że jak dotąd poprawisz. Obecnie zaznaczasz je po ich znalezieniu, co zmniejsza użyteczność algorytmu (ponieważ możesz nie mieć optymalnego rozwiązania). Planujesz wyszukać wszystkie kształty, a następnie wybrać, które z nich użyć, a które nie. Czy mam jak dotąd rację? Ponieważ chcesz zmaksymalizować liczbę bloków zawartych w kształtach T po zakończeniu algorytmu.

Jeśli mam rację, to moim zdaniem optymalne rozwiązanie dla Twojej sytuacji.

Wykorzystamy programowanie całkowite liniowe.

Myślę, że korzystałem z tego w przeszłości:

http://sourceforge.net/projects/lpsolve/

http://lpsolve.sourceforge.net/5.5/Java/README.html

(Możesz sprawić, żeby działał w wielu językach, użyłem go z PHP, Javą i C)

Będziemy rejestrować każdy możliwy kształt litery T na planszy, a następnie użyć ILP, aby zmaksymalizować liczbę bloków, które są pokryte. ILP jest wykładniczo złożona. Biorąc pod uwagę rozmiar planszy, nie będzie to problemem. Uruchomiłem o wiele bardziej skomplikowane pytania min./maks. Na wykresach z ILP i zajęło to ułamek sekundy do ukończenia i do 30-90 sekund z setkami wierzchołków (w twoim przypadku spada to ułamek sekundy).

Co poleciłbym zrobić:

1. Znajdź wszystkie możliwe kształty linii
2. Znajdź wszystkie przecięcia między kształtami linii tego samego koloru
3. Znajdź wszystkie możliwe kształty T, przeszukując wszystkie skrzyżowania.
4. Zdefiniuj zmienną boolowską w problemie liniowym dla każdego kształtu T ( 0 <= Bi <= 1) Ponieważ wartości są liczbami całkowitymi, pozostawia to 0 lub 1.
5. Utwórz warunki dla każdej pary kształtów T przecinających się ( Bi + Bj <= 1)
6. Funkcja celu będzie (suma bloków w kształcie „T” (i) * Bi)
7. Uruchom solver i przyciemnij kształty T, gdzie odpowiadające im logiczne wartości logiczne wynoszą 1 w optymalnym rozwiązaniu.

To cenna wiedza, często korzystałem z rozwiązań liniowych w projektach roboczych.

ILP jest w zasadzie sposobem rozwiązywania problemów z selekcją, w których chcesz osiągnąć maksimum lub minimum dla niektórych funkcji liniowych.

Możesz przeczytać więcej tutaj, używając Integer Programowanie liniowe, a programowanie liniowe jest takie samo dla programisty, tyle że Integer jest znacznie bardziej złożony dla komputera, co może skutkować długim czasem działania. Nie w twoim przypadku, jest to bardzo proste i w najgorszym przypadku powinno to zająć mniej niż milisekundy.

Myślę, że możesz przeczytać więcej tutaj:

http://en.wikipedia.org/wiki/Integer_linear_programming#Integer_unknowns

To dobrze to wyjaśnia:

http://fisher.osu.edu/~croxton_4/tutorial/

Jest to w zasadzie rozwiązanie problemu decyzyjnego, jak podejmować decyzje, które maksymalizują pożądany rezultat. Zakłada to, że funkcja, która ocenia wynik, jest liniowa, co w twoim konkretnym przypadku. Funkcja, która ocenia wynik w tym przypadku, sumuje bloki dla wszystkich kształtów T, które postanowiłeś przyciemnić.

Matematycznie, jak ustawić zmienne: w naszym obecnym przypadku wartości logiczne (czy przyciemniłem kształt T z indeksem i czy nie) do wartości optymalnych, aby zmaksymalizować pożądany wynik: przyciemnienie jak największej liczby bloków bez przyciemniania przecinających się kształtów T. Tak długo, jak pożądany wynik można obliczyć za pomocą funkcji liniowej, gdy masz ustawione wszystkie zmienne, rozwiąże to. W naszym przypadku sprawdzamy, które kształty T przyciemniliśmy i sumujemy bloki, które obejmują.

Wiem, że nie jest to trywialne, więc jeśli zdecydujesz się na skok, nie wahaj się komentować, a ja opracuję.

Gdy masz już listę wszystkich (prawdopodobnie nakładających się) kształtów T występujących w twojej siatce, pozostajesz z maksymalnym zestawem problemów z pakowaniem .

Zasadniczo jest to problem NP-zupełny. Jednak twoja siatka jest na tyle mała (i zwykle rozpada się na jeszcze mniejsze niezależne podproblemy), że uzyskanie dokładnych rozwiązań może być wykonalne.

Dodatek: Oto podstawowy algorytm wyszukiwania wstecznego śledzenia, który może załatwić sprawę:

function max_packing_recursive ( set A, set S, set M ):
    if |M| < |S| then let M = S;
    for each shape X in A do:
        remove X from A;
        let B = A;
        remove all shapes that intersect with X from B;
        if |M| < |B| + |S| + 1 then:        // upper bound
            let M = max_packing_recursive( B, S + {X}, M );
        end if
        if |M| >= |A| + |S| then return M;  // shortcut
    end for
    return M;
end function

function max_packing( set A ):
    return max_packing_recursive( A, {}, {} );
end function

Tutaj {X, Y, Z}oznacza zespół zawierający elementy X, Yi Z(przy {}czym zbiór pusty), a |Q|oznacza rozmiar zestawu Q.

W funkcji rekurencyjnej zestaw Azawiera kształty dostępne dla pozostałego rozwiązania, Szawiera kształty w bieżącym potencjalnym rozwiązaniu i Mjest jak dotąd maksymalnym rozwiązaniem (które można zapisać jako zmienną globalną zamiast zwracać ją z powrotem łańcuch połączeń). Ważna optymalizacja znajduje się w linii oznaczonej symbolem // upper bound, która przycina gałęzie drzewa wyszukiwania, które nie mogą zwrócić lepszego rozwiązania niż M.

(W rzeczywistości, ponieważ wiemy, że każdy kształt T zawiera dokładnie cztery miejsca, o wiele lepszą górną granicę można uzyskać, zastępując |B|liczbą różnych miejsc objętych kształtami B, podzielonych przez cztery i zaokrąglone w dół (i podobnie |A|w przypadku linia oznaczona // shortcut). Algorytm podany powyżej działa jednak w przypadku dowolnych kolekcji kształtów.)

Możliwą dodatkową optymalizacją, której nie wdrożyłem powyżej, byłoby sprawdzenie na początku funkcji rekurencyjnej, czy Adzieli się na wiele niezależnych podzbiorów, w tym sensie, że żadne kształty w różnych podzbiorach nie nakładają się, a jeśli tak, zastosuj algorytm dla każdego z podzbiorów osobno. (W każdym razie zdecydowanie powinieneś to zrobić przynajmniej raz na najwyższym poziomie przed wywołaniem algorytmu rekurencyjnego). Odpowiednie sortowanie kształtów Aprzed zapętleniem ich, np. W porządku rosnącym według liczby nakładających się kształtów, może również pomóc .