algorithm - 对于 A* 算法，这是一个不错的启发式函数吗？为什么或者为什么不？
问题描述
15 - 拼图问题解释：https ://en.wikipedia.org/wiki/15_puzzle
为了解决 15-puzzle 问题，我编写了一个启发式函数来决定最好访问哪个状态。因此，我编写了一个名为 update fgh 的启发式函数，对于每个节点，它将 g 增加 1，并且 h 相对于每个节点与目标状态的距离而增加。
15 拼图问题是由 15 个图块组成的随机数组，每个图块编号为 1-15，它们以随机顺序散布在一个 4 x 4 的盒子上，并添加了一个空白图块。
要解决 15 谜题，您必须将空白瓷砖代替瓷砖从左侧移动到右侧、底部或顶部。
当每个数字按 1-15 的顺序排列，最后是空白瓷砖时，15 拼图问题就解决了。
我的代码中的变量如下
///[pnode 中的变量]///
N - 代表预编译器中的 4 个图块，以使代码更具可移植性，当然也是出于安全原因。
NxN - 代表预编译器中的 4 个 4 块数组，以使代码更便携，当然也是出于安全原因。
pnode - 包含拼图所在状态的拼图节点。
f - 启发式的 f 变量。
g - 启发式的 g 变量。
h - 启发式的 h 变量。
zero_column && zero row - 表示 p 节点中零图块的变量
*next 和 *parent - 拼图节点的子节点和父节点，每个 pnode 都有一个 next 零列向上，向下，向左或向右移动，如果启发式最便宜，则选择向左或向右向上的节点
///[全局变量]///
int 目标行[NxN]; - 包含 16 个节点的数组的目标行。
int 目标列[NxN]; - 包含 16 个节点的数组的目标列
结构节点*开始，*目标；- 程序用户使用 argv[] 以随机顺序选择数字 1-15 初始化和选择的起始节点加上一个空白节点。并创建一个目标节点来比较目标和初始节点
结构节点 *open = NULL, *close = NULL; - 两个具有开放和可用节点的节点以及根本无法添加或使用的节点，因此被置于封闭状态以避免进一步考虑它们。
结构节点 *succ_nodes[4]; - 成功节点 指向成功的 4 个 pnode 数组的指针。
update_fgh(struct node *pnode)
{
pnode->f = g + h;
for(i = 0; i < 16; i++)
g++;
for(j =0; j< 16; j++){
//Goal is a global variable state.
if(pnode->start[i] != goal[j])
pnode->h++;
else
continue;
}
pnode->f = pnode->g+->h;
}
这是使用启发式的代码：
#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){
int tile = pnode->tiles[row1][coulmn1];
pnode->tiles[row1][column1]=pnode->tiles[row2][column2];
pnode->tiles[row2][column2]=tile;
}
/*update the f,g,h function values for a node */
update_fgh(struct node *pnode)
{
pnode->f = g + h;
for(i = 0; i < 16; i++)
g++;
for(j =0; j< 16; j++){
//Goal is a global variable state.
if(pnode->start[i] != goal[j])
pnode->h++;
else
continue;
}
pnode->f = pnode->g+->h;
}
/* 0 goes down by a row */
void move_down(struct node * pnode){
swap(pnode->zero_row, pnode->zero_column, pnode->zero_row+1, pnode->zero_column, pnode);
pnode->zero_row++;
}
/* 0 goes right by a column */
void move_right(struct node * pnode){
swap(pnode->zero_row, pnode->zero_column, pnode->zero_row, pnode->zero_column+1, pnode);
pnode->zero_column++;
}
/* 0 goes up by a row */
void move_up(struct node * pnode){
swap(pnode->zero_row, pnode->zero_column, pnode->zero_row-1, pnode->zero_column, pnode);
pnode->zero_row--;
}
/* 0 goes left by a column */
void move_left(struct node * pnode){
swap(pnode->zero_row, pnode->zero_column, pnode->zero_row, pnode->zero_column-1, pnode);
pnode->zero_column--;
}
/* 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){
if(nodes_same(*pnode_list, succ_nodes[i]) == TRUE)
pnode_list = pnode_list->next;
}
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 */
解决方案
推荐阅读
- ruby - 如何在井字棋盘中找到第一个获胜组合？
- macos - 使用 AppleScript 调用 NSWorkspace 方法
- sql - SQL Server：调用可能不存在的表的代码
- python - 两个数之和。如果输入的值无效，如何进行输入循环？
- html - type 属性不适用于 form_widget
- python - 以不同频率同步定时并行进程
- javascript - 如何 HTTP GET .js 文件并提取“导出”变量？
- python - 在python中搜索特定行，然后是特定行（TXT文件）
- python - 使用python将动态嵌套json转换为csv的通用解决方案
- docker - 从外部容器访问数据