A* algorithm

Collapse
This topic is closed.
X
X
Collapse
 
  • Page of 1
  • Time
  • Show
Clear All
new posts
Previous template Next
  • sulekhasweety@gmail.com
    #1

    A* algorithm

    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*,v oid*);
    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,siz eof(bln));

    qsort(a,size,si zeof(int),compa re);

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

    if( subsetsum(a,siz e,sum,selected, i))
    printanswer(a,s ize,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[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;

    }
    Tags: None
    • Barry Schwarz
      #2
      Re: A* algorithm

      On Fri, 4 Apr 2008 09:11:58 -0700 (PDT), sulekhasweety@g mail.com
      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*,v oid*);
      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,siz eof(bln));
      >
      qsort(a,size,si zeof(int),compa re);
      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,siz e,sum,selected, i))
      printanswer(a,s ize,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(*selecte d) 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

        Comment

        • Joachim Schmitz
          #3
          Re: A* algorithm

          Barry Schwarz wrote:
          On Fri, 4 Apr 2008 09:11:58 -0700 (PDT), sulekhasweety@g mail.com
          wrote:
          <snip>
          >int compare(void*,v oid*);
          <snip>
          > qsort(a,size,si zeof(int),compa re);
          >
          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


            Comment

            • sulekhasweety@gmail.com
              #4
              Re: A* algorithm

              On Apr 5, 1:45 pm, Barry Schwarz <schwa...@dqel. comwrote:
              On Fri, 4 Apr 2008 09:11:58 -0700 (PDT), sulekhaswe...@g mail.com
              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*,v oid*);
              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,siz eof(bln));
              >
                qsort(a,size,si zeof(int),compa re);
              >
              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,siz e,sum,selected, i))
                   printanswer(a,s ize,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(*selecte d) 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*,v oid*);
              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,siz eof(char));

              qsort(a,size,si zeof(int),compa re);

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

              if( subsetsum(a,siz e,sum,selected, i))
              printanswer(a,s ize,selected);

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

              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

                Comment

                • Barry Schwarz
                  #5
                  Re: A* algorithm

                  On Sat, 5 Apr 2008 12:06:33 +0200, "Joachim Schmitz"
                  <nospam.jojo@sc hmitz-digital.dewrote :
                  >Barry Schwarz wrote:
                  >On Fri, 4 Apr 2008 09:11:58 -0700 (PDT), sulekhasweety@g mail.com
                  >wrote:
                  ><snip>
                  >>int compare(void*,v oid*);
                  ><snip>
                  >> qsort(a,size,si zeof(int),compa re);
                  >>
                  >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

                    Comment

                    • Barry Schwarz
                      #6
                      Re: A* algorithm

                      On Sat, 5 Apr 2008 09:00:39 -0700 (PDT), sulekhasweety@g mail.com
                      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*,v oid*);
                      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,siz eof(char));
                      >
                      qsort(a,size,si zeof(int),compa re);
                      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,siz e,sum,selected, i))
                      printanswer(a,s ize,selected);
                      >
                      memset(selected ,0,size * sizeof(*selecte d));
                      }
                      >
                      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

                        Comment

                        • Joachim Schmitz
                          #7
                          Re: A* algorithm

                          Barry Schwarz wrote:
                          On Sat, 5 Apr 2008 12:06:33 +0200, "Joachim Schmitz"
                          <nospam.jojo@sc hmitz-digital.dewrote :
                          >
                          >Barry Schwarz wrote:
                          >>On Fri, 4 Apr 2008 09:11:58 -0700 (PDT), sulekhasweety@g mail.com
                          >>wrote:
                          ><snip>
                          >>>int compare(void*,v oid*);
                          ><snip>
                          >>> qsort(a,size,si zeof(int),compa re);
                          >>>
                          >>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


                            Comment

                            • Joachim Schmitz
                              #8
                              Re: A* algorithm

                              Barry Schwarz wrote:
                              On Sat, 5 Apr 2008 09:00:39 -0700 (PDT), sulekhasweety@g mail.com
                              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<stdli b.h>
                              >#include<strin g.h>
                              >>
                              >/*typedef enum {FALSE,TRUE}*/
                              > char bln;
                              >int subsetsum(int*, int,int,char* ,int);
                              >int compare(void*,v oid*);
                              >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,siz eof(char));
                              >>
                              > qsort(a,size,si zeof(int),compa re);
                              >
                              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


                                Comment

                                • sulekhasweety@gmail.com
                                  #9
                                  Re: A* algorithm

                                  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,siz eof(*selected)) ;

                                  qsort(a,size,si zeof(int),compa re);

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

                                  if( subsetsum(a,siz e,sum,selected, i))
                                  printanswer(a,s ize,selected);

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

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

                                    Comment

                                    • Barry Schwarz
                                      #10
                                      Re: A* algorithm

                                      On Sun, 6 Apr 2008 09:17:42 +0200, "Joachim Schmitz"
                                      <nospam.jojo@sc hmitz-digital.dewrote :
                                      >Barry Schwarz wrote:
                                      >On Sat, 5 Apr 2008 12:06:33 +0200, "Joachim Schmitz"
                                      ><nospam.jojo@s chmitz-digital.dewrote :
                                      >>
                                      >>Barry Schwarz wrote:
                                      >>>On Fri, 4 Apr 2008 09:11:58 -0700 (PDT), sulekhasweety@g mail.com
                                      >>>wrote:
                                      >><snip>
                                      >>>>int compare(void*,v oid*);
                                      >><snip>
                                      >>>> qsort(a,size,si zeof(int),compa re);
                                      >>>>
                                      >>>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

                                        Comment

                                        • Barry Schwarz
                                          #11
                                          Re: A* algorithm

                                          On Sun, 6 Apr 2008 04:46:27 -0700 (PDT), sulekhasweety@g mail.com
                                          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,siz eof(*selected)) ;
                                          >
                                          >qsort(a,size,s izeof(int),comp are);
                                          >
                                          >for(i=0;i < (size-1);i++)
                                          >{
                                          >printf("\n i = %d",i);
                                          >
                                          >if( subsetsum(a,siz e,sum,selected, i))
                                          >printanswer(a, size,selected);
                                          >
                                          >memset(selecte d,0,size * sizeof(*selecte d));
                                          >}
                                          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[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]);
                                          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

                                            Comment

                                            Previous template Next
                                            Working...