Re: Better, Simpler Programming Contest
 

(double)

[ March 03, 2004, 03:03: Message edited by: Saber Cherry ]

Re: Better, Simpler Programming Contest
 

I get confused about the difference between NP-Hard and NP-Complete. But generally, minSAT-type problems are NP-hard.

Anyway, I did a google search to clear up my confusion...

http://en.wikipedia.org/wiki/Computa...plexity_theory

I sort of recall that "NP-Complete" problems have to have a yes or no answer, and NP-Hard problems can have any answer. So a minimization/maximization that could be rephrased as NP-complete by asking "Is there a solution that scores above 100?" would itself be NP-hard.

It confuses me since I've been told contradictory facts:

NP-C must have a yes or no answer.
NP-H can have any answer.
NP-H is a subset of NP-C.

So I was trying to avoid confusion by saying "NP", but that failed=)

Incidentally, according to that site, Class P is the set of problems solvable in polynomial time, and Class NP is a set of problems that are probably not in Class P. To quote it:

<font size="2" face="sans-serif, arial, verdana">Thus... I think it is correct to call an NP-C problem "NP". But then, it's just some random internet site http://forum.shrapnelgames.com/images/icons/icon10.gif

[ March 03, 2004, 03:05: Message edited by: Saber Cherry ]

Re: Better, Simpler Programming Contest
 

<font size="2" face="sans-serif, arial, verdana">Well, isn't it just a variant of the knapsack problem, which is known to be NP-complete?

Re: Better, Simpler Programming Contest
 

<font size="2" face="sans-serif, arial, verdana">That is, indeed, hard to say. There's a way to make it more difficult, BTW, that I was pondering... a "Combined Arms" bonus. The value of a unit would be based on the number you build, so that (for example) the first of any unit was worth 2x the normal value, the second was worth 3/2x the normal value, the third was worth 4/3 of the normal value, and so forth. Not only would this be good for an AI (which would not always produce the same 2 or 3 units), but I get the feeling that it would ensure the problem was NP and not P.

Re: Better, Simpler Programming Contest
 

<font size="2" face="sans-serif, arial, verdana">Well, isn't it just a variant of the knapsack problem, which is known to be NP-complete? </font><hr /></blockquote><font size="2" face="sans-serif, arial, verdana">Hmmm.

It looks like a multidimensional variant of the unbounded knapsack problem. Adding the combined arms bonus would change that, though.

Re: Better, Simpler Programming Contest
 

<font size="2" face="sans-serif, arial, verdana">Thus... I think it is correct to call an NP-C problem "NP". But then, it's just some random internet site http://forum.shrapnelgames.com/images/icons/icon10.gif </font><hr /></blockquote><font size="2" face="sans-serif, arial, verdana">I apologize for diverting this thread into a discussion of computational complexity, but I'd like to remind everyone that Phil started it. :->

In any case, the wording on the website you reference is a bit confusing, so hopefully this will help clear up the confusion.

P is the class of (decision) problems solvable in polynomial time by a deterministic (i.e., ordinary) computer.

NP is the class of (decision) problems that are solvable in polynomial time by a non-deterministic computer. (The best way to think about NP is as problems who's answer can be checked in polynomial time.)

Every problem in P is also in NP but it is widely believed that there are problems in NP that are not in P.

NP-Complete are the hardest problems in NP. In particular, if an efficient (deterministic polynomial time) solution were found to any NP-Complete problem, then P = NP.

Every NP-Complete problem is in NP. Therefore, every NP-Complete problem is a decision (Yes/No) problem.

A Problem is NP-Hard if it is at least as hard as every problem in NP. That is, a problem is NP-Hard if solving said problem allows one to solve every problem in NP. (If there is an efficient solution to any NP-Hard problem then P=NP).

NP-Hard problems can be decision problems but they don't have to be. Every NP-Complete problem is also NP-Hard.

So technically, the optimization problem that Saber Cherry proposed can't be NP-Complete because it's not a decision problem. However, one can easily transform any optimization problem into an equivilant decision problem. For instance, instead of asking to maximize value, you can ask, "Is it possible to achieve a value of k?" (which is a decision problem). This is equivalent to the optimization problem because if you had an efficient program to solve the decision problem, you could run it many times (using a binary search) to find the optimal value of k. That is, (assume M is some big number larger than the maximum possible value) you could first run the program to find out if it's possible to achieve M/2. If it is possible to achieve M/2 then you run the program for 3*M/4. If 3*M/4 isn't achievable you would try 5*M/8. (In the worst case this requires running the decision program log(M) times which is polynomial in the size of your problem instance).

Hopefully the above explaination made some things more clear. (I apologize if my earlier post caused some confusion, what I really meant was "Is the decision Version of the optimization problem NP-Complete").

Also, thanks a lot for the unbounded Knapsack link. (I'm not familiar with the proof that unbounded Knapsack is NP-Hard, but I will undoubtably spend time tossing and turning in my bed tonight trying to figure out why this true <grin>).

- Matt Lepinski :->

Re: Better, Simpler Programming Contest
 

Ummm.... And here I thought this was a thread about a simple programming problem.... and yet I don't have a clue about half the stuff being said. :S

Oh well, I guess I'll just get back to solving the problem... http://forum.shrapnelgames.com/images/icons/icon10.gif http://forum.shrapnelgames.com/images/icons/icon10.gif http://forum.shrapnelgames.com/images/icons/icon10.gif

EDIT:
I think you're number in the example for Holy is way off... I've never come accross any province with 120 holy...

[ March 03, 2004, 06:02: Message edited by: LaFollet ]

Re: Better, Simpler Programming Contest
 

<font size="2" face="sans-serif, arial, verdana">Ooops! Thanks for pointing that out, I corrected it. Holy was supposed to be "4" http://forum.shrapnelgames.com/images/icons/blush.gif

And - Yay! Someone is working on the problem http://forum.shrapnelgames.com/images/icons/icon10.gif http://forum.shrapnelgames.com/images/icons/icon10.gif

...however, the number of votes is still listed as 2 for me, both people who won't participate... http://forum.shrapnelgames.com/image...s/confused.gif

Re: Better, Simpler Programming Contest
 

Well this is my approach so far:
1) Load both the resource info and unit info from text files.
2) Sort the units based on their "value"
3) Start using up all the resources that I can to make as many of the highest valued unit that I can. (With the test this is limited by Holy, as it usually is in game.)
4) Use up as much other resources with the next unit with the next highest value.
5) Keep doing this until resources are used up.


Anyone have any thoughts? Comments? Suggestions? http://forum.shrapnelgames.com/images/icons/icon10.gif

Re: Better, Simpler Programming Contest
 

<font size="2" face="sans-serif, arial, verdana">This greedy approach will give you quite good solutions to the problem, but not necessarily optimal ones. The quickest way to find an optimal solution for a handful of units is probably a brute-force search; for slightly larger problems I suppose that stochastic search techniques such as genetic algorithms or simulated annealing will yield decent results quickly.