Implementacja algorytmu (grafowego)

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;
}

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.

0

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

3
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.

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;
}

0

Już widzisz problem?
Nie?
Podziel jeszcze bardziej.

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?

1

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.

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! Tak jak pisałem wcześniej, 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
0

Więc nikt nie jest w stanie mi pomóc? :/

0

Z algorytmem 1 dałem sobie spokój na razie.

Postanowiłem jednak program z algorytmem 0 przerobić tak, żeby wczytywał dane z pliku. W czasie kompilacji nie ma błędów ani ostrzeżeń, jednak w trakcie pojawia się błąd "naruszenia ochrony pamięci".

#include <cstdio>
#include <cstring>
#include <queue>
#include <stdlib.h>
#include <fstream>
#include <cstdlib>
#include <iostream>
#include <string>
#include <sstream>

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() {
		
		string filename = "plik.txt";
		ifstream file;
		file.open(filename.c_str());

		string s;
		getline(file, s);
		stringstream ss(s);
		ss.str(s);
		ss.clear();
		ss >> N;
		
		
		for (i = 1; i <= N; i++) {
            //k=i; //scanf("%d", &k);
            //printf("Preferencje kobiety nr %d:\n", i);
			for (j = 1; j <= N; j++)
                //scanf("%d", &PrefK[i][j]);
				getline(file, s);
				ss.str(s);
				ss.clear();
				ss >> PrefK[i][j] >> PrefM[i][j];
        }
		
		file.close();

    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;
}

Pewnie jest coś nie tak z tym fragmentem funkcji wczytaj():

string filename = "plik.txt";
		ifstream file;
		file.open(filename.c_str());

		string s;
		getline(file, s);
		stringstream ss(s);
		ss.str(s);
		ss.clear();
		ss >> N;
		
		
		for (i = 1; i <= N; i++) {
            //k=i; //scanf("%d", &k);
            //printf("Preferencje kobiety nr %d:\n", i);
			for (j = 1; j <= N; j++)
                //scanf("%d", &PrefK[i][j]);
				getline(file, s);
				ss.str(s);
				ss.clear();
				ss >> PrefK[i][j] >> PrefM[i][j];
        }
		
		file.close();

plik.txt wygląda tak:

10
2 1
1 2
4 3
3 4
6 5
5 6
8 7
7 8
10 9
9 10

Bardzo proszę o pomoc :)

0
Stachu87 napisał(a):

...
Bardzo proszę o pomoc :)
Nie ma możliwości ci pomóc, ponieważ ignorujesz każdą próbę pomocy.

0
Stachu87 napisał(a):

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
  1. Co to znaczyć być R[i] doskonałym?
  2. L2[i] = L[i] ∪ A[i] oraz R2[i] = V \ L[i] . Nie ma to sensu. Czym jest L2[i] (Twoje L'i)? L[i] jest już zbiorem wszystkich niedopasowanych wierzchołków wg Twoje definicji. Po co powiększać go o niedopasowanych mężczyzn z tej samej iteracji?
  3. niech B[i] będzie zbiorem wierzchołków w R2[i] pozostających niedopasowanymi przez M2[i]
    L[i+1] = L[i] ∪ B[i] oraz R[i+1] = V \ L[i+1]
    Czyli co, zbiór wierzchołków niedopasowanych L ma tylko rosnąć w kolejnych iteracjach? Nigdy się nie kurczy?
  4. Masz 2 wywołania algorytmu akceptacji w jednej iteracji. Może po prostu wytłumacz czym się różnią, ponieważ ten pseudokod nie jest czytelny.
0
_13th_Dragon napisał(a):
Stachu87 napisał(a):

...
Bardzo proszę o pomoc :)
Nie ma możliwości ci pomóc, ponieważ ignorujesz każdą próbę pomocy.

Ile razy mam powtarzać, że ja NIE IGNORUJĘ żadnej próby pomocy?!
Wtedy nie zrozumieliście w czym mam problem, a teraz już chodzi o coś zupełnie innego: https://4programmers.net/Forum/1634545
Proszę uprzejmie o pomoc i proszę bez złośliwości.

0
nalik napisał(a):
  1. Co to znaczyć być R[i] doskonałym?
  2. L2[i] = L[i] ∪ A[i] oraz R2[i] = V \ L[i] . Nie ma to sensu. Czym jest L2[i] (Twoje L'i)? L[i] jest już zbiorem wszystkich niedopasowanych wierzchołków wg Twoje definicji. Po co powiększać go o niedopasowanych mężczyzn z tej samej iteracji?
  3. niech B[i] będzie zbiorem wierzchołków w R2[i] pozostających niedopasowanymi przez M2[i]
    L[i+1] = L[i] ∪ B[i] oraz R[i+1] = V \ L[i+1]
    Czyli co, zbiór wierzchołków niedopasowanych L ma tylko rosnąć w kolejnych iteracjach? Nigdy się nie kurczy?
  4. Masz 2 wywołania algorytmu akceptacji w jednej iteracji. Może po prostu wytłumacz czym się różnią, ponieważ ten pseudokod nie jest czytelny.

Tym algorytmem już wprawdzie przestałem się zajmować, o czym wspomniałem w ostatnim poście tutaj (https://4programmers.net/Forum/1634545), jednak bardzo dziękuję, że w końcu ktoś zrozumiał w czym miałem na początku problem :) Więc dziękuję nalik za chęć pomocy :)

  1. Dopasowanie (skojarzenie) M jest R-doskonałe, jeśli każdy wierzchołek R jest dopasowany w M.
  2. L2[i] to suma: zbioru wierzchołków niedopasowanych w S (algorytm akceptacji/odrzucenia przed wejściem w pętlę) oraz zbioru mężczyzn z R[i] niedopasowanych w M[i] (z i-tej iteracji w pętli)
  3. W którejś iteracji nie będzie już niedopasowanych wierzchołków.
  4. Zauważ, że drugie wywołanie algorytmu jest na innych zbiorach.

Ogólnie algorytm pochodzi z załączonego niżej artykułu naukowego (zaczyna się na 10 stronie). W tłumaczeniu na polski, jego opis wygląda tak:

Początkowa lewa strona L1 jest podzbiorem wierzchołków pozostawionych niedopasowanych w każdym stabilnym dopasowaniu G. Dopasowanie M1 uzyskane przez uruchomienie algorytmu akceptecji/odrzucenia Gale'a – Shapleya między L1 a R1 = V \ L1 będzie dobre w odniesieniu do (L1, R1). Właściwość (1) dobrego dopasowania pasuje przez samą naturę algorytmu akceptacji/odrzucenia i właściwość (2) dobrego dopasowania dowolnego dopasowania M1 ⊆ L1 × R1 jest prawdziwa, ponieważ L1 jest niezależnym zbiorem w G i stąd w GM.
Jeśli każdy wierzchołek R1 otrzymuje propozycję, to mamy nasze pożądane dopasowanie. W przeciwnym razie wejdziemy w drugi etap pierwszej iteracji. W drugim etapie przenosimy wszystkich niedopasowanych mężczyzn z R1 do L1 i uruchamiamy algorytm akceptacji/odrzucenia między nowym L1 (nazwany zbiorem L'1) i nowym R1 (nazwany zbiorem R'1), aby obliczyć M'1 Pokażę, że M'1 jest dobre w odniesieniu do nowej części zbioru lewej-prawej.
Jeśli M'1 dopasowuje wszystkie wierzchołki po prawej stronie, jest to pożądane dopasowanie. W przeciwnym razie niech B1 oznacza zbiór niedopasowanych wierzchołków (kobiet) [jak pokazano poniżej] po prawej stronie, którzy nie są dopasowani przez M'1. Ustawiamy L2 = L1 ∪ B1 (nasz stary L1 wraz z B1) i R2 = R1 \ B1 (nasz stary R1 z usuniętym B1). Zauważmy, że niedopasowani mężczyźni, którzy przenieśli się z prawej strony na lewą w drugim etapie pierwszej
iteracji powracają na prawą. Ich celem było zidentyfikowanie zbioru B1. Algorytm przechodzi do następnej iteracji.
W i-tej iteracji tego algorytmu uruchamiamy najpierw algorytm Gale'a – Shapleya na (Li, Ri), aby uzyskać dopasowanie Mi. Jeśli Mi jest Ri-doskonałe, to algorytm zwraca to dopasowanie. W innym wypadku niech Ai będzie zbiorem mężczyzn w Ri, którzy nie mają dopasowania w Mi. Przypisujemy L'i = Li ∪ Ai i uruchamiamy algorytm Gale'a – Shapleya na (L'i, V \ L'i), aby uzyskać dopasowanie M'i. Jeśli M'i dopasuje wszystkie wierzchołki po prawej stronie, zwracane jest M'i. Inaczej niech Bi będzie zbiorem niedopasowanych wierzchołków (kobiet) [jak udowodniono poniżej] po prawej stronie. Przypisujemy Li+1 = Li ∪ Bi i rozpoczynamy następną iterację.
Oto jak działa ten algorytm na przykładzie
Rysunek

  • Zbiór L1 = {a1, a4, b3, b6} (zestaw wierzchołków pozostawionych niedopasowanymi w stabilnym dopasowaniu S). Dopasowanie M1 to {(a1, b1), (a4, b4), (a3, b3), (a6, b6)}.
  • Mężczyźni a2 i a5, którzy nie mają dopasowania po prawej stronie, przesuwają się w lewo w drugim etapie pierwszej iteracji i mamy L'1 = L1 ∪ {a2, a5} = {a1, a4, b3, b6, a2, a5}. Daje to dopasowanie M'1 = {(a4, b4), (a3, b3), (a6, b6), (a2, b1), (a5, b5)}.
  • Wierzchołek b2 jest jedynym niedopasowanym wierzchołkiem po prawej stronie. Przypisujemy więc L2 = L1 ∪ {b2} = {a1, a4, b3, b6, b2}. Otrzymujemy dopasowanie M2 = {(a1, b1), (a3, b3), (a4, b4), (a6, b6), (a2, b2)}.
  • Mężczyzna a5, który nie ma dopasowania po prawej stronie, przesuwa się w lewo w drugim etapie drugiej iteracji i mamy L'2 = L2 ∪ {a5} = {a1, a4, b3, b6, b2, a5} . Daje to dopasowanie M'2 = {(a1, b1), (a3, b3), (a4, b4), (a6, b6), (a2, b2), (a5, b5)}. To dopasowanie to R'2-doskonałe, stąd mamy pożądane dopasowanie i algorytm kończy się.
0
Stachu87 napisał(a):
  1. Dopasowanie (skojarzenie) M jest R-doskonałe, jeśli każdy wierzchołek R jest dopasowany w M.
   if Mi jest Ri-doskonałe then zwróć Mi
...
   if M`i jest R`i-doskonałe then zwróć M`i
...

Nic z tego nie wynika. Lepiej byś podał artykuł po angielsku, bo tłumaczenie niezrozumiałe.

0

Załączyłem artykuł do tamtego postu. Nie wiem, dlaczego się nie załączył...

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