Szukam algorytmu - minimalna liczba zbiorów obejmujących wszystkie elementy

Odpowiedz Nowy wątek
2019-07-09 16:24
0

Witam wszystkich. Z góry przepraszam za zawracanie głowy, jeśli rozwiązanie jest "oczywiste", ale jestem samoukiem i wiem, że mam często podstawowe braki. Natomiast pobieżne przejrzenie Cormena i pytania do wujka Google nie dały odpowiedzi.

Problem jaki mam można sprowadzić do czegoś takiego:
Danych jest n zbiorów. Każdy zbiór zawiera różną liczbę liczb od 1 do Nx.
Chodzi o znalezienie minimalnej liczby zbiorów, w których znajdą się wszystkie liczby od 1 do Nx (jeśli jakieś liczby się powtórzą, to nie jest to problem).

Nie chcę gotowca, z przyjemnością sam to napiszę :) Niemniej byłbym wdzięczny za nakierowanie, z czego powinienem tutaj skorzystać? Czy może to problem NP-zupełny? Proszę o pomoc :)

Rozumiem, że znamy liczbę N? Edit: glupie pytanie:), wiadomo, ze znamy. - lion137 2019-07-09 16:38

Pozostało 580 znaków

2019-07-09 16:27
3

https://en.wikipedia.org/wiki/Set_cover_problem

Pozostało 580 znaków

2019-07-09 16:28
1

Ja czegoś nie rozumiem. Zbiorów możesz mieć dowolną ilość, ale nigdzie nie jest powiedziane, że wszystkie licznb z podanego zakresu się w nich będą zawierać. Może być tak, że np. liczba 7 nigdzie się nie pojawi, przez co warunek "znajdą się wszystkie liczby od 1 do Nx" może nigdy nie zostać spełniony.

Czy przypadkiem nie zapomniałeś wspomnieć o jakimś istotnym elemencie zadania? Bo, moim zdaniem, obecnie jest to niemożliwe do ustalenia. Piszesz o możliwych powtórzeniach, ale problemem raczej jest sytuacja odwrotna, czyli brak jakichś wartości.


That game of life is hard to play
I'm gonna lose it anyway
The losing card I'll someday lay
So this is all I have to say

Pozostało 580 znaków

2019-07-09 16:59
1

@cerrato: ten problem to set cover, Jak podlinkowano, po prostu zapomnial dodac. Problem jest na liscie 21 NP hard, wiec moze ktos zazartowal?:)


Dlatego też napisałem "Czy przypadkiem nie zapomniałeś wspomnieć o jakimś istotnym elemencie zadania? " :D - cerrato 2019-07-09 17:05

Pozostało 580 znaków

2019-07-09 17:08
0

Dziękuję za szybkie odpowiedzi.
Nie, nie żartowałem - jak wspominałem, mam braki, więc poza plecakowym i komiwojażerem nie miałem styczności z NP-zupełnymi... Ok, czyli poza przejrzeniem wszystkich możliwości nie da rady na znalezienie "z pewnością" optymalnego rozwiązania ;) Dzięki :)

A moze ktos zazartowal, dajac Ci ten problem:)? - lion137 2019-07-09 17:23

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0