Optymalizacja dyskretna dla funkcji macierzy

Question

To jest pytanie optymalizacyjne, które uprościłem z bardziej konkretnego problemu, który mam, ale nie jestem pewien, gdzie dokładnie ten problem został sklasyfikowany, ani metody uzyskania rozwiązanie (brute force, symulowane wyżarzanie, programowanie liniowe?). Każda pomoc lub referencje są doceniane!

Mamy dwie macierze MXN M1 i M2, gdzie każdy wpis jest 1 lub 0.

Próbuję dostać się z macierzy M1 do macierzy M2 w najkrótszym możliwym czasie.

Celem jest zmniejszenie całkowitego czasu, w którym czas jest zdefiniowany przez następujące:

• 0 -> 1 przejścia = 1S
• 1 -> 0 przejście = 0,1 s

Jedynym sposobem zmiany matrycy jest wybór zestawu wierszy i kolumn, a wszystkie elementy na przecięciach zaznaczonych wierszy i kolumn zostają przełączone na 0/1, a całe przejście zajmuje czas określony powyżej.

przykład:

 
M1 
1 1 1 
1 1 0 
1 0 0 

M2 
0 0 1 
0 1 1 
1 1 1 

pierwszej iteracji:

1. Wybierz wiersze 2 i 3, a kolumny 2 i 3 M1.

2. Konwersja wszystkie przecinające się elementy do 1

   • trwa 1s

 
M1 
1 1 1 
1 1 1 
1 1 1 

drugiej iteracji:

1. wybrać wiersze 1, a kolumny 1 i 2 z M1.

2. Konwersja wszystkie elementy przecinające się do 0

   • trwa 0,1 s

 
M1 
0 0 1 
1 1 1 
1 1 1 

trzeci iteracji:

1. Wybór rzędu 2 i kolumna 1 M1.

2. konwersji wybranego elementu do 0

   • trwa 0,1 s

 
M1 
0 0 1 
0 1 1 
1 1 1 

W tym przypadku, całkowity czas jest 1.2s.

Answer 1

W przypadku podanych rozmiarów wygląda na to, że bardzo trudno będzie je zindeksować. Tak czy inaczej, oto kilka pomysłów.

Kiedy komórka musi się zmienić z 0 na 1, będę pisać +, kiedy musi się zmienić w innym kierunku będę pisać -, a kiedy musi zostać jak jest, będę pisać albo 0 albo 1 (tj. czymkolwiek jest obecnie). Np. wystąpienie problemu w kwestii OP wygląda jak

- - - 1 
- - 1 + 
- 1 + + 
1 + + + 

Rozważmy nieco łatwiejszy monotonia wersję problemu, w którym nigdy nie zmieni komórkę dwukrotnie.

• Generalnie wymaga dużo więcej ruchów, ale daje użyteczny punkt początkowy i górną granicę.
• W tej wersji problemu nie ma znaczenia, w jakiej kolejności wykonujemy ruchy.
• Proste odmiany mogą być bardziej skuteczne jako heurystyki, np. wykonywanie niewielkiej liczby początkowych ruchów 0-1>, w których każda komórka + jest zmieniana na 1, a inne komórki również mogą być zmienione, a następnie seria ruchów 1-> 0 w celu zmiany/naprawienia wszystkich innych komórek.

zmniejszanie problemu bezpiecznie

[EDIT 12.11.2014: Fixed 3rd poniżej regułę. Niestety to może zastosować znacznie rzadziej]

Poniższe sztuczki nigdy spowodować rozwiązanie stać suboptimal i może uprościć problem.

• Usuń wszystkie wiersze lub kolumny, które zawierają nie + komórek beta lub - -cell: żaden ruch nigdy z nich nie skorzysta.
• Jeśli istnieją identyczne wiersze lub kolumny, zwiń je: niezależnie od tego, co robisz w tym pojedynczym zwiniętym wierszu lub kolumnie, możesz zrobić to we wszystkich wierszach lub kolumnach oddzielnie.
• Jeśli istnieje jakikolwiek wiersz z tylko jednym + komórek beta i bez 1-cells, można od razu rozwiązać wszystkie + komórek beta w całej kolumny zawierające go jednym 0-> 1 ruch, gdyż w monotonnym problem nie jest możliwe, aby naprawić tę komórkę w tym samym ruchu 0-> 1, jak każda inna komórka w innej kolumnie. Podobnie z zamienionymi rzędami i kolumnami oraz z pojedynczą komórką-komórkową i bez komórek--.

Wielokrotne stosowanie tych zasad może przynieść dalsze uproszczenie.

bardzo proste heurystyczne

można skorygować cały wiersz lub kolumnę + lub - komórkach p, w jednym ruchu. Dlatego zawsze możliwe jest rozwiązanie problemu za pomocą 2 * min (szerokość, wysokość) ruchów (2 jest tam, ponieważ możemy potrzebować zarówno ruchów 0-> 1 i 1-> 0). Nieco lepszym rozwiązaniem byłoby chciwie znaleźć wiersz lub kolumnę z większością komórek wymagających korekty i poprawić ją jednym ruchem, swobodnie przełączając między wierszami i kolumnami.

Najlepszy możliwy ruch

Załóżmy, że mamy dwa + komórek beta (i, j) (k, l) z í < = k i j < = l. Można je zmieniać w tym samym ruchu 0-> 1 dokładnie wtedy, gdy oba ich "przeciwległe rogi" (i, l) i (k, j) są albo + lub 1. Zwróć też uwagę, że jeśli jeden lub oba (i, j) i (k, l) są równe 1 (zamiast +), to można je włączyć do tego samego ruchu, nawet jeśli ruch ten nie miałby wpływu na jedno lub oba z nich. Jeśli więc zbudujemy wykres G, w którym mamy wierzchołek dla każdej komórki i krawędź między dwoma wierzchołkami (i, j) i (k, l) za każdym razem (i, j), (k, l), (i, l) i (k, j) wszystkie są albo + albo 1, clique na tym wykresie odpowiada zestawowi komórek, które mogą być wszystkie zmienione na (lub pozostawione na) 1 w jednym ruchu 0-> 1. Aby znaleźć najlepszy możliwy ruch - to jest ruch, który zmienia najbardziej możliwe 0s na 1s - nie chcemy mieć maksymalnej wielkości kliki na wykresie; to, czego naprawdę chcemy, to klika zawierająca największą liczbę wierzchołków komórek +. Możemy sformułować ILP że znajdzie to, używając 0/1 zmienną x_i_j reprezentować czy wierzchołek (i, j) jest w kliki:

Maximise the sum over all variables x_i_j such that (i, j) is a `+`-cell 
Subject to 
    x_i_j + x_k_l <= 1 for all i, j, k, l s.t. there is no edge (i, j)-(k, l) 
    x_i_j in {0, 1} for all i, j 

Ograniczenia uniknięcia parę wierzchołków z obu wchodzących jeśli nie ma między nimi żadnej krawędzi, a funkcja celu próbuje znaleźć tak duży podzbiór wierzchołków komórek jak to możliwe, który je spełnia.

Oczywiście ta sama procedura działa w przypadku wyszukiwania ruchów o wartości od 1 do 0.

(Będziesz już napotkasz problemy po prostu budujących wykres tej wielkości: z N i M około 1000, istnieje około miliona wierzchołków, a nawet milion milionów krawędziach i znalezienie maksymalnej kliki jest NP. -hard problemem, więc jest to powolny nawet na wykresach z setkami krawędzi ...)

Najmniej możliwych ruchów

podobne podejście można powiedzieć nam najmniejszą liczbę 0-> 1 (lub 1-> 0) wymagane ruchy, a jednocześnie daj nam reprezentatywną komórkę z każdego ruchu. Tym razem szukamy największego independent set w tym samym wykresie G:

Maximise the sum over all variables x_i_j such that (i, j) is a `+`-cell 
Subject to 
    x_i_j + x_k_l <= 1 for all i, j, k, l s.t. there is an edge (i, j)-(k, l) 
    x_i_j in {0, 1} for all i, j 

Wszystko zmieniło się problemem było to, że „nie ma krawędź” zmieniono na „krawędź”. Znajduje to teraz (może być więcej niż jeden) zestaw maksymalnych rozmiarów wierzchołków komórek, które nie dzielą między sobą krawędzi. Żadna para takich komórek nie może być zmieniona przez ten sam ruch 0-> 1 (bez zmiany komórki 0 lub -- komórki na 1, której zakazujemy w monotonnej wersji problemu, ponieważ wtedy musiałaby być zmieniane po raz drugi), więc jednak wiele wierzchołków jest zwracanych, a przynajmniej tyle osobnych ruchów 0-> 1 jest wymaganych. A ponieważ poprosiliśmy o niezależny zestaw o maksymalnej wartości, nie są potrzebne żadne ruchy (jeśli więcej ruchów wymagałoby potrzebnych, byłby większy niezależny zestaw z wieloma wierzchołkami).