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

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

Rejestracja: 13 lat temu

Ostatnio: 1 rok temu

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

Rejestracja: 1 rok temu

Ostatnio: 10 godzin temu

3

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

Pozostało 580 znaków

2019-07-09 16:28
Moderator Kariera

Rejestracja: 2 lata temu

Ostatnio: 45 sekund temu

Lokalizacja: Poznań

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.


Naczelny forumowy hejter Apple

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

Rejestracja: 3 lata temu

Ostatnio: 17 godzin temu

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

Rejestracja: 13 lat temu

Ostatnio: 1 rok temu

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

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