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

トラバースしたいツリーは、ボードの状態のツリーです。これは暗黙のツリーになります。ツリーのデータ構造を構築してボードで埋めることはありません。ツリーの各ノードは、ボード上のすべてのタイルの 1 つの位置です。ルート ノードは、周囲にランダムに配置された 8 つのタイルと中央に 1 つの空白があるボードです。状態を知るだけで各状態の子を簡単に計算できるため、トラバースするツリー データ構造を持つ必要はありません。ルートから 4 つの子があります (それぞれのサイド タイルが穴に滑り込みます)。それらのそれぞれには 3 つの子しかありません (ボードの端のため)。一部の移動は、回避したいサイクルを作成します (たとえば、最初の移動を 2 番目の移動で元に戻す)。

このツリー (サイクルなし) を想像すると、ツリーのノードはすべて他のボード状態です。これらの状態のいくつかは、パズルの解決策です。これらのソリューション ノードのいずれかからの移動のセットは、ルートからツリーを介してゴール ノードまでの単なるパスです。

そのサイズのパズルの場合、おそらくゴールまで直接検索できます。より複雑な問題 (たとえば、256x256 のスライディング タイル パズル、またはチェスのようなより複雑なゲーム) では、エンドゲームを「見る」ことができません。そのような場合、あなたが良くなっているのか悪くなっているのかを評価するためのスコアリング機能が必要になります。次に、ツリーをたどって、目標の状態を確認し、答えを見つけるのに十分近い有望な領域に移動します。

于 2013-07-22T05:19:55.070 に答える