Pytania otagowane jako set-cover

1
Przekształcanie arbitralnej osłony w osłonę wierzchołków
Podano wykres płaski G=(V,E)G=(V,E)G=(V,E) i niech oznacza jego osadzenie w płaszczyźnie st, każda krawędź ma długość . Mam ponadto zestaw punktów, w których każdy punkt jest zawarty w . Ponadto, dla dowolnego punktu w istnieje z odległością geodezyjną do co najwyżej jeden. (Odległość jest mierzona jako najkrótsza odległość w obrębie …
1
Pokrycie siatki prostokątami
Mamy siatkę . Mamy zbiór prostokątów na tej siatki, każdy prostokąta może być przedstawiony jako -by- binarna matryca . Chcemy pokryć siatkę tymi prostokątami.N 1 N 2 RN1×N2N1×N2N_1 \times N_2N1N1N_1N2N2N_2RRR Czy wersja decyzyjna tego zestawu obejmuje problem NP-zupełny? Dane wejściowe: Collection prostokątów na siatce (rozmiar wejściowy: ) iN 1 N …
1
Znalezienie minimalnego pokrycia podzbioru skończonego produktu kartezjańskiego według produktów kartezjańskich
Biorąc pod uwagę podzbiór iloczynu kartezjańskiego dwóch skończonych zestawów, chciałbym znaleźć jego minimalną osłonę przez zestawy, które same są produktami kartezjańskimi.I×JI×JI \times J Na przykład, biorąc pod uwagę iloczyn między i , mogę obserwować podzbiór i spróbuj pokryć go minimalną liczbą produktów kartezjańskich.I={A,B,C}I={A,B,C}I=\{A,B,C\}J={1,2,3}J={1,2,3}J=\{1,2,3\}{(A,2),(B,3),(B,2)}{(A,2),(B,3),(B,2)}\{(A,2), (B,3), (B,2)\} to zrobić na dwa sposoby: …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.