Implementacja algorytmu (grafowego)

Odpowiedz Nowy wątek
2019-09-10 20:30
0

Witajcie!

Liczę na Waszą pomoc. Mam taki oto problem z implementacją algorytmu (grafowego):

Dane wejściowe to przykład stabilnego małżeństwa G = (A ∪ B, E) z niekompletnymi listami i ścisłymi preferencjami. Celem jest obliczenie dopasowania (skojarzenia) M w G, które jest największym popularnym dopasowaniem. Więc chcemy znaleźć część zbioru (partycję) (L, R) i dopasowanie M, które jest dobre w odniesieniu do tej części zbioru i które jest R-doskonałe. Wierzchołki w R mogą być postrzegane jako „poszukiwane” wierzchołki, ponieważ wszystkie są dopasowane w M, a wierzchołki w L są wierzchołkami, które szukają partnerów w R.
Dla wygody będę odnosić się do elementów A i B odpowiednio jako mężczyzn i kobiet. Niech A0 ⊂ A i B0 ⊂ B będą odpowiednio zbiorami tych mężczyzn i kobiet, którzy nie są dopasowani w żadnym stabilnym dopasowaniu G = (A ∪ B, E). Każde stabilne dopasowanie w G pozostawia te same wierzchołki niedopasowane. Niech L1 = A0 ∪ B0. Zauważmy, że L1 jest zbiorem niezależnym. Niech R1 = V \ L1. Rozpoczynamy algorytm od części zbioru (L1, R1).
Algorytm jest iteracyjny, a w każdej iteracji część zbioru (L, R) jest aktualizowana przy użyciu algorytmu akceptacji/odrzucenia Gale-Shapleya* na bieżącym L i R. W ten sposób będziemy używać algorytmu Gale–Shapleya kilka razy w naszym algorytmie. Ten algorytm akceptacji/ odrzucenia (L, R) dla dowolnego L ⊂ A ∪ B i R = V \ L podałem poniżej. Podprogram ten opisuje algorytm Gale – Shapleya na grafie „dwudzielnym” otrzymanym przez umieszczenie L na lewej i R po prawej stronie i zbiór krawędzi ograniczony do E ∩ (L × R); tutaj wierzchołki L „oświadczają się” wierzchołkom R.

Algorytm akceptacji/odrzucenia jest "algorytmem 0", a ten, z którym mam problem, to "Algorytm 1". Poniżej są pseudokody obu algorytmów oraz kod algorytmu 0.

*Algorytm akceptacji/odrzucenia Gale'a-Shapleya polega na kolejnych rundach składania i przyjmowania lub odrzucania ofert. Każdy kawaler i każda panna ma swój ranking (listę preferencji). Każda z panien przyjmuje najlepszą z ofert, ale nie jest to akceptacja ostateczna. W kolejnej rundzie odrzuceni kawalerowie składają kolejne oferty kolejnym pannom ze swoich list. Jeśli któraś z nich otrzyma propozycję korzystniejszą niż ta warunkowo przyjęta wcześniej, może wymienić partnera. Procedura kończy się dopiero wtedy, gdy wszyscy mają swoją parę.

Algorytm 0. Algorytm akceptacji/odrzucenia

M = Ø
while jest jakieś u ∈ L niedopasowane w M, które nie zostało jeszcze odrzucone przez żadnego z kandydatek\kandydatów w R 
do
 u oświadcza się najbardziej preferowanemu kandydatowi\kandydatce v ∈ R, który nie odrzucił u
 if v woli u od M(v) then
 M(v) = u //Więc wierzchołek, który był poprzednim partnerem w M, został teraz odrzucony przez v. 
 else
 v odrzuca u
 end if
end while
Zwróć M

Algorytm 1. Wejście: G = (A ∪ B, E) z listami ścisłych preferencji
Niech S będzie stabilnym dopasowaniem uzyskanym przez algorytm akceptacji/odrzucenia na
(A, B). {To znaczy, mężczyźni proponują, a kobiety decydują.}
Niech L1 = zbiór wierzchołków pozostających niedopasowanymi w S; niech R1 = V \ L1
i = 1

while TRUE do
   oblicz dopasowanie Mi poprzez algorytm akceptacji/odrzucenia na (Li,Ri)
   if Mi jest Ri-doskonałe then zwróć Mi
     niech Ai ⊂ A będzie zbiorem mężczyzn w Ri, którzy są niedopasowani w Mi
   L`i = Li ∪ Ai oraz R`i = V \ L`i 
   oblicz dopasowanie M`i poprzez algorytm akceptacji/odrzucenia na (L`i, R`i)
   if M`i jest R`i-doskonałe then zwróć M`i
   niech Bi będzie zbiorem wierzchołków w R`i pozostających niedopasowanymi przez M`i

   Li+1 = Li ∪ Bi oraz Ri+1 = V \ Li+1
   i = i + 1
end while

Kod algorytmu 0:

#include <cstdio>
#include <cstring>
#include <queue>
#include <stdlib.h>
using namespace std;

// Mężczyźni i kobiety są reprezentowani przez liczby całkowite 1 ... N

// PrefM to lista preferencji wszystkich mężczyzn do wszystkich kobiet.
// PrefM[m][i] = k jeśli k jest na i-tej pozycji na liście preferencji m

// PrefK to lista preferencji wszystkich kobiet do wszystkich mężczyzn.
// PrefK[k][i] = m jeśli m jest na i-tej pozycji na liście preferencji k

// Ranking podaje ranking każdego mężczyzny na liście preferencji każdej kobiety
// Ranking[k][m] = i jeśli PrefK [k] [i] = m

// Partner daje bieżący "związek" każdej kobiety
// Partner[k] = m jeśli k jest obecnie związana z m

// Next podaje indeks następnej kobiety, której ma się oświadczyć wg listy preferencji każdego mężczyzny
// Next[m] = i jeśli m oświadczył się wszystkim k oraz PrefM[m][j] = k dla j = 1 ... i-1, ale nie PrefM[m][i]

int Ranking[505][505], PrefM[505][505], PrefK[505][505], Next[505], Partner[505];

int main()  {
    int T, N, i, j, m, k;

    queue <int> WolniM; //Wolni mężczyźni

    printf("Liczba testow: ");
    scanf("%d", &T);
    while (T--) {
        printf("Liczba kobiet i mezczyzn: ");
        scanf("%d", &N);

        for (i = 1; i <= N; i++) {
            k=i; //scanf("%d", &k);
            printf("Preferencje kobiety nr %d:\n", k);
            for (j = 1; j <= N; j++)
                scanf("%d", &PrefK[k][j]);
        }
        for (i = 1; i <= N; i++) {
            m=i;//scanf("%d", &m);
            printf("Preferencje mezczyzny nr %d:\n", m);
            for (j = 1; j <= N; j++)
                scanf("%d", &PrefM[m][j]);
        }

        for (i = 1; i <= N; i++)
            for (j = 1; j <= N; j++)
                Ranking[i][PrefK[i][j]] = j;

        memset(Partner, 0, N * sizeof(int));

        for (i = 1; i <= N; i++) {
            WolniM.push(i);
            Next[i] = 1;
        }

        while (!WolniM.empty())    {
            m = WolniM.front();
            //printf("\nm=%d Next[m]=%d\n", m, Next[m]);
            k = PrefM[m][Next[m]++];
            //printf("k=%d Next[m]=%d\n", k, Next[m]);
            if (Partner[k] == 0)   {
                Partner[k] = m;
                WolniM.pop();
            } else if (Ranking[k][m] < Ranking[k][Partner[k]])  {
                WolniM.pop();
                WolniM.push(Partner[k]);
                Partner[k] = m;
            }
        }

        printf("\nDobrane pary (m, k):\n");
        for (k = 1; k <= N; k++)
            printf("%d, %d\n", Partner[k], k);
    }
    system("pause");
    return 0;
}

Pozostało 580 znaków

2019-09-11 09:13
3

Problem polega na tym, że masz tylko jedną funkcję i to na dodatek main, przez co nie jesteś w stanie ogarnąć tego co napisałeś.
Podziel problem na mniejsze, pisząc wiele małych funkcji odpowiedzialnych za mniejsze problemy (wczytywanie danych, wypisywanie danych, kolejne etapy algorytmu).
Mało tego, jako że kodujesz w C++ skorzystaj z klas.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 1x, ostatnio: MarekR22, 2019-09-11 09:13

Pozostało 580 znaków

2019-09-16 18:14
0

Większy problem mam np. z tym, jak zakodować sprawdzenie czy dopasowanie (skojarzenie) jest R-doskonałe... :/

Pozostało 580 znaków

2019-09-16 18:41
2
Stachu87 napisał(a):

Większy problem mam np. z tym, jak zakodować sprawdzenie czy dopasowanie (skojarzenie) jest R-doskonałe... :/

No to inaczej.
To, że twój kod jest napisany jako jednolity main, z nazwami symboli, które nam nic nie mówią, powoduje, że nie jesteśmy w stanie przeczytać twojego kodu, bez narażenia się na wielki ból głowy.
Uwierz mi, jeśli podzielisz ten kod na mniejsze fragmenty, nam będzie łątwiej pomóc i tobie też łątwiej bedzie ogarnąć kod.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.

Pozostało 580 znaków

2019-09-16 22:12
0

Powtarzasz się.
Tego kodu nie jest dużo i nie mam problemu z jego ogarnięciem. Symbole wyjaśniłem na początku kodu. Problem jest gdzieindziej.
Skoro jednak się upierasz, to trochę go podzielę, choć niedużo tam jest do dzielenia:

#include <cstdio>
#include <cstring>
#include <queue>
#include <stdlib.h>
using namespace std;

// Mężczyźni i kobiety są reprezentowani przez liczby całkowite 1 ... N

// PrefM to lista preferencji wszystkich mężczyzn do wszystkich kobiet.
// PrefM[m][i] = k jeśli k jest na i-tej pozycji na liście preferencji m

// PrefK to lista preferencji wszystkich kobiet do wszystkich mężczyzn.
// PrefK[k][i] = m jeśli m jest na i-tej pozycji na liście preferencji k

// Ranking podaje ranking każdego mężczyzny na liście preferencji każdej kobiety
// Ranking[k][m] = i jeśli PrefK [k] [i] = m

// Partner daje bieżący "związek" każdej kobiety
// Partner[k] = m jeśli k jest obecnie związana z m

// Next podaje indeks następnej kobiety, której ma się oświadczyć wg listy preferencji każdego mężczyzny
// Next[m] = i jeśli m oświadczył się wszystkim k oraz PrefM[m][j] = k dla j = 1 ... i-1, ale nie PrefM[m][i]

int Ranking[505][505], PrefM[505][505], PrefK[505][505], Next[505], Partner[505];
int T, N, i, j, m, k;

void wczytaj() {
    printf("Liczba kobiet i mezczyzn: ");
    scanf("%d", &N);
    for (i = 1; i <= N; i++) {
            k=i; //scanf("%d", &k);
            printf("Preferencje kobiety nr %d:\n", k);
            for (j = 1; j <= N; j++)
                scanf("%d", &PrefK[k][j]);
        }
    for (i = 1; i <= N; i++) {
            m=i;//scanf("%d", &m);
            printf("Preferencje mezczyzny nr %d:\n", m);
            for (j = 1; j <= N; j++)
                scanf("%d", &PrefM[m][j]);
        }

    for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++)
            Ranking[i][PrefK[i][j]] = j;

    memset(Partner, 0, N * sizeof(int));

    for (i = 1; i <= N; i++) {
            WolniM.push(i);
            Next[i] = 1;
        }
}           

void algorytm0 () {
        queue <int> WolniM; //Wolni mężczyźni

        while (!WolniM.empty())    {
            m = WolniM.front();
            //printf("\nm=%d Next[m]=%d\n", m, Next[m]);
            k = PrefM[m][Next[m]++];
            //printf("k=%d Next[m]=%d\n", k, Next[m]);
            if (Partner[k] == 0)   {
                Partner[k] = m;
                WolniM.pop();
            } else if (Ranking[k][m] < Ranking[k][Partner[k]])  {
                WolniM.pop();
                WolniM.push(Partner[k]);
                Partner[k] = m;
            }
        }
}   
void wypisz() {
    printf("\nDobrane pary (m, k):\n");
        for (k = 1; k <= N; k++)
            printf("%d, %d\n", Partner[k], k);
}
int main()  {

    printf("Liczba testow: ");
    scanf("%d", &T);
    while (T--) {

        wczytaj();
        algorytm0();
        wypisz();

    }
    system("pause");
    return 0;
}
Funkcja wczytaj() nie będzie mogła skorzystać z WolniM jeśli nie wie co to jest - Hodor 2019-09-17 11:38
Zdefiniuj sobie WolniM w mainie i przekazuj jako parametr do wczytaj() i algorytm0() - Hodor 2019-09-17 11:42

Pozostało 580 znaków

2019-09-16 22:18
0

Już widzisz problem?
Nie?
Podziel jeszcze bardziej.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2019-09-16 22:25
0

Bardziej się nie da podzielić.
Zresztą problem jest nie w istniejącym kodzie, ale w implementacji pseudo-kodu, powtarzam jeszcze raz - jak sprawdzić, czy dopasowanie (skojarzenie) jest R-doskonałe?

Pozostało 580 znaków

2019-09-17 08:58
0

No i teraz już widzę bez problemu, widzę jeden błąd:

queue <int> WolniM; //Wolni mężczyźni

        while (!WolniM.empty()) 

pętla nigdy się nie wykonuje.

Offtopic: umiesz korzystać z debuggera? Jeśli nie, to naucz się ASAP.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 1x, ostatnio: MarekR22, 2019-09-17 09:00
Nie mogę tego teraz odpalić, tylko zerknąłem, ale czemu miałaby się ta pętla nigdy nie wykonać? Kilka linijek wcześniej jest do kolejki pushowane - Hodor 2019-09-17 11:32
Ok sorki, patrzyłem na kod z głównego postu. :D - Hodor 2019-09-17 11:35

Pozostało 580 znaków

2019-09-17 21:57
0

Wiedziałem, że mój kod z pierwszego postu jest lepszy... :/
Chyba wystarczy jak kolejkę przeniosę do globalnych:

#include <cstdio>
#include <cstring>
#include <queue>
#include <stdlib.h>
using namespace std;

// Mężczyźni i kobiety są reprezentowani przez liczby całkowite 1 ... N

// PrefM to lista preferencji wszystkich mężczyzn do wszystkich kobiet.
// PrefM[m][i] = k jeśli k jest na i-tej pozycji na liście preferencji m

// PrefK to lista preferencji wszystkich kobiet do wszystkich mężczyzn.
// PrefK[k][i] = m jeśli m jest na i-tej pozycji na liście preferencji k

// Ranking podaje ranking każdego mężczyzny na liście preferencji każdej kobiety
// Ranking[k][m] = i jeśli PrefK [k] [i] = m

// Partner daje bieżący "związek" każdej kobiety
// Partner[k] = m jeśli k jest obecnie związana z m

// Next podaje indeks następnej kobiety, której ma się oświadczyć wg listy preferencji każdego mężczyzny
// Next[m] = i jeśli m oświadczył się wszystkim k oraz PrefM[m][j] = k dla j = 1 ... i-1, ale nie PrefM[m][i]

int Ranking[505][505], PrefM[505][505], PrefK[505][505], Next[505], Partner[505];
int T, N, i, j, m, k;
queue <int> WolniM; //Wolni mężczyźni

void wczytaj() {
    printf("Liczba kobiet i mezczyzn: ");
    scanf("%d", &N);
    for (i = 1; i <= N; i++) {
            k=i; //scanf("%d", &k);
            printf("Preferencje kobiety nr %d:\n", k);
            for (j = 1; j <= N; j++)
                scanf("%d", &PrefK[k][j]);
        }
    for (i = 1; i <= N; i++) {
            m=i;//scanf("%d", &m);
            printf("Preferencje mezczyzny nr %d:\n", m);
            for (j = 1; j <= N; j++)
                scanf("%d", &PrefM[m][j]);
        }

    for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++)
            Ranking[i][PrefK[i][j]] = j;

    memset(Partner, 0, N * sizeof(int));

    for (i = 1; i <= N; i++) {
            WolniM.push(i);
            Next[i] = 1;
        }
}           

void algorytm0 () {

        while (!WolniM.empty())    {
            m = WolniM.front();
            //printf("\nm=%d Next[m]=%d\n", m, Next[m]);
            k = PrefM[m][Next[m]++];
            //printf("k=%d Next[m]=%d\n", k, Next[m]);
            if (Partner[k] == 0)   {
                Partner[k] = m;
                WolniM.pop();
            } else if (Ranking[k][m] < Ranking[k][Partner[k]])  {
                WolniM.pop();
                WolniM.push(Partner[k]);
                Partner[k] = m;
            }
        }
}   
void wypisz() {
    printf("\nDobrane pary (m, k):\n");
        for (k = 1; k <= N; k++)
            printf("%d, %d\n", Partner[k], k);
}
int main()  {

    printf("Liczba testow: ");
    scanf("%d", &T);
    while (T--) {

        wczytaj();
        algorytm0();
        wypisz();

    }
    system("pause");
    return 0;
}

Jednak nie chodzi mi o kod algorytmu 0! Powtarzam kolejny raz, że mam problem z implementacją tego pseudokodu algorytmu 1:

while TRUE do
   oblicz dopasowanie Mi poprzez algorytm akceptacji/odrzucenia na (Li,Ri)
   if Mi jest Ri-doskonałe then zwróć Mi
     niech Ai ⊂ A będzie zbiorem mężczyzn w Ri, którzy są niedopasowani w Mi
   L`i = Li ∪ Ai oraz R`i = V \ L`i 
   oblicz dopasowanie M`i poprzez algorytm akceptacji/odrzucenia na (L`i, R`i)
   if M`i jest R`i-doskonałe then zwróć M`i
   niech Bi będzie zbiorem wierzchołków w R`i pozostających niedopasowanymi przez M`i

   Li+1 = Li ∪ Bi oraz Ri+1 = V \ Li+1
   i = i + 1
end while

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