Uzyskanie minimalnej liczby ogonków monet po wielokrotnym wielokrotnym przewróceniu całego wiersza lub kolumny

Question

Jeśli monety są umieszczane na siatce i można odwracać tylko cały wiersz lub kolumnę, w jaki sposób można odwrócić monety, aby uzyskać minimalną liczbę ogony.

Próbowałem użyć chciwego rozwiązania, w którym odwracam wiersz lub kolumnę, w której liczba ogonków jest większa od głów i powtarzam proces, dopóki nie zmieni się liczba. Ale odkryłem, że takie podejście nie daje mi pewnego razu optymalnego rozwiązania.

HHT 
THH 
THT 

Na przykład, jeśli monety są umieszczone jak wyżej i przerzucić monety w poniższy sposób uzyskana wartość wynosi 3, ale w rzeczywistości odpowiedź brzmi 2.

1. Flip the row 3 
HHT 
THH 
HTH 
2. Then there exists no row or column where the number of tails are greater than that of heads. 
3. But if I flip the column 3, row 3, column 1, there exists a solution whose value is 2. 
THH 
HHT 
HHH 

Więc myślę powyższy algorytm nie działa. Jakie podejście i jakiego algorytmu należy użyć?

Answer 1

Najpierw zwróćmy uwagę, że nie ma sensu przekręcać tego samego wiersza lub kolumny dwa lub więcej razy (lepszym rozwiązaniem jest zawsze odwrócenie wiersza/kolumny od zera lub jeden raz), a kolejność odwracamy wiersze lub kolumny nie ma znaczenia, więc możemy opisać rozwiązanie jako tablicę o długości 2N. Jeden bit na wiersz i jeden bit na kolumnę. Włącz, jeśli raz odwrócimy ten wiersz/kolumnę, jeśli odwrócimy go zero razy.

Musimy więc wyszukiwać 2^(2N) możliwych rozwiązań, preferując rozwiązania o większej liczbie zer.

drugie zauważmy, że dla jednego rozwiązania istnieją cztery możliwe stany monety:

1. Moneta nie zostało przerzuconych (0 koziołki)
2. Moneta została przerzuconych przez jego rząd (1 odwrotną)
3. moneta została odwrócona przez kolumnę (1 przerzutnika)
4. moneta została odwrócona przez zarówno w rzędy i kolumny (2 koziołki)

N otice że stan 1 do 4 wynik w pierwotnej wartości monety

zauważyć również, że stan 2 i 3 w wyniku w przeciwnym pierwotnej wartości monety

start wyrażając pierwotnego stanu monet jako macierz binarna (B). Pole 2N-bitowe jako 2 binarne wektory (R, C) i całkowita liczba ogonów jako funkcja tego f (B, R, C) i całkowita liczba bitów jako funkcja g (V_1, V_2)

Twoim celem jest, aby f> = minimum, minimalizując g.

Myślisz, że jeśli najpierw naprawimy naszą konfigurację R (które wiersze odwrócimy), jak możemy rozwiązać problem tylko dla C (które kolumny przerzucimy)? Innymi słowy, zastanów się nad prostszym problemem polegającym tylko na tym, że wolno odwracać kolumny i nie wolno im odwracać wierszy. Jak rozwiązać ten problem? (wskazówka: DP) Czy możesz teraz rozszerzyć tę stategię na pełny problem?

Answer 2

Nie jestem pewien co do kompletnego algorytmu, ale jedną z rzeczy, które powinieneś zdecydowanie wypróbować, to duża liczba symetrii w twoim problemie.

Wiele różnych konfiguracji monet będzie w rzeczywistości równoważnych, więc można je obracać, odzwierciedlać konfigurację bez zmiany problemu. Co najważniejsze, ponieważ możesz odwrócić cały zestaw przez odwrócenie wszystkich wierszy, szukanie minimalnej liczby ogonków jest równoznaczne z szukaniem minimalnej liczby głów.

w Twoim przypadku, byłoby

HHT 
THH 
THT 

HTT 
TTH 
TTT 

Poprzez przerzucanie kolumnę środkową, a skończysz (wtedy trzeba odwrócić wszystko, oczywiście, jeśli naprawdę potrzebujesz).

Answer 3

Oczywistym rozwiązaniem jest wypróbowanie wszystkich możliwości odwrócenia wiersza lub kolumny. Takich możliwości jest O(2^(2N)). Jednak możemy rozwiązać problem w O(N^2 * 2^N) za pomocą kombinacji chciwości + brutalnej siły.

Generuj wszystkie możliwości odwracania wierszy (O(2^N)) i dla każdej z nich odwróć każdą kolumnę, która ma więcej ogonów niż głów. Weź rozwiązanie, które daje ci minimalne ogony.

To powinno zadziałać. Dodam więcej szczegółów o tym, dlaczego nieco później.

Answer 4

Jednym podejściem byłoby użycie http://en.wikipedia.org/wiki/Branch_and_bound, na przemian z uwzględnieniem nowych pionowych linii i nowych poziomych linii. Istnieje również pewna symetria, którą możesz usunąć - jeśli odwrócisz wszystkie poziome linie i całą pionową linię, skończysz z powrotem tam, gdzie zaczynałeś, więc z odgałęzieniem i granicą możesz równie arbitralnie założyć, że lewa pionowa linia nigdy nie jest odwrócona .

HHT 
THH 
THT 

W tym przykładzie, jeśli założymy, że od lewej pionowa linia nie jest odwrócony, a następnie, jeśli rozgałęzia się na najniższym poziomej linii Znamy wartość skrajnej lewej najmniejszej monety, więc mamy dwa możliwe rozwiązania częściowe - taki, w którym ta pojedyncza znana moneta jest ustalona na ogonach, a ta, w której jest zamocowana na głowach. Jeśli najpierw spróbujemy rozszerzyć częściowe rozwiązanie, w którym pojedyncza znana moneta jest głowicą i odkryjemy, że możemy rozszerzyć to na rozwiązanie, które nie wytwarza żadnych ogonków, wówczas możemy odrzucić wszystkie częściowe rozwiązania produkowane przez rozszerzenie drugiej, ponieważ wszystkie jego potomkowie muszą mieć co najmniej jeden ogon.

Będę następną gałęzią na lewej, ale jednej linii pionowej, która da nam inną znaną monetę, i dalej rozgałęziam się naprzemiennie poziomo i pionowo.

To będzie możliwy sposób na znalezienie dokładnego rozwiązania, jeśli istnieje rozwiązanie prawie idealne lub jeśli stół jest bardzo mały. W przeciwnym razie będziesz musiał przerwać to wcześniej lub sprawić, by pomijał on wiarygodne rozwiązania, aby problem został rozwiązany w rozsądnym czasie, a prawdopodobnie nie uzyskasz dokładnej najlepszej odpowiedzi.