Krdytkyu

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 */

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.