A* search on 4x4 sliding tile puzzle scales poorly
up vote
2
down vote
favorite
I am trying to improve the time complexity of my A* search algorithm and I have tried approaching this from every which way I believe is possible. I believe I may be doing something fundamentally wrong here and would appreciate a second look.
I start with a 4x4 board of values 0-15 that can be shuffled to achieve this order (where 0 represents a blank spot)
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0
The catch: when running this program on a board with a minor change like:
1 2 3 4
5 6 7 8
9 10 0 11
13 14 15 12
The program executes fine
But in more complex cases, say 15 moves are made from original board instead of just 2, the program takes an absurd amount of time to complete when I am aiming for 1-2 min execution time.
6 2 3 7
10 12 4 11
1 13 0 9
5 14 15 8
This case above takes an absurd amount of time.
The program is called in this fashion:
./a.out -s 6 2 3 7 10 12 4 11 1 13 0 9 5 14 15 8
where -m flag signals multithreading and -s signals single thread.
Included below is my program:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.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 */
};
// globals
int goal_rows[NxN];
int goal_columns[NxN];
struct node *start,*goal;
struct node *open = NULL, *closed = NULL;
struct node *succ_nodes[4];
pthread_barrier_t bar, barrier_before_filtering, barrier_after_filtering;
int finish=0, multithread=0;
// print board
void print_a_node(struct node *pnode) {
int i,j;
if (pnode != NULL) {
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(int argc, 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 staten");
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 staten");
print_a_node(goal);
return start;
}
/* merge unrepeated nodes into open list after filtering */
void merge_to_open() {
struct node *temp;
struct node *curr;
struct node *the_succ_node;
for (int i=0;i<4;i++) {
curr = open;
temp = open;
if (succ_nodes[i] != NULL) {
the_succ_node=(struct node *) malloc(sizeof(struct node));
for(int k=0;k<N;k++){
for(int j=0;j<N;j++){
the_succ_node->tiles[k][j]=succ_nodes[i]->tiles[k][j];
}
}
// copy data
the_succ_node->zero_row = succ_nodes[i]->zero_row;
the_succ_node->zero_column = succ_nodes[i]->zero_column;
the_succ_node->parent = succ_nodes[i]->parent;
the_succ_node->f = succ_nodes[i]->f;
the_succ_node->g = succ_nodes[i]->g;
the_succ_node->h = succ_nodes[i]->h;
// insert at beginning if smallest
if (curr == NULL) {
open = the_succ_node;
} else if (the_succ_node->f <= curr->f) {
if (the_succ_node->h <= curr->h) {
the_succ_node->next = curr;
open = the_succ_node;
} else {
while (1) {
temp = curr;
curr = curr->next;
if (curr == NULL) {
// insert at end of list
temp->next = the_succ_node;
the_succ_node->next = NULL;
break;
}
if (the_succ_node->h <= curr->h) {
the_succ_node->next = curr;
temp->next = the_succ_node;
break;
}
}
}
} else { // if not smallest
while (1) {
temp = curr;
curr = curr->next;
if (curr == NULL) {
// insert at end of list
temp->next = the_succ_node;
the_succ_node->next = NULL;
break;
}
if (the_succ_node->f <= curr->f) {
the_succ_node->next = curr;
temp->next = the_succ_node;
break;
}
}
}
}
}
}
/*swap two tiles in a node*/
void swap(int row1,int column1,int row2,int column2, struct node * pnode){
int tmp;
tmp = pnode->tiles[row1][column1];
pnode->tiles[row1][column1] = pnode->tiles[row2][column2];
pnode->tiles[row2][column2] = tmp;
}
int manhattan(struct node * pnode) {
int sum = 0;
int ourValue = 0;
int fbool = 0;
// for each point, finding distance to
// rest of the point
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// grab our value
ourValue = pnode->tiles[i][j];
fbool = 0;
for (int m = 0; m < N; m++) {
for (int n = 0; n < N; n++) {
// found match
if (ourValue == goal->tiles[m][n]) {
sum += (abs(i - m) + abs(j - n));
fbool = 1;
break;
}
}
if (fbool) {
break;
}
}
}
}
return sum;
}
/*update the f,g,h function values for a node */
void update_fgh(struct node *pnode){
// call manhattan distance for h
pnode->h = manhattan(pnode);
// check height of list for g
pnode->g = pnode->parent->g+1;
// add both for f
pnode->f = pnode->g + pnode->h;
}
struct node *move(struct node *pnode, int xMove, int yMove) {
struct node *newp;
int i,j,h,xSpot,ySpot;
xSpot = pnode->zero_row;
ySpot = pnode->zero_column;
// malloc
newp=(struct node*)malloc(sizeof(struct node));
// copy from orig
for(i=0;i<N;i++){
for(j=0;j<N;j++){
newp->tiles[i][j]=pnode->tiles[i][j];
}
}
newp->next = NULL;
newp->parent = pnode; // do we need to trace back here?
newp->zero_row = xSpot+xMove;
newp->zero_column = ySpot+yMove;
swap(xSpot, ySpot, xSpot + xMove, ySpot + yMove, newp);;
newp->h=0;
newp->g=0;
newp->f=0;
return newp;
}
/* expand a node, get its children nodes, and organize the children nodes using
* array succ_nodes.
*/
void expand(struct node *selected) {
// set new nodes parents to selected
int i, j;
struct node *temp;
for(int k=0;k<N;k++) {
succ_nodes[k]=NULL;
}
i = selected->zero_row;
j = selected->zero_column;
if((i+1) < N){ /* DOWN */
succ_nodes[0] = move(selected, 1, 0);
update_fgh(succ_nodes[0]);
}
if((j+1) < N){ /* RIGHT */
succ_nodes[1] = move(selected, 0, 1);
update_fgh(succ_nodes[1]);
}
if((i-1) >=0){ /* UP */
succ_nodes[2] = move(selected, -1, 0);
update_fgh(succ_nodes[2]);
}
if((j-1) >=0){ /* LEFT */
succ_nodes[3] = move(selected, 0, -1);
update_fgh(succ_nodes[3]);
}
}
// checks if nodes are same
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) {
struct node *temp;
temp = pnode_list;
if (succ_nodes[i] != NULL) {
while (temp != NULL) {
if (nodes_same(succ_nodes[i], temp)) {
if (succ_nodes[i]->f >= temp->f) {
succ_nodes[i] = NULL;
break;
}
}
temp = temp->next;
}
}
}
void *filter_threads(void *id){
int *myid = (int *)id;
int found = 0;
//printf("thread %dn",*myid);
while(1){
// sync w main
pthread_barrier_wait(&barrier_before_filtering);
//... /* check the found flag, and exit when found is set */
if (finish) { break; }
// filter
filter(*myid, open);
filter(*myid, closed);
//... /* barrier sync */
pthread_barrier_wait(&barrier_after_filtering);
}
}
void printnodes() {
struct node *temp;
temp = open;
while (temp != NULL) {
printf("n");
printf("nfor below open->f = %d, open->g = %d, open->h = %dn", temp->f, temp->g, temp->h);
print_a_node(temp);
temp=temp->next;
}
}
int main(int argc,char **argv) {
int iter, cnt, errno;
struct node *copen, *cp, *solution_path;
pthread_t thread[N-1];
int ret, i, pathlen=0, index[N-1];
solution_path=NULL;
multithread = (strcmp(argv[1], "-m") == 0) ? 1 : 0; /* set multithread flag based on argv[1] */
start=initialize(argc-1,argv+1); /* init initial and goal states */
open=start;
// add catch for not -s or -m
// add catch for argc != 17
if(multithread){
//printf("Multithread enabledn");
pthread_barrier_init(&bar, NULL, 4);
pthread_barrier_init(&barrier_before_filtering, NULL, 4);
pthread_barrier_init(&barrier_after_filtering, NULL, 4);
for (i = 0; i < 3; i++) {
index[i] = i+1;
ret = pthread_create(thread+i, NULL, filter_threads, &(index[i]));
if (ret != 0) {
errno = ret; perror("pthread_create"); return -1;
}
}
}
iter=0;
while (open!=NULL) { /* Termination cond with a solution is tested in expand. */
//printf("nentered main while EXPAND iter = %dn", iter);
copen=open;
open=open->next; /* get the first node from open to expand */
if(nodes_same(copen,goal)){
if(multithread){
finish=1;
pthread_barrier_wait(&barrier_before_filtering);
for (i=0; i < N-1; i++) {
pthread_join(thread[i], NULL);
}
pthread_barrier_destroy(&barrier_before_filtering);
pthread_barrier_destroy(&barrier_after_filtering);
}
do{ /* trace back and add the nodes on the path to a list */
copen->next=solution_path; // to maintain copen list
solution_path=copen;
copen=copen->parent;
pathlen++;
} while(copen!=NULL);
printf("Path (length=%d):nn", pathlen);
copen=solution_path;
cp = copen; /* print out the nodes on the list */
while (cp != NULL) {
print_a_node(cp);
cp = cp->next;
}
return 0;
}
// expand successive nodes into succ_nodes
expand(copen);
if(multithread){
//... /* barrier sync */
pthread_barrier_wait(&barrier_before_filtering);
filter(0,open);
filter(0,closed);
//... /* barrier sync */
pthread_barrier_wait(&barrier_after_filtering);
}
else{
for(i=0;i<4;i++){
filter(i,open);
filter(i,closed);
}
}
merge_to_open(); /* New open list */
/* New closed */
copen->next=closed;
closed=copen;
//merge_to_closed(copen);
/* print out something so that you know your
* program is still making progress
*/
iter++;
if(iter %1000 == 0) {
printf("iter %dn", iter);
}
}
printf("nnNo solution found!!n");
return 0;
} /* end of main */
c time-limit-exceeded pthreads a-star sliding-tile-puzzle
edited 2 days ago
200_success
127k15148410
asked Nov 18 at 5:18
Kubie
1113
New contributor
Kubie is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
2
down vote
favorite
I am trying to improve the time complexity of my A* search algorithm and I have tried approaching this from every which way I believe is possible. I believe I may be doing something fundamentally wrong here and would appreciate a second look.
I start with a 4x4 board of values 0-15 that can be shuffled to achieve this order (where 0 represents a blank spot)
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0
The catch: when running this program on a board with a minor change like:
1 2 3 4
5 6 7 8
9 10 0 11
13 14 15 12
The program executes fine
But in more complex cases, say 15 moves are made from original board instead of just 2, the program takes an absurd amount of time to complete when I am aiming for 1-2 min execution time.
6 2 3 7
10 12 4 11
1 13 0 9
5 14 15 8
This case above takes an absurd amount of time.
The program is called in this fashion:
./a.out -s 6 2 3 7 10 12 4 11 1 13 0 9 5 14 15 8
where -m flag signals multithreading and -s signals single thread.
Included below is my program:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.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 */
};
// globals
int goal_rows[NxN];
int goal_columns[NxN];
struct node *start,*goal;
struct node *open = NULL, *closed = NULL;
struct node *succ_nodes[4];
pthread_barrier_t bar, barrier_before_filtering, barrier_after_filtering;
int finish=0, multithread=0;
// print board
void print_a_node(struct node *pnode) {
int i,j;
if (pnode != NULL) {
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(int argc, 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 staten");
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 staten");
print_a_node(goal);
return start;
}
/* merge unrepeated nodes into open list after filtering */
void merge_to_open() {
struct node *temp;
struct node *curr;
struct node *the_succ_node;
for (int i=0;i<4;i++) {
curr = open;
temp = open;
if (succ_nodes[i] != NULL) {
the_succ_node=(struct node *) malloc(sizeof(struct node));
for(int k=0;k<N;k++){
for(int j=0;j<N;j++){
the_succ_node->tiles[k][j]=succ_nodes[i]->tiles[k][j];
}
}
// copy data
the_succ_node->zero_row = succ_nodes[i]->zero_row;
the_succ_node->zero_column = succ_nodes[i]->zero_column;
the_succ_node->parent = succ_nodes[i]->parent;
the_succ_node->f = succ_nodes[i]->f;
the_succ_node->g = succ_nodes[i]->g;
the_succ_node->h = succ_nodes[i]->h;
// insert at beginning if smallest
if (curr == NULL) {
open = the_succ_node;
} else if (the_succ_node->f <= curr->f) {
if (the_succ_node->h <= curr->h) {
the_succ_node->next = curr;
open = the_succ_node;
} else {
while (1) {
temp = curr;
curr = curr->next;
if (curr == NULL) {
// insert at end of list
temp->next = the_succ_node;
the_succ_node->next = NULL;
break;
}
if (the_succ_node->h <= curr->h) {
the_succ_node->next = curr;
temp->next = the_succ_node;
break;
}
}
}
} else { // if not smallest
while (1) {
temp = curr;
curr = curr->next;
if (curr == NULL) {
// insert at end of list
temp->next = the_succ_node;
the_succ_node->next = NULL;
break;
}
if (the_succ_node->f <= curr->f) {
the_succ_node->next = curr;
temp->next = the_succ_node;
break;
}
}
}
}
}
}
/*swap two tiles in a node*/
void swap(int row1,int column1,int row2,int column2, struct node * pnode){
int tmp;
tmp = pnode->tiles[row1][column1];
pnode->tiles[row1][column1] = pnode->tiles[row2][column2];
pnode->tiles[row2][column2] = tmp;
}
int manhattan(struct node * pnode) {
int sum = 0;
int ourValue = 0;
int fbool = 0;
// for each point, finding distance to
// rest of the point
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// grab our value
ourValue = pnode->tiles[i][j];
fbool = 0;
for (int m = 0; m < N; m++) {
for (int n = 0; n < N; n++) {
// found match
if (ourValue == goal->tiles[m][n]) {
sum += (abs(i - m) + abs(j - n));
fbool = 1;
break;
}
}
if (fbool) {
break;
}
}
}
}
return sum;
}
/*update the f,g,h function values for a node */
void update_fgh(struct node *pnode){
// call manhattan distance for h
pnode->h = manhattan(pnode);
// check height of list for g
pnode->g = pnode->parent->g+1;
// add both for f
pnode->f = pnode->g + pnode->h;
}
struct node *move(struct node *pnode, int xMove, int yMove) {
struct node *newp;
int i,j,h,xSpot,ySpot;
xSpot = pnode->zero_row;
ySpot = pnode->zero_column;
// malloc
newp=(struct node*)malloc(sizeof(struct node));
// copy from orig
for(i=0;i<N;i++){
for(j=0;j<N;j++){
newp->tiles[i][j]=pnode->tiles[i][j];
}
}
newp->next = NULL;
newp->parent = pnode; // do we need to trace back here?
newp->zero_row = xSpot+xMove;
newp->zero_column = ySpot+yMove;
swap(xSpot, ySpot, xSpot + xMove, ySpot + yMove, newp);;
newp->h=0;
newp->g=0;
newp->f=0;
return newp;
}
/* expand a node, get its children nodes, and organize the children nodes using
* array succ_nodes.
*/
void expand(struct node *selected) {
// set new nodes parents to selected
int i, j;
struct node *temp;
for(int k=0;k<N;k++) {
succ_nodes[k]=NULL;
}
i = selected->zero_row;
j = selected->zero_column;
if((i+1) < N){ /* DOWN */
succ_nodes[0] = move(selected, 1, 0);
update_fgh(succ_nodes[0]);
}
if((j+1) < N){ /* RIGHT */
succ_nodes[1] = move(selected, 0, 1);
update_fgh(succ_nodes[1]);
}
if((i-1) >=0){ /* UP */
succ_nodes[2] = move(selected, -1, 0);
update_fgh(succ_nodes[2]);
}
if((j-1) >=0){ /* LEFT */
succ_nodes[3] = move(selected, 0, -1);
update_fgh(succ_nodes[3]);
}
}
// checks if nodes are same
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) {
struct node *temp;
temp = pnode_list;
if (succ_nodes[i] != NULL) {
while (temp != NULL) {
if (nodes_same(succ_nodes[i], temp)) {
if (succ_nodes[i]->f >= temp->f) {
succ_nodes[i] = NULL;
break;
}
}
temp = temp->next;
}
}
}
void *filter_threads(void *id){
int *myid = (int *)id;
int found = 0;
//printf("thread %dn",*myid);
while(1){
// sync w main
pthread_barrier_wait(&barrier_before_filtering);
//... /* check the found flag, and exit when found is set */
if (finish) { break; }
// filter
filter(*myid, open);
filter(*myid, closed);
//... /* barrier sync */
pthread_barrier_wait(&barrier_after_filtering);
}
}
void printnodes() {
struct node *temp;
temp = open;
while (temp != NULL) {
printf("n");
printf("nfor below open->f = %d, open->g = %d, open->h = %dn", temp->f, temp->g, temp->h);
print_a_node(temp);
temp=temp->next;
}
}
int main(int argc,char **argv) {
int iter, cnt, errno;
struct node *copen, *cp, *solution_path;
pthread_t thread[N-1];
int ret, i, pathlen=0, index[N-1];
solution_path=NULL;
multithread = (strcmp(argv[1], "-m") == 0) ? 1 : 0; /* set multithread flag based on argv[1] */
start=initialize(argc-1,argv+1); /* init initial and goal states */
open=start;
// add catch for not -s or -m
// add catch for argc != 17
if(multithread){
//printf("Multithread enabledn");
pthread_barrier_init(&bar, NULL, 4);
pthread_barrier_init(&barrier_before_filtering, NULL, 4);
pthread_barrier_init(&barrier_after_filtering, NULL, 4);
for (i = 0; i < 3; i++) {
index[i] = i+1;
ret = pthread_create(thread+i, NULL, filter_threads, &(index[i]));
if (ret != 0) {
errno = ret; perror("pthread_create"); return -1;
}
}
}
iter=0;
while (open!=NULL) { /* Termination cond with a solution is tested in expand. */
//printf("nentered main while EXPAND iter = %dn", iter);
copen=open;
open=open->next; /* get the first node from open to expand */
if(nodes_same(copen,goal)){
if(multithread){
finish=1;
pthread_barrier_wait(&barrier_before_filtering);
for (i=0; i < N-1; i++) {
pthread_join(thread[i], NULL);
}
pthread_barrier_destroy(&barrier_before_filtering);
pthread_barrier_destroy(&barrier_after_filtering);
}
do{ /* trace back and add the nodes on the path to a list */
copen->next=solution_path; // to maintain copen list
solution_path=copen;
copen=copen->parent;
pathlen++;
} while(copen!=NULL);
printf("Path (length=%d):nn", pathlen);
copen=solution_path;
cp = copen; /* print out the nodes on the list */
while (cp != NULL) {
print_a_node(cp);
cp = cp->next;
}
return 0;
}
// expand successive nodes into succ_nodes
expand(copen);
if(multithread){
//... /* barrier sync */
pthread_barrier_wait(&barrier_before_filtering);
filter(0,open);
filter(0,closed);
//... /* barrier sync */
pthread_barrier_wait(&barrier_after_filtering);
}
else{
for(i=0;i<4;i++){
filter(i,open);
filter(i,closed);
}
}
merge_to_open(); /* New open list */
/* New closed */
copen->next=closed;
closed=copen;
//merge_to_closed(copen);
/* print out something so that you know your
* program is still making progress
*/
iter++;
if(iter %1000 == 0) {
printf("iter %dn", iter);
}
}
printf("nnNo solution found!!n");
return 0;
} /* end of main */
c time-limit-exceeded pthreads a-star sliding-tile-puzzle
edited 2 days ago
200_success
127k15148410
asked Nov 18 at 5:18
Kubie
1113
New contributor
Kubie is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
Why is this question tagged as c++? Is there any reason you need this code to be bilingual, when you don't appear to be using any C++-specific features?
– 200_success
2 days ago
What does the program do? What is the expected output?
– Emily L.
2 days ago
@200_success didn't know if the C tag was a well-monitored tag on its own, I apologize
– Kubie
2 days ago
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I am trying to improve the time complexity of my A* search algorithm and I have tried approaching this from every which way I believe is possible. I believe I may be doing something fundamentally wrong here and would appreciate a second look.
I start with a 4x4 board of values 0-15 that can be shuffled to achieve this order (where 0 represents a blank spot)
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0
The catch: when running this program on a board with a minor change like:
1 2 3 4
5 6 7 8
9 10 0 11
13 14 15 12
The program executes fine
But in more complex cases, say 15 moves are made from original board instead of just 2, the program takes an absurd amount of time to complete when I am aiming for 1-2 min execution time.
6 2 3 7
10 12 4 11
1 13 0 9
5 14 15 8
This case above takes an absurd amount of time.
The program is called in this fashion:
./a.out -s 6 2 3 7 10 12 4 11 1 13 0 9 5 14 15 8
where -m flag signals multithreading and -s signals single thread.
Included below is my program:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.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 */
};
// globals
int goal_rows[NxN];
int goal_columns[NxN];
struct node *start,*goal;
struct node *open = NULL, *closed = NULL;
struct node *succ_nodes[4];
pthread_barrier_t bar, barrier_before_filtering, barrier_after_filtering;
int finish=0, multithread=0;
// print board
void print_a_node(struct node *pnode) {
int i,j;
if (pnode != NULL) {
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(int argc, 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 staten");
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 staten");
print_a_node(goal);
return start;
}
/* merge unrepeated nodes into open list after filtering */
void merge_to_open() {
struct node *temp;
struct node *curr;
struct node *the_succ_node;
for (int i=0;i<4;i++) {
curr = open;
temp = open;
if (succ_nodes[i] != NULL) {
the_succ_node=(struct node *) malloc(sizeof(struct node));
for(int k=0;k<N;k++){
for(int j=0;j<N;j++){
the_succ_node->tiles[k][j]=succ_nodes[i]->tiles[k][j];
}
}
// copy data
the_succ_node->zero_row = succ_nodes[i]->zero_row;
the_succ_node->zero_column = succ_nodes[i]->zero_column;
the_succ_node->parent = succ_nodes[i]->parent;
the_succ_node->f = succ_nodes[i]->f;
the_succ_node->g = succ_nodes[i]->g;
the_succ_node->h = succ_nodes[i]->h;
// insert at beginning if smallest
if (curr == NULL) {
open = the_succ_node;
} else if (the_succ_node->f <= curr->f) {
if (the_succ_node->h <= curr->h) {
the_succ_node->next = curr;
open = the_succ_node;
} else {
while (1) {
temp = curr;
curr = curr->next;
if (curr == NULL) {
// insert at end of list
temp->next = the_succ_node;
the_succ_node->next = NULL;
break;
}
if (the_succ_node->h <= curr->h) {
the_succ_node->next = curr;
temp->next = the_succ_node;
break;
}
}
}
} else { // if not smallest
while (1) {
temp = curr;
curr = curr->next;
if (curr == NULL) {
// insert at end of list
temp->next = the_succ_node;
the_succ_node->next = NULL;
break;
}
if (the_succ_node->f <= curr->f) {
the_succ_node->next = curr;
temp->next = the_succ_node;
break;
}
}
}
}
}
}
/*swap two tiles in a node*/
void swap(int row1,int column1,int row2,int column2, struct node * pnode){
int tmp;
tmp = pnode->tiles[row1][column1];
pnode->tiles[row1][column1] = pnode->tiles[row2][column2];
pnode->tiles[row2][column2] = tmp;
}
int manhattan(struct node * pnode) {
int sum = 0;
int ourValue = 0;
int fbool = 0;
// for each point, finding distance to
// rest of the point
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// grab our value
ourValue = pnode->tiles[i][j];
fbool = 0;
for (int m = 0; m < N; m++) {
for (int n = 0; n < N; n++) {
// found match
if (ourValue == goal->tiles[m][n]) {
sum += (abs(i - m) + abs(j - n));
fbool = 1;
break;
}
}
if (fbool) {
break;
}
}
}
}
return sum;
}
/*update the f,g,h function values for a node */
void update_fgh(struct node *pnode){
// call manhattan distance for h
pnode->h = manhattan(pnode);
// check height of list for g
pnode->g = pnode->parent->g+1;
// add both for f
pnode->f = pnode->g + pnode->h;
}
struct node *move(struct node *pnode, int xMove, int yMove) {
struct node *newp;
int i,j,h,xSpot,ySpot;
xSpot = pnode->zero_row;
ySpot = pnode->zero_column;
// malloc
newp=(struct node*)malloc(sizeof(struct node));
// copy from orig
for(i=0;i<N;i++){
for(j=0;j<N;j++){
newp->tiles[i][j]=pnode->tiles[i][j];
}
}
newp->next = NULL;
newp->parent = pnode; // do we need to trace back here?
newp->zero_row = xSpot+xMove;
newp->zero_column = ySpot+yMove;
swap(xSpot, ySpot, xSpot + xMove, ySpot + yMove, newp);;
newp->h=0;
newp->g=0;
newp->f=0;
return newp;
}
/* expand a node, get its children nodes, and organize the children nodes using
* array succ_nodes.
*/
void expand(struct node *selected) {
// set new nodes parents to selected
int i, j;
struct node *temp;
for(int k=0;k<N;k++) {
succ_nodes[k]=NULL;
}
i = selected->zero_row;
j = selected->zero_column;
if((i+1) < N){ /* DOWN */
succ_nodes[0] = move(selected, 1, 0);
update_fgh(succ_nodes[0]);
}
if((j+1) < N){ /* RIGHT */
succ_nodes[1] = move(selected, 0, 1);
update_fgh(succ_nodes[1]);
}
if((i-1) >=0){ /* UP */
succ_nodes[2] = move(selected, -1, 0);
update_fgh(succ_nodes[2]);
}
if((j-1) >=0){ /* LEFT */
succ_nodes[3] = move(selected, 0, -1);
update_fgh(succ_nodes[3]);
}
}
// checks if nodes are same
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) {
struct node *temp;
temp = pnode_list;
if (succ_nodes[i] != NULL) {
while (temp != NULL) {
if (nodes_same(succ_nodes[i], temp)) {
if (succ_nodes[i]->f >= temp->f) {
succ_nodes[i] = NULL;
break;
}
}
temp = temp->next;
}
}
}
void *filter_threads(void *id){
int *myid = (int *)id;
int found = 0;
//printf("thread %dn",*myid);
while(1){
// sync w main
pthread_barrier_wait(&barrier_before_filtering);
//... /* check the found flag, and exit when found is set */
if (finish) { break; }
// filter
filter(*myid, open);
filter(*myid, closed);
//... /* barrier sync */
pthread_barrier_wait(&barrier_after_filtering);
}
}
void printnodes() {
struct node *temp;
temp = open;
while (temp != NULL) {
printf("n");
printf("nfor below open->f = %d, open->g = %d, open->h = %dn", temp->f, temp->g, temp->h);
print_a_node(temp);
temp=temp->next;
}
}
int main(int argc,char **argv) {
int iter, cnt, errno;
struct node *copen, *cp, *solution_path;
pthread_t thread[N-1];
int ret, i, pathlen=0, index[N-1];
solution_path=NULL;
multithread = (strcmp(argv[1], "-m") == 0) ? 1 : 0; /* set multithread flag based on argv[1] */
start=initialize(argc-1,argv+1); /* init initial and goal states */
open=start;
// add catch for not -s or -m
// add catch for argc != 17
if(multithread){
//printf("Multithread enabledn");
pthread_barrier_init(&bar, NULL, 4);
pthread_barrier_init(&barrier_before_filtering, NULL, 4);
pthread_barrier_init(&barrier_after_filtering, NULL, 4);
for (i = 0; i < 3; i++) {
index[i] = i+1;
ret = pthread_create(thread+i, NULL, filter_threads, &(index[i]));
if (ret != 0) {
errno = ret; perror("pthread_create"); return -1;
}
}
}
iter=0;
while (open!=NULL) { /* Termination cond with a solution is tested in expand. */
//printf("nentered main while EXPAND iter = %dn", iter);
copen=open;
open=open->next; /* get the first node from open to expand */
if(nodes_same(copen,goal)){
if(multithread){
finish=1;
pthread_barrier_wait(&barrier_before_filtering);
for (i=0; i < N-1; i++) {
pthread_join(thread[i], NULL);
}
pthread_barrier_destroy(&barrier_before_filtering);
pthread_barrier_destroy(&barrier_after_filtering);
}
do{ /* trace back and add the nodes on the path to a list */
copen->next=solution_path; // to maintain copen list
solution_path=copen;
copen=copen->parent;
pathlen++;
} while(copen!=NULL);
printf("Path (length=%d):nn", pathlen);
copen=solution_path;
cp = copen; /* print out the nodes on the list */
while (cp != NULL) {
print_a_node(cp);
cp = cp->next;
}
return 0;
}
// expand successive nodes into succ_nodes
expand(copen);
if(multithread){
//... /* barrier sync */
pthread_barrier_wait(&barrier_before_filtering);
filter(0,open);
filter(0,closed);
//... /* barrier sync */
pthread_barrier_wait(&barrier_after_filtering);
}
else{
for(i=0;i<4;i++){
filter(i,open);
filter(i,closed);
}
}
merge_to_open(); /* New open list */
/* New closed */
copen->next=closed;
closed=copen;
//merge_to_closed(copen);
/* print out something so that you know your
* program is still making progress
*/
iter++;
if(iter %1000 == 0) {
printf("iter %dn", iter);
}
}
printf("nnNo solution found!!n");
return 0;
} /* end of main */
c time-limit-exceeded pthreads a-star sliding-tile-puzzle
edited 2 days ago
200_success
127k15148410
asked Nov 18 at 5:18
Kubie
1113
New contributor
Kubie is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
I am trying to improve the time complexity of my A* search algorithm and I have tried approaching this from every which way I believe is possible. I believe I may be doing something fundamentally wrong here and would appreciate a second look.
I start with a 4x4 board of values 0-15 that can be shuffled to achieve this order (where 0 represents a blank spot)
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0
The catch: when running this program on a board with a minor change like:
1 2 3 4
5 6 7 8
9 10 0 11
13 14 15 12
The program executes fine
But in more complex cases, say 15 moves are made from original board instead of just 2, the program takes an absurd amount of time to complete when I am aiming for 1-2 min execution time.
6 2 3 7
10 12 4 11
1 13 0 9
5 14 15 8
This case above takes an absurd amount of time.
The program is called in this fashion:
./a.out -s 6 2 3 7 10 12 4 11 1 13 0 9 5 14 15 8
where -m flag signals multithreading and -s signals single thread.
Included below is my program:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.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 */
};
// globals
int goal_rows[NxN];
int goal_columns[NxN];
struct node *start,*goal;
struct node *open = NULL, *closed = NULL;
struct node *succ_nodes[4];
pthread_barrier_t bar, barrier_before_filtering, barrier_after_filtering;
int finish=0, multithread=0;
// print board
void print_a_node(struct node *pnode) {
int i,j;
if (pnode != NULL) {
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(int argc, 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 staten");
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 staten");
print_a_node(goal);
return start;
}
/* merge unrepeated nodes into open list after filtering */
void merge_to_open() {
struct node *temp;
struct node *curr;
struct node *the_succ_node;
for (int i=0;i<4;i++) {
curr = open;
temp = open;
if (succ_nodes[i] != NULL) {
the_succ_node=(struct node *) malloc(sizeof(struct node));
for(int k=0;k<N;k++){
for(int j=0;j<N;j++){
the_succ_node->tiles[k][j]=succ_nodes[i]->tiles[k][j];
}
}
// copy data
the_succ_node->zero_row = succ_nodes[i]->zero_row;
the_succ_node->zero_column = succ_nodes[i]->zero_column;
the_succ_node->parent = succ_nodes[i]->parent;
the_succ_node->f = succ_nodes[i]->f;
the_succ_node->g = succ_nodes[i]->g;
the_succ_node->h = succ_nodes[i]->h;
// insert at beginning if smallest
if (curr == NULL) {
open = the_succ_node;
} else if (the_succ_node->f <= curr->f) {
if (the_succ_node->h <= curr->h) {
the_succ_node->next = curr;
open = the_succ_node;
} else {
while (1) {
temp = curr;
curr = curr->next;
if (curr == NULL) {
// insert at end of list
temp->next = the_succ_node;
the_succ_node->next = NULL;
break;
}
if (the_succ_node->h <= curr->h) {
the_succ_node->next = curr;
temp->next = the_succ_node;
break;
}
}
}
} else { // if not smallest
while (1) {
temp = curr;
curr = curr->next;
if (curr == NULL) {
// insert at end of list
temp->next = the_succ_node;
the_succ_node->next = NULL;
break;
}
if (the_succ_node->f <= curr->f) {
the_succ_node->next = curr;
temp->next = the_succ_node;
break;
}
}
}
}
}
}
/*swap two tiles in a node*/
void swap(int row1,int column1,int row2,int column2, struct node * pnode){
int tmp;
tmp = pnode->tiles[row1][column1];
pnode->tiles[row1][column1] = pnode->tiles[row2][column2];
pnode->tiles[row2][column2] = tmp;
}
int manhattan(struct node * pnode) {
int sum = 0;
int ourValue = 0;
int fbool = 0;
// for each point, finding distance to
// rest of the point
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// grab our value
ourValue = pnode->tiles[i][j];
fbool = 0;
for (int m = 0; m < N; m++) {
for (int n = 0; n < N; n++) {
// found match
if (ourValue == goal->tiles[m][n]) {
sum += (abs(i - m) + abs(j - n));
fbool = 1;
break;
}
}
if (fbool) {
break;
}
}
}
}
return sum;
}
/*update the f,g,h function values for a node */
void update_fgh(struct node *pnode){
// call manhattan distance for h
pnode->h = manhattan(pnode);
// check height of list for g
pnode->g = pnode->parent->g+1;
// add both for f
pnode->f = pnode->g + pnode->h;
}
struct node *move(struct node *pnode, int xMove, int yMove) {
struct node *newp;
int i,j,h,xSpot,ySpot;
xSpot = pnode->zero_row;
ySpot = pnode->zero_column;
// malloc
newp=(struct node*)malloc(sizeof(struct node));
// copy from orig
for(i=0;i<N;i++){
for(j=0;j<N;j++){
newp->tiles[i][j]=pnode->tiles[i][j];
}
}
newp->next = NULL;
newp->parent = pnode; // do we need to trace back here?
newp->zero_row = xSpot+xMove;
newp->zero_column = ySpot+yMove;
swap(xSpot, ySpot, xSpot + xMove, ySpot + yMove, newp);;
newp->h=0;
newp->g=0;
newp->f=0;
return newp;
}
/* expand a node, get its children nodes, and organize the children nodes using
* array succ_nodes.
*/
void expand(struct node *selected) {
// set new nodes parents to selected
int i, j;
struct node *temp;
for(int k=0;k<N;k++) {
succ_nodes[k]=NULL;
}
i = selected->zero_row;
j = selected->zero_column;
if((i+1) < N){ /* DOWN */
succ_nodes[0] = move(selected, 1, 0);
update_fgh(succ_nodes[0]);
}
if((j+1) < N){ /* RIGHT */
succ_nodes[1] = move(selected, 0, 1);
update_fgh(succ_nodes[1]);
}
if((i-1) >=0){ /* UP */
succ_nodes[2] = move(selected, -1, 0);
update_fgh(succ_nodes[2]);
}
if((j-1) >=0){ /* LEFT */
succ_nodes[3] = move(selected, 0, -1);
update_fgh(succ_nodes[3]);
}
}
// checks if nodes are same
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) {
struct node *temp;
temp = pnode_list;
if (succ_nodes[i] != NULL) {
while (temp != NULL) {
if (nodes_same(succ_nodes[i], temp)) {
if (succ_nodes[i]->f >= temp->f) {
succ_nodes[i] = NULL;
break;
}
}
temp = temp->next;
}
}
}
void *filter_threads(void *id){
int *myid = (int *)id;
int found = 0;
//printf("thread %dn",*myid);
while(1){
// sync w main
pthread_barrier_wait(&barrier_before_filtering);
//... /* check the found flag, and exit when found is set */
if (finish) { break; }
// filter
filter(*myid, open);
filter(*myid, closed);
//... /* barrier sync */
pthread_barrier_wait(&barrier_after_filtering);
}
}
void printnodes() {
struct node *temp;
temp = open;
while (temp != NULL) {
printf("n");
printf("nfor below open->f = %d, open->g = %d, open->h = %dn", temp->f, temp->g, temp->h);
print_a_node(temp);
temp=temp->next;
}
}
int main(int argc,char **argv) {
int iter, cnt, errno;
struct node *copen, *cp, *solution_path;
pthread_t thread[N-1];
int ret, i, pathlen=0, index[N-1];
solution_path=NULL;
multithread = (strcmp(argv[1], "-m") == 0) ? 1 : 0; /* set multithread flag based on argv[1] */
start=initialize(argc-1,argv+1); /* init initial and goal states */
open=start;
// add catch for not -s or -m
// add catch for argc != 17
if(multithread){
//printf("Multithread enabledn");
pthread_barrier_init(&bar, NULL, 4);
pthread_barrier_init(&barrier_before_filtering, NULL, 4);
pthread_barrier_init(&barrier_after_filtering, NULL, 4);
for (i = 0; i < 3; i++) {
index[i] = i+1;
ret = pthread_create(thread+i, NULL, filter_threads, &(index[i]));
if (ret != 0) {
errno = ret; perror("pthread_create"); return -1;
}
}
}
iter=0;
while (open!=NULL) { /* Termination cond with a solution is tested in expand. */
//printf("nentered main while EXPAND iter = %dn", iter);
copen=open;
open=open->next; /* get the first node from open to expand */
if(nodes_same(copen,goal)){
if(multithread){
finish=1;
pthread_barrier_wait(&barrier_before_filtering);
for (i=0; i < N-1; i++) {
pthread_join(thread[i], NULL);
}
pthread_barrier_destroy(&barrier_before_filtering);
pthread_barrier_destroy(&barrier_after_filtering);
}
do{ /* trace back and add the nodes on the path to a list */
copen->next=solution_path; // to maintain copen list
solution_path=copen;
copen=copen->parent;
pathlen++;
} while(copen!=NULL);
printf("Path (length=%d):nn", pathlen);
copen=solution_path;
cp = copen; /* print out the nodes on the list */
while (cp != NULL) {
print_a_node(cp);
cp = cp->next;
}
return 0;
}
// expand successive nodes into succ_nodes
expand(copen);
if(multithread){
//... /* barrier sync */
pthread_barrier_wait(&barrier_before_filtering);
filter(0,open);
filter(0,closed);
//... /* barrier sync */
pthread_barrier_wait(&barrier_after_filtering);
}
else{
for(i=0;i<4;i++){
filter(i,open);
filter(i,closed);
}
}
merge_to_open(); /* New open list */
/* New closed */
copen->next=closed;
closed=copen;
//merge_to_closed(copen);
/* print out something so that you know your
* program is still making progress
*/
iter++;
if(iter %1000 == 0) {
printf("iter %dn", iter);
}
}
printf("nnNo solution found!!n");
return 0;
} /* end of main */
c time-limit-exceeded pthreads a-star sliding-tile-puzzle
c time-limit-exceeded pthreads a-star sliding-tile-puzzle
edited 2 days ago
200_success
127k15148410
asked Nov 18 at 5:18
Kubie
1113
New contributor
Kubie is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 days ago
200_success
127k15148410
asked Nov 18 at 5:18
Kubie
1113
New contributor
Kubie is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 days ago
200_success
127k15148410
edited 2 days ago
200_success
127k15148410
edited 2 days ago
200_success
127k15148410
127k15148410
asked Nov 18 at 5:18
Kubie
1113
New contributor
Kubie is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Nov 18 at 5:18
Kubie
1113
asked Nov 18 at 5:18
Kubie
1113
1113
New contributor
Kubie is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Kubie is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Kubie is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
Why is this question tagged as c++? Is there any reason you need this code to be bilingual, when you don't appear to be using any C++-specific features?
– 200_success
2 days ago
What does the program do? What is the expected output?
– Emily L.
2 days ago
@200_success didn't know if the C tag was a well-monitored tag on its own, I apologize
– Kubie
2 days ago
add a comment |
2
Why is this question tagged as c++? Is there any reason you need this code to be bilingual, when you don't appear to be using any C++-specific features?
– 200_success
2 days ago
What does the program do? What is the expected output?
– Emily L.
2 days ago
@200_success didn't know if the C tag was a well-monitored tag on its own, I apologize
– Kubie
2 days ago
2
2
Why is this question tagged as c++? Is there any reason you need this code to be bilingual, when you don't appear to be using any C++-specific features?
– 200_success
2 days ago
Why is this question tagged as c++? Is there any reason you need this code to be bilingual, when you don't appear to be using any C++-specific features?
– 200_success
2 days ago
What does the program do? What is the expected output?
– Emily L.
2 days ago
What does the program do? What is the expected output?
– Emily L.
2 days ago
@200_success didn't know if the C tag was a well-monitored tag on its own, I apologize
– Kubie
2 days ago
@200_success didn't know if the C tag was a well-monitored tag on its own, I apologize
– Kubie
2 days ago
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
You're doing the same mistake that everyone who posts that their A* is slow is doing.
You're using the wrong data structure for your open and closed structure. The closed should be a set, usually you choose a hashtable based one but a tree based one will do too. And the open set needs to be a priority queue which you typically implement using a heap.
Please search around on this site for other A* questions that will show your examples.
answered 2 days ago
Emily L.
11.2k12372
Thanks for the input. I really thought closed should be sorted in some fashion.
– Kubie
2 days ago
Closed is used to determine if you can avoid expanding a node, thus you only need to determine if the node is in the closed set. Hence hash table is preferred as your don't need ordering.
– Emily L.
2 days ago
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
You're doing the same mistake that everyone who posts that their A* is slow is doing.
You're using the wrong data structure for your open and closed structure. The closed should be a set, usually you choose a hashtable based one but a tree based one will do too. And the open set needs to be a priority queue which you typically implement using a heap.
Please search around on this site for other A* questions that will show your examples.
answered 2 days ago
Emily L.
11.2k12372
Thanks for the input. I really thought closed should be sorted in some fashion.
– Kubie
2 days ago
Closed is used to determine if you can avoid expanding a node, thus you only need to determine if the node is in the closed set. Hence hash table is preferred as your don't need ordering.
– Emily L.
2 days ago
add a comment |
up vote
1
down vote
You're doing the same mistake that everyone who posts that their A* is slow is doing.
You're using the wrong data structure for your open and closed structure. The closed should be a set, usually you choose a hashtable based one but a tree based one will do too. And the open set needs to be a priority queue which you typically implement using a heap.
Please search around on this site for other A* questions that will show your examples.
answered 2 days ago
Emily L.
11.2k12372
Thanks for the input. I really thought closed should be sorted in some fashion.
– Kubie
2 days ago
Closed is used to determine if you can avoid expanding a node, thus you only need to determine if the node is in the closed set. Hence hash table is preferred as your don't need ordering.
– Emily L.
2 days ago
add a comment |
up vote
1
down vote
up vote
1
down vote
You're doing the same mistake that everyone who posts that their A* is slow is doing.
You're using the wrong data structure for your open and closed structure. The closed should be a set, usually you choose a hashtable based one but a tree based one will do too. And the open set needs to be a priority queue which you typically implement using a heap.
Please search around on this site for other A* questions that will show your examples.
answered 2 days ago
Emily L.
11.2k12372
You're doing the same mistake that everyone who posts that their A* is slow is doing.
You're using the wrong data structure for your open and closed structure. The closed should be a set, usually you choose a hashtable based one but a tree based one will do too. And the open set needs to be a priority queue which you typically implement using a heap.
Please search around on this site for other A* questions that will show your examples.
answered 2 days ago
Emily L.
11.2k12372
answered 2 days ago
Emily L.
11.2k12372
answered 2 days ago
Emily L.
11.2k12372
answered 2 days ago
Emily L.
11.2k12372
11.2k12372
Thanks for the input. I really thought closed should be sorted in some fashion.
– Kubie
2 days ago
Closed is used to determine if you can avoid expanding a node, thus you only need to determine if the node is in the closed set. Hence hash table is preferred as your don't need ordering.
– Emily L.
2 days ago
add a comment |
Thanks for the input. I really thought closed should be sorted in some fashion.
– Kubie
2 days ago
Closed is used to determine if you can avoid expanding a node, thus you only need to determine if the node is in the closed set. Hence hash table is preferred as your don't need ordering.
– Emily L.
2 days ago
Thanks for the input. I really thought closed should be sorted in some fashion.
– Kubie
2 days ago
Thanks for the input. I really thought closed should be sorted in some fashion.
– Kubie
2 days ago
Closed is used to determine if you can avoid expanding a node, thus you only need to determine if the node is in the closed set. Hence hash table is preferred as your don't need ordering.
– Emily L.
2 days ago
Closed is used to determine if you can avoid expanding a node, thus you only need to determine if the node is in the closed set. Hence hash table is preferred as your don't need ordering.
– Emily L.
2 days ago
add a comment |
Kubie is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
Kubie is a new contributor. Be nice, and check out our Code of Conduct.
Kubie is a new contributor. Be nice, and check out our Code of Conduct.
Kubie is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f207894%2fa-search-on-4x4-sliding-tile-puzzle-scales-poorly%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
Why is this question tagged as c++? Is there any reason you need this code to be bilingual, when you don't appear to be using any C++-specific features?
– 200_success
2 days ago
What does the program do? What is the expected output?
– Emily L.
2 days ago
@200_success didn't know if the C tag was a well-monitored tag on its own, I apologize
– Kubie
2 days ago