0

我在这里链接了代码..我只是觉得我不了解搜索算法。我还没有真正尝试过，但我知道我不需要做其他事情。我觉得这对我来说太简单了，我无法理解。

当我阅读广度优先搜索时，我确实知道在树上向下移动一个级别之前我必须搜索行（对于深度首先向下移动也是如此），但是如何编码？我只是难过。

基本上，这是一个使用 Glut/OPENGL 的 8-Puzzle，计算机会在其中搜索您，并且应该将动作输出给所述用户。空白总是从中间开始。我将订单保存在一个数组中，然后需要输出动作。我被难住的是搜索本身。

#include <stdio.h>                         // standard C libraries
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <string.h>
#include <GL/glut.h>                       // GLUT library
#include "cs_graphics_setup.h"             // Header for CS4250/5250/6250 courses


// Constants
#define WINDOW_XS 25                       // Window size
#define WINDOW_YS 256
#define WINDOW_NAME "Sliding Box Game"     // Window name
#define FONT_10 GLUT_BITMAP_TIMES_ROMAN_10 // font size to 10
#define FONT_24 GLUT_BITMAP_TIMES_ROMAN_24 // font size to 24
#define ANI_MSEC 10                        // gap between frames


// Structures
typedef struct pt
{
    GLfloat x, y;
} MyPoint;


// Global Variables
MyPoint bottomLeftPt;

int xside = 80;
int yside = 80;
int innerx = 70;
int innery = 70;
int i, j, temp, v;

int arrayNumRand[9] = {1, 2, 3, 4, 0, 5, 6, 7, 8};

//multidimensional array that holds the x-coordinate of the big square, the
//y-coordinate of the big square, and the number that is to be displayed.
int arrayCoord[9][2] =
{
    {8, 168},
    {88, 168},
    {168, 168},
    {8, 88},
    {88, 88},
    {168, 88},
    {8, 8},
    {88, 8},
    {168, 8}
};

//int goUp = 0;  // 0- go up, 1- come down

// Function prototypes
void display_func(void);
void keyboard_func(unsigned char c, int x, int y);
//void animation_func(int val);
void drawSquareFn(int, int, int, int, int);
void display_num(int, int, int);


int main(int argc, char **argv)
{
    glutInit(&argc, argv);
    init_setup(WINDOW_XS, WINDOW_YS, WINDOW_NAME);
    //initial testing of arrayNumRand randomization
    srand(time(NULL));
    for(i = 0; i <9; i++)
    {
        j = (rand() %8)+1;
        if(j != 4 && i != 4)
        {
            temp = arrayNumRand[i];
            arrayNumRand[i] = arrayNumRand[j];
            arrayNumRand[j] = temp;
        }
    }
    for(i = 0; i <9; i++)
    {
        printf(" %d", arrayNumRand[i]);
    }
    glutDisplayFunc(display_func);
    glutKeyboardFunc(keyboard_func);
    //glutTimerFunc(ANI_MSEC, animation_func, 0);
    glutMainLoop();
    return 1;
}   // end of main()


void display_func(void)
{
    glClearColor(0.50, 78.0, 139.0, 0.0); // background color (purple)
    glClear(GL_COLOR_BUFFER_BIT);         // clearing the buffer not to keep the color
    for(v = 0; v <9; v ++)
    {
        drawSquareFn(arrayCoord[v][0], arrayCoord[v][1], xside, yside, v);
    }
    glFlush();
    glutSwapBuffers();                    // double buffering
}   // end of display_func()



void keyboard_func(unsigned char c, int x, int y)
{
    switch(c)
    {
        /*case 'b' :
        case 'B' :
            //breadth_first_search function

            glutPostRedisplay();
            break;

        case 'd' :
        case 'D' :
            //depth_first_search function

            glutPostRedisplay();
            break;*/
    case 'i' :
    case 'I' :
        for(i = 0; i <9; i++)
        {
            j = (rand() %8)+1;
            if(j != 4 && i != 4)
            {
                temp = arrayNumRand[i];
                arrayNumRand[i] = arrayNumRand[j];
                arrayNumRand[j] = temp;
            }
            display_func();
        }
        for(i = 0; i <9; i++)
        {
            printf(" %d", arrayNumRand[i]);
        }
        break;
    case 'Q' :
    case 'q' :
        printf("Good Bye !\n");
        exit(0);                 // terminates the program
    }  // end of switch
}   // end of keyboard_func()


/*void animation_func(int val)
{
int moveGap = 5;

if( goUp == 0 )
{
    bottomLeftPt.x += moveGap;
    bottomLeftPt.y += moveGap;

    if( bottomLeftPt.x+recLength > WINDOW_XS)
    {
        bottomLeftPt.x -= moveGap;
        bottomLeftPt.y -= moveGap;

        goUp = 1;
    }
    else if( bottomLeftPt.y+recHeight > WINDOW_YS)
    {
        bottomLeftPt.x -= moveGap;
        bottomLeftPt.y -= moveGap;

        goUp = 1;
    }
}
else // goUp = 1
{
    bottomLeftPt.x -= moveGap;
    bottomLeftPt.y -= moveGap;

    if( bottomLeftPt.x < 50)
    {
        bottomLeftPt.x += moveGap;
        bottomLeftPt.y += moveGap;

        goUp = 0;
    }
    else if( bottomLeftPt.y < 50)
    {
        bottomLeftPt.x += moveGap;
        bottomLeftPt.y += moveGap;

        goUp = 0;
    }
}

glutPostRedisplay();
glutTimerFunc(ANI_MSEC, animation_func, 0);
}//end animation_func*/

//beginning of drawSquare Function to create the two nested squares and place the     number on the board.
void drawSquareFn(int x, int y, int xside, int yside, int num)
{
    // draw a rectangle
    glColor3f(0.0, 0.0, 0.0);           // setting pen color (black)
    glBegin(GL_POLYGON);
    glVertex2i(x, y);
    glVertex2i(x+xside, y);
    glVertex2i(x+xside, y+yside);
    glVertex2i(x, y+yside);
    glEnd();
    // draw the outline of rectangle
    glColor3f(0.0, 0.0, 0.0);           // setting pen color (black)
    glBegin(GL_LINES);
    glVertex2i(x, y);
    glVertex2i(x+xside, y);
    glVertex2i(x+xside, y);
    glVertex2i(x+xside, y+yside);
    glVertex2i(x+xside, y+yside);
    glVertex2i(x, y+yside);
    glVertex2i(x, y+yside);
    glVertex2i(x,y);
    glEnd();
    x += 5;
    y += 5;
    if(arrayNumRand[num] != 0)
    {
        // draw inner rectangle
        glColor3f(1.0, 1.0, 1.0);           // setting pen color (black)
        glBegin(GL_POLYGON);
        glVertex2i(x, y);
        glVertex2i(x+innerx, y);
        glVertex2i(x+innerx, y+innery);
        glVertex2i(x, y+innery);
        glEnd();
        //// draw the outline of rectangle
        //glColor3f(1.0, 1.0, 1.0);         // setting pen color (black)
        //glBegin(GL_LINES);
        //  glVertex2i(x, y);
        //  glVertex2i(x+innerx, y);
        //  glVertex2i(x+innerx, y);
        //  glVertex2i(x+innerx, y+innery);
        //  glVertex2i(x+innerx, y+innery);
        //  glVertex2i(x, y+innery);
        //  glVertex2i(x, y+innery);
        //  glVertex2i(x,y);
        //  glEnd();
        x += 23;
        y += 23;
        //new x value, new y-value, and the number listed above and decide upon color display_num
        display_num(x, y, num);
    }
}

void display_num(int newx, int newy, int newnum)
{
    int points[10];
    int i = 0, j;
    int pos;
    int is_negative = 0;
    for(j = 0; j < 10; j++)
    {
        points[j] = ' ';
    }
    if(newnum < 0)
    {
        is_negative = 1;
        newnum *= -1;
    }
    while(newnum > 9)
    {
        points[i] = newnum % 10;
        newnum = newnum / 10;
        i += 1;
    }
    points[i] = 1;
    glColor3f(0.0, 0.0, 0.0);
    pos = newx;
    if(is_negative == 1)
    {
        glRasterPos2i(pos, newy);
        glutBitmapCharacter(FONT_24, '-');
        pos += glutBitmapWidth(FONT_24, '-');
    }
    glRasterPos2i(pos, newy);
    glutBitmapCharacter(FONT_24, (char)(arrayNumRand[newnum]+48));
    pos += glutBitmapWidth(FONT_24, (char)(arrayNumRand[newnum]+48));
}

void breadthFirstSearch()

void depthFirstSearch()
{
}
4

1 回答 1

0

您要遍历的树是棋盘状态树。这将是一个隐式树：您不会构建树数据结构并用板填充它。树中的每个节点都是板上所有图块的一个位置。您的根节点是棋盘，周围有 8 个随机排列的瓷砖，中间有 1 个空白。无需遍历树数据结构，因为您只需知道状态即可轻松计算每个状态的子节点。从根部开始，您有 4 个孩子（每个侧瓦都滑入洞中）。每个人只有 3 个孩子（由于棋盘的边缘）。有些动作会产生循环（例如，在您的第二个动作中撤消您的第一个动作），这是您想要避免的。

如果您想象这棵树（没有循环），那么树的节点就是所有其他板状态。其中一些州是解决这个难题的方法。从这些解决方案节点中的任何一个开始，这组移动只是从根通过树到目标节点的路径。

对于这种大小的谜题，您可能只需直接搜索目标即可。对于更复杂的问题（例如 256x256 滑动拼图，或更复杂的游戏，如国际象棋），您将无法“看到”残局。在这些情况下，您将必须有一个评分功能来评估您是变得更好还是更糟。然后，您将通过树导航到足够接近的有希望的区域，以便您查看目标状态并找到答案。

于 2013-07-22T05:19:55.070 回答