# 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*);

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

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;

}

{
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

2. ### Barry SchwarzGuest

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*);
>
>
> 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);

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

3. ### Joachim SchmitzGuest

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);

>
> 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
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*);

>
> > 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);

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

>
> >     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*);

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

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;

}

{
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
5. ### Barry SchwarzGuest

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);

>>
>> 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
6. ### Barry SchwarzGuest

On Sat, 5 Apr 2008 09:00:39 -0700 (PDT),
wrote:

snip 120+ lines of obsolete code

>
>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*);
>
>
> 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))
>
> 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
7. ### Joachim SchmitzGuest

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);
>>>
>>> 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
8. ### Joachim SchmitzGuest

Barry Schwarz wrote:
> On Sat, 5 Apr 2008 09:00:39 -0700 (PDT),
> wrote:
>
>
> snip 120+ lines of obsolete code
>
>
>>
>> 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*);
>>
>>
>> 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
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*);

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

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;
}

{
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
10. ### Barry SchwarzGuest

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);
>>>>
>>>> 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
11. ### Barry SchwarzGuest

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*);
>
>
>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))
>
>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
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;
>}
>
>{
>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