LABORATOR 2
METODA BRANCH AND CUT (B&C)
Exemplu: Problema Pierspico
Inspirată de faimosul Perspico, Miruna se gândeşte la următorul joc: se
dă o matrice cu N linii şi M coloane în care fiecare număr între 0 şi N *
M - 1 apare exact o singură dată. O mutare validă în acest joc constă
din interschimbarea elementului 0 cu unul dintre cei 4 vecini ai săi.
Miruna câştigă dacă reuşeşte să aducă matricea în următoarea
configuraţie:
• pe orice poziţie (x, y), cu excepţia poziţiei (N, M), trebuie să se
găsească valoarea (x - 1) * M + y;
• pe poziţia (N, M) trebuie să se găsească valoarea 0.
Fiind dată o configuraţie a jocului, ajutaţi-o pe Miruna să îl termine. Pe
prima linie din fişierul de intrare [Link] se află două numere
întregi N şi M, având semnificaţia din enunţ. Următoarele N linii vor
conţine câte M numere naturale, reprezentând elementele matricei.
Varianta 1
Date de intrare Date de ieșire
3 3 Se va afișa fiecare soluție obținută
3 8 1 după fiecare mișcare realizată, până la
2 5 0 obținerea soluției:
7 6 4
1 2 3
4 5 6
7 8 0
Varianta 2
Pe prima linie din fişierul de intrare [Link] se află două numere
întregi N şi M, având semnificaţia din enunţ. Următoarele N linii vor
conţine câte M numere naturale, reprezentând elementele matricei.
1 din 7 Profesor A.D.
În fişierul de ieşire [Link] se vor scrie mai multe numere naturale
din intervalul [1, 4], reprezentând mutările efectuate, codificarea lor
fiind următoarea:
1 – Dacă elementul 0 se interschimbă cu cel de deasupra.
2 – Dacă elementul 0 se interschimbă cu cel din dreapta.
3 – Dacă elementul 0 se interschimbă cu cel de dedesubt.
4 – Dacă elementul 0 se interschimbă cu cel din stânga.
Restricţii:
• 2 ≤ N, M ≤ 64
• Dacă există mai multe soluţii poate fi afişată oricare.
• Se garantează că pe toate fişierele de test există cel puţin o
soluţie.
Date de intrare Date de ieșire
3 3 2 3 3 2
0 1 3
4 2 6 Mutările efectuate vor fi în
7 5 8 urm[toarele direcţii: E, S, S, E. După
efectuarea lor matricea va arăta
astfel:
1 2 3
4 5 6
7 8 0
Urmează implementarea C++ a problemei din varianta 1, pentru a
rezolva problema jocului Pierspico folosind metoda B&C:
#include <iostream>
#include <queue>
using namespace std;
#define N 3
struct Node{
Node* parent;
int mat[N][N];
int x, y, cost, level;
};
int printMatrix(int mat[N][N]){
2 din 7 Profesor A.D.
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++)
cout<<mat[i][j]<<" "; cout<<endl;
}
}
Node* newNode(int mat[N][N], int x, int y, int newX, int newY, int
level, Node* parent){
Node* node = new Node;
node->parent = parent;
memcpy(node->mat, mat, sizeof node->mat);
swap(node->mat[x][y], node->mat[newX][newY]);
node->cost = INT_MAX;
node->level = level;
node->x = newX; node->y = newY;
return node;
}
int row[] = {1, 0, -1, 0};
int col[] = {0, -1, 0, 1};
int calculateCost(int initial[N][N], int final[N][N]){
int count = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (initial[i][j] && initial[i][j] != final[i][j])
count++;
return count;
}
int isSafe(int x, int y){
return (x >= 0 && x < N && y >= 0 && y < N);
}
void printPath(Node* root){
if (root == NULL) return;
printPath(root->parent);
printMatrix(root→mat); cout<<endl;
}
struct comp{
bool operator()(const Node* lhs, const Node* rhs) const{
return (lhs->cost + lhs->level) > (rhs->cost + rhs-
>level);
}
};
void solve(int initial[N][N], int x, int y, int final[N][N]){
priority_queue<Node*, std::vector<Node*>, comp> pq;
Node* root = newNode(initial, x, y, x, y, 0, NULL);
root->cost = calculateCost(initial, final);
[Link](root);
while (![Link]()) {
3 din 7 Profesor A.D.
Node* min = [Link](); [Link]();
if (min->cost == 0){
printPath(min); return;
}
for (int i = 0; i < 4; i++){
if (isSafe(min->x + row[i], min->y +
col[i])){
Node* child = newNode(min->mat,
min->x, min->y, min->x + row[i], min->y + col[i],min->level + 1,
min);
child->cost = calculateCost(child-
>mat, final);
[Link](child);
}
}
}
}
int main(){
// Datele initiale pentru Pierspico
int initial[N][N] ={ {3, 8, 1}, {2, 5, 0},{7, 6, 4} };
int final[N][N] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 0} };
int x = 1, y = 2;
cout<<"Solutiile obtinute dupa fiecare pas realizat sunt:
"<<endl;
solve(initial, x, y, final);
cout<<"Au fost realizate 20 etape pentru a obtine
solutia."<<endl;
return 0;
}
Soluția obținută în urma execuției codului C++ este:
Solutiile obtinute dupa fiecare pas realizat sunt:
3 8 1
2 5 0
7 6 4
3 8 1
2 0 5
7 6 4
3 0 1
2 8 5
7 6 4
4 din 7 Profesor A.D.
3 1 0
2 8 5
7 6 4
3 1 5
2 8 0
7 6 4
3 1 5
2 8 4
7 6 0
3 1 5
2 8 4
7 0 6
3 1 5
2 0 4
7 8 6
3 0 5
2 1 4
7 8 6
0 3 5
2 1 4
7 8 6
2 3 5
0 1 4
7 8 6
2 3 5
1 0 4
7 8 6
2 3 5
1 4 0
7 8 6
2 3 0
1 4 5
7 8 6
2 0 3
1 4 5
5 din 7 Profesor A.D.
7 8 6
0 2 3
1 4 5
7 8 6
1 2 3
0 4 5
7 8 6
1 2 3
4 0 5
7 8 6
1 2 3
4 5 0
7 8 6
1 2 3
4 5 6
7 8 0
Au fost realizate 20 etape pentru a obtine solutia.
SARCINA PENTRU LECȚIA DE LABORATOR
Să se determine soluția optimală a problemei mixte de programare
liniară:
Varianta 1 Varianta 2
Max x1 x2 Min x1 x2
2 x1 2 x2 1
2 x1 2 x2 1
(F ) (G )
81 10 x2 13 81 10 x2 13
x1 , x2 0; x1 , x2 x1 , x2 0; x1 , x2
6 din 7 Profesor A.D.
SARCINA PENTRU TEMA PENTRU ACASĂ
1) Problema misionarilor și a canibalilor
Fie x misionari şi y canibali se află la marginea unui râu, cu scopul de
a trece pe celălalt mal. Ei au la dispoziţie o barcă de două persoane.
Dacă la un moment dat, pe un mal sau pe celălalt numărul canibalilor
întrece pe cel al misionarilor, misionarii sînt în pericol de a fi mâncaţi
de canibali. Problema constă în a afla cum pot trece râul cele (x+y)
persoane în deplină siguranţă. Se știe că x,y ≥ 3.
Să se scrie soluția problemei, apoi să se implementeze această
problemă în limbajul C++.
2) Problema Lupul-Capra-Varza
Un om, ducând la târg un lup, o capră şi o varză ajunge în dreptul unui
râu pe care trebuie să-l treacă peste o punte îngustă. Cum va proceda
el, ştiind că:
- lupul mănâncă capra şi capra mănâncă varza;
- omul nu poate să-i treacă pe toţi o dată şi nici câte doi;
- numărul de traversări trebuie să fie minim?
Să se scrie soluția problemei, apoi să se implementeze această
problemă în limbajul C++.
7 din 7 Profesor A.D.