Essential Algorithms A Practical Approach to Computer Algorithms Using Python and C# vol 2 by Unknown

Author:Unknown
Language: eng
Format: epub

// Try to improve the solution.

Boolean: had_improvement = True

While (had_improvement)

Chapter 12 ■ Decision Trees 383

// Assume this time we won't have any improvement.

had_improvement = False

// Try swapping items.

For index = 0 To max_index

<Swap item number index into the other group>

// See if this improves the test solution.

If <this swap improves the test solution> Then

had_improvement = True

Else

<Swap the item back>

End If

Next index

Loop

// See if this solution is an improvement.

<If the test solution is an improvement, save it>

Next i

End MakeImprovements

The algorithm enters a loop to perform a certain number of trials. For each

trial, it picks a random test solution.

It then enters a loop that executes as long as the algorithm finds an improve-

ment for the random test solution. Each time through this improvement loop,

the algorithm tries swapping each item into the group to which it isn’t currently

assigned. If that swap improves the test solution, the algorithm keeps it. If that

swap does not improve the test solution, the algorithm undoes it.

After it can find no more improvements, the algorithm compares the test

solution to the best solution found so far and keeps it if it is better.

You can pick the number of trials to run in the same ways that you can for the

random heuristic described in the previous section. You can let the algorithm

run a fixed number of trials, a number of trials that depends on the number

of weights being partitioned, until it finds no improved best solution, or until

you stop it.

Sometimes, it is not possible to improve a path by making a single swap.

For example, suppose you are partitioning the weights 6, 5, 5, 5, 3, and 3. Sup-

pose also that you pick a random path that makes the two groups {6, 3, 3} and

{5, 5, 5} so that the groups have total weights of 12 and 15. Therefore, their total weights differ by 3.

Moving an item from the first group to the second only makes the difference

greater, so that won’t improve the solution.

If you moved an item with weight 5 from the second group to the first, the

groups would be {6, 5, 3, 3} and {5, 5}, so their total weights would be 17 and

10—also not an improvement.

384

Chapter 12 ■ Decision Trees

No single swap can improve this solution. But if you move an item

with weight 3 from the first group to the second and you also move an

item with weight 5 from the second group to the first, you get the groups {6, 5, 3}

and {5, 5, 3}. The groups would then have weights 14 and 13, an improvement

over the original solution.

The single swap strategy described in this section won’t find this improvement,

because it requires you to make two swaps at the same time. Other improve-

ment strategies try swapping two items at the same time. Of course, there are

also improvements that you cannot make by swapping two items, which you

can make by swapping three items, so that strategy doesn’t always work either.

Still, swapping two items at a time isn’t too difficult and may result in some

improvements, so it is worth implementing.

Simulated

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.