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.
Problem mam z implementacją Algorytmu 1. Poniżej są pseudokody obu algorytmów oraz kod Algorytmu 0 (w nim powinno być już wszystko OK).
*Algorytm akceptacji/odrzucenia Gale'a-Shapleya (zwany dalej "Algorytmem 0") 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 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;
}