Jump to content

Algorithm Problem


zak100

Recommended Posts

Hi,

I am trying to execute the following algorithm shown in the image.  I am trying to get the table shown in the image:

 

1st Iteration
L2: 1:CS=A, SL = A, NSL = A
L3: while NSL!=[]: true
L4:
L6:no children: false
L17:NSL =BCDA
L18:CS:=B
L19:SL=BA
L20, L21

2nd Iteration
L3:While NSL (true)
L4:
L6:no children: false
L17: NSL=EFBCDA
L18: CS:=E
L19:SL:= EBA
L20, L21

3rd Iteration
L3:while NSL (true)
L4:
L6:no children: false
L17:NSL= HIEFBCDA
L18: CS:= H
L19:SL:=HEBA
L20, L21
 

At this point its fine but when there are no more children of current node, it has to backtrack, so it should execute the while loop, at that point I am losing the track:

L3:while NSL(true)
L4:
L6:no children: true
L7:begin
L8:while SL is not empty (true) and CS:=H
L9: DE=H
L10:SL=EBA
L11:NSL=IEFBCDA
L12:CS=I
L14:SL= IEBA

 

Now it should keep traversing the while loop but I am having problem with this. Somebody please correct this algorithm or guide me a better backtracking algorithm which has the contents of table.

 

Zulfi.

 

Zulfi.

 

Q2 ExampleBT.png

Link to comment
Share on other sites

  • 2 weeks later...

The last steps on the iteration you are stuck at gives: (Bold by me)

On 9/14/2020 at 6:30 AM, zak100 said:

L12:CS=I
L14:SL= IEBA

Which means that the next lap of the loop starts with:

L7:begin
L8:while SL is not empty (true) and CS:=I  (The first element of the list SL was changed inside the loop from the value H to the value I)

With that modified condition you can continue analysing the next iteration through L9-L14 again instead of being stuck.

 

Edited by Ghideon
clarified a description
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.