时间戳

首页 > 解决方案 > 关于如何制作启发式和目标状态的问题。C语言中的15个难题

c - 关于如何制作启发式和目标状态的问题。C语言中的15个难题

问题描述

我正在做一个家庭作业，用 A* 搜索解决 15 个难题。

所以 15 拼图问题的总体思路是，你有一个可以向上、向下、向左或向右移动的空白零瓷砖，目标是从 1 到 15 的顺序获得拼图，空白瓷砖是第 16 个瓷砖在拼图上。

我不太了解目标状态的概念，我是否在程序中写了这样的东西来制作目标状态？

for (i = 0; i < 16; i++)
{
goal_state[i] = i;
if(i == 16)
goal_state[i] = 0;
}

此外，启发式的想法，我理解 f(n) = g(n) + h(n) 但我如何将其转换为代码？移动 1 格是否会使 g 的值增加 1？我移动的瓷砖越多，g 增加的越多？h(n) 用于估计从 n 到目标的最便宜路径的成本。

如何估算最便宜路径的成本？我已经在寻找最便宜的路径了。

这是我到目前为止的代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 4
#define NxN (N*N)
#define TRUE 1
#define FALSE 0

struct node {
    int tiles[N][N];
    int f, g, h;
    short zero_row, zero_column;    /* location (row and colum) of blank tile 0 */
    struct node *next;
    struct node *parent;            /* used to trace back the solution */
};

int goal_rows[NxN];
int goal_columns[NxN];
struct node *start,*goal;
struct node *open = NULL, *closed = NULL;
struct node *succ_nodes[4];

void print_a_node(struct node *pnode) {
    int i,j;
    for (i=0;i<N;i++) {
        for (j=0;j<N;j++)
            printf("%2d ", pnode->tiles[i][j]);
        printf("\n");
    }
    printf("\n");
}

struct node *initialize(char **argv){
    int i,j,k,index, tile;
    struct node *pnode;

    pnode=(struct node *) malloc(sizeof(struct node));
    index = 1;
    for (j=0;j<N;j++)
        for (k=0;k<N;k++) {
            tile=atoi(argv[index++]);
            pnode->tiles[j][k]=tile;
            if(tile==0) {
                pnode->zero_row=j;
                pnode->zero_column=k;
            }
        }
    pnode->f=0;
    pnode->g=0;
    pnode->h=0;
    pnode->next=NULL;
    pnode->parent=NULL;
    start=pnode;
    printf("initial state\n");
    print_a_node(start);

    pnode=(struct node *) malloc(sizeof(struct node));
    goal_rows[0]=3;
    goal_columns[0]=3;

    for(index=1; index<NxN; index++){
        j=(index-1)/N;
        k=(index-1)%N;
        goal_rows[index]=j;
        goal_columns[index]=k;
        pnode->tiles[j][k]=index;
    }
    pnode->tiles[N-1][N-1]=0;         /* empty tile=0 */
    pnode->f=0;
    pnode->g=0;
    pnode->h=0;
    pnode->next=NULL;
    goal=pnode;
    printf("goal state\n");
    print_a_node(goal);

    return start;
}

/* merge unrepeated nodes into open list after filtering */
void merge_to_open() {
}

/*swap two tiles in a node*/
void swap(int row1,int column1,int row2,int column2, struct node * pnode){
}

/*update the f,g,h function values for a node */
void update_fgh(struct node *pnode){
}

/* 0 goes down by a row */
void move_down(struct node * pnode){
}

/* 0 goes right by a column */
void move_right(struct node * pnode){
}

/* 0 goes up by a row */
void move_up(struct node * pnode){
}

/* 0 goes left by a column */
void move_left(struct node * pnode){
}

/* expand a node, get its children nodes, and organize the children nodes using
 * array succ_nodes.
 */
void expand(struct node *selected) {
}

int nodes_same(struct node *a,struct node *b) {
    int flg=FALSE;
    if (memcmp(a->tiles, b->tiles, sizeof(int)*NxN) == 0)
        flg=TRUE;
    return flg;
}

/* Filtering. Some nodes in succ_nodes may already be included in either open
 * or closed list. Remove them. It is important to reduce execution time.
 * This function checks the (i)th node in succ_nodes array. You must call this
 & function in a loop to check all the nodes in succ_nodes.
 */
void filter(int i, struct node *pnode_list){
}


int main(int argc,char **argv) {
    int iter,cnt;
    struct node *copen, *cp, *solution_path;
    int ret, i, pathlen=0, index[N-1];

    solution_path=NULL;
    start=initialize(argv); /* init initial and goal states */
    open=start;

    iter=0;
    while (open!=NULL) {    /* Termination cond with a solution is tested in expand. */
        copen=open;
        open=open->next;  /* get the first node from open to expand */
        if(nodes_same(copen,goal)){ /* goal is found */
            do{ /* trace back and add the nodes on the path to a list */
                copen->next=solution_path;
                solution_path=copen;
                copen=copen->parent;
                pathlen++;
            } while(copen!=NULL);
            printf("Path (lengh=%d):\n", pathlen);
            copen=solution_path;
            ... /* print out the nodes on the list */
            break;
        }
        expand(copen);       /* Find new successors */
        for(i=0;i<4;i++){
            filter(i,open);
            filter(i,closed);
        }
        merge_to_open(); /* New open list */
        copen->next=closed;
        closed=copen;       /* New closed */
        /* print out something so that you know your
         * program is still making progress
         */
        iter++;
        if(iter %1000 == 0)
            printf("iter %d\n", iter);
    }
    return 0;
} /* end of main */

标签： c

解决方案

我不太了解目标状态的概念，我是否在程序中写了这样的东西来制作目标状态？

tiles[N][N]是的，你可以写这个，尽管如果目标状态和节点的状态具有相同的维度形状，它会更适合比较。

此外，启发式的想法，我理解 f(n) = g(n) + h(n) 但我如何将其转换为代码？移动 1 格是否会使 g 的值增加 1？

那肯定是有道理的。

如何估算最便宜路径的成本？

为了找到一条成本最低的路径，要求启发式函数永远不要高估到达目标的路径的实际成本。一种可能性是取每个现有瓦片到其目标位置的水平和垂直距离之和；此功能的一个弱点可能是它经常严重低估成本，因此不能很好地帮助快速找到最佳路径。我只是想不出这里有什么好的功能。但是，我只是在 Wikipedia 页面上阅读了15-puzzle，这是一种常用的启发式方法。

推荐阅读