what is 3 - 1 = 2 ?

[ahmedzaalan]

can you explain this please?

2 g) If we are at level 0, and we had no success in placing A_i, place it like in steps 2 b) and 2 c), but without recursion. We have now 3 - 1 = 2 more activities to place. Go to step 2) (some methods to avoid cycling are used here).

what is 3 - 1 = 2
and what is cycle and how do you prevent it?

[Liviu Lalescu]

3 activities = A_p, A_q, A_r.

1 activity = A_i.

We needed to place A_i. Now we placed A_i, but displaced A_p, A_q and A_r. So, if we had n correctly placed activities, now we have n-2 correctly placed activities.

Cycling: I displace A_p, A_q, A_r, place A_i. Place A_p, A_q. Then place A_r and displace A_i. I am back to the same situation. The algorithm is cycling.

Avoid it: remember that A_p, A_q and A_r were displaced from slots S_p, S_q and S_r. Next time, if I can choose to displace A_m from S_m or A_p from S_p, I choose A_m from S_m, as it was not displaced. For the exact implementation, see generate.cpp, search for text "tabu" (without quotes).

Please let me know if now it is clear.