Speed And Heuristics

If you try this program out you will find that at first everything works quickly with answers flashing up after a few seconds. However if you try N=30,000 say then things slow to a stop.

The problem is that the knapsack algorithm slows down as 2^N which makes the problem for 30,000 number about 10^10000 (yes 1 followed by 10,000 zeros) times longer to solve than the 1000 number problem – so don't wait for a solution too long. 

To see this in action try N=50, 500 and 5000. In most cases you will give up waiting for the 5000 case. 

It is the huge number of different combinations that have to be considered that makes the task so difficult.

It is a the definition of NP problems that finding a solution takes a long time but verifying that you have a solution is very quick. In this case you have to search all possible combinations to find a solution but checking that you have a solution is just a matter of adding the values provided up and checking that the sum to the target and are in the array. 

However, how do you know that there isn't a short cut that means you don't have to consider every possible combination?

There are algorithms that attempt to solve the problem more quickly. For example there are variations on the greedy algorithm - pick the first number closest to the target, then the next closest and so on. A more sophisticated greedy algorithm is based on dynamic programming. The key factor in all of these algorithms is that they usually find the solution in reasonable time but there is no promise that they will ever find the solution without examining every possible combination. They may be advanced but they are still "heuristics", i.e. algorithms that usually work quicker than an exhaustive search but this isn't guaranteed.

Uses

The knapsack problem is the basis for one method of public key cryptography.

A set of numbers in a given order is made public and any user can code a message by multiplying each number by a zero or a one according to the messages binary representation.

All of the values are added up to give a single value and this is of course the "target" value in a knapsack problem using the given set of numbers.

Of course you can't decode the message because this would mean solving the knapsack problem for very very large N. However the intended recipient of the message can decode it because they have a "shadow" set of numbers with a special properties that make the solution of the knapsack problem very easy. So anyone can code a message using the public numbers but only the recipient can decode it without solving the full knapsack problem.

Unfortunately a few years ago it was discovered that the need to use a "shadow" set of values made the knapsack problem posed by the public values rather easier to solve than was originally thought – i.e. there was a way of doing the job much faster than 2^N. So now the knapsack code is no longer used but it is still interesting and with a better set of shadow values might even be resurrected one day.

The program can be downloaded from the CodeBin. Note you have to register with I Programmer to access this.  

Related Articles:

How not to shuffle - the Knuth Fisher-Yates algorithm       

Recursion

Public Key Encryption

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

<ASIN:9810221207>

<ASIN:059651610X>

<ASIN:3540613560>