Προβλήματα ανάθεσης στον Κεντρικό Σχεδιασμό: N άτομα για Ν δουλειές

Δημοσιεύω εδώ τον κώδικα / λογισμικό, σε C++, που λύνει προβλήματα ανάθεσης/κατανομής, τυπικά για τον Κεντρικό Σχεδιασμό. Συγκεκριμένα, Ν άτομα εκφράζουν τις προτιμήσεις του για Ν δουλειές. Στο input file input.txt η πρώτη γραμμή περιέχει 3 ακέραιους: αριθμός ατόμων (Ν) αριθμός δουλειών (Ν) αριθμός προτιμήσεων (Μ). Ακολουθούν οι Μ προτιμήσεις σε Μ διαφορετικές γραμμές. Κάθε γραμμή περιέχει 2 ακέραιους: αύξων αριθμός ατόμου (από το μηδέν) αύξων αριθμός δουλειάς. π.χ. 0 4 σημαίνει ότι το πρώτο άτομο (0) προτιμά / μπορεί να κάνει την δουλειά νούμερο 4. Κάθε άτομο μπορεί να εκφράσει όσες προτιμήσεις θέλει για όσες δουλειές θέλει. Αν ένα άτομο δεν εκφράσει προτίμηση το πρόγραμμα θα αποτύχει γιατί προϋπόθεση είναι Ν άτομα να κάνουν Ν δουλειές, 1 δουλειά για κάθε άτομο ακριβώς.

Το πρόγραμμα είναι γραμμένο σε C++ από τον Felix Fung μια μετατροπή από εμένα που αφορά τα εισαγώμενα δεδομένα (input file) για ευκολότερη λειτουργία.

Compile: g++ bpm2.cpp -o bpm2

Εκτέλεση: ./bpm2 input.txt

input.txt είναι τα αρχικά δεδομένα, να ένα παράδειγμα με 5 άτομα, 5 δουλειές και 11 προτιμήσεις (π.χ. το άτομο 0 προτιμά να κάνει την δουλειά 0):


5 5 11
0 0
1 0
1 3
2 0
2 1
3 1
3 2
4 2
4 1
4 3
4 4


/* From https://github.com/flxf/maximum-bipartite-matching
author: flxf (Felix Fung, https://github.com/flxf)
modified: AXP
input.txt input file:
5 5 11
0 0
1 0
1 3
2 0
2 1
3 1
3 2
4 2
4 1
4 3
4 4

run: g++ bpm2.cpp && a.out input.txt
*/
#include
#include
#include
#include
#include

#define uint unsigned int
#define UNMATCHED 0xffffffff
#define MAX_INSTANCE_SIZE 500

using namespace std;

uint size_A, size_B, num_edges;
vector graph[MAX_INSTANCE_SIZE];
uint matched[MAX_INSTANCE_SIZE];
bool visited[MAX_INSTANCE_SIZE];

typedef struct _vertex {
char type;
uint id;
} vertex;

uint vertex_to_uid(vertex v) {
return ((v.type == 'A') ? 0 : size_A) + v.id;
}

vertex uid_to_vertex(uint uid) {
vertex ret;
if (uid < size_A) {
ret = (vertex) { 'A', uid };
} else {
ret = (vertex) { 'B', uid - size_A };
}
ret.type = (uid < size_A) ? 'A' : 'B';
ret.id = (uid < size_A) ? uid : uid - size_A;
return ret;
}

bool augment_path(uint uid) {
visited[uid] = true;

for (uint i = 0; i < graph[uid].size(); i++) {
uint neighbour = graph[uid][i];
if (visited[neighbour]) {
continue;
}

if (matched[neighbour] == UNMATCHED) {
matched[uid] = neighbour;
matched[neighbour] = uid;
return true;
} else if (matched[neighbour] != uid) {
visited[neighbour] = true;
if (augment_path(matched[neighbour])) {
matched[uid] = neighbour;
matched[neighbour] = uid;
return true;
}
}
}

return false;
}

int main(int argc, char **argv) {
if( argc != 2 ){ fprintf(stderr, "Usage : %s input.txt\n\nThe input.txt should contain a first line with N M E (N=number of persons, M=number of jobs, E=number of edges). Then it should contain E lines of 2 integers X Y denoting that person X prefers to do job Y.\n", argv[0]); exit(1); }

char *infile = argv[1];
FILE *INF = fopen(infile, "r");
if( INF == NULL ){ fprintf(stderr, "%s : failed to open file '%s' for reading.\n", argv[0], infile); exit(1); }

fscanf(INF, "%d %d %d\n", &size_A, &size_B, &num_edges);

fill(matched, matched + MAX_INSTANCE_SIZE, UNMATCHED);

vertex vertex_A, vertex_B;
uint uid_A, uid_B;
for (uint i = 0; i < num_edges; i++) {
vertex_A.type = 'A';
vertex_B.type = 'B';
fscanf(INF, "%d %d\n", &vertex_A.id, &vertex_B.id);
fprintf(stdout, "%s : %d) person %d prefers job %d.\n", argv[0], i+1, vertex_A.id, vertex_B.id);
uid_A = vertex_to_uid(vertex_A);
uid_B = vertex_to_uid(vertex_B);

graph[uid_A].push_back(uid_B);
graph[uid_B].push_back(uid_A);
}
fclose(INF);
fprintf(stdout, "%s : done, read %d preferences from file '%s' for a graph of %d persons and %d jobs.\n", argv[0], num_edges, infile, size_A, size_B);
uint size_matching = 0;
for (uint i = 0; i < size_A; i++) {
if (matched[i] == UNMATCHED) {
fill(visited, visited + MAX_INSTANCE_SIZE, false);
if (augment_path(i)) {
size_matching++;
}
}
}

printf("Size of maximum matching: %d\n", size_matching);
for (uint i = 0; i < size_A; i++) {
if (matched[i] != UNMATCHED) {
vertex matched_A = uid_to_vertex(i);
vertex matched_B = uid_to_vertex(matched[i]);
printf("person %d gets job %d\n", matched_A.id, matched_B.id);
}
}

return 0;
}

τέλος κώδικα!
——
ΑΧΠ

Μια σκέψη σχετικά μέ το “Προβλήματα ανάθεσης στον Κεντρικό Σχεδιασμό: N άτομα για Ν δουλειές”

Σχολιάστε

Εισάγετε τα παρακάτω στοιχεία ή επιλέξτε ένα εικονίδιο για να συνδεθείτε:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση /  Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση /  Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση /  Αλλαγή )

Σύνδεση με %s