Discussion:
Lab 3
(too old to reply)
Gupta Kunal Kishore
2004-02-16 00:29:32 UTC
Permalink
Hi

I am not sure what does Lab 3 mean by DECISION LEVEL ?
Also I am wondering what's the use of assignstack if we have
solver->variables to store the values assigned to variables, and how does
this assignStack works??

Can some T.A. please help me.

Thanks
Diego Huang
2004-02-16 16:02:04 UTC
Permalink
Each call to the function solve is one decision level. Take a look at the
pseudocode for solve(). Each decision level will include the deductions,
and a guess of the next unassigned variable. So, for example:

dec level 1: x1 = 0
dec level 2: x4 = 1, x5 = 0, x2 = 0
dec level 3: x3 = 0, x6 = 1

And also, say for example that the decisions in level 3 lead to a
conflict, so you backtrack to level 2, which means that you remove the
assignments made in level 3 and are left with the assignments of level 1
and 2.

Take a look also at the given functions getNextVar() and backTrack() to
get a better idea of how the structures are supposed to be used.

The reason for also having solver->variables is so that you have all the
assignments in one neat little place. Because if you were to use the stack
to get the assignments, you'd have to loop through an array, and then go
through a linked list to get the values. If you use solver->variables,
it's just a one-dimensional array. Again, take a look at how they wrote
backTrack(), and you'll see how the stack and solver->variables work
together.

HTH,

Diego
Date: Mon, 16 Feb 2004 00:29:32 GMT
Newsgroups: ut.ecf.ece242
Subject: Lab 3
Hi
I am not sure what does Lab 3 mean by DECISION LEVEL ?
Also I am wondering what's the use of assignstack if we have
solver->variables to store the values assigned to variables, and how does
this assignStack works??
Can some T.A. please help me.
Thanks
Alexander Smith
2004-02-16 16:24:10 UTC
Permalink
Hi everyone,

Sorry for the delay in responding to newsgroup posts. Diego is exactly
correct (except that decision levels are zero-based, so in the example
below, they should start at 0, not 1). Another useful piece of advice
Diego gives is to look at the code we've given you. Instead of just giving
you .o files, we gave you C code. You should be able to understand how it
works if you read it. It might give you hints on how the data structures
are to be used.

Alexander
Post by Diego Huang
Each call to the function solve is one decision level. Take a look at the
pseudocode for solve(). Each decision level will include the deductions,
dec level 1: x1 = 0
dec level 2: x4 = 1, x5 = 0, x2 = 0
dec level 3: x3 = 0, x6 = 1
And also, say for example that the decisions in level 3 lead to a
conflict, so you backtrack to level 2, which means that you remove the
assignments made in level 3 and are left with the assignments of level 1
and 2.
Take a look also at the given functions getNextVar() and backTrack() to
get a better idea of how the structures are supposed to be used.
The reason for also having solver->variables is so that you have all the
assignments in one neat little place. Because if you were to use the stack
to get the assignments, you'd have to loop through an array, and then go
through a linked list to get the values. If you use solver->variables,
backTrack(), and you'll see how the stack and solver->variables work
together.
HTH,
Diego
Date: Mon, 16 Feb 2004 00:29:32 GMT
Newsgroups: ut.ecf.ece242
Subject: Lab 3
Hi
I am not sure what does Lab 3 mean by DECISION LEVEL ?
Also I am wondering what's the use of assignstack if we have
solver->variables to store the values assigned to variables, and how does
this assignStack works??
Can some T.A. please help me.
Thanks
Diego Huang
2004-02-16 16:53:47 UTC
Permalink
Hi,

I have a question about the backtracking part.

Say that I'm in dlevel 2, made deductions for x3 and x4 in this level, and
the next unassigned var is x5. So, following the pseudocode for solve(), I
try x5 = 0. If this doesn't work, branch() will backtrack. backTrack()
will delete all assignments at this level, which includes the deductions
for x3 and x4. So later, in solve(), when I try x5 = 1, the deductions are
not there anymore? Am I missing or overlooking something here?

Thanks,

Diego
Date: Mon, 16 Feb 2004 16:24:10 GMT
Newsgroups: ut.ecf.ece242
Subject: Re: Lab 3
Hi everyone,
Sorry for the delay in responding to newsgroup posts. Diego is exactly
correct (except that decision levels are zero-based, so in the example
below, they should start at 0, not 1). Another useful piece of advice
Diego gives is to look at the code we've given you. Instead of just giving
you .o files, we gave you C code. You should be able to understand how it
works if you read it. It might give you hints on how the data structures
are to be used.
Alexander
Post by Diego Huang
Each call to the function solve is one decision level. Take a look at the
pseudocode for solve(). Each decision level will include the deductions,
dec level 1: x1 = 0
dec level 2: x4 = 1, x5 = 0, x2 = 0
dec level 3: x3 = 0, x6 = 1
And also, say for example that the decisions in level 3 lead to a
conflict, so you backtrack to level 2, which means that you remove the
assignments made in level 3 and are left with the assignments of level 1
and 2.
Take a look also at the given functions getNextVar() and backTrack() to
get a better idea of how the structures are supposed to be used.
The reason for also having solver->variables is so that you have all the
assignments in one neat little place. Because if you were to use the stack
to get the assignments, you'd have to loop through an array, and then go
through a linked list to get the values. If you use solver->variables,
backTrack(), and you'll see how the stack and solver->variables work
together.
HTH,
Diego
Date: Mon, 16 Feb 2004 00:29:32 GMT
Newsgroups: ut.ecf.ece242
Subject: Lab 3
Hi
I am not sure what does Lab 3 mean by DECISION LEVEL ?
Also I am wondering what's the use of assignstack if we have
solver->variables to store the values assigned to variables, and how does
this assignStack works??
Can some T.A. please help me.
Thanks
Alexander Smith
2004-02-17 02:54:30 UTC
Permalink
The pseudo-code in Figure 5 has been now been corrected. Everyone should
download a new copy of the handout.


It is solve() that should be calling branch() with dlevel+1, not the other
way around. This way, the new assignment will get put in the *next*
decision level. In Diego's example below, this would mean x5=0 would go in
level 3. Then, if that failed, backtrack would "undo" x5=0, but would
leave the deduced values of x3 and x4 alone. The same thing would happen
for x5=1 - it would go in dlevel 3.

You may be wondering if anything will ever go into dlevel 0. In fact, this
can happen if you have clauses with only one linteral in them. The Unit
Literal Rule applies to these clauses, so they will produce deductions
which will get put in dlevel 0. However, if all the clauses in your
formula have two or more variables, then dlevel 0 will remain empty.

Alexander
Post by Diego Huang
Hi,
I have a question about the backtracking part.
Say that I'm in dlevel 2, made deductions for x3 and x4 in this level, and
the next unassigned var is x5. So, following the pseudocode for solve(), I
try x5 = 0. If this doesn't work, branch() will backtrack. backTrack()
will delete all assignments at this level, which includes the deductions
for x3 and x4. So later, in solve(), when I try x5 = 1, the deductions are
not there anymore? Am I missing or overlooking something here?
Thanks,
Diego
Date: Mon, 16 Feb 2004 16:24:10 GMT
Newsgroups: ut.ecf.ece242
Subject: Re: Lab 3
Hi everyone,
Sorry for the delay in responding to newsgroup posts. Diego is exactly
correct (except that decision levels are zero-based, so in the example
below, they should start at 0, not 1). Another useful piece of advice
Diego gives is to look at the code we've given you. Instead of just giving
you .o files, we gave you C code. You should be able to understand how it
works if you read it. It might give you hints on how the data structures
are to be used.
Alexander
Post by Diego Huang
Each call to the function solve is one decision level. Take a look at the
pseudocode for solve(). Each decision level will include the deductions,
dec level 1: x1 = 0
dec level 2: x4 = 1, x5 = 0, x2 = 0
dec level 3: x3 = 0, x6 = 1
And also, say for example that the decisions in level 3 lead to a
conflict, so you backtrack to level 2, which means that you remove the
assignments made in level 3 and are left with the assignments of level 1
and 2.
Take a look also at the given functions getNextVar() and backTrack() to
get a better idea of how the structures are supposed to be used.
The reason for also having solver->variables is so that you have all the
assignments in one neat little place. Because if you were to use the stack
to get the assignments, you'd have to loop through an array, and then go
through a linked list to get the values. If you use solver->variables,
backTrack(), and you'll see how the stack and solver->variables work
together.
HTH,
Diego
Date: Mon, 16 Feb 2004 00:29:32 GMT
Newsgroups: ut.ecf.ece242
Subject: Lab 3
Hi
I am not sure what does Lab 3 mean by DECISION LEVEL ?
Also I am wondering what's the use of assignstack if we have
solver->variables to store the values assigned to variables, and how does
this assignStack works??
Can some T.A. please help me.
Thanks
Arshad Shahzad
2004-02-22 02:38:52 UTC
Permalink
I thought we can only have one assingment at one dlevel,i.e if there are 4
variables then we will have four dlevels.
I don't seem to understand this concept of dlevels .Can any one plz
explain me how this works,
thanks
Post by Diego Huang
Each call to the function solve is one decision level. Take a look at the
pseudocode for solve(). Each decision level will include the deductions,
dec level 1: x1 = 0
dec level 2: x4 = 1, x5 = 0, x2 = 0
dec level 3: x3 = 0, x6 = 1
And also, say for example that the decisions in level 3 lead to a
conflict, so you backtrack to level 2, which means that you remove the
assignments made in level 3 and are left with the assignments of level 1
and 2.
Take a look also at the given functions getNextVar() and backTrack() to
get a better idea of how the structures are supposed to be used.
The reason for also having solver->variables is so that you have all the
assignments in one neat little place. Because if you were to use the stack
to get the assignments, you'd have to loop through an array, and then go
through a linked list to get the values. If you use solver->variables,
backTrack(), and you'll see how the stack and solver->variables work
together.
HTH,
Diego
Date: Mon, 16 Feb 2004 00:29:32 GMT
Newsgroups: ut.ecf.ece242
Subject: Lab 3
Hi
I am not sure what does Lab 3 mean by DECISION LEVEL ?
Also I am wondering what's the use of assignstack if we have
solver->variables to store the values assigned to variables, and how does
this assignStack works??
Can some T.A. please help me.
Thanks
Arshad Shahzad
2004-02-22 15:35:41 UTC
Permalink
Can someone plz reply for the massege i posted regarding dlevels.
thanks
Post by Arshad Shahzad
I thought we can only have one assingment at one dlevel,i.e if there are 4
variables then we will have four dlevels.
I don't seem to understand this concept of dlevels .Can any one plz
explain me how this works,
thanks
Post by Diego Huang
Each call to the function solve is one decision level. Take a look at the
pseudocode for solve(). Each decision level will include the deductions,
dec level 1: x1 = 0
dec level 2: x4 = 1, x5 = 0, x2 = 0
dec level 3: x3 = 0, x6 = 1
And also, say for example that the decisions in level 3 lead to a
conflict, so you backtrack to level 2, which means that you remove the
assignments made in level 3 and are left with the assignments of level 1
and 2.
Take a look also at the given functions getNextVar() and backTrack() to
get a better idea of how the structures are supposed to be used.
The reason for also having solver->variables is so that you have all the
assignments in one neat little place. Because if you were to use the stack
to get the assignments, you'd have to loop through an array, and then go
through a linked list to get the values. If you use solver->variables,
backTrack(), and you'll see how the stack and solver->variables work
together.
HTH,
Diego
Date: Mon, 16 Feb 2004 00:29:32 GMT
Newsgroups: ut.ecf.ece242
Subject: Lab 3
Hi
I am not sure what does Lab 3 mean by DECISION LEVEL ?
Also I am wondering what's the use of assignstack if we have
solver->variables to store the values assigned to variables, and how does
this assignStack works??
Can some T.A. please help me.
Thanks
Loading...