A star, AO* star, HILL,tower of hanoi

 A* ALGORITHM PROGRAM

#include <stdlib.h>

#include <stdio.h>

#include <string.h>

#include <float.h>

/* and not not_eq */

#include <iso646.h>

/* add -lm to command line to compile with this header */

#include <math.h>

 

#define map_size_rows 10

#define map_size_cols 10

 

char map[map_size_rows][map_size_cols] = {

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},

    {1, 0, 0, 0, 0, 0, 0, 0, 0, 1},

    {1, 0, 0, 0, 0, 0, 0, 0, 0, 1},

    {1, 0, 0, 0, 0, 1, 1, 1, 0, 1},

    {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},

    {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},

    {1, 0, 0, 1, 1, 1, 1, 1, 0, 1},

    {1, 0, 0, 0, 0, 0, 0, 0, 0, 1},

    {1, 0, 0, 0, 0, 0, 0, 0, 0, 1},

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

};

 

/* description of graph node */

struct stop {

    double col, row;

    /* array of indexes of routes from this stop to neighbours in array of all routes */

    int * n;

    int n_len;

    double f, g, h;

    int from;

};

 

int ind[map_size_rows][map_size_cols] = {

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1},

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1},

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1},

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1},

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1},

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1},

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1},

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1},

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1},

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

};

 

/* description of route between two nodes */

struct route {

    /* route has only one direction! */

    int x; /* index of stop in array of all stops of src of this route */

    int y; /* intex of stop in array of all stops od dst of this route */

    double d;

};

 

int main() {

    int i, j, k, l, b, found;

    int p_len = 0;

    int * path = NULL;

    int c_len = 0;

    int * closed = NULL;

    int o_len = 1;

    int * open = (int*)calloc(o_len, sizeof(int));

    double min, tempg;

    int s;

    int e;

    int current;

    int s_len = 0;

    struct stop * stops = NULL;

    int r_len = 0;

    struct route * routes = NULL;

 

    for (i = 1; i < map_size_rows - 1; i++) {

        for (j = 1; j < map_size_cols - 1; j++) {

            if (!map[i][j]) {

                ++s_len;

                stops = (struct stop *)realloc(stops, s_len * sizeof(struct stop));

                int t = s_len - 1;

                stops[t].col = j;

                stops[t].row = i;

                stops[t].from = -1;

                stops[t].g = DBL_MAX;

                stops[t].n_len = 0;

                stops[t].n = NULL;

                ind[i][j] = t;

            }

        }

    }

 

    /* index of start stop */

    s = 0;

    /* index of finish stop */

    e = s_len - 1;

 

    for (i = 0; i < s_len; i++) {

        stops[i].h = sqrt(pow(stops[e].row - stops[i].row, 2) + pow(stops[e].col - stops[i].col, 2));

    }

 

    for (i = 1; i < map_size_rows - 1; i++) {

        for (j = 1; j < map_size_cols - 1; j++) {

            if (ind[i][j] >= 0) {

                for (k = i - 1; k <= i + 1; k++) {

                    for (l = j - 1; l <= j + 1; l++) {

                        if ((k == i) and (l == j)) {

                            continue;

                        }

                        if (ind[k][l] >= 0) {

                            ++r_len;

                            routes = (struct route *)realloc(routes, r_len * sizeof(struct route));

                            int t = r_len - 1;

                            routes[t].x = ind[i][j];

                            routes[t].y = ind[k][l];

                            routes[t].d = sqrt(pow(stops[routes[t].y].row - stops[routes[t].x].row, 2) + pow(stops[routes[t].y].col - stops[routes[t].x].col, 2));

                            ++stops[routes[t].x].n_len;

                            stops[routes[t].x].n = (int*)realloc(stops[routes[t].x].n, stops[routes[t].x].n_len * sizeof(int));

                            stops[routes[t].x].n[stops[routes[t].x].n_len - 1] = t;

                        }

                    }

                }

            }

        }

    }

 

    open[0] = s;

    stops[s].g = 0;

    stops[s].f = stops[s].g + stops[s].h;

    found = 0;

 

    while (o_len and not found) {

        min = DBL_MAX;

 

        for (i = 0; i < o_len; i++) {

            if (stops[open[i]].f < min) {

                current = open[i];

                min = stops[open[i]].f;

            }

        }

 

        if (current == e) {

            found = 1;

 

            ++p_len;

            path = (int*)realloc(path, p_len * sizeof(int));

            path[p_len - 1] = current;

            while (stops[current].from >= 0) {

                current = stops[current].from;

                ++p_len;

                path = (int*)realloc(path, p_len * sizeof(int));

                path[p_len - 1] = current;

            }

        }

 

        for (i = 0; i < o_len; i++) {

            if (open[i] == current) {

                if (i not_eq (o_len - 1)) {

                    for (j = i; j < (o_len - 1); j++) {

                        open[j] = open[j + 1];

                    }

                }

                --o_len;

                open = (int*)realloc(open, o_len * sizeof(int));

                break;

            }

        }

 

        ++c_len;

        closed = (int*)realloc(closed, c_len * sizeof(int));

        closed[c_len - 1] = current;

 

        for (i = 0; i < stops[current].n_len; i++) {

            b = 0;

 

            for (j = 0; j < c_len; j++) {

                if (routes[stops[current].n[i]].y == closed[j]) {

                    b = 1;

                }

            }

 

            if (b) {

                continue;

            }

 

            tempg = stops[current].g + routes[stops[current].n[i]].d;

 

            b = 1;

 

            if (o_len > 0) {

                for (j = 0; j < o_len; j++) {

                    if (routes[stops[current].n[i]].y == open[j]) {

                        b = 0;

                    }

                }

            }

 

            if (b or (tempg < stops[routes[stops[current].n[i]].y].g)) {

                stops[routes[stops[current].n[i]].y].from = current;

                stops[routes[stops[current].n[i]].y].g = tempg;

                stops[routes[stops[current].n[i]].y].f = stops[routes[stops[current].n[i]].y].g + stops[routes[stops[current].n[i]].y].h;

 

                if (b) {

                    ++o_len;

                    open = (int*)realloc(open, o_len * sizeof(int));

                    open[o_len - 1] = routes[stops[current].n[i]].y;

                }

            }

        }

    }

 

    for (i = 0; i < map_size_rows; i++) {

        for (j = 0; j < map_size_cols; j++) {

            if (map[i][j]) {

                putchar(0xdb);

            } else {

                b = 0;

                for (k = 0; k < p_len; k++) {

                    if (ind[i][j] == path[k]) {

                        ++b;

                    }

                }

                if (b) {

                    putchar('x');

                } else {

                    putchar('.');

                }

            }

        }

        putchar('\n');

    }

 

    if (not found) {

        puts("IMPOSSIBLE");

    } else {

        printf("path cost is %d:\n", p_len);

        for (i = p_len - 1; i >= 0; i--) {

            printf("(%1.0f, %1.0f)\n", stops[path[i]].col, stops[path[i]].row);

        }

    }

 

    for (i = 0; i < s_len; ++i) {

        free(stops[i].n);

    }

    free(stops);

    free(routes);

    free(path);

    free(open);

    free(closed);

 

    return 0;

}

 

 

 

 

 

 

 

 

AO* ALGORITHM

#include <iostream>
	#include<bits/stdc++.h>
	using namespace std;
	struct node
	{
	int data;
	vector< vector<node* >* >v;
	bool mark;
	bool solved;
	};
	int edge_cost=0;
	void insert(node* root)
	{
	cout<<"Enter data of node :"<<endl;
	cin>>root->data;
	//vector<vector<node*> >vec=root->v;
	cout<<"Enter number of OR nodes for value "<<root->data<<" :"<<endl;
	int or_no;
	cin>>or_no;
	for(int i=0;i<or_no;i++)
	{
	vector<node*>* ans=new vector<node*>;
	cout<<"Enter number of AND nodes for "<<i+1<<" or node for value "<<root->data<<" :"<<endl;
	int and_no;
	cin>>and_no;
	for(int j=0;j<and_no;j++)
	{
	node* n=new node;
	n->solved=false;
	n->mark=false;
	insert(n);
	(*ans).push_back(n);
	//cout<<"inserted node with value"<<n->data<<endl;
	}
	root->v.push_back(ans);
	}
	}
	void aostar(node* root)
	{
	vector<node*>* min_ans=new vector<node*>;
	(*min_ans).push_back(root);
	while(!root->solved)
	{
	node* next_node=root;
	stack<node*>st;
	while(next_node && next_node->mark)
	{
	if((next_node->v).size()==0)
	{
	root->solved=true;
	return;
	}
	int cost=INT_MAX;
	st.push(next_node);
	for(unsigned int i=0;i<next_node->v.size();i++)
	{
	vector<node*>*ans=(next_node->v)[i];
	vector<node*> ans_v=*ans;
	int temp_cost=0;
	for(unsigned int j=0;j<(ans_v.size());j++)
	{
	node* n=ans_v[j];
	temp_cost+=n->data;
	}
	if(temp_cost<cost)
	{
	min_ans=ans;
	cost=temp_cost;
	}
	}
	vector<node*> min_ans_v=*min_ans;
	next_node=NULL;
	for(unsigned int j=0;j<min_ans_v.size();j++)
	{
	if(min_ans_v[j]->mark)
	{
	next_node=min_ans_v[j];
	break;
	}
	}
	}
	vector<node*> min_ans_v=*min_ans;
	for(unsigned int j=0;j<min_ans_v.size();j++)
	{
	node* n=min_ans_v[j];
	cout<<"Exploring :"<<n->data<<endl;
	int final_cost=INT_MAX;
	if(n->v.size()==0)
	{
	n->mark=true;
	}
	else{
	for(unsigned int i=0;i<n->v.size();i++)
	{
	vector<node*>*ans=(n->v)[i];
	vector<node*> ans_v=*ans;
	int temp_cost=0;
	for(unsigned int j=0;j<(ans_v.size());j++)
	{
	node* n=ans_v[j];
	temp_cost+=n->data;
	temp_cost+=edge_cost;
	}
	if(temp_cost<final_cost)
	{
	final_cost=temp_cost;
	}
	}
	n->data=final_cost;
	n->mark=true;
	}
	cout<<"Marked : "<<n->data<<endl;
	}
	for(int i=0;i<20;i++) cout<<"=";
	cout<<endl;
	while(!st.empty())
	{
	node* n=st.top();
	cout<<n->data<<" ";
	st.pop();
	int final_cost=INT_MAX;
	for(unsigned int i=0;i<n->v.size();i++)
	{
	vector<node*>*ans=(n->v)[i];
	vector<node*> ans_v=*ans;
	int temp_cost=0;
	for(unsigned int j=0;j<(ans_v.size());j++)
	{
	node* n=ans_v[j];
	temp_cost+=n->data;
	temp_cost+=edge_cost;
	}
	if(temp_cost<final_cost)
	{
	min_ans=ans;
	final_cost=temp_cost;
	}
	}
	n->data=final_cost;
	}
	cout<<endl;
	next_node=root;
	}
	}
	void print(node* root)
	{
	if(root)
	{
	cout<<root->data<<" ";
	vector<vector<node*>* >vec=root->v;
	for(unsigned int i=0;i<(root->v).size();i++)
	{
	vector<node*>* ans=(root->v)[i];
	vector<node*> ans_v=*ans;
	for(unsigned int j=0;j<ans_v.size();j++)
	{
	node* n=ans_v[j];
	print(n);
	}
	}
	}
	return;
	}
	int main()
	{
	node* root=new node;
	root->solved=false;
	root->mark=false;
	insert(root);cout<<endl;
	cout<<"Enter the edge cost: "<<endl;cin>>edge_cost;cout<<endl;
	cout<<"The tree is as follows :"<<endl;
	print(root);
	cout<<endl;
	aostar(root);
	cout<<"The minimum cost is : "<<root->data<<endl;
	return 0;
	}

 

HILL CLIMBING

 

calcCost (int ArrayOfCities[], const int NUM_CITIES)

{

      int c = 0;

      for (int i = 0; i < NUM_CITIES; ++i)

      {

            for (int j = i + 1; j < NUM_CITIES; ++j)

            {

                  if (ArrayOfCities[j] < ArrayOfCities[i])

                  {

                        c++;

                  }

            }

      }

      return c;

}

 

void SwapElements (int ArrayOfCities[], int i, int j)

{

      int temp = ArrayOfCities[i];

      ArrayOfCities[i] = ArrayOfCities[j];

      ArrayOfCities[j] = temp;

}

 

int main()

{

      const int CITIES = 8;

      int iIndex = 1;

      int ArrayOfCities[CITIES];

 

      for (int i = 0; i < CITIES; ++i)

      {

            cout << "Enter distance for city " << iIndex << endl;

            cin >> ArrayOfCities[i];

            ++iIndex;

      }

 

      int bestCost = calcCost(ArrayOfCities, CITIES);

      int iNewCost = 0, iSwaps = 0;

      while (bestCost > 0)

      {

            for (int i = 0; i < CITIES - 1; ++i)

            {

                  SwapElements(ArrayOfCities, i, i + 1);

                  iNewCost = calcCost(ArrayOfCities, CITIES);

                  if (bestCost > iNewCost)

                  {

                        ++iSwaps;

                        cout << "Performing Swap: " << iSwaps << endl;

                        for (int i = 0; i < CITIES; ++i)

                        {

                               cout << ArrayOfCities[i] << "->";

                        }

 

                        cout << "\n";

                        bestCost = iNewCost;

                  }

                  else

                  {

                        SwapElements(ArrayOfCities, i, i + 1);

                  }

            }

      }

     

      cout << "\nFinal Route: \n";

      for (int i = 0; i < CITIES; i++)

      {

            cout << ArrayOfCities[i] << endl;

      }

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#include <stdio.h>

#include<iostream>

#include<fstream>

#include<string.h>

using namespace std;

bool check(char **board,int i,int j,int st,int N){

if(st == 1){

if(board[i][j] == 'K'){

return false;

}

for(int k = 0;k<N;k++){

if(board[i][k] == 'Q'){

return false;

}

}

for(int k = 0;k<N;k++){

if(board[k][j] == 'Q'){

return false;

}

}

for(int k = i-1,s = j-1;k >= 0 && s >= 0;k--,s--){

if(board[k][s] == 'Q'){

return false;

}

}

for(int k=i+1,s=j+1;k<N && s<N;k++,s++){

if(board[k][s] == 'Q'){

return false;

}

}

for(int k=i-1,s=j+1;k>=0 && s<N;k--,s++){

if(board[k][s] == 'Q'){

return false;

}

}

for(int k = i+1,s = j-1;k<N && s >= 0;k++,s--){

if(board[k][s] == 'Q'){

return false;

}

}

int k = i;

int s = j;

if( k-2 >= 0){

if(s-1 >= 0){

if(board[k-2][s-1] == 'K'){

return false;

}

}

if(s+1 < N){

if(board[k-2][s+1] == 'K'){

return false;

}

}

}

if( k+2 < N){

if(s-1 >= 0){

if(board[k+2][s-1] == 'K'){

return false;

}

}

if(s+1 < N){

if(board[k+2][s+1] == 'K'){

return false;

}

}

}

if( s-2 >= 0){

if(k-1 >= 0){

if(board[k-1][s-2] == 'K'){

return false;

}

}

if(k+1 < N){

if(board[k+1][s-2] == 'K'){

return false;

}

}

}

if( s+2 < N){

if(k-1 >= 0){

if(board[k-1][s+2] == 'K'){

return false;

}

}

if(k+1 < N){

if(board[k+1][s+2] == 'K'){

return false;

}

}

}

}

if(st == 2){

if(board[i][j] == 'Q'){

return false;

}

int k = i;

int s = j;

if( k-2 >= 0){

if(s-1 >= 0){

if(board[k-2][s-1] == 'K'){

return false;

}

}

if(s+1 < N){

if(board[k-2][s+1] == 'K'){

return false;

}

}

}

if( k+2 < N){

if(s-1 >= 0){

if(board[k+2][s-1] == 'K'){

return false;

}

}

if(s+1 < N){

if(board[k+2][s+1] == 'K'){

return false;

}

}

}

if( s-2 >= 0){

if(k-1 >= 0){

if(board[k-1][s-2] == 'K'){

return false;

}

}

if(k+1 < N){

if(board[k+1][s-2] == 'K'){

return false;

}

}

}

if( s+2 < N){

if(k-1 >= 0){

if(board[k-1][s+2] == 'K'){

return false;

}

}

if(k+1 < N){

if(board[k+1][s+2] == 'K'){

return false;

}

}

}

}

return true;

}

void initializeBoard(char **board,int Q,int K,int N){

for(int i = 0;i<N;i++){

for(int j = 0;j<N;j++){

board[i][j] = ' ';

}

}

for(int i = 0;i<N;i++){

for(int j = 0;j<N;j++){

if(Q > 0){

if(check(board,i,j,1,N)){

board[i][j] = 'Q';

Q--;

}

}

if(K > 0){

if(check(board,i,j,2,N)){

board[i][j] = 'K';

K--;

}

}

if(Q == 0 && K == 0){

break;

}

}

}

}

void printBoard(char **Board,int N){

cout<<endl;

for(int i =0;i<N;i++){

for(int j = 0;j<N;j++){

cout<<"|"<<Board[i][j];

}

cout<<"|"<<endl;

}

}

int main(){

int N;

int Q;

int K;

int tmax;

std::cout << "Value of N: "; cin >> N; cout << endl;

if (cin.fail())

{

std::cout << "Please enter integer only & try again. Thanks!" << endl;

exit(0);

}

else if (N < 4)

{

std::cout << " No possible solution. Please try again for n > 4.";

exit(0);

}

std::cout << "Value of Q: "; cin >> Q; cout << endl;

if (cin.fail())

if (cin.fail())

{

std::cout << "Please enter integer only & try again. Thanks!" << endl;

exit(0);

}

else if (Q < 1)

{

std::cout << " No possible solution. Please try again for Q > 1.";

exit(0);

}

std::cout << "Value of K: "; cin >> K; cout << endl;

if (cin.fail())

if (cin.fail())

{

std::cout << "Please enter integer only & try again. Thanks!" << endl;

exit(0);

}

else if (K < 1)

{

std::cout << " No possible solution. Please try again for K > 1.";

exit(0);

}

char **board = new char*[N];

for(int i = 0;i<N;i++){

board[i] = new char[N];

}

initializeBoard(board,Q,K,N);

printBoard(board,N);

return 0;

}

tower of hanoi

#include "stdio.h"

void towers(int,char,char,char);

void towers(int n,char frompeg,char topeg,char auxpeg)

 { /* If only 1 disk, make the move and return */

   if(n==1)

     { printf("\nMove disk 1 from peg %c to peg %c",frompeg,topeg);

       return;

     }

   /* Move top n-1 disks from A to B, using C as auxiliary */

   towers(n-1,frompeg,auxpeg,topeg);

   /* Move remaining disks from A to C */

   printf("\nMove disk %d from peg %c to peg %c",n,frompeg,topeg);

   /* Move n-1 disks from B to C using A as auxiliary */

   towers(n-1,auxpeg,topeg,frompeg);

 }

main()

 { int n;

   printf("Enter the number of disks : ");

   scanf("%d",&n);

   printf("The Tower of Hanoi involves the moves :\n\n");

   towers(n,'A','C','B');

   return 0;

 }