Untitled
unknown
plain_text
2 years ago
40 kB
3
Indexable
Practical 2::::::
#include<bits/stdc++.h>
using namespace std;
int current_matrix[3][3],upward_matrix[3][3],downward_matrix[3][3],right_matrix[3][3],left_matrix[3][3];
int goal_matrix[3][3]={1,2,3,4,5,6,7,8,999};
int a,b;
int h_up=0,h_down=0,h_right=0,h_left=0,main_h=0;
void choose_mat(int h_left,int h_right,int h_down,int h_up,int max_heuristic_value);
void print(int mat[3][3])
{
for(a=0;a<=2;a++)
{
for(b=0;b<=2;b++)
{
printf("%d\t",mat[a][b]);
}
printf("\n");
}
cout<<"\n";
}
int calculate_heuristic (int mat[3][3])
{
int h_value=0;
for(a=0;a<=2;a++)
{
for(b=0;b<=2;b++)
{
if(goal_matrix[a][b]==mat[a][b])
{
h_value++;
}
}
}
return h_value;
}
void replace_mat(int mat[3][3])
{
for(a=0;a<=2;a++)
{
for(b=0;b<=2;b++)
{
current_matrix[a][b]=mat[a][b];
}
}
}
int find_up(int mat[3][3])
{
int u,temp1;
for(a=0;a<=2;a++)
{
for(b=0;b<=2;b++)
{
if(mat[a][b]==999)
{
temp1=mat[a-1][b];
upward_matrix[a-1][b]=mat[a][b];
upward_matrix[a][b]=temp1;
}
else
{
upward_matrix[a][b]=mat[a][b];
}
}
}
u=calculate_heuristic(upward_matrix);
return u;
}
int find_down(int mat[3][3])
{
int d,temp2;
for(a=0;a<=2;a++)
{
for(b=0;b<=2;b++)
{
downward_matrix[a][b]=mat[a][b];
}
}
for(a=0;a<=2;a++)
{
for(b=0;b<=2;b++)
{
if(mat[a][b]==999)
{
downward_matrix[a+1][b]=999;
temp2=mat[a+1][b];
downward_matrix[a][b]=temp2;
}
}
}
d=calculate_heuristic(downward_matrix);
return d;
}
int find_right(int mat[3][3])
{
for(a=0;a<=2;a++)
{
for(b=0;b<=2;b++)
{
right_matrix[a][b]=mat[a][b];
}
}
int r,temp3,i,j;
for(i=0;i<=2;i++)
{
for(j=0;j<=2;j++)
{
if(mat[i][j]==999)
{
temp3=mat[i][j+1];
right_matrix[i][j+1]=mat[i][j];
right_matrix[i][j]=temp3;
}
}
}
r=calculate_heuristic(right_matrix);
return r;
}
int find_left(int mat[3][3])
{
int l,temp4;
for(a=0;a<=2;a++)
{
for(b=0;b<=2;b++)
{
left_matrix[a][b]=mat[a][b];
}
}
for(a=0;a<=2;a++)
{
for(b=0;b<=2;b++)
{
if(mat[a][b]==999)
{
temp4=mat[a][b-1];
left_matrix[a][b-1]=mat[a][b];
left_matrix[a][b]=temp4;
}
}
}
l=calculate_heuristic(left_matrix);
return l;
}
int find_max(int a,int b,int c,int d)
{
int largest;
largest= (a>b)?(a>c)?(a>d)?a:d:(c>d)?c:d:(b>c)?(b>d)?b:d:(c>d)?c:d;
return largest;
}
void find_final_state(int mat[3][3])
{
int max_heuristic_value;
for(a=0;a<=2;a++)
{
for(b=0;b<=2;b++)
{
if(current_matrix[a][b]==999 && a==0 && b==0)
{
h_down=find_down(current_matrix);
h_right=find_right(current_matrix);
max_heuristic_value=find_max(h_left,h_right,h_down,h_up);
cout<<"Possible states"<<endl;
cout<<"downward h="<<h_up<<endl;
print(downward_matrix);
cout<<"right h="<<h_right<<endl;
print(right_matrix);
choose_mat(h_left,h_right,h_down,h_up,max_heuristic_value);
break;
}
else if(current_matrix[a][b]==999 && a==0 && b==0)
{
h_down=find_down(current_matrix);
h_right=find_right(current_matrix);
max_heuristic_value=find_max(h_left,h_right,h_down,h_up);
cout<<"Possible states"<<endl;
cout<<"downward h="<<h_up<<endl;
print(downward_matrix);
cout<<"right h="<<h_right<<endl;
print(right_matrix);
cout<<"left h="<<h_left<<endl;
print(left_matrix);
choose_mat(h_left,h_right,h_down,h_up,max_heuristic_value);
break;
}
else if(current_matrix[a][b]==999 &&a==0 && b==2)
{
h_down=find_down(current_matrix);
h_left=find_left(current_matrix);
max_heuristic_value=find_max(h_left,h_right,h_down,h_up);
cout<<"Possible states"<<endl;
cout<<"downward h="<<h_down<<endl;
print(downward_matrix);
cout<<"left h="<<h_left<<endl;
print(left_matrix);
choose_mat(h_left,h_right,h_down,h_up,max_heuristic_value);
break;
}
else if(current_matrix[a][b]==999 &&a==1 && b==0)
{
h_up=find_up(current_matrix);
h_down=find_down(current_matrix);
h_right=find_right(current_matrix);
max_heuristic_value=find_max(h_left,h_right,h_down,h_up);
cout<<"Possible states"<<endl;
cout<<"upward h="<<h_up<<endl;
print(upward_matrix);
cout<<"downward h="<<h_down<<endl;
print(downward_matrix);
cout<<"right h="<<h_right<<endl;
print(right_matrix);
choose_mat(h_left,h_right,h_down,h_up,max_heuristic_value);
break;
}
else if(current_matrix[a][b]==999 &&a==1 && b==1)
{
h_up=find_up(current_matrix);
h_down=find_down(current_matrix);
h_right=find_right(current_matrix);
h_left=find_left(current_matrix);
max_heuristic_value=find_max(h_left,h_right,h_down,h_up);
cout<<"Possible states"<<endl;
cout<<"upward h="<<h_up<<endl;
print(upward_matrix);
cout<<"downward h="<<h_down<<endl;
print(downward_matrix);
cout<<"right h="<<h_right<<endl;
print(right_matrix);
cout<<"left h="<<h_left<<endl;
print(left_matrix);
choose_mat(h_left,h_right,h_down,h_up,max_heuristic_value);
break;
}
else if(current_matrix[a][b]==999 &&a==1 && b==2)
{
h_up=find_up(current_matrix);
h_down=find_down(current_matrix);
h_left=find_left(current_matrix);
max_heuristic_value=find_max(h_left,h_right,h_down,h_up);
cout<<"Possible states"<<endl;
cout<<"upward h="<<h_up<<endl;
print(upward_matrix);
cout<<"downward h="<<h_down<<endl;
print(downward_matrix);
cout<<"left h="<<h_left<<endl;
print(left_matrix);
choose_mat(h_left,h_right,h_down,h_up,max_heuristic_value);
break;
}
else if(current_matrix[a][b]==999 &&a==2 && b==0)
{
h_up=find_up(current_matrix);
h_right=find_right(current_matrix);
max_heuristic_value=find_max(h_left,h_right,h_down,h_up);
cout<<"Possible states"<<endl;
cout<<"upward h="<<h_up<<endl;
print(upward_matrix);
cout<<"right h="<<h_right<<endl;
print(right_matrix);
choose_mat(h_left,h_right,h_down,h_up,max_heuristic_value);
break;
}
else if(current_matrix[a][b]==999 &&a==2 && b==1)
{
h_up=find_up(current_matrix);
h_right=find_right(current_matrix);
h_left=find_left(current_matrix);
max_heuristic_value=find_max(h_left,h_right,h_down,h_up);
cout<<"Possible states"<<endl;
cout<<"upward h="<<h_up<<endl;
print(upward_matrix);
cout<<"right h="<<h_right<<endl;
print(right_matrix);
cout<<"left h="<<h_left<<endl;
print(left_matrix);
choose_mat(h_left,h_right,h_down,h_up,max_heuristic_value);
break;
}
else if(current_matrix[a][b]==999 &&a==2&& b==2)
{
h_up=find_up(current_matrix);
h_left=find_left(current_matrix);
max_heuristic_value=find_max(h_left,h_right,h_down,h_up);
cout<<"possible states"<<endl;
cout<<"upward h="<<h_up<<endl;
print(upward_matrix);
cout<<"left h="<<h_left<<endl;
print(left_matrix);
choose_mat(h_left,h_right,h_down,h_up,max_heuristic_value);
break;
}
}
}
}
void func(int mat[3][3],int m)
{
replace_mat(mat);
print(current_matrix);
main_h=m;
if(main_h==9)
{
return;
}
else{
find_final_state(current_matrix);
}
}
void choose_mat(int h_left, int h_right,int h_down,int h_up,int max_heuristic_value)
{
cout<<"selected matrix is with heuristic value="<<max_heuristic_value<<endl;
if(max_heuristic_value==h_right)
{
func(right_matrix,max_heuristic_value);
}
if(max_heuristic_value==h_down)
{
func(downward_matrix,max_heuristic_value);
}
if(max_heuristic_value==h_up)
{
func(upward_matrix,max_heuristic_value);
}
if(max_heuristic_value==h_left)
{
func(left_matrix,max_heuristic_value);
}
}
int main()
{
int h;
int initial_matrix[3][3]={1,2,3,999,4,6,7,5,8};
cout<<"initial Matrix:"<<endl;
print(initial_matrix);
cout<<(goal_matrix);
for(a=0;a<=2;a++)
{
for(b=0;b<=2;b++)
{
current_matrix[a][b]=initial_matrix[a][b];
}
}
cout<<"current_matrix"<<endl;
print(current_matrix);
h=calculate_heuristic(current_matrix);
cout<<"h="<<h<<endl;
find_final_state(current_matrix);
}
Practical 3::::::
#include <cstdio>
#include <stack>
#include <map>
#include <algorithm>
using namespace std;
// Representation of a state (x, y)
// x and y are the amounts of water in litres in the two jugs respectively
struct state {
int x, y;
// Used by map to efficiently implement lookup of seen states
bool operator < (const state& that) const {
if (x != that.x) return x < that.x;
return y < that.y;
}
};
// Capacities of the two jugs respectively and the target amount
int capacity_x, capacity_y, target;
void dfs(state start, stack <pair <state, int> >& path) {
stack <state> s;
state goal = (state) {-1, -1};
// Stores seen states so that they are not revisited and
// maintains their parent states for finding a path through
// the state space
// Mapping from a state to its parent state and rule no. that
// led to this state
map <state, pair <state, int> > parentOf;
s.push(start);
parentOf[start] = make_pair(start, 0);
while (!s.empty()) {
// Get the state at the front of the stack
state top = s.top();
s.pop();
// If the target state has been found, break
if (top.x == target || top.y == target) {
goal = top;
break;
}
// Find the successors of this state
// This step uses production rules to produce successors of the current state
// while pruning away branches which have been seen before
// Rule 1: (x, y) -> (capacity_x, y) if x < capacity_x
// Fill the first jug
if (top.x < capacity_x) {
state child = (state) {capacity_x, top.y};
// Consider this state for visiting only if it has not been visited before
if (parentOf.find(child) == parentOf.end()) {
s.push(child);
parentOf[child] = make_pair(top, 1);
}
}
// Rule 2: (x, y) -> (x, capacity_y) if y < capacity_y
// Fill the second jug
if (top.y < capacity_y) {
state child = (state) {top.x, capacity_y};
if (parentOf.find(child) == parentOf.end()) {
s.push(child);
parentOf[child] = make_pair(top, 2);
}
}
// Rule 3: (x, y) -> (0, y) if x > 0
// Empty the first jug
if (top.x > 0) {
state child = (state) {0, top.y};
if (parentOf.find(child) == parentOf.end()) {
s.push(child);
parentOf[child] = make_pair(top, 3);
}
}
// Rule 4: (x, y) -> (x, 0) if y > 0
// Empty the second jug
if (top.y > 0) {
state child = (state) {top.x, 0};
if (parentOf.find(child) == parentOf.end()) {
s.push(child);
parentOf[child] = make_pair(top, 4);
}
}
// Rule 5: (x, y) -> (min(x + y, capacity_x), max(0, x + y - capacity_x)) if y > 0
// Pour water from the second jug into the first jug until the first jug is full
// or the second jug is empty
if (top.y > 0) {
state child = (state) {min(top.x + top.y, capacity_x), max(0, top.x + top.y - capacity_x)};
if (parentOf.find(child) == parentOf.end()) {
s.push(child);
parentOf[child] = make_pair(top, 5);
}
}
// Rule 6: (x, y) -> (max(0, x + y - capacity_y), min(x + y, capacity_y)) if x > 0
// Pour water from the first jug into the second jug until the second jug is full
// or the first jug is empty
if (top.x > 0) {
state child = (state) {max(0, top.x + top.y - capacity_y), min(top.x + top.y, capacity_y)};
if (parentOf.find(child) == parentOf.end()) {
s.push(child);
parentOf[child] = make_pair(top, 6);
}
}
}
// Target state was not found
if (goal.x == -1 || goal.y == -1)
return;
// backtrack to generate the path through the state space
path.push(make_pair(goal, 0));
// remember parentOf[start] = (start, 0)
while (parentOf[path.top().first].second != 0)
path.push(parentOf[path.top().first]);
}
int main() {
stack <pair <state, int> > path;
printf("Enter the capacities of the two jugs : ");
scanf("%d %d", &capacity_x, &capacity_y);
printf("Enter the target amount : ");
scanf("%d", &target);
dfs((state) {0, 0}, path);
if (path.empty())
printf("\nTarget cannot be reached.\n");
else {
printf("\nNumber of moves to reach the target : %d\nOne path to the target is as follows :\n", path.size() - 1);
while (!path.empty()) {
state top = path.top().first;
int rule = path.top().second;
path.pop();
switch (rule) {
case 0: printf("State : (%d, %d)\n#\n", top.x, top.y);
break;
case 1: printf("State : (%d, %d)\nAction : Fill the first jug\n", top.x, top.y);
break;
case 2: printf("State : (%d, %d)\nAction : Fill the second jug\n", top.x, top.y);
break;
case 3: printf("State : (%d, %d)\nAction : Empty the first jug\n", top.x, top.y);
break;
case 4: printf("State : (%d, %d)\nAction : Empty the second jug\n", top.x, top.y);
break;
case 5: printf("State : (%d, %d)\nAction : Pour from second jug into first jug\n", top.x, top.y);
break;
case 6: printf("State : (%d, %d)\nAction : Pour from first jug into second jug\n", top.x, top.y);
break;
}
}
}
return 0;
}
Practical 4:::::::
// Solving 8-Puzzle Using Steepest Ascent Hill Climbing Algorithm
#include <bits/stdc++.h>
using namespace std;
const char UP ='1';
const char DOWN= '2';
const char LEFT= '3';
const char RIGHT= '4';
void printArray(int** array)
{
for(int a=0;a<3;a++)
{
for(int b=0;b<3;b++)
{
cout<< setw(8) << array[a][b];
}
cout<<endl;
}
cout<<endl;
}
// Calculate Manhattan distance
int manhattan_distance(int** start_state,int** goal_state)
{
int manhattan_distance=0;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
if(start_state[i][j] > 0)
{
for(int k=0;k<3;k++)
{
for(int l=0;l<3;l++)
{
if (goal_state[k][l] == start_state[i][j])
{
manhattan_distance=manhattan_distance + (abs(i-k)+abs(j-l));
}
}
}
}
}
}
return manhattan_distance;
}
void makeMove(int** temp,int move)
{
int flag=0;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
if(temp[i][j] == 0)
{
if(move==1)
{
temp[i][j] = temp[i-1][j];
temp[i-1][j] = 0;
flag=1;
break;
}
else if(move==2)
{
temp[i][j] = temp[i+1][j];
temp[i+1][j] = 0;
flag=1;
break;
}
else if(move==3)
{
temp[i][j] = temp[i][j-1];
temp[i][j-1] = 0;
flag=1;
break;
}
else
{
temp[i][j] = temp[i][j+1];
temp[i][j+1] = 0;
flag=1;
break;
}
}
}
if(flag==1){break;}
}
}
//-----------------------------------------------------------------------------------------------------------
int tile_Ordering(int** current_state,int** goal_state,int move)
{
int** temp = new int*[3]; // allocate an array of 3 int pointers - these represents rows
for(int i=0;i<3;i++)
{
temp[i]=new int[3]; // these represents columns
for(int j=0;j<3;j++)
{
temp[i][j] = current_state[i][j];
}
}
makeMove(temp,move);
printArray(temp);
int manhattan=manhattan_distance(temp,goal_state);
cout<<"Current Manhattan number :"<<manhattan<<endl<<endl<<endl;
for(int i=0;i<3;i++)
{
delete temp[i];
}
delete temp;
return manhattan;
}
//----------------------------------------------------------------------------------------------------------
void steepestAscentHillClimbing( int** start_state, int** goal_state,int former_move)
{
int arr[4] = {100,100,100,100};
cout<<"--------------------------------------------------------------------------------"<<endl;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
if (start_state[i][j] == 0)
{
if(i>0 && former_move!=2)
{
cout<<"Checking child (moving 0 up) "<<endl;
arr[0]=tile_Ordering(start_state,goal_state,1);
}
if(i<2 && former_move!=1)
{
cout<<"Checking child (moving 0 down) "<<endl;
arr[1]=tile_Ordering(start_state,goal_state,2);
}
if(j>0 && former_move!=4)
{
cout<<"Checking child (moving 0 left) "<<endl;
arr[2]=tile_Ordering(start_state,goal_state,3);
}
if(j<2 && former_move!=3)
{
cout<<"Checking child (moving 0 right) "<<endl;
arr[3]=tile_Ordering(start_state,goal_state,4);
}
}
}
cout<<endl;
}
int localOptimum=99;
int index=0;
for(int i=0;i<4;i++)
{
if(arr[i]<localOptimum)
{
localOptimum=arr[i];
index=i+1;
}
}
makeMove(start_state,index);
cout<<"Next state = minimum Manhattan number :"<<endl;
printArray(start_state);
if(localOptimum==0)
{
cout<<"goal state reached"<<endl;
return;
}
else
steepestAscentHillClimbing(start_state,goal_state,index);
}
int main()
{
int** initial = new int*[3]; // allocate an array of 3 int pointers - these represents rows
for(int i=0;i<3;i++)
{
initial[i]=new int[3]; // these represents columns
}
int** final = new int*[3]; // allocate an array of 3 int pointers - these represents rows
for(int i=0;i<3;i++)
{
final[i]=new int[3]; // these represents columns
}
int player_Input;
cout << "Enter initial board configuration - 0 denotes empty position" << endl;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
cout<<"Enter input A["<<i<<"]["<<j<<"]"<<endl;
cin>>player_Input;
initial[i][j]=player_Input;
}
}
cout<<"--------------------------------------------------------------------------------"<<endl;
cout << "Enter final board configuration - 0 denotes empty position" << endl;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
cout<<"Enter input A["<<i<<"]["<<j<<"]"<<endl;
cin>>player_Input;
final[i][j]=player_Input;
}
cout<<"\n---------------------------Your initial matrix is-------------------------------\n"<<endl;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
cout << setw(8) << initial[i][j];
}
cout<<endl;
}
cout<<"\n---------------------------Your final matrix is--------------------------------\n"<<endl;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
cout << setw(8) << final[i][j];
}
cout<<endl;
}
cout<<"\n--------------------------------------------------------------------------------"<<endl;
cout<<"\n--------------------------------------------------------------------------------"<<endl;
cout<<"\nCalling Steepest Ascent Hill Climbing function\n"<<endl;
steepestAscentHillClimbing(initial,final,0);
for(int i=0;i<3;i++)
{
delete initial[i];
delete final[i];
}
delete initial;
delete final;
return 0;
}
Practical 5:::::::
#include<bits/stdc++.h>
using namespace std;
struct Move
{
int row, col;
};
char player = 'x', opponent = 'o';
// This function returns true if there are moves
// remaining on the board. It returns false if
// there are no moves left to play.
bool isMovesLeft(char board[3][3])
{
for (int i = 0; i<3; i++)
for (int j = 0; j<3; j++)
if (board[i][j]=='_')
return true;
return false;
}
// This is the evaluation function as discussed
// in the previous article ( http://goo.gl/sJgv68 )
int evaluate(char b[3][3])
{
// Checking for Rows for X or O victory.
for (int row = 0; row<3; row++)
{
if (b[row][0]==b[row][1] &&
b[row][1]==b[row][2])
{
if (b[row][0]==player)
return +10;
else if (b[row][0]==opponent)
return -10;
}
}
// Checking for Columns for X or O victory.
for (int col = 0; col<3; col++)
{
if (b[0][col]==b[1][col] &&
b[1][col]==b[2][col])
{
if (b[0][col]==player)
return +10;
else if (b[0][col]==opponent)
return -10;
}
}
// Checking for Diagonals for X or O victory.
if (b[0][0]==b[1][1] && b[1][1]==b[2][2])
{
if (b[0][0]==player)
return +10;
else if (b[0][0]==opponent)
return -10;
}
if (b[0][2]==b[1][1] && b[1][1]==b[2][0])
{
if (b[0][2]==player)
return +10;
else if (b[0][2]==opponent)
return -10;
}
// Else if none of them have won then return 0
return 0;
}
// This is the minimax function. It considers all
// the possible ways the game can go and returns
// the value of the board
int minimax(char board[3][3], int depth, bool isMax)
{
int score = evaluate(board);
// If Maximizer has won the game return his/her
// evaluated score
if (score == 10)
return score;
// If Minimizer has won the game return his/her
// evaluated score
if (score == -10)
return score;
// If there are no more moves and no winner then
// it is a tie
if (isMovesLeft(board)==false)
return 0;
// If this maximizer's move
if (isMax)
{
int best = -1000;
// Traverse all cells
for (int i = 0; i<3; i++)
{
for (int j = 0; j<3; j++)
{
// Check if cell is empty
if (board[i][j]=='_')
{
// Make the move
board[i][j] = player;
// Call minimax recursively and choose
// the maximum value
best = max( best,
minimax(board, depth+1, !isMax) );
// Undo the move
board[i][j] = '_';
}
}
}
return best;
}
// If this minimizer's move
else
{
int best = 1000;
// Traverse all cells
for (int i = 0; i<3; i++)
{
for (int j = 0; j<3; j++)
{
// Check if cell is empty
if (board[i][j]=='_')
{
// Make the move
board[i][j] = opponent;
// Call minimax recursively and choose
// the minimum value
best = min(best,
minimax(board, depth+1, !isMax));
// Undo the move
board[i][j] = '_';
}
}
}
return best;
}
}
// This will return the best possible move for the player
Move findBestMove(char board[3][3])
{
int bestVal = -1000;
Move bestMove;
bestMove.row = -1;
bestMove.col = -1;
// Traverse all cells, evaluate minimax function for
// all empty cells. And return the cell with optimal
// value.
for (int i = 0; i<3; i++)
{
for (int j = 0; j<3; j++)
{
// Check if cell is empty
if (board[i][j]=='_')
{
// Make the move
board[i][j] = player;
// compute evaluation function for this
// move.
int moveVal = minimax(board, 0, false);
// Undo the move
board[i][j] = '_';
// If the value of the current move is
// more than the best value, then update
// best/
if (moveVal > bestVal)
{
bestMove.row = i;
bestMove.col = j;
bestVal = moveVal;
}
}
}
}
printf("The value of the best Move is : %d\n\n",
bestVal);
return bestMove;
}
// Driver code
int main()
{
char board[3][3] =
{
{ 'x', 'o', 'x' },
{ 'o', 'o', 'x' },
{ '_', '_', '_' }
};
Move bestMove = findBestMove(board);
printf("The Optimal Move is :\n");
printf("ROW: %d COL: %d\n\n", bestMove.row,
bestMove.col );
return 0;
}
Practical 7:::::::
#include <stdio.h>
#define max 100
int main(void)
{
int n;
int m = 9999;
printf("Enter the number of nodes: \n");
scanf("%d", &n);
int i, j;
int mat[n][n];
printf("Enter the matrix: \n");
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
scanf("%d", &mat[i][j]);
}
}
int arr[n];
printf("Enter the heuristic: \n");
for (i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
int start;
printf("Enter the start node: \n");
scanf("%d", &start);
int goal;
printf("Enter the goal state: \n");
scanf("%d", &goal);
int visited[max] = {0};
visited[start] = 1;
int x = start;
int p = 0;
int y;
int v;
int sum = 0;
printf("Start stare is %c\n", start + 65);
printf("Goal state is %c\n", goal + 65);
while (x != goal)
{
for (i = 0; i < n; i++)
{
if (mat[x][i] != 0 && visited[i] != 1)
{
p = mat[x][i] + arr[i];
if (m > p)
{
y = mat[x][i];
m = p;
v = i;
}
}
}
sum = sum + y;
visited[v] = 1;
printf("%c", v + 65);
x = v;
m = 9999;
}
printf("The cost is %d\n", sum);
return 0;
}
Practical 8:::::::
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <time.h>
#include <getopt.h>
static int arrows;
static int debug = 0;
#define YOU 0
#define WUMPUS 1
#define PIT1 2
#define PIT2 3
#define BATS1 4
#define BATS2 5
#define LOCS 6
static int loc[LOCS];
#define NOT 0
#define WIN 1
#define LOSE -1
static int finished;
static int cave[20][3] =
{
{1,4,7},
{0,2,9}, {1,3,11}, {2,4,13}, {0,3,5}, {4,6,14},
{5,7,16}, {0,6,8}, {7,9,17}, {1,8,10}, {9,11,18},
{2,10,12}, {11,13,19}, {3,12,14}, {5,13,15},
{14,16,19}, {6,15,17}, {8,16,18}, {10,17,19}, {12,15,18},
};
int getnum(char* prompt)
{
int n;
printf("%s: ", prompt);
scanf("%d", &n);
return n;
}
int getlet(char* prompt)
{
char c = '\n';
printf("%s: ", prompt);
while (c == '\n') {
scanf("%c", &c);
}
return toupper(c);
}
void print_instructions()
{
printf( "WELCOME TO 'HUNT THE WUMPUS'\n"
"THE WUMPUS LIVES IN A CAVE OF 20 ROOMS. EACH ROOM\n"
"HAS 3 TUNNELS LEADING TO OTHER ROOMS. (LOOK AT A\n"
"DODECAHEDRON TO SEE HOW THIS WORKS-IF YOU DON'T KNOW\n"
"WHAT A DODECAHEDRON IS, ASK SOMEONE)\n"
"\n"
" HAZARDS:\n"
" BOTTOMLESS PITS: TWO ROOMS HAVE BOTTOMLESS PITS INTHEM\n"" IF YOU GO THERE, YOU FALL INTO THE PIT (& LOSE!)\n"
" SUPER BATS : TWO OTHER ROOMS HAVE SUPER BATS. IF YOU\n"
" GO THERE, A BAT GRABS YOU AND TAKES YOU TO SOME OTHER\n"
" ROOM AT RANDOM. (WHICH MAY BE TROUBLESOME)\n"
" WUMPUS:\n"
" THE WUMPUS IS NOT BOTHERED BY HAZARDS (HE HAS SUCKER\n"
" FEET AND IS TOO BIG FOR A BAT TO LIFT). USUALLY\n"
" HE IS ASLEEP. TWO THINGS WAKE HIM UP: YOU SHOOTINGAN\n"
" ARROW OR YOU ENTERING HIS ROOM.\n"
" IF THE WUMPUS WAKES HE MOVES (P=.75) ONE ROOM\n"
" OR STAYS STILL (P=.25). AFTER THAT, IF HE IS WHERE YOU\n"
" ARE, HE EATS YOU UP AND YOU LOSE!\n"
"\n"
" YOU:\n"
" EACH TURN YOU MAY MOVE OR SHOOT A CROOKED ARROW\n"
" MOVING: YOU CAN MOVE ONE ROOM (THRU ONE TUNNEL)\n"
" ARROWS: YOU HAVE 5 ARROWS. YOU LOSE WHEN YOU RUNOUT\n"
" EACH ARROW CAN GO FROM 1 TO 5 ROOMS. YOU AIMBYTELLING\n"
" THE COMPUTER THE ROOM#S YOU WANT THE ARROWTOGOTO.\n"
" IF THE ARROW CAN'T GO THAT WAY (IF NO TUNNEL) IT MOVES\n"
" AT RANDOM TO THE NEXT ROOM.\n"
" IF THE ARROW HITS THE WUMPUS, YOU WIN.\n"
" IF THE ARROW HITS YOU, YOU LOSE.\n"
" WARNINGS:\n"
" WHEN YOU ARE ONE ROOM AWAY FROM A WUMPUS OR HAZARD,\n"
" THE COMPUTER SAYS:\n"
" WUMPUS: 'I SMELL A WUMPUS'\n"
" BAT : 'BATS NEARBY'\n"
" PIT : 'I FEEL A DRAFT'\n"
"\n"
);
}
void show_room()
{
printf("\n");
for (int k = 0; k < 3; k++) {
int room = cave[loc[YOU]][k];
if (room == loc[WUMPUS]) {
printf("I SMELL A WUMPUS!\n");
} else if (room == loc[PIT1] || room == loc[PIT2]) {
printf("I FEEL A DRAFT\n");
} else if (room == loc[BATS1] || room == loc[BATS2]) {
printf("BATS NEARBY!\n");
}
}
printf("YOU ARE IN ROOM %d\n", loc[YOU]+1);
printf("TUNNELS LEAD TO %d %d %d\n\n", cave[loc[YOU]][0]+1, cave[loc[YOU]][1]+1, cave[loc[YOU]][2]+1);
}
int move_or_shoot()
{
int c = -1;
while ((c != 'S') && (c != 'M')) {
c = getlet("SHOOT OR MOVE (S-M)");
}
return (c == 'S') ? 1 : 0;
}
void move_wumpus()
{
int k = rand() % 4;
if (k < 3) {
loc[WUMPUS] = cave[loc[WUMPUS]][k];
}
if (loc[WUMPUS] == loc[YOU]) {
printf("TSK TSK TSK - WUMPUS GOT YOU!\n");
finished = LOSE;
}
}
void shoot()
{
int path[5];
int scratchloc = -1;
finished = NOT;
int len = -1;
while (len < 1 || len > 5) {
len = getnum("NO. OF ROOMS (1-5)");
}
int k = 0;
while (k < len) {
path[k] = getnum("ROOM #") - 1;
if ((k>1) && (path[k] == path[k-2])) {
printf("ARROWS AREN'T THAT CROOKED - TRY ANOTHER ROOM\n");
continue;
}
k++;
}
scratchloc = loc[YOU];
for (int k = 0; k < len; k++) {
if ((cave[scratchloc][0] == path[k]) ||
(cave[scratchloc][1] == path[k]) ||
(cave[scratchloc][2] == path[k])) {
scratchloc = path[k];
} else {
scratchloc = cave[scratchloc][rand()%3];
}
if (scratchloc == loc[WUMPUS]) {
printf("AHA! YOU GOT THE WUMPUS!\n");
finished = WIN;
} else if (scratchloc == loc[YOU]) {
printf("OUCH! ARROW GOT YOU!\n");
finished = LOSE;
}
if (finished != NOT) {
return;
}
}
printf("MISSED\n");
move_wumpus();
if (--arrows <= 0) {
finished = LOSE;
}
}
void move()
{
int scratchloc = -1;
while (scratchloc == -1) {
scratchloc = getnum("WHERE TO")-1;
if (scratchloc < 0 || scratchloc > 19) {
scratchloc = -1;
continue;
}
if ((cave[loc[YOU]][0] != scratchloc) &
(cave[loc[YOU]][1] != scratchloc) &
(cave[loc[YOU]][2] != scratchloc) &
(loc[YOU] != scratchloc)) {
printf("NOT POSSIBLE\n");
scratchloc = -1;
continue;
}
}
loc[YOU] = scratchloc;
while ((scratchloc == loc[BATS1]) || (scratchloc == loc[BATS2])) {
printf("ZAP--SUPER BAT SNATCH! ELSEWHEREVILLE FOR YOU!\n");
scratchloc = loc[YOU] = rand()%20;
}
if (scratchloc == loc[WUMPUS]) {
printf("... OOPS! BUMPED A WUMPUS!\n");
move_wumpus();
}
if (scratchloc == loc[PIT1] || scratchloc == loc[PIT2]) {
printf("YYYYIIIIEEEE . . . FELL IN PIT\n");
finished = LOSE;
}
}
void game_setup()
{
for (int j = 0; j < LOCS; j++) {
loc[j] = -1;
while (loc[j] < 0) {
loc[j] = rand()%20;
for (int k=0; k<j-1; k++) {
if (loc[j] == loc[k]) {
loc[j] = -1;
}
}
}
}
}
void game_play() {
arrows = 5;
printf("HUNT THE WUMPUS\n");
if (debug) {
printf("Wumpus is at %d, pits at %d & %d, bats at %d & %d\n", loc[WUMPUS]+1, loc[PIT1]+1, loc[PIT2]+1, loc[BATS1]+1, loc[BATS2]+1);
}
finished = NOT;
while (finished == NOT) {
show_room();
if (move_or_shoot()) {
shoot();
} else {
move();
}
}
if (finished == WIN) {
printf("HEE HEE HEE - THE WUMPUS'LL GET YOU NEXT TIME!!\n");
}
if (finished == LOSE) {
printf("HA HA HA - YOU LOSE!\n");
}
int c = getlet("NEW GAME (Y-N)");
if (c == 'N') {
exit(0);
}
}
void handle_params(int argc, char* argv[]) {
int c;
while ((c = getopt(argc, argv, "s:dh")) != -1) {
switch (c) {
case 's':
srand(atoi(optarg));
break;
case 'd':
debug = 1;
break;
case 'h':
default:
printf("usage: ./%s [-h] [-d] [-s seed]\n", argv[0]);
exit(1);
}
}
}
int main(int argc, char* argv[])
{
srand(time(0));
handle_params(argc, argv);
int c = getlet("INSTRUCTIONS (Y-N)");
if (c == 'Y') {
print_instructions();
}
do {
game_setup();
game_play();
} while (getlet("NEW GAME (Y-N)") != 'N');
return 0;
}
Practical 10::::::
#include <bits/stdc++.h>
using namespace std;
class NaiveBayesClassifier
{
private:
unordered_map<int,double> classes;
unordered_map<int, unordered_map<int, double>> attributesPerClass;
public:
NaiveBayesClassifier(vector<vector<int>> &data, int DimSize)
{
for(auto entry:data)
{
if(classes.find(entry[0])==classes.end())
{
classes[entry[0]] = 1;
unordered_map<int, double> pxc;
attributesPerClass[entry[0]] = pxc;
}
else
{
classes[entry[0]] += 1;
}
for(int k=1; k<=DimSize; k++)
{
if(attributesPerClass[entry[0]].find(entry[k]) == attributesPerClass[entry[0]].end())
{
attributesPerClass[entry[0]][entry[k]] = 1;
}
else
{
attributesPerClass[entry[0]][entry[k]] += 1;
}
}
}
for(auto seg: attributesPerClass)
{
if(seg.first == 0)
{
cout<<"---Class Apple"<< " ---"<<endl;
}
if(seg.first == 1)
{
cout<<"---Class PineApple"<< " ---"<<endl;
}
if(seg.first == 2)
{
cout<<"---Class Cherry"<< " ---"<<endl;
}
for(auto entry: seg.second)
{
entry.second /= classes[seg.first];
cout<<"Attribute P(A="<<entry.first << "| B="<<seg.first<<") = "<<entry.second<<endl;
}
classes[seg.first] /= data.size();
cout<<"Class P(B="<<seg.first<< ") = "<<classes[seg.first]<<"\n\n";
}
}
int predict(vector<int> attributes)
{
int maxcid = -1;
double maxp = 0;
for(auto cls: classes)
{
double pCx = cls.second;
for(int i=0; i<attributes.size(); i++)
{
pCx *= attributesPerClass[cls.first][attributes[i]];
}
if(pCx > maxp)
{
maxp = pCx;
maxcid = cls.first;
}
}
cout<<"PRedict Class:\t"<<maxcid<< "===>P(A|B) = "<<maxp<<endl;
return maxcid;
}
};
void populateData(vector<vector<int>> &data, unordered_map<string, int> &classmap, unordered_map<string, int> &attrimap,
string c, string a1, string a2, int K)
{
vector<int> apair = {classmap[c],attrimap[a1], attrimap[a2]};
vector<vector<int>> newarr(K, apair);
data.insert(data.end(), newarr.begin(), newarr.end());
}
int main() {
unordered_map<string, int> classmap = {{"apple", 0}, {"pineapple", 1}, {"cherry", 2}};
unordered_map<string, int> attrimap =
{
{"red",0},{"green",1},{"yellow",2},
{"round",10},{"oval",11}, {"heart", 12}
};
vector<vector<int>> data;
populateData(data, classmap, attrimap, "apple", "green","round",20);
populateData(data, classmap, attrimap, "apple", "red","round",50);
populateData(data, classmap, attrimap, "apple", "yellow","round",10);
populateData(data, classmap, attrimap, "apple", "red","oval",5);
populateData(data, classmap, attrimap, "apple", "red","heart",5);
populateData(data, classmap, attrimap, "pineapple", "green","oval",30);
populateData(data, classmap, attrimap, "pineapple", "yellow","oval",70);
populateData(data, classmap, attrimap, "pineapple", "green","round",5);
populateData(data, classmap, attrimap, "pineapple", "yellow","round",5);
populateData(data, classmap, attrimap, "cherry", "yelloe","heart",50);
populateData(data, classmap, attrimap, "cherry", "red","heart",70);
populateData(data, classmap, attrimap, "cherry", "yellow","round",5);
random_shuffle(data.begin(),data.end());
NaiveBayesClassifier mymodel(data,2);
int cls = mymodel.predict({attrimap["red"],attrimap["round"]});
if(cls == 0)
{
cout<<"Predicted Class:\tApple"<<endl;
}
if(cls==1)
{
cout<<"Predicted Class:\tPineApple"<<endl;
}
if(cls==2)
{
cout<<"Predicted Class:\tCherry"<<endl;
}
return 0;
}
Editor is loading...