Velocity Reviews > A* algorithm

# A* algorithm

sulekhasweety@gmail.com
Guest
Posts: n/a

 04-04-2008
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[i] == FALSE && a[i] <= sum)
{
selected[i] = TRUE;
if(subsetsum(a,n,sum - a[i],selected,i+1))
return TRUE;

selected[i] = FALSE;
}

return FALSE;

}

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

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

puts("");
}

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

}

Barry Schwarz
Guest
Posts: n/a

 04-05-2008
On Fri, 4 Apr 2008 09:11:58 -0700 (PDT), http://www.velocityreviews.com/forums/(E-Mail Removed)
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);

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))
>
> 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[i] == FALSE && a[i] <= sum)
> {
> selected[i] = TRUE;
> if(subsetsum(a,n,sum - a[i],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[i] and a[i] attempt to evaluate
non-existent objects. This is called undefined behavior.

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

Remove del for email

Joachim Schmitz
Guest
Posts: n/a

 04-05-2008
Barry Schwarz wrote:
> On Fri, 4 Apr 2008 09:11:58 -0700 (PDT), (E-Mail Removed)
> 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

sulekhasweety@gmail.com
Guest
Posts: n/a

 04-05-2008
On Apr 5, 1:45*pm, Barry Schwarz <(E-Mail Removed)> wrote:
> On Fri, 4 Apr 2008 09:11:58 -0700 (PDT), (E-Mail Removed)
> 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[i] == FALSE && a[i] <= sum)
> > * {
> > * * *selected[i] = TRUE;
> > * * *if(subsetsum(a,n,sum - a[i],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[i] and a[i] attempt to evaluate
> non-existent objects. *This is called undefined behavior.
>
>
>
>
>
> > * * *return TRUE;

>
> > * * *selected[i] = FALSE;
> > * }

>
> > * return FALSE;

>
> > }

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

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

>
> > * *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[i] == 0 && a[i] <= sum)
{
selected[i] = 1;
if(subsetsum(a,n,sum - a[i],selected,i+1))
return 1;

selected[i] = 0;
}

return 0;

}

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

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

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

Barry Schwarz
Guest
Posts: n/a

 04-06-2008
On Sat, 5 Apr 2008 12:06:33 +0200, "Joachim Schmitz"
<(E-Mail Removed)> wrote:

>Barry Schwarz wrote:
>> On Fri, 4 Apr 2008 09:11:58 -0700 (PDT), (E-Mail Removed)
>> 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
Guest
Posts: n/a

 04-06-2008
On Sat, 5 Apr 2008 09:00:39 -0700 (PDT), (E-Mail Removed)
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[i] == 0 && a[i] <= sum)
> {
> selected[i] = 1;
> if(subsetsum(a,n,sum - a[i],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[i] = 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[i])
> printf("\t%d",a[i]);
>
> 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

Joachim Schmitz
Guest
Posts: n/a

 04-06-2008
Barry Schwarz wrote:
> On Sat, 5 Apr 2008 12:06:33 +0200, "Joachim Schmitz"
> <(E-Mail Removed)> wrote:
>
>> Barry Schwarz wrote:
>>> On Fri, 4 Apr 2008 09:11:58 -0700 (PDT), (E-Mail Removed)
>>> 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
Guest
Posts: n/a

 04-06-2008
Barry Schwarz wrote:
> On Sat, 5 Apr 2008 09:00:39 -0700 (PDT), (E-Mail Removed)
> 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

sulekhasweety@gmail.com
Guest
Posts: n/a

 04-06-2008
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[i] == 0 && a[i] <= sum)
{
selected[i] = 1;
if(subsetsum(a,n,sum - a[i],selected,i+1))
return 1;

selected[i] = 0;
}

return 0;
}

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

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

puts("");
}

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

Barry Schwarz
Guest
Posts: n/a

 04-06-2008
On Sun, 6 Apr 2008 09:17:42 +0200, "Joachim Schmitz"
<(E-Mail Removed)> wrote:

>Barry Schwarz wrote:
>> On Sat, 5 Apr 2008 12:06:33 +0200, "Joachim Schmitz"
>> <(E-Mail Removed)> wrote:
>>
>>> Barry Schwarz wrote:
>>>> On Fri, 4 Apr 2008 09:11:58 -0700 (PDT), (E-Mail Removed)
>>>> 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