IA Cautari

#include<iostream>
#include<conio.h>
#include<iomanip>

using namespace std;
int H[20];
int CreareMatrice(int A[20][20])
{

    A[0][1] = 75;
    A[1][0] = 75;

    A[0][2] = 140;
    A[2][0] = 140;

    A[0][3] = 118;
    A[3][0] = 118;

    A[1][4] = 71;
    A[4][1] = 71;

    A[4][2] = 151;
    A[2][4] = 151;

    A[3][7] = 111;
    A[7][3] = 111;

    A[7][10] = 70;
    A[10][7] = 70;

    A[10][11] = 75;
    A[11][10] = 75;

    A[11][12] = 120;
    A[12][11] = 120;

    A[2][5] = 99;
    A[5][2] = 99;

    A[2][6] = 80;
    A[6][2] = 80;

    A[6][12] = 146;
    A[12][6] = 146;

    A[6][9] = 97;
    A[9][6] = 97;

    A[12][9] = 138;
    A[9][12] = 138;

    A[5][8] = 211;
    A[8][5] = 211;

    A[9][8] = 101;
    A[8][9] = 101;

    A[8][13] = 90;
    A[13][8] = 90;

    A[8][14] = 85;
    A[14][8] = 85;

    A[14][15] = 98;
    A[15][14] = 98;

    A[15][16] = 86;
    A[16][15] = 86;

    A[14][17] = 142;
    A[17][14] = 142;

    A[17][18] = 92;
    A[18][17] = 92;

    A[18][19] = 87;
    A[19][18] = 87;


    return 0;
}

//creare H - se refera la distanta pana la Bucuresti
int CreareVector(int H[20]){
    H[0]=366; //Arad
    H[1]=374;//Zerind
    H[2]=253;//Sibiu
    H[3]=329;//Timisoara
    H[4]=380;//Oradea
    H[5]=176;//Fagaras
    H[6]=193;//RV
    H[7]=244;//Lugoj
    H[8]=0;//Bucuresti
    H[9]=101;//Pitesti
    H[10]=241;//Mehadia
    H[11]=242;//Drobeta
    H[12]=160;//Craiova
    H[13]=77;//Giurgiu
    H[14]=80;//Urziceni
    H[15]=151;//Hirsova
    H[16]=161;//Efoerie
    H[17]=199;//Vaslui
    H[18]=226;//Iasi
    H[19]=234;//Neamt
    return 0;
}

int gasireVecini(int n,int A[20][20], /*char *nume[20],*/int noduri[20],int &nrnoduri)
{
    //cout << "Orasul " << nume[n] << " are ca vecini:" << endl;
    for(int i=0; i<20; i++)
        if (A[n][i] != 0)
        {
            noduri[nrnoduri++] = i;
            //cout << "-" << nume[i] << " aflat la " << A[n][i] << " km distanta" << endl;
        }

    return 0;
}


int latime(int start, int stop, int A[20][20], char *nume[20])
{
    int nrNoduri = 0, contorViz = 0;

    int noduri[20];//orasele in asteptare
    int viz[20];//orase deja vizitate
    int parinte[20];//parinte[i]=j =>j este parintele lui i
    int gasit = 0;
    for (int i = 0; i < 20; i++)
        viz[i] = 0;
    viz[start] = 1;
    noduri[0] = start;
    nrNoduri++;
    int contorpas = 0;

    cout << "Pasul " << contorpas++ << ": ";
    for (int i = 0; i < nrNoduri; i++)
        cout << nume[noduri[i]] << " ";
    cout << endl;


    while (gasit == 0 && nrNoduri > 0)
    {
        int nod = noduri[0];
        //cout << nume[nod] << " ";
        for (int i = 0; i < nrNoduri - 1; i++)
            noduri[i] = noduri[i + 1];
        nrNoduri--;
        if (nod == stop)
            gasit = 1;
        else
            for (int i = 0; i<20; i++)
                if ((A[nod][i] != 0) && (viz[i] == 0))
                {
                    noduri[nrNoduri++] = i;
                    viz[i] = 1;//cout << "-" << nume[i] << " aflat la " << A[n][i] << " km distanta" << endl;
                    parinte[i] = nod;
                }
        cout << "Pasul " << contorpas++ << ": ";
        for (int i = 0; i < nrNoduri; i++)
            cout << nume[noduri[i]] << " ";
        cout << endl;
        //cout << nume[nod] << " ";

    }
    cout << endl;
    int temp = stop;
    int contorTraseu = 0;
    int traseu[20];
    while (parinte[temp] != start)
    {
        traseu[contorTraseu++] = temp;
        temp = parinte[temp];
    }
    traseu[contorTraseu++] = temp;
    traseu[contorTraseu++] = parinte[temp];
    for (int i = contorTraseu - 1; i >= 0; i--)
    {
        cout << nume[traseu[i]] << ", ";
    }

    return 0;
}

int adancime(int start, int stop, int A[20][20], char *nume[20])
{



    int nrNoduri = 0, contorViz = 0;

    int noduri[20];//orasele in asteptare
    int viz[20];//orase deja vizitate
    int parinte[20];//parinte[i]=j =>j este parintele lui i
    int gasit = 0;
    for (int i = 0; i < 20; i++)
        viz[i] = 0;
    viz[start] = 1;
    noduri[0] = start;
    nrNoduri++;
    int contorpas = 0;

    cout << "Pasul " << contorpas++ << ": ";
    for (int i = 0; i < nrNoduri; i++)
        cout << nume[noduri[i]] << " ";
    cout << endl;


    while (gasit == 0 && nrNoduri > 0)
    {
        int nod = noduri[0];
        for (int i = 0; i < nrNoduri - 1; i++)
            noduri[i] = noduri[i + 1];
        nrNoduri--;
        if (nod == stop)
            gasit = 1;
        else
            for (int i = 0; i<20; i++)
                if ((A[nod][i] != 0) && (viz[i] == 0))
                {
                    for (int j = nrNoduri-1; j >= 0; j--)
                        noduri[j+1] = noduri[j];
                    nrNoduri++;
                    noduri[0] = i;
                    viz[i] = 1;
                    parinte[i] = nod;
                }
        cout << "Pasul " << contorpas++ << ": ";
        for (int i = 0; i < nrNoduri; i++)
            cout << nume[noduri[i]] << " ";
        cout << endl;

    }
    cout << endl;
    int temp = stop;
    int contorTraseu = 0;
    int traseu[20];
    while (parinte[temp] != start)
    {
        traseu[contorTraseu++] = temp;
        temp = parinte[temp];
    }
    traseu[contorTraseu++] = temp;
    traseu[contorTraseu++] = parinte[temp];
    for (int i = contorTraseu - 1; i >= 0; i--)
    {
        cout << nume[traseu[i]] << ", ";
    }

    return 0;
}
//cautare limitata stocam adancimea fiecarui nod din arbore

int adancimeLimitata(int start, int stop, int A[20][20], char *nume[20], int limita)
{

    int nrNoduri = 0, contorViz = 0;

    int noduri[20];//orasele in asteptare
    int viz[20];//orase deja vizitate
    int parinte[20];//parinte[i]=j =>j este parintele lui i
    int gasit = 0;
    for (int i = 0; i < 20; i++)
        viz[i] = 0;
    viz[start] = 1;
    noduri[0] = start;
    nrNoduri++;
    int contorpas = 0;

    cout << "Pasul " << contorpas++ << ": ";
    for (int i = 0; i < nrNoduri; i++)
        cout << nume[noduri[i]] << " ";
    cout << endl;
    int adancime[20];
    adancime[start]=0;


    while (gasit == 0 && nrNoduri > 0)
    {
        int nod = noduri[0];
        for (int i = 0; i < nrNoduri - 1; i++)
            noduri[i] = noduri[i + 1];
        nrNoduri--;
        if (nod == stop)
            gasit = 1;
        else
            for (int i = 0; i<20; i++)
                if ((A[nod][i] != 0) && (viz[i] == 0) && adancime[nod]<limita-1)
                {
                    for (int j = nrNoduri-1; j >= 0; j--)
                        noduri[j+1] = noduri[j];
                    nrNoduri++;
                    noduri[0] = i;
                    viz[i] = 1;
                    parinte[i] = nod;
                    adancime[i]=adancime[nod]+1;
                }
        cout << "Pasul " << contorpas++ << ": ";
        for (int i = 0; i < nrNoduri; i++)
        {
            cout << nume[noduri[i]] << " ";
        }
        cout << endl;
    }

    if(gasit)
    {
        cout << endl;
        int temp = stop;
        int contorTraseu = 0;
        int traseu[20];
        while (parinte[temp] != start)
        {
            traseu[contorTraseu++] = temp;
            temp = parinte[temp];
        }
        traseu[contorTraseu++] = temp;
        traseu[contorTraseu++] = parinte[temp];
        for (int i = contorTraseu - 1; i >= 0; i--)
        {
            cout<<nume[traseu[i]]<<" "<<adancime[traseu[i]] <<", ";
        }
    }
    else
        cout<<"nu  s-a gasit drum de la  "<<nume[start]<<" la  " <<nume[stop]<<"cu limita  "<<limita<<endl;
    return 0;
}

int cautareLimApel(int start, int stop, int A[20][20], char *nume[20], int limita)
{

    int nrNoduri = 0, contorViz = 0;

    int noduri[20];//orasele in asteptare
    int viz[20];//orase deja vizitate
    int parinte[20];//parinte[i]=j =>j este parintele lui i
    int gasit = 0;
    for (int i = 0; i < 20; i++)
        viz[i] = 0;
    viz[start] = 1;
    noduri[0] = start;
    nrNoduri++;
    int contorpas = 0;

    cout << "Pasul " << contorpas++ << ": ";
    for (int i = 0; i < nrNoduri; i++)
        cout << nume[noduri[i]] << " ";
    cout << endl;
    int adancime[20];
    adancime[start]=0;

    while (gasit == 0 && nrNoduri > 0)
    {
        int nod = noduri[0];
        for (int i = 0; i < nrNoduri - 1; i++)
            noduri[i] = noduri[i + 1];
        nrNoduri--;
        if (nod == stop)
            gasit = 1;
        else
            for (int i = 0; i<20; i++)
                if ((A[nod][i] != 0) && (viz[i] == 0) && adancime[nod]<limita-1)
                {
                    for (int j = nrNoduri-1; j >= 0; j--)
                        noduri[j+1] = noduri[j];
                    nrNoduri++;
                    noduri[0] = i;
                    viz[i] = 1;
                    parinte[i] = nod;
                    adancime[i]=adancime[nod]+1;
                }
        cout << "Pasul " << contorpas++ << ": ";
        for (int i = 0; i < nrNoduri; i++)
        {
            cout << nume[noduri[i]] << " ";
        }
        cout << endl;
    }

    if(gasit)
    {
        cout << endl;
        int temp = stop;
        int contorTraseu = 0;
        int traseu[20];
        while (parinte[temp] != start)
        {
            traseu[contorTraseu++] = temp;
            temp = parinte[temp];
        }
        traseu[contorTraseu++] = temp;
        traseu[contorTraseu++] = parinte[temp];
        for (int i = contorTraseu - 1; i >= 0; i--)
        {
            cout<<nume[traseu[i]]<<" "<<adancime[traseu[i]] <<", ";
        }
    }
    return gasit;
}

void cautareIterativa(int start, int stop, int A[20][20], char *nume[20])
{
    int gasit = 0;
    int limita = 1;
    while((limita < 20) && (gasit == 0))
    {
        gasit = cautareLimApel(start,stop,A,nume, limita);
        if (gasit == 0)
            limita++;
    }
    if (gasit)
        cout<<"solutia a fost gasita cu cautare iterativa si limita"<<limita<<endl;
}


int cautareCostUniform(int start, int stop, int A[20][20], char *nume[20])
{


    int cost[20];
    cost[start]=0;
    int nrNoduri = 0, contorViz = 0;

    int noduri[40];//orasele in asteptare
    int viz[20];//orase deja vizitate
    int parinte[20];//parinte[i]=j =>j este parintele lui i
    int gasit = 0;
    for (int i = 0; i < 20; i++)
        viz[i] = 0;
    viz[start] = 1;
    noduri[0] = start;
    nrNoduri++;
    int contorpas = 0;


    cout << "Pasul " << contorpas++ << ": ";
    for (int i = 0; i < nrNoduri; i++)
        cout << nume[noduri[i]] << " ";
    cout << endl;


    while (gasit == 0 && nrNoduri > 0)
    {
        int nod = noduri[0];
        for (int i = 0; i < nrNoduri - 1; i++)
            noduri[i] = noduri[i + 1];
        nrNoduri--;
        if (nod == stop)
            gasit = 1;
        else
            for (int i = 0; i<20; i++)
                if ((A[nod][i] != 0) )  //
                {
                    int costNou=cost[nod]+A[nod][i];
                    if(viz[i]==0 ||(cost[i]>costNou))
                    {
                        viz[i] = 1;
                        parinte[i] = nod;
                        cost[i]=cost[nod]+A[nod][i];
                        int poz=0;
                        while((poz<nrNoduri)&&(cost[i]>cost[noduri[poz]]))
                            poz++;
                        cout<<poz<<endl;

                        for(int j=nrNoduri; j>poz; j--)
                        {
                            noduri[j]=noduri[j-1];
                        }

                        noduri[poz]=i;

                        nrNoduri++;
                    }


                }
        cout << "Pasul " << contorpas++ << ": ";
        for (int i = 0; i < nrNoduri; i++)
            cout << nume[noduri[i]] << " ";
        cout << endl;

    }
    cout << endl;
    int temp = stop;
    int contorTraseu = 0;
    int traseu[20];
    while (parinte[temp] != start)
    {
        traseu[contorTraseu++] = temp;
        temp = parinte[temp];
    }
    traseu[contorTraseu++] = temp;
    traseu[contorTraseu++] = parinte[temp];
    for (int i = contorTraseu - 1; i >= 0; i--)
    {
        cout << nume[traseu[i]] << " "<<cost[traseu[i]]<<", ";
    }

    return 0;
}
int cautareGreedy(int start, int stop, int A[20][20], char *nume[20])
{


    int cost[20];
    cost[start]=0;
    int nrNoduri = 0, contorViz = 0;

    int noduri[40];//orasele in asteptare
    int viz[20];//orase deja vizitate
    int parinte[20];//parinte[i]=j =>j este parintele lui i
    int gasit = 0;
    for (int i = 0; i < 20; i++)
        viz[i] = 0;
    viz[start] = 1;
    noduri[0] = start;
    nrNoduri++;
    int contorpas = 0;


    cout << "Pasul " << contorpas++ << ": ";
    for (int i = 0; i < nrNoduri; i++)
        cout << nume[noduri[i]] << " ";
    cout << endl;


    while (gasit == 0 && nrNoduri > 0)
    {
        int nod = noduri[0];
        for (int i = 0; i < nrNoduri - 1; i++)
            noduri[i] = noduri[i + 1];
        nrNoduri--;
        if (nod == stop)
            gasit = 1;
        else
            for (int i = 0; i<20; i++)
                if ((A[nod][i] != 0) )  //
                {
                    int costNou=cost[nod]+A[nod][i];
                    if(viz[i]==0)
                    {
                        viz[i] = 1;
                        parinte[i] = nod;
                        cost[i]=cost[nod]+A[nod][i];
                        int poz=0;
                        while((poz<nrNoduri)&&(H[i]>H[noduri[poz]]))
                            poz++;
                        cout<<poz<<endl;

                        for(int j=nrNoduri; j>poz; j--)
                        {
                            noduri[j]=noduri[j-1];
                        }

                        noduri[poz]=i;

                        nrNoduri++;
                    }


                }
        cout << "Pasul " << contorpas++ << ": ";
        for (int i = 0; i < nrNoduri; i++)
            cout << nume[noduri[i]] << " ";
        cout << endl;

    }
    cout << endl;
    int temp = stop;
    int contorTraseu = 0;
    int traseu[20];
    while (parinte[temp] != start)
    {
        traseu[contorTraseu++] = temp;
        temp = parinte[temp];
    }
    traseu[contorTraseu++] = temp;
    traseu[contorTraseu++] = parinte[temp];
    for (int i = contorTraseu - 1; i >= 0; i--)
    {
        cout << nume[traseu[i]] << " "<<cost[traseu[i]]<<", ";
    }

    return 0;
}

int cautareAStar(int start, int stop, int A[20][20], char *nume[20])
{


    int cost[20];
    cost[start]=0;
    int nrNoduri = 0, contorViz = 0;

    int noduri[40];//orasele in asteptare
    int viz[20];//orase deja vizitate
    int parinte[20];//parinte[i]=j =>j este parintele lui i
    int gasit = 0;
    for (int i = 0; i < 20; i++)
        viz[i] = 0;
    viz[start] = 1;
    noduri[0] = start;
    nrNoduri++;
    int contorpas = 0;


    cout << "Pasul " << contorpas++ << ": ";
    for (int i = 0; i < nrNoduri; i++)
        cout << nume[noduri[i]] << " ";
    cout << endl;


    while (gasit == 0 && nrNoduri > 0)
    {
        int nod = noduri[0];
        for (int i = 0; i < nrNoduri - 1; i++)
            noduri[i] = noduri[i + 1];
        nrNoduri--;
        if (nod == stop)
            gasit = 1;
        else
            for (int i = 0; i<20; i++)
                if ((A[nod][i] != 0) )  //
                {
                    int costNou=cost[nod]+A[nod][i];
                    if(viz[i]==0 ||(cost[i]>costNou))
                    {
                        viz[i] = 1;
                        parinte[i] = nod;
                        cost[i]=cost[nod]+A[nod][i];
                        int poz=0;
                        while((poz<nrNoduri)&&((cost[i]+H[i])>(cost[noduri[poz]]+H[noduri[poz]])))
                            poz++;
                        cout<<poz<<endl;

                        for(int j=nrNoduri; j>poz; j--)
                        {
                            noduri[j]=noduri[j-1];
                        }
                        noduri[poz]=i;

                        nrNoduri++;
                    }


                }
        cout << "Pasul " << contorpas++ << ": ";
        for (int i = 0; i < nrNoduri; i++)
            cout << nume[noduri[i]] << " ";
        cout << endl;

    }
    cout << endl;
    int temp = stop;
    int contorTraseu = 0;
    int traseu[20];
    while (parinte[temp] != start)
    {
        traseu[contorTraseu++] = temp;
        temp = parinte[temp];
    }
    traseu[contorTraseu++] = temp;
    traseu[contorTraseu++] = parinte[temp];
    for (int i = contorTraseu - 1; i >= 0; i--)
    {
        cout << nume[traseu[i]] << " "<<cost[traseu[i]]<<", ";
    }

    return 0;
}
int main()
{
    char *nume[20] = { "Arad", "Zerind", "Sibiu", "Timisoara", "Oradea", "Fagaras", "Ramnicu Valcea", "Lugoj", "Bucuresti", "Pitesti", "Mehadia", "Drobeta", "Craiova", "Giurgiu", "Urziceni", "Hirsova", "Eforie", "Vaslui", "Iasi", "Neamt" };
    //                   0         1        2          3          4          5              6            7          8           9         10          11        12         13         14          15         16        17       18      19

    int A[20][20] = { { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
        { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
    };


    CreareMatrice(A);
    CreareVector(H);
    int start = 0, stop = 8;
    cout << endl<<"Cautare in latime:" << endl;
    latime(start, stop, A, nume);
    cout << endl << endl<< "Cautare in adancime:" << endl;
    adancime(start, stop, A, nume);
    cout << endl << endl<< "Cautare in adancime limitata:" << endl;
    adancimeLimitata(start,stop,A,nume,4);
    cout << endl << endl<< "Cautare in adancime limitata:" << endl;
    cautareIterativa(start,stop,A,nume);
    cout << endl << endl<< "Cautare cost uniform:" << endl;
    cautareCostUniform(start,stop,A,nume);
    cout << endl << endl<< "Cautare Greedy:" << endl;
    cautareGreedy(start,stop,A,nume);
    cout << endl << endl<< "Cautare A*:" << endl;
    cautareAStar(start,stop,A,nume);
    _getch();
    return 0;
}