0
$\begingroup$

I've got an idea for a tool I want to make but I am not sure how to go on about trying to solve it... I was hoping if you could help me classify it and also give me some suggestions on how I could try solving it.

Background

This summer I played through the Persona 4 JRPG game, similar to Pokemon. In the game, you can collect and level up "personas". The game also features a system that allows players to combine personas through "fusion" to create other personas.

There are tools out there that calculate the various combinations of "parents" possible to create a certain persona. However, these tools only give the immediate parents, I want to create a tool that given a set of personas the player has available, shows all the fusions that need to be made to crate a persona, as cheaply as possible (there is a price involved).

Details

There are about 100 or so personas in the game and each persona belongs to a certain arcana (type).

When a player has found a certain persona, he or she can "summon" (create) it later for a certain price. These summoning costs are what makes out the price for the total creation chain.

The fusion is done by combining two or three personas. The resulting persona's arcane is a look-up depending on the parents', and the resulting persona is then the persona with lowest rank in the given arcana with a rank greater than the average of the parents.

After fusion is done, the resulting persona is added to the list of available personas which the player can create.

Details of the fusion are explained in this link: http://persona4.wikidot.com/fusiontutor

Task

Given a list of available personas, I want to return the whole "fusion-chain" while minimizing the total cost.

What makes this problem so difficult is the fact that the available personas changes depending on the order they are created. In general, it seems that it is cheaper to summon a persona than to summon its parents and fuse them. Because of this, it seems I would have to investigate every permutation possible...

Question

I would like to classify this problem, is it np-complete? np-hard? or even worse? It looks like a simple dynamic programming problem, but what do you do when the result is dependent on the order in which you solve each sub-problem?

Also, I wonder if anyone has some ideas on how this could be solved, preferably with as low total cost as possible.

Note: I don't know about suitable tags so I would welcome suggestions for that as well :)

$\endgroup$
  • 1
    $\begingroup$ You haven't described the one thing that "makes the problem so difficult" -- how the available personas depend on creation order. So how can anyone possibly say what the complexity of the problem is? $\endgroup$ – David Richerby Nov 27 '14 at 9:46
  • $\begingroup$ Thanks for the feedback! I tried to shorten it a bit and clarify it. Hope it's better now. Maybe should add some figures later if it is still unclear. $\endgroup$ – Shump Nov 27 '14 at 10:57
  • 1
    $\begingroup$ The shortened qurstion is certainly more readable -- thanks. Unfortunately, it's impossible to answer. NP-completeness is a very precise notion. You can't hope to prove that a problem is NP-complete unless you know exactly what the problem is and "In general, it seems that it is cheaper" to do one thing than another just isn't precise enough. For example, if it's only 0.00001% cheaper, you could probably just assume it's the same cost and get the right answer by dynamic programming. If it's 99.99999% cheaper, you can probably get the right answer by always assuming (continued) $\endgroup$ – David Richerby Nov 27 '14 at 11:11
  • $\begingroup$ that you always just directly summon the thing you want, instead of making it from its parents. In reality, it's probably neither of these extremes, maybe that makes the problem harder. But without knowing exactly what the problem is, it's impossible to say how hard it is. $\endgroup$ – David Richerby Nov 27 '14 at 11:12
  • $\begingroup$ Thanks for the comment. The reason I say "in general" is because it depends on the persona. Each persona might have 20 or so combinations to create it by fusion. Some are cheaper than directly summoning, some are not. I have not found a system for this... Maybe this wasn't clear. The purpose of my question is mainly to solve it as well as possible, not to prove np-completeness. But my hope was to identify this as a general problem and use already known method for tackling this problem. $\endgroup$ – Shump Nov 27 '14 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.