{"action":"created","issue":{"url":"https://api.github.com/repos/RubenVerborgh/Computing-Interesting-Paths/issues/2","repository_url":"https://api.github.com/repos/RubenVerborgh/Computing-Interesting-Paths","labels_url":"https://api.github.com/repos/RubenVerborgh/Computing-Interesting-Paths/issues/2/labels{/name}","comments_url":"https://api.github.com/repos/RubenVerborgh/Computing-Interesting-Paths/issues/2/comments","events_url":"https://api.github.com/repos/RubenVerborgh/Computing-Interesting-Paths/issues/2/events","html_url":"https://github.com/RubenVerborgh/Computing-Interesting-Paths/issues/2","id":148830456,"number":2,"title":"Doubts regarding A* heuristic","user":{"login":"DieterDePaepe","id":3605663,"avatar_url":"https://avatars.githubusercontent.com/u/3605663?v=3","gravatar_id":"","url":"https://api.github.com/users/DieterDePaepe","html_url":"https://github.com/DieterDePaepe","followers_url":"https://api.github.com/users/DieterDePaepe/followers","following_url":"https://api.github.com/users/DieterDePaepe/following{/other_user}","gists_url":"https://api.github.com/users/DieterDePaepe/gists{/gist_id}","starred_url":"https://api.github.com/users/DieterDePaepe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/DieterDePaepe/subscriptions","organizations_url":"https://api.github.com/users/DieterDePaepe/orgs","repos_url":"https://api.github.com/users/DieterDePaepe/repos","events_url":"https://api.github.com/users/DieterDePaepe/events{/privacy}","received_events_url":"https://api.github.com/users/DieterDePaepe/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2016-04-16T08:18:44Z","updated_at":"2016-04-16T21:54:49Z","closed_at":null,"body":"On slide 22, it is mentioned that the Jaccard distance is used as a heuristic.\r\n\r\nGiven 2 nodes `V` and `U`, where `V` has 1000 different predicates connected to it, and `U` has 1 unique predicate connected to it. The heuristic would estimate:\r\n\r\n    goalDistance = 1 - |1| / |1000| = 0.999\r\n\r\nHowever, the actual weight between `V` and `U` is based on the occurrent of the connecting predicate in the remainder of the graph. As such, the heuristic might overestimate the actual distance. Although this is technically allowed in A*, it might result in paths that are longer than the actual shortest path."},"comment":{"url":"https://api.github.com/repos/RubenVerborgh/Computing-Interesting-Paths/issues/comments/210912295","html_url":"https://github.com/RubenVerborgh/Computing-Interesting-Paths/issues/2#issuecomment-210912295","issue_url":"https://api.github.com/repos/RubenVerborgh/Computing-Interesting-Paths/issues/2","id":210912295,"user":{"login":"RubenVerborgh","id":675313,"avatar_url":"https://avatars.githubusercontent.com/u/675313?v=3","gravatar_id":"","url":"https://api.github.com/users/RubenVerborgh","html_url":"https://github.com/RubenVerborgh","followers_url":"https://api.github.com/users/RubenVerborgh/followers","following_url":"https://api.github.com/users/RubenVerborgh/following{/other_user}","gists_url":"https://api.github.com/users/RubenVerborgh/gists{/gist_id}","starred_url":"https://api.github.com/users/RubenVerborgh/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/RubenVerborgh/subscriptions","organizations_url":"https://api.github.com/users/RubenVerborgh/orgs","repos_url":"https://api.github.com/users/RubenVerborgh/repos","events_url":"https://api.github.com/users/RubenVerborgh/events{/privacy}","received_events_url":"https://api.github.com/users/RubenVerborgh/received_events","type":"User","site_admin":false},"created_at":"2016-04-16T21:54:49Z","updated_at":"2016-04-16T21:54:49Z","body":"Overestimation is fine in this case; having a more interesting path is more important than having the shortest path. Special here is that the weight function and the heuristic have conflicting interests: the weight function wants the path to be as interesting (= difficult) as possible, whereas the heuristic wants to get things done fast."}}