15 - Объяснение проблемы головоломки: https://en.wikipedia.org/wiki/15_puzzle
Чтобы решить проблему 15 головоломок, я написал эвристическую функцию, чтобы решить, к какому состоянию лучше всего обращаться. Итак, я написал эвристическую функцию с именем 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 содержит следующий с нулевым соlumn, сдвинутый вверх, вниз, влево или вправо, с выбранным узлом вверх вниз влево или вправо, если эвристика является самой дешевой
/// [глобальные переменные] ///
int goal_rows [NxN];- Строки цели, которые содержат массив из 16 узлов.
int goal_columns [NxN];- Столбцы цели, которые содержат массив из 16 узлов
struct node * start, * goal;- Начальный узел, который инициализируется и выбирается пользователем программы с помощью argv [] для выбора чисел 1-15 в случайном порядке плюс пустой узел. и создать целевой узел для сравнения целевого и начального узла
struct node * open = NULL, * closed = NULL;- Два узла с открытыми и доступными узлами наряду с узлами, которые просто не могут быть добавлены или использованы и поэтому помещены в закрытые, чтобы избежать дальнейшего их рассмотрения.
struct node * succ_nodes [4];- Успешные узлы - указатель, который указывает на массив из 4 успешных узлов.
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 */