{"action":"created","issue":{"url":"https://api.github.com/repos/EmmittJ/PoESkillTree/issues/98","labels_url":"https://api.github.com/repos/EmmittJ/PoESkillTree/issues/98/labels{/name}","comments_url":"https://api.github.com/repos/EmmittJ/PoESkillTree/issues/98/comments","events_url":"https://api.github.com/repos/EmmittJ/PoESkillTree/issues/98/events","html_url":"https://github.com/EmmittJ/PoESkillTree/issues/98","id":54226951,"number":98,"title":"\"Skill highlighted nodes\" is (too) greedy","user":{"login":"MLanghof","id":6524684,"avatar_url":"https://avatars.githubusercontent.com/u/6524684?v=3","gravatar_id":"","url":"https://api.github.com/users/MLanghof","html_url":"https://github.com/MLanghof","followers_url":"https://api.github.com/users/MLanghof/followers","following_url":"https://api.github.com/users/MLanghof/following{/other_user}","gists_url":"https://api.github.com/users/MLanghof/gists{/gist_id}","starred_url":"https://api.github.com/users/MLanghof/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MLanghof/subscriptions","organizations_url":"https://api.github.com/users/MLanghof/orgs","repos_url":"https://api.github.com/users/MLanghof/repos","events_url":"https://api.github.com/users/MLanghof/events{/privacy}","received_events_url":"https://api.github.com/users/MLanghof/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":43,"created_at":"2015-01-13T18:11:22Z","updated_at":"2015-04-05T12:34:35Z","closed_at":null,"body":"The current algorithm just greedily finds the closest target node and connects to it, then repeats. This way, it will never introduce Steiner points and will generally fail to find an optimal solution.\r\n\r\nExample: I highlighted \"Coldhearted Calculation\" and \"Void Barrier\" (e.g. with regex \"Void Barrier|Coldhearted\") and have an empty Shadow tree. If I click on \"Skill highlighted nodes\", the current algorithm will first grab Coldhearted Calculation (7 points to grab vs 9 for void barrier) and then Void Barrier, resulting in [this tree](http://www.pathofexile.com/passive-skill-tree/AAAAAgYBRXwsRjy9UEKiLg5IXfLjhDY9bWzndNsaEHu-Og==) with 14 points.\r\n[This tree](http://www.pathofexile.com/passive-skill-tree/AAAAAgYBDkhd8uOENj1tbOd02xoQe746D6uzDiHAsNg=) uses one point less though.\r\n\r\nThe problem of connecting a set of target nodes within a tree (with minimal point investment) is known as the [Steiner Tree problem](http://en.wikipedia.org/wiki/Steiner_tree_problem). It is NP-hard, so it will be quite difficult to devise an algorithm that finds the optimum reliably and within reasonable time for this kind of app.\r\nI'm working on something for this, but I just wanted to create this issue so others who wonder if the current algorithm is optimal can learn about it. And possibly also to let others know someone is working on it."},"comment":{"url":"https://api.github.com/repos/EmmittJ/PoESkillTree/issues/comments/89763243","html_url":"https://github.com/EmmittJ/PoESkillTree/issues/98#issuecomment-89763243","issue_url":"https://api.github.com/repos/EmmittJ/PoESkillTree/issues/98","id":89763243,"user":{"login":"MLanghof","id":6524684,"avatar_url":"https://avatars.githubusercontent.com/u/6524684?v=3","gravatar_id":"","url":"https://api.github.com/users/MLanghof","html_url":"https://github.com/MLanghof","followers_url":"https://api.github.com/users/MLanghof/followers","following_url":"https://api.github.com/users/MLanghof/following{/other_user}","gists_url":"https://api.github.com/users/MLanghof/gists{/gist_id}","starred_url":"https://api.github.com/users/MLanghof/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MLanghof/subscriptions","organizations_url":"https://api.github.com/users/MLanghof/orgs","repos_url":"https://api.github.com/users/MLanghof/repos","events_url":"https://api.github.com/users/MLanghof/events{/privacy}","received_events_url":"https://api.github.com/users/MLanghof/received_events","type":"User","site_admin":false},"created_at":"2015-04-05T12:34:35Z","updated_at":"2015-04-05T12:34:35Z","body":"Ok, I feel like I'm closing in on being done. I have a nice little UI window now that keeps the user updated, I'm currently abusing the \"compare trees\" visual for showing what the algorithm's current best solution is (really happy with that) and the convergence speed is nice.\r\n\r\nI decided to combine the genetic algorithm (multiple individuals that exchange dna (= solution) fragments, weaker individuals are purged every iteration) with a simulated annealing for the mutation (accepting a mutation to a worse state becomes less likely with the progressively decreasing \"temperature\").\r\nUsual ~100 point trees take a slight while (depending on your hardware), but the results so far seem great (I'll make sure to get a test build up soon so you guys can challenge it with your trees).\r\n\r\nI still have to do some cleaning up and stuff, but I think the bulk is done. Although I already have plans..."}}