1. Dom
  2. Pytanie i odpowiedź
  3. maksymalna liczba kostek domina może być umieszczona wewnątrz figury

maksymalna liczba kostek domina może być umieszczona wewnątrz figury

2011-01-24 7 views
11

Załóżmy, że pewna figurka na kwadratowym papierze. Boki postaci idą prosto na linie kwadratowego papieru. Figura może mieć dowolny (nawet wypukły) kształt. Jak znaleźć maksymalną liczbę kostek domina (1x2 prostokątny), które można umieścić na tej figurze. Niedozwolone jest umieszczanie domina nad innym. Dozwolone jest umieszczanie domina tylko w taki sposób, gdy jego boki spoczywają dokładnie na liniach kwadratowego papieru.maksymalna liczba kostek domina może być umieszczona wewnątrz figury

Źródło

2011-01-24 Sergey Demyanov

+1

co pan próbował dowiedzieć się samemu? jaki jest dokładnie twój problem? czy możesz podać kilka przykładów? czy to zadanie domowe? – oezi

+0

to nie jest praca domowa, dostałem ten problem od mojego przyjaciela, próbowałem rozwiązać go za pomocą ołówka i papieru i nie mogłem. Teraz nie znam żadnego rozwiązania poza brutalną siłą. Próbowałem kilku euristyki, ale zawsze istnieje przykład, kiedy moje rozwiązanie nie jest najlepsze. –

+0

@Sega: musisz podać pytanie bardziej precyzyjnie lub prawdopodobnie zostanie ono zamknięte. W jaki sposób definiuje się na przykład granicę? –

Odpowiedz

14

Wygląda jak maximum cardinality matching problem in a bipartite graph. Kwadraty są wierzchołkami, a kostki domina są krawędziami, które należą do dopasowania.

Aby zobaczyć, że wykres jest dwustronny, wyobraź sobie kwadraty malowane szachownicą. Czarne jedyne sąsiadujące białe i na odwrót.

Źródło

2011-01-24 10:49:40

+3

+1 Piękny. Skopię się za to, że tego nie widziałem. :-) – templatetypedef

+0

wow, piękne! wydaje się być poprawne! –

+0

Czy to rozwiązanie można uogólnić? Co jeśli domeny są na przykład 3x1 lub 4x2? – templatetypedef

0

można sklasyfikować kwadraty przez liczbę wolnych sąsiednich kwadratów jako typ 0, 1, 2, 3 lub 4.

Uważam, że powinno działać:

  1. znaleźć typ 1 kwadrat, umieścić tam domina w jedyny możliwy sposób i powtórzyć

  2. innego, znaleźć wolny narożniku utworzonym przez dwie przyległe typu 2 i 3 kwadraty, tam miejsce domina i przejdź do 1

  3. indziej umieścić domino w każdym typie 2 placu i iść do 1

  4. skończysz

Źródło

2011-01-24 11:13:17 salva

+0

Tak, to jest zasadniczo to, co robi najprostszy algorytm maksymalnego dopasowania. –

Powiązane problemy

 Powiązane problemy