8 puzzle (Bài toán Ta canh)


#include <iostream>
using namespace std;
#define MAX 3

// the result state must be
int Final_State[MAX][MAX] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 0}
};

// initialize
int Current_State[MAX][MAX] = {
{0, 1, 3},
{4, 2, 5},
{7, 8, 6}
};

// moving step (0,-1) that means (i, j-1) => Move left
// moving step (-1,0) that means (i-1, j) => Move up
// moving step (0,+1) that means (i, j+1) => Move right
// moving step (+1,0) that means (i+1, j) => Move down
int di[4] = {0, -1, 0, +1};
int dj[4] = {-1, 0, +1, 0};

int DD[13][MAX][MAX];
int nDD = 0;
int step = 0;

void Swapper(int &a, int &b){ a = a^b; b = a^b; a = a^b; }

// find the index of an element in matrix
int FindIndex(int a[MAX][MAX], int row, int column, int &rowIndex, int &columnIndex, int x){
for(int i=0; i<MAX; i++){
for(int j=0; j<MAX; j++){
if(a[i][j] == x){
rowIndex = i;
columnIndex = j;
return 1;
}
}
}
return -1;
}

int TotalMoving(int T[MAX][MAX]){
int total = 0;
int rowIndex, columnIndex;
for(int i=0; i<MAX; i++){
for(int j=0; j<MAX; j++){
if(T[i][j] != 0){
FindIndex(Final_State, MAX, MAX, rowIndex, columnIndex, T[i][j]);
total += (abs(rowIndex-i) + abs(columnIndex-j));
}
}
}
return total;
}
// copy all element from A to B
void ArrayCopy(int a[MAX][MAX], int b[MAX][MAX], int na, int nb){
for(int i=0; i<na; i++){
for(int j=0; j<nb; j++){
b[i][j] = a[i][j];
}
}
}

void PrintArray(int a[MAX][MAX], int row, int column){
for(int i=0; i<row; i++){
for(int j=0; j<column; j++){
cout << a[i][j] << " ";
}
cout << endl;
}
}

bool IsDuplicate(int T1[MAX][MAX], int T2[MAX][MAX]){
for(int i=0; i<MAX; i++){
for(int j=0; j<MAX; j++){
if(T1[i][j] != T2[i][j]){
return false;
}
}
}
return true;
}

// T: current state
bool IsVisited(int T[MAX][MAX]){
for(int i=0; i<nDD; i++){
if(IsDuplicate(T, DD[i])){
return true;
}
}
return false;
}

int Solve(){
int i_zero_index, j_zero_index;

int minSum;
int T[MAX][MAX];
int temp[MAX][MAX];

while(1){
cout <<"\nstep " << step + 1 << ":" << endl;
PrintArray(Current_State, MAX, MAX);
// param 0: find index of zero
FindIndex(Current_State, MAX, MAX, i_zero_index, j_zero_index, 0);

minSum = 100;
for(int i=0; i<4; i++){
int i_neighbour_index = i_zero_index + di[i];
int j_neighbour_index = j_zero_index + dj[i];
if(i_neighbour_index >= 0 && i_neighbour_index < MAX && j_neighbour_index >= 0 && j_neighbour_index < MAX){
ArrayCopy(Current_State, temp, MAX, MAX);
Swapper(temp[i_zero_index][j_zero_index], temp[i_neighbour_index][j_neighbour_index]);
int sum = TotalMoving(temp);
if(sum < minSum && IsVisited(temp) == false){
minSum = sum;
ArrayCopy(temp, T, MAX, MAX);
}
}
}
ArrayCopy(T, Current_State, MAX, MAX);
ArrayCopy(Current_State, DD[nDD++], MAX, MAX);
step++;
if(minSum == 0){
return 1;
}
if(step == 13){
return 0;
}
}
return 0;
}

int main()
{
ArrayCopy(Current_State, DD[nDD++], MAX, MAX);
if(Solve() == 0){
cout << "Failed !";
}
else{
cout << "\nStep " << step + 1 << ":" << endl;
PrintArray(Current_State, MAX, MAX);
cout << "\nSuccess!" << endl;
}
return 0;
}

TSP (Travelling Salesman problem)


#include <iostream>
using namespace std;
#define MAX 100
#define INF 354754546

int n = 5;
int step = 0;
int path[MAX];
int visited[MAX];
int array[MAX][MAX] = {
{INF, 3, 4, 2, 7},
{3, INF, 4, 6, 3},
{4, 4, INF, 5, 8},
{2, 6, 5, INF, 6},
{7, 3, 8, 6, INF}
};

void TSP(int start)
{
int min = 0;
while(step < n)
{
for(int i=0; i<step; i++) // find minimum cost.
{
if(visited[i] == 0 && array[start][i] < array[start][min])
{
min = i;
}
}
array[start][min] = array[min][start] = INF;
start = min; // set the next start point.
path[step++] = start; // next step.
visited[start] = 1; // set this point visited.
}
}

void PrintPath()
{
for(int i=0; i<n; i++){
cout << path[i] << " ";
}
}
int main()
{
TSP(0); // start from the first point
PrintPath();
return 0;
}

Job Scheduling (Bài toán phân công công việc)


#include <iostream>
using namespace std;
#define MAX 30

class Job{
public:
int time;
int index;
};
class Machine{
public:
int totalTime; // total of time
int numberOfJob;
Job job[MAX];
};

void Input(Job job[], int numberOfJob){
int i;
for(i=0; i<numberOfJob; i++){
cout << "Input work time for job: " << i+1 << ":"; job[i].index = i+1; cin >> job[i].time;
}
}
void OutputEachJob(Job job[], int numberOfJob){
int i;
for(i=0; i<numberOfJob; i++){
cout << " [" << job[i].index << "] = " << job[i].time;
}
}

void JobSwapper(Job &job1, Job &job2){
Job temp;
temp.time = job1.time; job1.time = job2.time; job2.time = temp.time;
temp.index = job1.index; job1.index = job2.index; job2.index = temp.index;
}

void JobSorter(Job job[], int numberOfJob){
int i,j;
for(i=0; i<numberOfJob-1; i++){
for(j=i+1; j<numberOfJob; j++){
if(job[i].time < job[j].time){
JobSwapper(job[i], job[j]);
}
}
}
}

void MachineInitilize(Machine machine[], int numberOfMachine){
int i;
for(i=0; i<numberOfMachine; i++){
machine[i].totalTime = 0;
machine[i].numberOfJob = 0;
}
}

int FindMachineWorkInMinimumTime(Machine machine[], int numberOfMachine){
int i, f = 0;
int min = machine[0].totalTime;
for(i=1; i<numberOfMachine; i++){ if(min > machine[i].totalTime){
min = machine[i].totalTime;
f = i;
}
}
return f;
}

void JobScheduler(Machine machine[], int numberOfMachine, Job job[], int numberOfJob){
int f, k, i;
for(i=0; i<numberOfJob; i++){
// choose machine which is worked in minimum time
f = FindMachineWorkInMinimumTime(machine, numberOfMachine);
// the number of job that the selected machine done
k = machine[f].numberOfJob;
// add the next job for the selected machine
machine[f].totalTime += job[i].time;
machine[f].job[k].time = job[i].time;
machine[f].job[k].index = job[i].index;
machine[f].numberOfJob++;
}
}

void OutputResult(Machine machine[], int numberOfMachine){
int i, j;
int max = machine[0].totalTime;
for(i=0; i<numberOfMachine; i++){
if(max < machine[i].totalTime){
max = machine[i].totalTime;
}
cout << endl << "Machine " << i+1 << ":";
cout << endl << "Total time: " << machine[i].totalTime;
cout << endl << "Job process: ";
for(j=0; j<machine[i].numberOfJob; j++){
cout << "[" << machine[i].job[j].index <<"] ";
}
}
cout << endl << "\nBest time to finish all job: " << max << endl;
cout << endl;
}

int main()
{
Job job[MAX];
Machine machine[MAX];
int numberOfMachine, numberOfJob;

cout << ":: JOB SCHEDULING PROBLEMS ::" << endl;
do{
cout << "Input the number of machine (0 < N < 30): "; cin >> numberOfMachine;
cout << "Input the number of Job (0 < N < 30): "; cin >> numberOfJob;
}while((numberOfMachine < 0 || numberOfMachine > 30) || (numberOfJob < 0 || numberOfJob > 30));

MachineInitilize(machine, numberOfMachine);
Input(job, numberOfJob);
JobSorter(job, numberOfJob);
JobScheduler(machine, numberOfMachine, job, numberOfJob);
OutputResult(machine, numberOfMachine);

return 0;
}

8 Puzzle problem (Bài toán Ta canh)


#include <iostream>
using namespace std;
#define MAX 3

// the result state must be
int Final_State[MAX][MAX] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 0}
};

// initialize
int Current_State[MAX][MAX] = {
{0, 1, 3},
{4, 2, 5},
{7, 8, 6}
};

// moving step (0,-1) that means (i, j-1) => Move left
// moving step (-1,0) that means (i-1, j) => Move up
// moving step (0,+1) that means (i, j+1) => Move right
// moving step (+1,0) that means (i+1, j) => Move down
int di[4] = {0, -1, 0, +1};
int dj[4] = {-1, 0, +1, 0};

int DD[13][MAX][MAX];
int nDD = 0;
int step = 0;

void Swapper(int &a, int &b){ a = a^b; b = a^b; a = a^b; }

// find index of an element in matrix
int FindIndex(int a[MAX][MAX], int row, int column, int &rowIndex, int &columnIndex, int x){
for(int i=0; i<MAX; i++){
for(int j=0; j<MAX; j++){
if(a[i][j] == x){
rowIndex = i;
columnIndex = j;
return 1;
}
}
}
return -1;
}

int TotalMoving(int T[MAX][MAX]){
int total = 0;
int rowIndex, columnIndex;
for(int i=0; i<MAX; i++){
for(int j=0; j<MAX; j++){
if(T[i][j] != 0){
FindIndex(Final_State, MAX, MAX, rowIndex, columnIndex, T[i][j]);
total += (abs(rowIndex-i) + abs(columnIndex-j));
}
}
}
return total;
}

void ArrayCopy(int a[MAX][MAX], int b[MAX][MAX], int na, int nb){
for(int i=0; i<na; i++){
for(int j=0; j<nb; j++){
b[i][j] = a[i][j];
}
}
}

void PrintArray(int a[MAX][MAX], int row, int column){
for(int i=0; i<row; i++){
for(int j=0; j<column; j++){
cout << a[i][j] << " ";
}
cout << endl;
}
}

bool IsDuplicate(int T1[MAX][MAX], int T2[MAX][MAX]){
for(int i=0; i<MAX; i++){
for(int j=0; j<MAX; j++){
if(T1[i][j] != T2[i][j]){
return false;
}
}
}
return true;
}

bool IsVisited(int T[MAX][MAX]){
for(int i=0; i<nDD; i++){
if(IsDuplicate(T, DD[i])){
return true;
}
}
return false;
}

int Solve(){
int i0, j0;

int minSum;
int T[MAX][MAX];
int temp[MAX][MAX];

while(1){
cout <<"\nstep " << step + 1 << ":" << endl;
PrintArray(Current_State, MAX, MAX);
// param 0: find index of zero
FindIndex(Current_State, MAX, MAX, i0, j0, 0);

minSum = 100;
for(int count=0; count<4; count++){
int lci = i0 + di[count];
int lcj = j0 + dj[count];
if(lci >= 0 && lci < MAX && lcj >= 0 && lcj < MAX){
ArrayCopy(Current_State, temp, MAX, MAX);
Swapper(temp[i0][j0], temp[lci][lcj]);
int sum = TotalMoving(temp);
if(sum < minSum && IsVisited(temp) == false){
minSum = sum;
ArrayCopy(temp, T, MAX, MAX);
}
}
}
ArrayCopy(T, Current_State, MAX, MAX);
ArrayCopy(Current_State, DD[nDD++], MAX, MAX);
step++;
if(minSum == 0){
return 1;
}
if(step == 13){
return 0;
}
}
return 0;
}

int main()
{
ArrayCopy(Current_State, DD[nDD++], MAX, MAX);
if(Solve() == 0){
cout << "Failed !";
}
else{
cout << "\nStep " << step + 1 << ":" << endl;
PrintArray(Current_State, MAX, MAX);
cout << "\nSuccess!" << endl;
}
return 0;
}

8-puzzle


#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <deque>
#include <stack>
using namespace std;

class State{
public:
int a[9];

State(){
for(int i=0; i<9; i++){
a[i] = rand() % 9;
while (found(i)) { a[i] = rand() % 9; }
}
}


void print(){
cout << "-----------------" << endl;
for(int i=0; i<9; i++){
if (i>0 && i%3==0) cout << endl;
cout << a[i] << "\t";
}
cout << endl << "-----------------" << endl;
}


int found(int i){
for(int j=0; j<i; j++){
if (a[i]==a[j]) return 1;
}
return 0;
}


int findzero(){
for (int i=0; i<9; i++){
if (a[i]==0) return i;
}
}


State exch(int i, int j){
State b;
for (int k=0; k<9; k++)
b.a[k]=a[k];
int t=b.a[i];
b.a[i]=b.a[j];
b.a[j]=t;
return b;
}
int equal(State s){
for(int i=0; i<9; i++){
if (a[i]!=s.a[i]) return 0;
}
return 1;
}


int goal(){
int g[9] = {1,2,3,8,0,4,7,6,5};
for (int i=0; i<9; i++){
if (a[i]!=g[i]) return 0;
}
return 1;
}
};

class Node{
public:
State s;
Node *father;
int action, cost, depth;


Node(){
State s();
father=NULL;
action=-1;
cost=1;
depth=0;
}


Node(State _s, Node *_father, int _action, int _depth){
s=_s;
father=_father;
action=_action;
depth=_depth;
}


Node copy(){
Node b;
for (int i=0; i<9; i++)
b.s.a[i]=s.a[i];
b.father=father;
b.action=action;
b.depth=depth;

return b;
}


void print(){
cout << "Cost: \t" << cost << endl;
cout << "Depth: \t" << depth << endl;
}


void expand(deque<Node> *deque){
int p = s.findzero();
// up(0)
if ((p!=0 && p!=1 && p!=2) && action!=1){
Node n(s.exch(p,p-3), this, 0, depth+1);
(*deque).push_back(n);
}
//down (1)
if ((p!=6 && p!=7 && p!=8) && action!=0){
Node n(s.exch(p,p+3), this, 1, depth+1);
(*deque).push_back(n);
}
//right (2)
if ((p!=2 && p!=5 && p!=8) && action!=3){
Node n(s.exch(p,p+1), this, 2, depth+1);
(*deque).push_back(n);
}
//left (3)
if ((p!=0 && p!=3 && p!=6) && action!=2){
Node n(s.exch(p,p-1), this, 3, depth+1);
(*deque).push_back(n);
}
}


int expanded(deque<State> *deque){
int max=(*deque).size()>depth?depth:(*deque).size();
for (int i=0; i<max; i++){
if ( s.equal( (*deque)[i] ) ){
return 1;
}
}
return 0;
}
int bfs(){
deque<Node> toexpand;
deque<State> expanded;

toexpand.push_back(*this);
while ( !toexpand.empty() ){
if ( toexpand.front().s.goal()==1 ){
cout << "BFS" << endl;
cout << "OK i found a solution!" << endl;
toexpand.front().print();
cost = toexpand.front().cost;
toexpand.clear();
return cost;
}
else{
if ( !(toexpand.front().expanded(&expanded)) ){
toexpand.front().expand(&toexpand);
expanded.push_front( toexpand.front().s );
toexpand[1].cost=toexpand[0].cost+1;
}
toexpand.pop_front();
}
}
if ( toexpand.empty() ) cout << endl << "I can't find any solution!" << endl;
return 0;
}

int dfs(int idsdepth){
deque<Node> toexpand;

if (idsdepth==-1) idsdepth = sizeof(int);

toexpand.push_back(*this);
while ( !toexpand.empty() ){
if (toexpand.back().depth < idsdepth){
if ( toexpand.back().s.goal()==1 ){
if (idsdepth == sizeof(int))
cout << "------|DFS|------" << endl;
else
cout << "------|IDS|------" << endl;
cout << "Solution found!" << endl;
toexpand.back().print();
toexpand.clear();
return cost;
}
else{
Node t;
t= toexpand.back().copy();
toexpand.pop_back();
t.expand(&toexpand);
}
}
else return 0;
}
if ( toexpand.empty() ) cout << endl << "Solution NOT found!" << endl;
return 0;
}

int ids(){
for(int i=0;;i++){
int t = dfs(i);
if (t!=0) return t;
}
}
};
int main(int argc, char *argv[]){
int num=1;
int bfscost=0;
int bfsfail=0;
int dfscost=0;
int dfsfail=0;
int idscost=0;
int idsfail=0;
cout << "\nEnter number of problems to solve: ";
cin >> num;
cout << endl;

if (argc == 2){
cout << "-------DEMO------\n\n";
}

for(int i=0;i<num;i++){
int _bfs=0;
int _dfs=0;
int _ids=0;

cout << "\n Problem " << i+1 << endl;
srand(argc==2?(2*i+1):time(NULL)+i);
Node n;
n.s.print();

_bfs=n.bfs();
// _dfs=n.dfs(-1);
// _ids=n.ids();

if (_bfs>0)
bfscost+=_bfs;
else
bfsfail+=1;

if (_dfs>0)
dfscost+=_dfs;
else
dfsfail+=1;

if (_ids>0)
idscost+=_ids;
else
idsfail+=1;
}
if (num > 1){
cout << "\n\n------|BFS|-------";
cout << "\nAverage cost = " << bfscost/(num-bfsfail);
cout << "\nSolved " << num-bfsfail << "/" << num;
cout << "\n------------------";
// cout << "\n\n------|DFS|-------";
// cout << "\nAverage cost = " << dfscost/(num-dfsfail);
// cout << "\nSolved " << num-dfsfail << "/" << num;
// cout << "\n------------------";
// cout << "\n\n------|IDS|-------";
// cout << "\nAverage cost = " << idscost/(num-idsfail);
// cout << "\nSolved " << num-idsfail << "/" << num;
// cout << "\n------------------";
cout << endl;
}

return 0;
}

Simple BFS (Tìm kiếm theo chiều rộng)

BFS:


#include <iostream>
#include <queue>
#define MAX 100
using namespace std;

int Array[MAX][MAX] = {
{0, 2, 1, 0, 0, 3},
{2, 0, 0, 0, 0, 5},
{1, 0, 0, 1, 3, 0},
{0, 0, 1, 0, 2, 0},
{0, 0, 3, 2, 0, 3},
{3, 5, 0, 0, 3, 0}
};
int V = 6;

// khai bao cac mang can thiet
int color[MAX], back[MAX];
queue<int> qlist;

void PrintPath(int u, int v, int back[])
{
if(u == v){
cout << v << " ";
}
else{
// dua vao nut cha de tim duong di ngan nhat.
PrintPath(u, back[v], back);
cout << v << " ";
}
}

void BFS(int start, int finish)
{
//khoi tao gia tri cho cac phan tu trong 2 mang color[], back[].
for(int i=0; i<V; i++){
// color = 0: chua di qua lan nao.
// color = 1: da di qua 1 lan.
// color = 2: tat ca dinh ke da duoc danh dau.
color[i] = 0;
back[i] = -1;
}
// bat dau tai dinh start
color[start] = 1;
qlist.push(start); // them start vao hang doi
while(!qlist.empty()){ // kiem tra neu queue khac rong
int u = qlist.front(); // lay gia tri phan tu dau tien trong queue
qlist.pop(); // bo ra phan tu dau tien
// tim dinh ke chua di qua lan nao
for(int v=0; v<V; v++){
if(Array[u][v] != 0 && color[v] == 0){
color[u] = 1;
back[v] = u; // luu lai nut cha cua dinh v
qlist.push(v); // them dinh v vao queue
}
}
// da duyet het dinh ke cua dinh u
color[u] = 2;
}
PrintPath(start, finish, back); // in ket qua.
}

int main()
{
int start, finish;
cout << "Nhap dinh bat dau: ";
cin >> start;
cout << "Nhap dinh ket thuc: ";
cin >> finish;
BFS(start, finish);

return 0;
}

Simple DFS (Tìm kiếm theo chiều sâu)

DFS:


#include <iostream>
#define MAX 100
using namespace std;

int Array[MAX][MAX] = {
{0, 2, 1, 0, 0, 3},
{2, 0, 0, 0, 0, 5},
{1, 0, 0, 1, 3, 0},
{0, 0, 1, 0, 2, 0},
{0, 0, 3, 2, 0, 3},
{3, 5, 0, 0, 3, 0}
};
int V = 6;
int TIME = 0;
int color[MAX], times[MAX], back[MAX];

void Visit(int u)
{
color[u] = 1;
TIME++;
times[u] = TIME;
for(int v = 0; v < V; v++){
if(Array[u][v] != 0 && color[v] == 0){
back[v] = u;
times[v] = times[u] + 1;
Visit(v);
}
}
color[u] = 2;
}

void DFS()
{
for(int i=0; i<V; i++){
color[i] = 0;
back[i] = times[i] = -1;
}
for(int i=0; i<V; i++){
if(color[i] == 0){
Visit(i);
}
}
}

void PrintPath(int start, int finish)
{
if(start == finish){
cout << finish << " ";
}
else{
if(back[finish] == -1){
cout << "Khong co duong di \n";
}
else{
PrintPath(start, back[finish]);
cout << finish << " ";
}
}
}

int main()
{
int start, finish;
cout << "Nhap dinh bat dau: ";
cin >> start;
cout << "Nhap dinh ket thuc: ";
cin >> finish;
DFS();
PrintPath(start, finish);

/*
Input:
- start = 0, finish = 5
Output:
0 1 5
*/

return 0;
}