Программирование в ограничениях, страница 2

// Например: «Норвежец живет в первом доме»

task &= p1[0][0];       //Первый - BMW

task &= p3[1][3];       //Второй - США

task &= p4[3][2];       //Четвертый - хэтчбек

// -<--// ->--- ограничение типа 2

// Ограничение, устанавливающее соответствие между двумя свойствами какого-либо объекта

// Например: «Англичанин живет в красном доме»

for (unsigned i = 0; i < N; i++)

task &= !( p2[i][3] ^ p3[i][0] );//Синий - Англия

for (unsigned i = 0; i < N; i++)              

task &= !( p1[i][0] ^ p2[i][1] );//BMW - Черный

// -<--// ->--- ограничение типа 3

// Ограничение между двумя объектами

// Например: расположение «слева» или «справа»

//BMW - слева от зеленого

for (unsigned i = 0; i < N - 1; i++)

task &= !( p1[i][0] ^ p2[i + 1][0] );

//США - слева от лимузина

for (unsigned i = 0; i < N - 1; i++)

task &= !( p3[i][3] ^ p4[i + 1][3] );

//Англия - слева от Honda

for (unsigned i = 0; i < N - 1; i++)

task &= !( p3[i][0] ^ p1[i + 1][3] );

//Япония - справа от синего

for (unsigned i = 0; i < N - 1; i++)

task &= !( p2[i][3] ^ p3[i + 1][1] );

//Jaguar - справа от Германии

for (unsigned i = 0; i < N - 1; i++)

task &= !( p3[i][2] ^ p1[i + 1][1] );

// -<--// ->--- ограничение типа 4

// Ограничение между двумя объектами

// Например: расположение «рядом» – дизъюнкция ограничений «слева» и «справа»

bdd temp11 = bddtrue;

bdd temp12 = bddtrue;

//Германия - рядом с зеленым      

for (unsigned i = 0; i < N - 1; i++)                            

temp11 &= !( p3[i][2] ^ p2[i + 1][0] );

for (unsigned i = 0; i < N - 1; i++)

temp12 &= !( p2[i][0] ^ p3[i + 1][2] );

task &= temp11 | temp12;

bdd temp21 = bddtrue;

bdd temp22 = bddtrue;

//Зеленый - рядом с Bentley

for (unsigned i = 0; i < N - 1; i++)

temp21 &= !( p2[i][0] ^ p1[i + 1][2] );

for (unsigned i = 0; i < N - 1; i++)

temp22 &= !( p1[i][2] ^ p2[i + 1][0] );

task &= temp21 | temp22;

bdd temp31 = bddtrue;

bdd temp32 = bddtrue;

//Синий - рядом с Японией

for (unsigned i = 0; i < N - 1; i++)

temp31 &= !( p2[i][3] ^ p3[i + 1][1] );

for (unsigned i = 0; i < N - 1; i++)

temp32 &= !( p3[i][1] ^ p2[i + 1][3] );

task &= temp31 | temp32;

bdd temp41 = bddtrue;

bdd temp42 = bddtrue;

//Honda - рядом с лимузином

for (unsigned i = 0; i < N - 1; i++)                            

temp41 &= !( p1[i][3] ^ p4[i + 1][3] );

for (unsigned i = 0; i < N - 1; i++)

temp42 &= !( p4[i][3] ^ p1[i + 1][3] );

task &= temp41 | temp42;

//Jaguar - рядом с седаном

bdd temp51 = bddtrue;

bdd temp52 = bddtrue;

for (unsigned i = 0; i < N - 1; i++)                      

temp51 &= !( p1[i][1] ^ p4[i + 1][1] );

for (unsigned i = 0; i < N - 1; i++)

temp52 &= !( p4[i][1] ^ p1[i + 1][1] );

task &= temp51 | temp52;

// -<--// ->--- ограничение по-умолчанию 5

// У двух различных объектов значения люого параметра (свойства) не совпадают.

for (unsigned j = 0; j < N; j++)

for (unsigned i = 0; i < N; i++)

for (unsigned k = i + 1; k < N; k++) {

task &= p1[i][j] >> !p1[k][j];

task &= p2[i][j] >> !p2[k][j];

task &= p3[i][j] >> !p3[k][j];

task &= p4[i][j] >> !p4[k][j];

/*task &= p5[i][j] >> !p5[k][j];*/

}

// -<--// вывод результатов

out.open("out.txt");

unsigned satcount = (unsigned)bdd_satcount(task);

out << satcount << " Решение:" << endl << endl;

if (satcount)

bdd_allsat(task, fun);

out.close();

bdd_done(); // завершение работы библиотеки

return 0;

}

void print(void)

{

for (unsigned i = 0; i < N; i++)

{

out<<i+1<<" Автомобиль: |";

for (unsigned j = 0; j < M; j++)

{

unsigned J = i*M*LOG_N + j*LOG_N;

unsigned num = 0;            

for (unsigned k = 0; k < LOG_N; k++) num += (unsigned)(var[J + k] << k);

out<<" "<<num<<" |";

}

out<<endl;

}

out<<endl;

}

void build(char* varset, unsigned n, unsigned I) {

if (I == n - 1) {

if (varset[I] >= 0) {

var[I] = varset[I];

print();

return;

}

var[I] = 0;

print();

var[I] = 1;

print();

return;

}

if (varset[I] >= 0) {

var[I] = varset[I];

build(varset, n, I + 1);

return;

}

var[I] = 0;

build(varset, n, I + 1);

var[I] = 1;

build(varset, n, I + 1);

}

// функция, используемая для вывода решений

void fun(char* varset, int size) {

build(varset, size, 0);

}

Решение:

1 Решение:

1 Автомобиль: | 0 | 1 | 2 | 1 |

2 Автомобиль: | 1 | 0 | 3 | 0 |

3 Автомобиль: | 2 | 3 | 0 | 3 |

4 Автомобиль: | 3 | 2 | 1 | 2 |

3.Интерпретация решения.

Интерпретация верная.