So it's been a while but I started looking into this today. I'll keep using this issue since it's already open. If possible, I'd appreciate if someone could follow through my thoughts in this post to verify my basic assumptions (I found a counterexample to one of my earlier "proofs" and despite many revisions Lemma 6 failed to be what I wanted it to be - things are a lot less trivial than they may seem initially). This should serve partially as documentation and partially as peer review.

The problem formally consists of trying to find a transformation from one node set (say, A) to another (B) through a serious of point allocations (including a node adjacent to the set) and deallocations or "unspecs" (removing a node without disconnecting any nodes from the set) over the graph G (the skill "tree") such that the number of deallocations is minimal and the number of nodes in the node set never exceeds a certain limit (N). We will also require A and B to contain at least 1 common node (class start node) that cannot be unspecced (or allocated).

I will include the option to have a certain amount of unallocated points u := N - |A|; these can be treated as nodes in A that are unspecced immediately and "for free". I will assume |A| = N from here on. (This also follows from combining the proofs in Lemma 1 and Lemma 3.)

Lemma 1: We can assume both node sets to have the same number of nodes N.
Proof: If B has more nodes than N, the problem is unsolvable. If it has k nodes less, then solving the problem for B̂ consisting of B and k added "leaf" nodes yields an optimal solution by omitting the allocation of those leaf nodes. There cannot be a better solution for B than this because otherwise the best solution for B̂ would consist of the solution for B plus the allocation of the k leaf nodes.

Lemma 2: We can represent the transformation as a series of "steps", whereby each step consists of one unspec followed by one allocation.
Proof: With every point that we unspec, we reduce the amount of options for where to allocate a point (ignoring the one we just unspecced, which is clearly suboptimal to allocate again right away). It is thus impossible to require more than one unspec in a row: The first allocation after a series of k unspecs could just as well happen after the first of those k unspecs. Since |A| = |B| (Lemma 1) we must allocate exactly as many nodes as we unspec. Together, this means we can represent the transformation as an alternating series of unspecs and allocations (starting with an unspec and ending with an allocation) which can be divided into steps as suggested, making the number of steps equivalent to the number of unspecs (and the optimal solution the one with a minimal amount of steps).

Lemma 3: The problem is symmetric in that solving the problem for A -> B immediately solves B -> A.
Proof: Executing the inverse steps for the optimal solution of A -> B in reverse order does not violate any constraints. If the resulting solution for B -> A was not optimal, then A -> B could not have been optimal since the inverse transformation takes the same amount of steps.

Lemma 4: The amount of necessary steps is bounded by N-1.
Proof: Unspeccing the entire tree minus the starting node and then speccing into the new tree takes N-1 unspecs (and according to Lemma 2 equally as many steps).

Lemma 5: The amount of necessary steps is not bounded in any form by the amount of nodes that differ between A and B (it is O(∞) with respect to |A ⊕ B|)
Proof: Consider the following example:
Black nodes represent A ∩ B (nodes that are in both sets), red nodes are A - B (all nodes in A but not B) and green nodes are B - A (all nodes in B but not A). In other words, we start with the graph consisting of red+black nodes and want to get to the graph of green+black nodes. The bottom node is the starting point that cannot be unspecced.
If no extra points are available, it is easy to see that we must always respec k+1 nodes, which can grow arbitrarily large compared to the one pair of nodes that A and B differ by.

Ok, that was the easy stuff. Now, as the first precursor to the next proof, here's a slightly more complex version of the previous proof's example: http://i.imgur.com/m5Soi0v.png
Variables next to the lines denote the amount of nodes those lines represent. Like the previous example, this problem can only be solved by completely unspeccing the entire red+black tree and then respeccing into green+black: There are not enough available nodes above the "a" level to connect both the red and green "a" line to the remaining graph at the same time, hence the green "a" line can only be completed if the red "a" line is at least partially unspecced, which requires everything above to also be unspecced. The same applies on the "b" level and the "c" level (with the last being a generalization of the previous example) - which is of course redundant because we have to unspec everything anyway, but it's an important observation with regards to what's to come.

However, we may also be able to use graph nodes that are in neither A nor B to get a better solution. Consider the following example from the real skill tree (viability aside):
Clearly, the optimal respec steps involve allocating two nodes from the Lord of the Dead cluster (above the cursor) after unspeccing the necessary two points from somewhere, then unspeccing the attribute nodes, respeccing them on the other side and then unspeccing the two Lord of the Dead points again to reallocate them where we unspecced them.

I will represent the available graph nodes that belong to neither A nor B as blue lines in my drawings, for example like this:
This is essentially the same example as the one in Lemma 5, however we only need 7 respecs instead of k+3: Unspec the 2 nodes on the right end of the black line, spec into the blue line, unspec the red line, allocate the green line, unspec 2 nodes from the left of the black line (assuming k≥2), connect the right end of the black line, unspec the 2 blue nodes and complete the black line again - conceptually the same as the skill tree example above.

Now for the thing that took me a while to figure out (and which I'm still not quiet satisfied with):

Lemma 6: An optimal solution may involve unspeccing the same node more than once (in the sense that a solution that unspecs a node more than once is not necessarily suboptimal).
Proof: Here is an example: http://i.imgur.com/07XYJgz.png
Bear with me as I walk you through it (Note: If you can come up with an easier example than this, please let me know. More importantly, if you are convinced I made a mistake, LET ME KNOW!).
This is conceptually the same as the "ladder" I showed previously. I have labelled the sections A-D and given names to some lines in orange (a, b, c, v, w). Numbers indicate the node counts, with those in parenthesis being irrelevant (but included for the sake of completeness).
Without making use of the blue lines, the best (and only) solution is respeccing the entire thing. And even if you managed to "flip" from red to green lines in the "A" section, everything in "B" above would still need to be respecced just the same (etc.). Hence, using the blue lines at each level is necessary for the optimal solution (and I will show that it is possible to do so, and further show that the optimal way can involve unspeccing some points in line v twice).

Overview:
We must start by "flipping" section A: B cannot be flipped without respeccing everything above (b is only available after flipping A), C's blue line requires 205 points but only 200 are available without disconnecting it from w. Flipping D before anything else is useless because we need those 200 points.
After this, we still cannot flip C, but flipping B gives us 10 extra points to work with that allow flipping C. Those 10 extra point are finally consumed by rebuilding D (flipped). To flip B, we have to unspec v and a that were used for flipping A, but we need v again in combination with c for flipping C in the optimal solution.

Let's start: To flip section A, we unspec the 200 points in section D, as well as 5 points from w (this leaves c ending in nowhere). We build v and a, then unspec the 10000 points on A's red line and allocate them into A's green line. We won't need section a anymore, so we can unspec the 5 points in line a right now.
Quick recap: Section A is flipped, v is allocated (all other blue lines are not), we have 5 spare points, section D is entirely unspecced and w is missing 5 points on the right. We can now look into flipping B using blue line b that became accessible, but we still cannot flip C. Respec points used = 10210

Now we have two choices for acquiring the points needed for b: Unspec 200 more points from w or unspec v.

If we unspec v (10410 respecs used), we build b and flip section B which gains us 10 extra points (13420). We unspec b (13625) and can now (re)build v+c while putting the 5 points we took away from w back into it. This allows flipping C (14625). We have 5 free points and everything except section D is complete, so we unspec v+c (14830), build D with the 210 points and are done.
If we instead take 200 points from w's right end (10410), we once again build b, flip section B for a 10 point gain (13420) and unspec b again (13625). w was missing 205 points so we put those back, complete v+c with 5 of the 10 extra points and flip C (14625). Unspec v+c (14830) for 5+205 free points that go into completing D.

Longest proof by example I ever gave, I think. I'm also fairly certain this example is way too complicated (I was originally going for showing that the only optimal solution may require a node to be respecced more than once, but I noticed errors in that while writing it down. Again, let me know if you can come up with an easier or more "powerful" example).

Lemma 6 is important because it directly impacts how (optimal) solutions can/must be represented. I would very much like to prove that there are cases where every optimal solution involves respeccing at least one node twice but I couldn't get there yet. It feels like it should just be a small step from what I have...

In particular, this would mean that we cannot represent the step sequence as some (repetition-less) permutation of nodes or assign each node a number/order for when it is respecced. I don't know if any such examples can even come up in the skill tree in practice, but it seems theoretically possible.

Respec Calculator #224

Description

Activity

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions