API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Apr 25th, 2017
64
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 15.16 KB | None | 0 0
raw download clone embed print report
  1. /*
  2.   Nadyan Suriel Pscheidt
  3.   Inteligencia artificial
  4.   Busca Cega
  5.  
  6.   Compilar com Interface grafica:
  7.   sudo apt-get install libsfml-dev
  8.   g++ -c buscaCega.cpp
  9.   g++ -o buscaCega buscaCega.o -lsfml-graphics -lsfml-window -lsfml-system
  10.   ./buscaCega
  11.  
  12.   Compilar humildemente pra rodar no terminal:
  13.   g++ -o buscaCega buscaCega.cpp
  14.   ./buscaCega
  15. */
  16.  
  17. /* Bibs */
  18. #include <cstdio>
  19. #include <cstring>
  20. #include <cstdlib>
  21. #include <unistd.h>
  22. #include <time.h>
  23. #include <list>
  24. //#include <SFML/Graphics.hpp>
  25.  
  26. /* Defs */
  27. #define TAM 42  //terreno TAMxTAM
  28.  
  29. /* struct para os pontos de origem e destino */
  30. typedef struct{
  31.     int x;
  32.     int y;
  33.     int paix, paiy;
  34. }Ponto;
  35.  
  36. /* Vars */
  37. std::list<Ponto> lista;
  38. Ponto origem, destino;
  39. int terreno[TAM][TAM];
  40. int visitados[TAM][TAM];
  41. char terrenoChar[TAM][TAM][2];
  42. char terrenoLarg[TAM][TAM][2];
  43. char terrenoUni[TAM][TAM][2];
  44. int qtdLarg = 0, qtdUni = 0, custoLarg = 0, custoUni = 0;
  45.  
  46. /* Funcs */
  47. void montaCenario();
  48. void imprimeCenario();
  49. void limpaTela();
  50. void initVisitados();
  51. void imprimeFinal();
  52. void bfs(int i, int j);
  53. int dfs(int i, int j);
  54. void uniforme(int i, int j);
  55. int buscaGulosa(int i, int j);
  56.  
  57. int main(){
  58.     int i, j;
  59.  
  60.     printf("Informe o ponto de inicio: ");
  61.     scanf("%d %d", &origem.x, &origem.y);
  62.     printf("Informe o ponto de destino: ");
  63.     scanf("%d %d", &destino.x, &destino.y);
  64.  
  65.     initVisitados();
  66.     montaCenario();
  67.     limpaTela();
  68.  
  69.     printf("\nExecutando Busca em Largura:\n\n");
  70.     bfs(origem.x, origem.y);
  71.  
  72.     /* Montagem da matriz de resultados largura */
  73.     /*for(i = 0; i < TAM; i++){
  74.         for(j = 0; j < TAM; j++){
  75.             if(terrenoChar[i][j][1] == '.'){
  76.                 terrenoLarg[i][j][0] = terrenoChar[i][j][0];
  77.                 terrenoLarg[i][j][1] = terrenoChar[i][j][1];
  78.             }else{
  79.                 terrenoLarg[i][j][0] = ' ';
  80.                 terrenoLarg[i][j][1] = ' ';
  81.             }
  82.         }
  83.     }*/
  84.  
  85.     //initVisitados();
  86.     //montaCenario();
  87.  
  88.     //printf("\n\nExecutando Busca Cega Uniforme:\n\n");
  89.     //uniforme(inicio.x, inicio.y);
  90.  
  91.     /* Montagem da matriz de resultados uniforme */
  92.   /*  for(i = 0; i < TAM; i++){
  93.         for(j = 0; j < TAM; j++){
  94.             if(terrenoChar[i][j][1] == '.'){
  95.                 terrenoUni[i][j][0] = terrenoChar[i][j][0];
  96.                 terrenoUni[i][j][1] = terrenoChar[i][j][1];
  97.             }else{
  98.                 terrenoUni[i][j][0] = ' ';
  99.                 terrenoUni[i][j][1] = ' ';
  100.             }
  101.         }
  102.     }
  103.  
  104.     limpaTela();
  105.     imprimeFinal();
  106.     //printf("\nLargura:\n  - Custo: %d\n  - Visitados: %d\n\nUniforme:\n  - Custo: %d\n  - Visitados: %d\n\n", custoLarg, qtdLarg, custoUni, qtdUni);
  107. */
  108.     // Interface grafica
  109.     /*
  110.     sf::RenderWindow window(sf::VideoMode(800, 800), "Busca Cega");
  111.     sf::RectangleShape rectangle(sf::Vector2f(120, 50));
  112.     rectangle.setFillColor(sf::Color::Blue);
  113.  
  114.     while(window.isOpen()){
  115.       sf::Event event;
  116.       while(window.pollEvent(event)){
  117.         if(event.type == sf::Event::Closed)
  118.           window.close();
  119.       }
  120.  
  121.       window.clear(sf::Color::Black);
  122.       window.draw(rectangle);
  123.       window.display();
  124.     }*/
  125.  
  126.     return 0;
  127. }
  128.  
  129. void montaCenario(){
  130.     FILE *f = fopen("terreno.txt", "r");
  131.     int i, j;
  132.  
  133.     for(i = 0; i < TAM; i++){
  134.         for(j = 0; j < TAM; j++){
  135.             fscanf(f, "%d", &terreno[i][j]);
  136.  
  137.             switch(terreno[i][j]){
  138.                 case 0:
  139.                     terrenoChar[i][j][0] = '0'; terrenoChar[i][j][1] = ' '; break;
  140.                 case 1:
  141.                     terrenoChar[i][j][0] = '1'; terrenoChar[i][j][1] = ' '; break;
  142.                 case 2:
  143.                     terrenoChar[i][j][0] = '2'; terrenoChar[i][j][1] = ' '; break;
  144.                 case 3:
  145.                     terrenoChar[i][j][0] = '3'; terrenoChar[i][j][1] = ' '; break;
  146.             }
  147.             terrenoLarg[i][j][0] = terrenoChar[i][j][0];
  148.             terrenoLarg[i][j][1] = terrenoChar[i][j][1];
  149.         }
  150.     }
  151. }
  152.  
  153. void imprimeCenario(){
  154.     int i, j;
  155.  
  156.     printf("\n");
  157.  
  158.     for(i = 0; i < TAM; i++){
  159.         for(j = 0; j < TAM; j++){
  160.             if(i == origem.x && j == origem.y)
  161.                 printf("   ");
  162.             else if(i == destino.x && j == destino.y)
  163.                 printf("   ");
  164.             else
  165.                 printf("%c%c ", terrenoChar[i][j][0], terrenoChar[i][j][1]);
  166.         }
  167.         printf("\n");
  168.     }
  169. }
  170.  
  171. int dfs(int i, int j){
  172.     terrenoChar[i][j][1] = '.';
  173.     visitados[i][j] = 1;
  174.  
  175.     limpaTela();
  176.     printf("\nExecutando Busca em Profundidade:\n\n");
  177.     imprimeCenario();
  178.     usleep(1000*30);
  179.  
  180.     if(i == destino.x && j == destino.y)
  181.         return 1;
  182.     else{
  183.         /* para cima */
  184.         if(i - 1 >= 0 && !visitados[i-1][j]){
  185.                   dfs(i-1, j);
  186.         }
  187.         /* para a direita */
  188.         else if(j + 1 < TAM && !visitados[i][j+1]){
  189.                   dfs(i, j+1);
  190.         }
  191.         /* para baixo */
  192.         else if(i + 1 < TAM && !visitados[i+1][j]){
  193.                   dfs(i+1, j);
  194.         }
  195.         /* para a esquerda */
  196.         else if(j - 1 >= 0 && !visitados[i][j-1]){
  197.                   dfs(i, j-1);
  198.         }
  199.     }
  200. }
  201.  
  202. void bfs(int i, int j){
  203.     Ponto paternidade[TAM][TAM];
  204.     int qtd = 0;
  205.  
  206.     //qtdLarg++; // contagem de posicoes
  207.     //custoLarg += terreno[i][j];
  208.  
  209.     //limpaTela();
  210.     //printf("\nExecutando Busca em Largura:\n\n");
  211.     //imprimeCenario();
  212.     //usleep(1000*30);
  213.  
  214.     visitados[i][j] = 1;
  215.  
  216.     Ponto inicio;
  217.     inicio.x = i; inicio.y = j;
  218.     inicio.paix = -1; inicio.paiy = -1; // nó raiz
  219.  
  220.     lista.push_front(inicio);
  221.  
  222.     while(!lista.empty()){
  223.         Ponto p = lista.front();
  224.         lista.pop_front();
  225.  
  226.         /* esquerda */
  227.         if(p.y - 1 >= 0 && !visitados[p.x][p.y-1]){
  228.             Ponto pnovo;
  229.             pnovo.x = p.x;
  230.             pnovo.y = p.y - 1;
  231.             pnovo.paix = p.x; pnovo.y = p.y;
  232.  
  233.             paternidade[pnovo.x][pnovo.y].paix = p.x;
  234.             paternidade[pnovo.x][pnovo.y].paiy = p.y;
  235.  
  236.             if(pnovo.x == destino.x && pnovo.y == destino.y)
  237.                 break;
  238.             else{
  239.                 qtd++;
  240.                 lista.push_back(pnovo);
  241.                 terrenoChar[pnovo.x][pnovo.y][1] = '.';
  242.                 visitados[pnovo.x][pnovo.y] = 1;
  243.                 limpaTela();
  244.                 imprimeCenario();
  245.                 usleep(1000*30);
  246.             }
  247.         }
  248.  
  249.         /* cima */
  250.         if(p.x - 1 >= 0 && !visitados[p.x-1][p.y]){
  251.             Ponto pnovo;
  252.             pnovo.x = p.x - 1;
  253.             pnovo.y = p.y;
  254.             pnovo.paix = p.x; pnovo.paiy = p.y;
  255.  
  256.             paternidade[pnovo.x][pnovo.y].paix = p.x;
  257.             paternidade[pnovo.x][pnovo.y].paiy = p.y;
  258.  
  259.             if(pnovo.x == destino.x && pnovo.y == destino.y)
  260.                 break;
  261.             else{
  262.                 qtd++;
  263.                 lista.push_back(pnovo);
  264.                 terrenoChar[pnovo.x][pnovo.y][1] = '.';
  265.                 visitados[pnovo.x][pnovo.y] = 1;
  266.                 limpaTela();
  267.                 imprimeCenario();
  268.                 usleep(1000*30);
  269.             }
  270.         }
  271.         /* direita */
  272.         if(p.y < TAM && !visitados[p.x][p.y+1]){
  273.             Ponto pnovo;
  274.             pnovo.x = p.x;
  275.             pnovo.y = p.y + 1;
  276.             pnovo.paix = p.x; pnovo.paiy = p.y;
  277.  
  278.             paternidade[pnovo.x][pnovo.y].paix = p.x;
  279.             paternidade[pnovo.x][pnovo.y].paiy = p.y;
  280.  
  281.             if(pnovo.x == destino.x && pnovo.y == destino.y)
  282.                 break;
  283.             else{
  284.                 qtd++;
  285.                 lista.push_back(pnovo);
  286.                 terrenoChar[pnovo.x][pnovo.y][1] = '.';
  287.                 visitados[pnovo.x][pnovo.y] = 1;
  288.                 limpaTela();
  289.                 imprimeCenario();
  290.                 usleep(1000*30);
  291.             }
  292.         }
  293.         /* baixo */
  294.         if(p.x + 1 < TAM && !visitados[p.x+1][p.y]){
  295.             Ponto pnovo;
  296.             pnovo.x = p.x + 1;
  297.             pnovo.y = p.y;
  298.             pnovo.paix = p.x; pnovo.paiy = p.y;
  299.  
  300.             paternidade[pnovo.x][pnovo.y].paix = p.x;
  301.             paternidade[pnovo.x][pnovo.y].paiy = p.y;
  302.  
  303.             if(pnovo.x == destino.x && pnovo.y == destino.y)
  304.                 break;
  305.             else{
  306.                 qtd++;
  307.                 lista.push_back(pnovo);
  308.                 terrenoChar[pnovo.x][pnovo.y][1] = '.';
  309.                 visitados[pnovo.x][pnovo.y] = 1;
  310.                 limpaTela();
  311.                 imprimeCenario();
  312.                 usleep(1000*30);
  313.             }
  314.         }
  315.         //printf("%d\n%d\n\n", p.y, visitados[p.x][p.y]);
  316.         //usleep(1000*1000);
  317.  
  318.  
  319.     }
  320.  
  321.     // caminho
  322.     Ponto fim;
  323.     fim.paix = destino.paix; fim.paiy = destino.paiy;
  324.     while(fim.paix != -1 && fim.paiy != -1){ // enquanto nao chegar na origem
  325.         terrenoLarg[fim.paix][fim.paiy][1] = '.';
  326.         fim.x = fim.paix;
  327.         fim.y = fim.paiy;
  328.     }
  329.  
  330.     limpaTela();
  331.     printf("\n\n");
  332.  
  333.     for(int i = 0; i < TAM; i++){
  334.         for(int j = 0; j < TAM; j++){
  335.             if(i == inicio.x && j == inicio.y)
  336.                 printf("I  ");
  337.             else if(i == destino.x && j == destino.y)
  338.                 printf("F  ");
  339.             else
  340.                 printf("%c%c ", terrenoLarg[i][j][0], terrenoLarg[i][j][1]);
  341.         }
  342.         printf("\n");
  343.     }
  344. }
  345.  
  346. void uniforme(int i, int j){
  347.     //qtdUni++; // contagem de posicoes
  348.     //custoUni += terreno[i][j];
  349.  
  350.     Ponto inicio;
  351.     inicio.x = i; inicio.y = j;
  352.  
  353.     lista.push_front(inicio);
  354.  
  355.     while(!lista.empty()){
  356.         int menor = 4;
  357.         Ponto p = lista.front();
  358.         lista.pop_front();
  359.  
  360.         if(p.y - 1 >= 0 && !visitados[p.x][p.y-1] && terreno[p.x][p.y-1] < menor){
  361.             Ponto pnovo;
  362.             pnovo.x = p.x;
  363.             pnovo.y = p.y - 1;
  364.             pnovo.paix = p.x; pnovo.y = p.y;
  365.             menor = terreno[p.x][p.y-1];
  366.  
  367.             if(pnovo.x == destino.x && pnovo.y == destino.y)
  368.                 break;
  369.             else{
  370.                 lista.push_back(pnovo);
  371.                 terrenoChar[pnovo.x][pnovo.y][1] = '.';
  372.                 visitados[pnovo.x][pnovo.y] = 1;
  373.                 limpaTela();
  374.                 imprimeCenario();
  375.                 usleep(1000*30);
  376.             }
  377.         }
  378.         /* cima */
  379.         if(p.x - 1 >= 0 && !visitados[p.x-1][p.y] && terreno[p.x-1][p.y] < menor){
  380.             Ponto pnovo;
  381.             pnovo.x = p.x - 1;
  382.             pnovo.y = p.y;
  383.             pnovo.paix = p.x; pnovo.paiy = p.y;
  384.             menor = terreno[p.x-1][p.y];
  385.  
  386.             if(pnovo.x == destino.x && pnovo.y == destino.y)
  387.                 break;
  388.             else{
  389.                 lista.push_back(pnovo);
  390.                 terrenoChar[pnovo.x][pnovo.y][1] = '.';
  391.                 visitados[pnovo.x][pnovo.y] = 1;
  392.                 limpaTela();
  393.                 imprimeCenario();
  394.                 usleep(1000*30);
  395.             }
  396.         }
  397.         /* direita */
  398.         if(p.y < TAM && !visitados[p.x][p.y+1] && terreno[p.x][p.y+1] < menor){
  399.             Ponto pnovo;
  400.             pnovo.x = p.x;
  401.             pnovo.y = p.y + 1;
  402.             pnovo.paix = p.x; pnovo.paiy = p.y;
  403.             menor = terreno[p.x][p.y+1];
  404.  
  405.             if(pnovo.x == destino.x && pnovo.y == destino.y)
  406.                 break;
  407.             else{
  408.                 lista.push_back(pnovo);
  409.                 terrenoChar[pnovo.x][pnovo.y][1] = '.';
  410.                 visitados[pnovo.x][pnovo.y] = 1;
  411.                 limpaTela();
  412.                 imprimeCenario();
  413.                 usleep(1000*30);
  414.             }
  415.         }
  416.         /* baixo */
  417.         if(p.x + 1 < TAM && !visitados[p.x+1][p.y] && terreno[p.x+1][p.y] < menor){
  418.             Ponto pnovo;
  419.             pnovo.x = p.x + 1;
  420.             pnovo.y = p.y;
  421.             pnovo.paix = p.x; pnovo.paiy = p.y;
  422.             menor = terreno[p.x+1][p.y];
  423.  
  424.             if(pnovo.x == destino.x && pnovo.y == destino.y)
  425.                 break;
  426.             else{
  427.                 lista.push_back(pnovo);
  428.                 terrenoChar[pnovo.x][pnovo.y][1] = '.';
  429.                 visitados[pnovo.x][pnovo.y] = 1;
  430.                 limpaTela();
  431.                 imprimeCenario();
  432.                 usleep(1000*30);
  433.             }
  434.         }
  435.         /* esquerda */
  436.  
  437.     }
  438. }
  439.  
  440.  
  441. int buscaGulosa(int i, int j){
  442.     int menor = 4; // para encontrar o menor
  443.     int i2 = 42, j2 = 42;
  444.  
  445.     qtdUni++; // contagem de posicoes
  446.     custoUni += terreno[i][j];
  447.  
  448.       /* Caso origem: 1 1
  449.               destino 30 35
  450.               funciona bem
  451.       */
  452.  
  453.       /* DESCOBRIR FORMA DE TRATAR CAMINHOS SEM SAIDA */
  454.  
  455.     terrenoChar[i][j][1] = '.';
  456.     visitados[i][j] = 1;
  457.  
  458.     limpaTela();
  459.     printf("\n\nExecutando Busca Cega Gulosa:\n\n");
  460.     imprimeCenario();
  461.     usleep(1000*30);
  462.  
  463.     if(i == destino.x && j == destino.y)
  464.         return 1;
  465.     else{
  466.         /* escolha do vizinho de menor custo */
  467.         /* se for para cima */
  468.         if(i - 1 >= 0 && !visitados[i-1][j]){
  469.             if(terreno[i-1][j] < menor ){
  470.                 i2 = i-1; j2 = j;
  471.                 menor = terreno[i-1][j];
  472.             }
  473.         }
  474.         /* se for para a direitra */
  475.         if(j + 1 < TAM && !visitados[i][j+1]){
  476.             if(terreno[i][j+1] < menor){
  477.                 i2 = i; j2 = j+1;
  478.                 menor = terreno[i][j+1];
  479.             }
  480.         }
  481.         /* se for para baixo */
  482.         if(i + 1 < TAM && !visitados[i+1][j]){
  483.             if(terreno[i+1][j] < menor){
  484.                 i2 = i+1; j2 = j;
  485.                 menor = terreno[i+1][j];
  486.             }
  487.         }
  488.         /* se for para a esquerda */
  489.         if(j - 1 >= 0 && !visitados[i][j-1]){
  490.             if(terreno[i][j-1] < menor){
  491.                 i2 = i; j2 = j-1;
  492.                 menor = terreno[i][j-1];
  493.             }
  494.         }
  495.         if(i2 != 42 && j2 != 42) /* se entrou em algum if */
  496.             uniforme(i2, j2);
  497.         else{
  498.             printf("\n\nFalha na busca, caminho nao encontrado!\n\n");
  499.             return 1;
  500.         }
  501.     }
  502. }
  503.  
  504. void initVisitados(){
  505.     int i, j;
  506.  
  507.     for(int i = 0; i < TAM; i++){
  508.         for(int j = 0; j < TAM; j++){
  509.             visitados[i][j] = 0;
  510.         }
  511.     }
  512. }
  513.  
  514. void imprimeFinal(){
  515.     int i, j;
  516.  
  517.     printf("\nCaminho percorrido pela busca em largura\n\n");
  518.  
  519.     for(i = 0; i < TAM; i++){
  520.         for(j = 0; j < TAM; j++){
  521.             if(i == origem.x && j == origem.y)
  522.                 printf("I  ");
  523.             else if(i == destino.x && j == destino.y)
  524.                 printf("F  ");
  525.             else
  526.                 printf("%c%c ", terrenoLarg[i][j][0], terrenoLarg[i][j][1]);
  527.         }
  528.         printf("\n");
  529.     }
  530.  
  531.     printf("\n\nCaminho percorrido pela busca de custo uniforme:\n\n");
  532.  
  533.     for(i = 0; i < TAM; i++){
  534.         for(j = 0; j < TAM; j++){
  535.           if(i == origem.x && j == origem.y)
  536.               printf("I  ");
  537.           else if(i == destino.x && j == destino.y)
  538.               printf("F  ");
  539.           else
  540.               printf("%c%c ", terrenoUni[i][j][0], terrenoUni[i][j][1]);
  541.         }
  542.         printf("\n");
  543.     }
  544.  
  545.     printf("\nLargura:\n  - Custo: %d\n  - Visitados: %d\n\nUniforme:\n  - Custo: %d\n  - Visitados: %d\n\n", custoLarg, qtdLarg, custoUni, qtdUni);
  546. }
  547.  
  548. void limpaTela(){
  549.     system("clear");
  550. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!