A* algorithm

Discussion in 'C Programming' started by sulekhasweety@gmail.com, Apr 4, 2008.

  1. Guest

    Hi ,

    this is the program showing implementation of a* algorithm, given n
    integers and a sum m ,write a program to find the set of integers
    summing to m using a* algorithm.

    but i am not getting the o/p correct , i am getting only one set of
    integers, can any one point the errors/corrections required ?

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>

    typedef enum {FALSE,TRUE}bln;
    int subsetsum(int*,int,int,bln* ,int);
    int compare(void*,void*);
    void printanswer(int*,int,bln*);


    int main(void)
    {

    int a[] = {5,3,4,8,9,6};
    int sum = 15;
    int size = sizeof(a)/sizeof(int);
    int i;

    bln *selected = calloc(size,sizeof(bln));

    qsort(a,size,sizeof(int),compare);

    for(i=0;i < size;i++)
    {
    printf("\n i = %d",i);

    if( subsetsum(a,size,sum,selected,i))
    printanswer(a,size,selected);

    memset(selected,FALSE,size);
    }

    return EXIT_SUCCESS;
    }


    int subsetsum(int *a,int n,int sum,bln *selected ,int start)
    {

    int i=start;

    if(sum == 0)
    return TRUE;



    if(selected == FALSE && a <= sum)
    {
    selected = TRUE;
    if(subsetsum(a,n,sum - a,selected,i+1))
    return TRUE;

    selected = FALSE;
    }

    return FALSE;

    }

    void printanswer(int* a,int n,bln* selected)
    {
    int i;

    for(i=0;i<n;i++)
    if(selected)
    printf("\t%d",a);

    puts("");
    }


    int compare(void* e1,void* e2)
    {
    return *(int*)e2 - *(int*)e1;

    }
    , Apr 4, 2008
    #1
    1. Advertising

  2. On Fri, 4 Apr 2008 09:11:58 -0700 (PDT),
    wrote:

    >Hi ,
    >
    >this is the program showing implementation of a* algorithm, given n
    >integers and a sum m ,write a program to find the set of integers
    >summing to m using a* algorithm.
    >
    >but i am not getting the o/p correct , i am getting only one set of
    >integers, can any one point the errors/corrections required ?
    >
    >#include<stdio.h>
    > #include<stdlib.h>
    > #include<string.h>
    >
    > typedef enum {FALSE,TRUE}bln;
    > int subsetsum(int*,int,int,bln* ,int);
    > int compare(void*,void*);
    > void printanswer(int*,int,bln*);
    >
    >
    > int main(void)
    > {
    >
    > int a[] = {5,3,4,8,9,6};
    > int sum = 15;
    > int size = sizeof(a)/sizeof(int);


    You would be better off using sizeof(*a) for the divisor.

    > int i;
    >
    > bln *selected = calloc(size,sizeof(bln));
    >
    > qsort(a,size,sizeof(int),compare);


    Your compiler should have reported a problem. Your compare function
    does not have the correct prototype to be used by qsort.

    Also sizeof(*a) here for the third argument.

    >
    > for(i=0;i < size;i++)
    > {
    > printf("\n i = %d",i);
    >
    > if( subsetsum(a,size,sum,selected,i))
    > printanswer(a,size,selected);
    >
    > memset(selected,FALSE,size);


    This sets the first six bytes pointed to by selected to zero.
    Unfortunately, you have no idea what type of integer selected points
    to. Since you only want to store 0 and 1 in each of the integers, you
    could make bln a typedef for char. Or you could change the third
    argument to size * sizeof(*selected) which would reinitialize the
    entire allocated array. As it stands now, if bln is not the same as
    char, you are not resetting the entire array for the next set of
    tests.

    > }
    >
    > return EXIT_SUCCESS;
    > }
    >
    >
    > int subsetsum(int *a,int n,int sum,bln *selected ,int start)
    > {
    >
    > int i=start;
    >
    > if(sum == 0)
    > return TRUE;
    >
    >
    >
    > if(selected == FALSE && a <= sum)
    > {
    > selected = TRUE;
    > if(subsetsum(a,n,sum - a,selected,i+1))


    It is possible to call subsetsum with start set to size-1. This
    recursive call would then call subsetsum with start set to size and i
    is then set to start and both selected and a attempt to evaluate
    non-existent objects. This is called undefined behavior.

    > return TRUE;
    >
    > selected = FALSE;
    > }
    >
    > return FALSE;
    >
    > }
    >
    > void printanswer(int* a,int n,bln* selected)
    > {
    > int i;
    >
    > for(i=0;i<n;i++)
    > if(selected)
    > printf("\t%d",a);
    >
    > puts("");
    > }
    >
    >
    > int compare(void* e1,void* e2)
    > {
    > return *(int*)e2 - *(int*)e1;
    >
    > }



    Remove del for email
    Barry Schwarz, Apr 5, 2008
    #2
    1. Advertising

  3. Barry Schwarz wrote:
    > On Fri, 4 Apr 2008 09:11:58 -0700 (PDT),
    > wrote:

    <snip>
    >> int compare(void*,void*);

    <snip>
    >> qsort(a,size,sizeof(int),compare);

    >
    > Your compiler should have reported a problem. Your compare function
    > does not have the correct prototype to be used by qsort.

    What's wrong with it? Besides the missing const?

    Bye, Jojo
    Joachim Schmitz, Apr 5, 2008
    #3
  4. Guest

    On Apr 5, 1:45 pm, Barry Schwarz <> wrote:
    > On Fri, 4 Apr 2008 09:11:58 -0700 (PDT),
    > wrote:
    >
    >
    >
    >
    >
    > >Hi ,

    >
    > >this is the program showing implementation of a* algorithm, given n
    > >integers and a sum m ,write a program to find the set of integers
    > >summing to m using a* algorithm.

    >
    > >but i am not getting the o/p correct , i am getting only one set of
    > >integers, can any one point the errors/corrections required ?

    >
    > >#include<stdio.h>
    > > #include<stdlib.h>
    > > #include<string.h>

    >
    > > typedef enum {FALSE,TRUE}bln;
    > > int subsetsum(int*,int,int,bln* ,int);
    > > int compare(void*,void*);
    > > void printanswer(int*,int,bln*);

    >
    > > int main(void)
    > > {

    >
    > >   int a[]  = {5,3,4,8,9,6};
    > >   int sum  = 15;
    > >   int size = sizeof(a)/sizeof(int);

    >
    > You would be better off using sizeof(*a) for the divisor.
    >
    > >   int i;

    >
    > >   bln *selected = calloc(size,sizeof(bln));

    >
    > >   qsort(a,size,sizeof(int),compare);

    >
    > Your compiler should have reported a problem.  Your compare function
    > does not have the correct prototype to be used by qsort.
    >
    > Also sizeof(*a) here for the third argument.
    >
    >
    >
    > >   for(i=0;i < size;i++)
    > >   {
    > >     printf("\n i = %d",i);

    >
    > >     if( subsetsum(a,size,sum,selected,i))
    > >      printanswer(a,size,selected);

    >
    > >     memset(selected,FALSE,size);

    >
    > This sets the first six bytes pointed to by selected to zero.
    > Unfortunately, you have no idea what type of integer selected points
    > to.  Since you only want to store 0 and 1 in each of the integers, you
    > could make bln a typedef for char.  Or you could change the third
    > argument to size * sizeof(*selected) which would reinitialize the
    > entire allocated array.  As it stands now, if bln is not the same as
    > char, you are not resetting the entire array for the next set of
    > tests.
    >
    >
    >
    >
    >
    > >   }

    >
    > >   return EXIT_SUCCESS;
    > > }

    >
    > > int subsetsum(int *a,int n,int sum,bln *selected ,int start)
    > > {

    >
    > >   int i=start;

    >
    > >   if(sum == 0)
    > >     return TRUE;

    >
    > >   if(selected == FALSE && a <= sum)
    > >   {
    > >      selected = TRUE;
    > >      if(subsetsum(a,n,sum - a,selected,i+1))

    >
    > It is possible to call subsetsum with start set to size-1.  This
    > recursive call would then call subsetsum with start set to size and  i
    > is then set to start and both selected and a attempt to evaluate
    > non-existent objects.  This is called undefined behavior.
    >
    >
    >
    >
    >
    > >      return TRUE;

    >
    > >      selected = FALSE;
    > >   }

    >
    > >   return FALSE;

    >
    > > }

    >
    > > void printanswer(int* a,int n,bln* selected)
    > > {
    > >    int i;

    >
    > >    for(i=0;i<n;i++)
    > >     if(selected)
    > >     printf("\t%d",a);

    >
    > >    puts("");
    > > }

    >
    > > int compare(void* e1,void* e2)
    > > {
    > >    return *(int*)e2 - *(int*)e1;

    >
    > > }



    I tried what u have said as follows , but still i am not get correct o/
    p


    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>

    /*typedef enum {FALSE,TRUE}*/
    char bln;
    int subsetsum(int*,int,int,char* ,int);
    int compare(void*,void*);
    void printanswer(int*,int,char*);


    int main(void)
    {

    int a[] = {5,3,4,8,9,6};
    int sum = 15;
    int size = sizeof(a)/sizeof(*a);
    int i;

    char *selected = calloc(size,sizeof(char));

    qsort(a,size,sizeof(int),compare);

    for(i=0;i < size;i++)
    {
    printf("\n i = %d",i);

    if( subsetsum(a,size,sum,selected,i))
    printanswer(a,size,selected);

    memset(selected,0,size * sizeof(*selected));
    }

    return EXIT_SUCCESS;
    }


    int subsetsum(int *a,int n,int sum,char *selected ,int start)
    {

    int i=start;

    if(sum == 0)
    return 1;



    if(selected == 0 && a <= sum)
    {
    selected = 1;
    if(subsetsum(a,n,sum - a,selected,i+1))
    return 1;

    selected = 0;
    }

    return 0;

    }

    void printanswer(int* a,int n,char* selected)
    {
    int i;

    for(i=0;i<n;i++)
    if(selected)
    printf("\t%d",a);

    puts("");
    }


    int compare(void* e1,void* e2)
    {
    return *(int*)e1 - *(int*)e2;

    }

    I am getting o/p as follows:-

    i = 0
    i = 1 4 5 6

    i = 2
    i = 3
    i = 4
    i = 5
    , Apr 5, 2008
    #4
  5. On Sat, 5 Apr 2008 12:06:33 +0200, "Joachim Schmitz"
    <> wrote:

    >Barry Schwarz wrote:
    >> On Fri, 4 Apr 2008 09:11:58 -0700 (PDT),
    >> wrote:

    ><snip>
    >>> int compare(void*,void*);

    ><snip>
    >>> qsort(a,size,sizeof(int),compare);

    >>
    >> Your compiler should have reported a problem. Your compare function
    >> does not have the correct prototype to be used by qsort.

    >What's wrong with it? Besides the missing const?
    >


    Isn't that enough?


    Remove del for email
    Barry Schwarz, Apr 6, 2008
    #5
  6. On Sat, 5 Apr 2008 09:00:39 -0700 (PDT),
    wrote:


    snip 120+ lines of obsolete code

    Please trim your posts when replying

    >
    >I tried what u have said as follows , but still i am not get correct o/
    >p
    >
    >
    > #include<stdio.h>
    > #include<stdlib.h>
    > #include<string.h>
    >
    > /*typedef enum {FALSE,TRUE}*/
    > char bln;
    > int subsetsum(int*,int,int,char* ,int);
    > int compare(void*,void*);
    > void printanswer(int*,int,char*);
    >
    >
    > int main(void)
    > {
    >
    > int a[] = {5,3,4,8,9,6};
    > int sum = 15;
    > int size = sizeof(a)/sizeof(*a);
    > int i;
    >
    > char *selected = calloc(size,sizeof(char));
    >
    > qsort(a,size,sizeof(int),compare);


    I said your compare function was wrong. It is still wrong. If you
    don't care why should I?

    >
    > for(i=0;i < size;i++)
    > {
    > printf("\n i = %d",i);
    >
    > if( subsetsum(a,size,sum,selected,i))
    > printanswer(a,size,selected);
    >
    > memset(selected,0,size * sizeof(*selected));
    > }
    >
    > return EXIT_SUCCESS;
    > }
    >
    >
    > int subsetsum(int *a,int n,int sum,char *selected ,int start)
    > {
    >
    > int i=start;
    >
    > if(sum == 0)
    > return 1;
    >
    >
    >
    > if(selected == 0 && a <= sum)
    > {
    > selected = 1;
    > if(subsetsum(a,n,sum - a,selected,i+1))


    This will still invoke undefined behavior when i in main is size-1.
    You haven't addressed that issue at all.

    > return 1;
    >
    > selected = 0;
    > }


    There is an error in the logic of this if block. It needs to be a
    loop. The net effect of the error is that subsetsum can only detect a
    solution when using sequential elements of a. That is why it catches
    4-5-6 when i is 1 in main but does not catch 3-4-8 when i is 0 or 6-9
    when i is 3. Take a sheet of paper and "play computer" to see it
    happen.

    >
    > return 0;
    >
    > }
    >
    > void printanswer(int* a,int n,char* selected)
    > {
    > int i;
    >
    > for(i=0;i<n;i++)
    > if(selected)
    > printf("\t%d",a);
    >
    > puts("");
    > }
    >
    >
    > int compare(void* e1,void* e2)
    > {
    > return *(int*)e1 - *(int*)e2;
    >
    > }
    >
    >I am getting o/p as follows:-
    >
    > i = 0
    > i = 1 4 5 6
    >
    > i = 2
    > i = 3
    > i = 4
    > i = 5



    Remove del for email
    Barry Schwarz, Apr 6, 2008
    #6
  7. Barry Schwarz wrote:
    > On Sat, 5 Apr 2008 12:06:33 +0200, "Joachim Schmitz"
    > <> wrote:
    >
    >> Barry Schwarz wrote:
    >>> On Fri, 4 Apr 2008 09:11:58 -0700 (PDT),
    >>> wrote:

    >> <snip>
    >>>> int compare(void*,void*);

    >> <snip>
    >>>> qsort(a,size,sizeof(int),compare);
    >>>
    >>> Your compiler should have reported a problem. Your compare function
    >>> does not have the correct prototype to be used by qsort.

    >> What's wrong with it? Besides the missing const?
    >>

    >
    > Isn't that enough?

    Maybe, but why didn't you say so rather than let us guess?

    Bye, Jojo
    Joachim Schmitz, Apr 6, 2008
    #7
  8. Barry Schwarz wrote:
    > On Sat, 5 Apr 2008 09:00:39 -0700 (PDT),
    > wrote:
    >
    >
    > snip 120+ lines of obsolete code
    >
    > Please trim your posts when replying
    >
    >>
    >> I tried what u have said as follows , but still i am not get correct
    >> o/ p
    >>
    >>
    >> #include<stdio.h>
    >> #include<stdlib.h>
    >> #include<string.h>
    >>
    >> /*typedef enum {FALSE,TRUE}*/
    >> char bln;
    >> int subsetsum(int*,int,int,char* ,int);
    >> int compare(void*,void*);
    >> void printanswer(int*,int,char*);
    >>
    >>
    >> int main(void)
    >> {
    >>
    >> int a[] = {5,3,4,8,9,6};
    >> int sum = 15;
    >> int size = sizeof(a)/sizeof(*a);
    >> int i;
    >>
    >> char *selected = calloc(size,sizeof(char));
    >>
    >> qsort(a,size,sizeof(int),compare);

    >
    > I said your compare function was wrong. It is still wrong. If you
    > don't care why should I?

    You hadn't said where it was wrong and still don't bother to.
    To the OP:
    int compare(const void*, const void*);

    Bye, Jojo
    Joachim Schmitz, Apr 6, 2008
    #8
  9. Guest

    Here is the corrected program

    #include< stdio.h >
    #include< stdlib.h >
    #include< string.h >


    char bln;
    int subsetsum(int*,int,int,char* ,int);
    int compare(const void*,const void*);
    void printanswer(int*,int,char*);


    int main(void)
    {

    int a[] = {5,3,4,8,9,6};
    int sum = 15;
    int size = sizeof(a)/sizeof(*a);
    int i;
    char *selected = calloc(size,sizeof(*selected));

    qsort(a,size,sizeof(int),compare);

    for(i=0;i < (size-1);i++)
    {
    printf("\n i = %d",i);

    if( subsetsum(a,size,sum,selected,i))
    printanswer(a,size,selected);

    memset(selected,0,size * sizeof(*selected));
    }

    return EXIT_SUCCESS;
    }


    int subsetsum(int *a,int n,int sum,char *selected ,int start)
    {
    int i;

    if(sum == 0)
    return 1;

    for(i=start;i <= (n-1);i++)
    if(selected == 0 && a <= sum)
    {
    selected = 1;
    if(subsetsum(a,n,sum - a,selected,i+1))
    return 1;

    selected = 0;
    }

    return 0;
    }

    void printanswer(int* a,int n,char* selected)
    {
    int i;

    for(i=0;i< n;i++)
    if(selected)
    printf("\t%d",a);

    puts("");
    }


    int compare(const void* e1,const void* e2)
    {
    return *(int*)e2 - *(int*)e1;
    }
    , Apr 6, 2008
    #9
  10. On Sun, 6 Apr 2008 09:17:42 +0200, "Joachim Schmitz"
    <> wrote:

    >Barry Schwarz wrote:
    >> On Sat, 5 Apr 2008 12:06:33 +0200, "Joachim Schmitz"
    >> <> wrote:
    >>
    >>> Barry Schwarz wrote:
    >>>> On Fri, 4 Apr 2008 09:11:58 -0700 (PDT),
    >>>> wrote:
    >>> <snip>
    >>>>> int compare(void*,void*);
    >>> <snip>
    >>>>> qsort(a,size,sizeof(int),compare);
    >>>>
    >>>> Your compiler should have reported a problem. Your compare function
    >>>> does not have the correct prototype to be used by qsort.
    >>> What's wrong with it? Besides the missing const?
    >>>

    >>
    >> Isn't that enough?

    >Maybe, but why didn't you say so rather than let us guess?
    >

    Because spoon feeding is not conducive to learning. He didn't ask why
    he got a diagnostic message he didn't understand. He asked why his
    code wasn't producing the expected results. Two reasonable first
    steps are to remove the undefined behavior and generate a clean
    compile.

    If he looked up qsort and checked the prototype, the lesson would stay
    with him a lot longer. Or at least he will improve his skill in
    looking it up. And maybe also figure out how to get his compiler to
    warn him if he makes a similar mistake again.


    Remove del for email
    Barry Schwarz, Apr 6, 2008
    #10
  11. On Sun, 6 Apr 2008 04:46:27 -0700 (PDT),
    wrote:

    >Here is the corrected program
    >


    It looks much better.

    >#include< stdio.h >
    >#include< stdlib.h >
    >#include< string.h >
    >
    >
    >char bln;
    >int subsetsum(int*,int,int,char* ,int);
    >int compare(const void*,const void*);
    >void printanswer(int*,int,char*);
    >
    >
    >int main(void)
    >{
    >
    >int a[] = {5,3,4,8,9,6};
    >int sum = 15;
    >int size = sizeof(a)/sizeof(*a);
    >int i;
    >char *selected = calloc(size,sizeof(*selected));
    >
    >qsort(a,size,sizeof(int),compare);
    >
    >for(i=0;i < (size-1);i++)
    >{
    >printf("\n i = %d",i);
    >
    >if( subsetsum(a,size,sum,selected,i))
    >printanswer(a,size,selected);
    >
    >memset(selected,0,size * sizeof(*selected));
    >}


    A style suggestion which will save you a lot of aggravation later
    (when you write larger programs). Learn to indent consistently. I
    prefer 3 or 4 spaces (not tabs if you post to Usenet) but the
    consistency is more important than the value (within reason). This
    block should look something like
    for
    {
    printf
    if
    printanswer
    memset
    }
    It lets you quickly recognize the range of loops and if statements.

    >
    >return EXIT_SUCCESS;
    >}
    >
    >
    >int subsetsum(int *a,int n,int sum,char *selected ,int start)
    >{
    >int i;
    >
    >if(sum == 0)
    >return 1;
    >
    >for(i=start;i <= (n-1);i++)


    Using size-1 in main and n-1 here eliminates the undefined behavior at
    the cost of not handling boundary conditions (also known as extreme
    cases or corner conditions). Try the same program with sum set 3.

    You should also try with sum set to 4 or 7 and decide how you want to
    clean up the output. (Hint: one solution would be a simple if in
    front of the call to printanswer.)

    >if(selected == 0 && a <= sum)
    >{
    >selected = 1;
    >if(subsetsum(a,n,sum - a,selected,i+1))
    >return 1;
    >
    >selected = 0;
    >}
    >
    >return 0;
    >}
    >
    >void printanswer(int* a,int n,char* selected)
    >{
    >int i;
    >
    >for(i=0;i< n;i++)
    >if(selected)
    >printf("\t%d",a);


    for
    if
    printf

    >
    >puts("");
    >}
    >
    >
    >int compare(const void* e1,const void* e2)
    >{
    >return *(int*)e2 - *(int*)e1;


    Many lint type programs will complain that you are casting away the
    const. Chang the two casts to (const int*), even though technically
    unnecessary (especially in this case with such a simple function),
    would eliminate that.

    Just for your info, the above is not completely safe in that it could
    result in overflow. Since your real purpose is the algorithm and not
    the sort, I wouldn't change it but the usual recommendation is

    const int *i2 = e2;
    const int *i1 = e1;
    return (*i1 > *i2) ? (-1) : (*i1 < *i2);
    (parentheses just for clarity)

    I wonder why you changed from an ascending sort to a descending one.

    >}



    Remove del for email
    Barry Schwarz, Apr 6, 2008
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jason Coyne  Gaijin42

    Word wrap line break code and algorithm for c#

    Jason Coyne Gaijin42, Apr 8, 2004, in forum: ASP .Net
    Replies:
    0
    Views:
    24,148
    Jason Coyne Gaijin42
    Apr 8, 2004
  2. Adam

    algorithm problem

    Adam, Nov 3, 2003, in forum: VHDL
    Replies:
    5
    Views:
    3,124
    A123b456c
    Nov 8, 2003
  3. senthil
    Replies:
    3
    Views:
    1,866
    prabinthomaskottayil
    Nov 25, 2011
  4. Ahmed Moustafa
    Replies:
    0
    Views:
    767
    Ahmed Moustafa
    Nov 15, 2003
  5. Bapaiah Katepalli
    Replies:
    1
    Views:
    1,483
    Mike Treseler
    Jun 23, 2006
Loading...

Share This Page