3
\$\begingroup\$

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 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() {

    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 %d\n",*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 = %d\n", 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 enabled\n");
        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 = %d\n", 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):\n\n", 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 %d\n", iter);
        }

    }

    printf("\n\nNo solution found!!\n");
    return 0;
} /* end of main */
\$\endgroup\$
  • 2
    \$\begingroup\$ 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? \$\endgroup\$ – 200_success Nov 18 '18 at 6:29
  • \$\begingroup\$ What does the program do? What is the expected output? \$\endgroup\$ – Emily L. Nov 18 '18 at 9:33
  • \$\begingroup\$ @200_success didn't know if the C tag was a well-monitored tag on its own, I apologize \$\endgroup\$ – Kubie Nov 18 '18 at 11:03
  • 1
    \$\begingroup\$ If you consider your question adequately answered, you should consider selecting an answer for the question. \$\endgroup\$ – Emily L. Nov 24 '18 at 4:28
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the input. I really thought closed should be sorted in some fashion. \$\endgroup\$ – Kubie Nov 18 '18 at 13:14
  • \$\begingroup\$ 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. \$\endgroup\$ – Emily L. Nov 18 '18 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.