Autor Wątek: algorytm podziału zbioru na podzbiory  (Przeczytany 1810 razy)

Offline pimp

  • Użytkownik

# Lipiec 04, 2010, 15:03:16
Mamy zbiór S obejmujący N ludzi. Każda osoba ze zbioru S spotkała od 0 do (N-1) innych osób ze zbioru S.
To czy 2 osoby się spotkały określamy przez wywołanie funkcji:
bool have_met(const Person& a, const Person& b);
która ma stały koszt wywołania dla dowolnych osób.

Problem?
1. Wyznaczyć wszystkie pary osób, które się spotkały.
Jest to banalne bo np. można zrobić podwójną pętlę i zebrać wyniki w "prawej górnej" części macierzy osób.
2. Wykorzystać informację o parach znających się osób wyznaczonych w kroku 1 do podziału zbioru S na od 1 do N podzbiorów, takich, że:
a) żadna osoba z podzbioru X nie zna żadnej osoby z pozostałych podzbiorów.
b) 2 osoby znajdują się w tym samym podzbiorze wtedy i tylko wtedy gdy się znają osobiście lub gdy znają się ze sobą ich znajomi (lub znajomi znajomych itd.)

Nie mogę wpaść na to jak wydajnie przeprowadzić ten podział na podzbiory w kroku 2 wykorzystując informację z kroku 1 (czyli bez ponownego wywoływania have_met() ); ???

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Kos

  • Użytkownik
    • kos.gd

# Lipiec 04, 2010, 15:08:47
Skoro masz gotową macierz, to zamiast odpalać na osobach have_met robisz odczyt z boola w odpowiedniego miejsce macierzy.

Offline pimp

  • Użytkownik

# Lipiec 04, 2010, 15:25:20
Skoro masz gotową macierz, to zamiast odpalać na osobach have_met robisz odczyt z boola w odpowiedniego miejsce macierzy.

OK. W tym kodzie wyznaczyłem "macierz" (std::vector<bool> met_results):
class Person
{
};

bool have_met(const Person& a, const Person& b);

#include <vector>


int main(int argc, char* argv[])
{
std::vector<Person> all_people;

std::vector<bool> met_results;
met_results.reserve( all_people.size() * all_people.size() / 2 );

for( std::vector<Person>::const_iterator i( all_people.begin() ); i != all_people.end(); ++i )
{
std::vector<Person>::const_iterator j( i );
++j;
for( ; j != all_people.end(); ++j )
met_results.push_back( have_met(*i, *j) );
}

std::vector< std::vector<Person> > groups_of_people;

return 0;
}

Może pokażesz jak teraz wypełnić std::vector< std::vector<Person> > groups_of_people ?

Offline Xion

  • Redaktor
    • xion.log

# Lipiec 04, 2010, 15:52:00
Problem nr 2 sprowadza się do wyznaczenia składowych spójności grafu, gdzie wierzchołkami są osoby, a krawędzie występują między osobą A i osobą B wtw. gdy A zna B (zakładając, że relacja jest symetryczna). Do tego można wykorzystać jakikolwiek algorytm chodzenia po grafach, np. BFS (breadth first search) lub DFS (depth first search).

Offline pimp

  • Użytkownik

# Lipiec 04, 2010, 17:10:28
Problem nr 2 sprowadza się do wyznaczenia składowych spójności grafu, gdzie wierzchołkami są osoby, a krawędzie występują między osobą A i osobą B wtw. gdy A zna B (zakładając, że relacja jest symetryczna). Do tego można wykorzystać jakikolwiek algorytm chodzenia po grafach, np. BFS (breadth first search) lub DFS (depth first search).

No dobrze, ale konkretniej? I jak w to włączyć wykorzystanie już posiadanych informacji o znających się osobach?
Nie mając zielonego pojęcia o algorytmach grafowych, na szybko skleciłem taki oto algorytm podziału:
std::list<Person> all_people;

std::list< std::list<Person> > groups_of_people;
while ( all_people.size() > 0 )
{
std::list<Person> group;
group.push_back( all_people.front() );
all_people.pop_front();
for ( std::list<Person>::const_iterator i( group.begin() ); i != group.end(); ++i )
for ( std::list<Person>::const_iterator j( all_people.begin() ); j != all_people.end(); )
if ( have_met( *i, *j ) )
{
group.push_back( *j );
all_people.erase( j++ );
}
else
++j;
groups_of_people.push_back( group );
}
Ale ciągle korzystam tu z have_met() bo nie wiem jak zbudować ten algorytm żeby korzystał z już wyznaczonej macierzy "znania się" (tak, relacja znania się jest symetryczna).

Offline Pan Hania

  • Użytkownik

# Lipiec 04, 2010, 17:34:14
Dobra, dla mnie to trzeba po prostu użyć union-finda. Będzie to mniej więcej wyglądać tak (pseudokod):
std::vector < std::pair < int, int > > pary;

//generowanie listy par
od i = 1  do N:
od j = 1 do N:
if (i != j and have_met(i, j)):
pary.push_back(std::make_pair(i, j));

//algorytm union-find, implementacje masz np. na Wikipedii
dla kazdego p w pary:
union(p.first, p.second);

Offline Knopi

  • Użytkownik

# Lipiec 05, 2010, 02:44:58
1. Robisz macierz sąsiedztwa
2. Robisz listę wszystkich osób( wierzchołków )
3. Robisz DFSa. Wszystkie wierzchołki przez które przejdzie należą do zbioru Ai ( wszystkie te wierzchołki się znają ) i usuwasz je z tej listy.
4. Dopóki lista nie jest pusta powtarzasz krok 3 wyznaczając kolejne takie zbiory.
5. Dostajesz tyle zbiorów ile razy wykonałeś krok 3.