0

I want to improve the review algorithm of an addon that I wrote for anki for creating flash cards from concept maps. The addon asks questions following the structure of the concept map. This screenshot shows an example of a concept map that is supposed to be imported. The blue boxes contain hyperlinks, if they were grafically displayed, the map would look like this

Relationships between concepts serve as questions while concepts serve as answers. During review, the learner is supposed to answer questions on a higher level in the hierarchy first, followed by questions on lower levels in the hierarchy. Questions are only asked when they are due (which is determined by anki with a spaced retrieval algorithm).

Given the example map, a possible sequence of questions could be "investigates" --> "modulated by" --> "splits up" (if "example" is not due) --> "stands for" --> "completely unrelated animation". The algorithm used in the addon is very simple and takes pretty long when a question has many crosslinks to other questions. I figured it would be nice to internally represent the concept map as a graph during review and then use some algorithm to quickly find the next due question.

I found this post on representing graphs in python which sounds quite promising. I think I could represent the concept map with something similar. I stumbled across Dijkstra's algorithm that is supposed to solve shortest path problems but it doesn't solve my problem since my review order needs to prefer going downwards in the hierarchy over going upwards. For example, if the current question is "requires" and further down "pronounciation" is due, "pronounciation" has to be preferred over "modulated by" even though the path length to pronounciation is 3 and the path length to "modulated by" is only one.

How do I write an algorithm that always prefers going downwards and while doing so finds the closest due question in my concept map?

Lukas Loos
  • 159
  • 1
  • 5
  • It seems that you have a *tree*, which may help a lot for this problem. Also, it appears that the edge weights are all 1, so it may be a straightforward tree algorithm to check if any children are present, and if not check for a parent. – AndyG Dec 19 '19 at 19:08
  • I'm sorry, from the screenshot it looks like a tree but actually all the blue boxes are hyperlinks to other parts of the tree which serve as crosslinks so effectively the resulting concept map is [a graph] (https://i.stack.imgur.com/oysGb.png) – Lukas Loos Dec 19 '19 at 19:25
  • How do you define "downwards" then? Your graph representation must reflect this. Directed edges appear to be inadequate because you will also need to ocassionally traverse "upwards" it seems, so I recommend each node has two lists, "up" nodes and "down" nodes. – AndyG Dec 19 '19 at 19:28
  • That's what I had in mind too, i just saw this article: https://en.wikipedia.org/wiki/Minimum_spanning_tree maybe using weights for "up" nodes that are bigger than all other paths might solve the problem? – Lukas Loos Dec 19 '19 at 19:30
  • Using weights is a great idea! So long as you can be very confident in how they get assigned. – AndyG Dec 19 '19 at 19:35
  • A minimum spanning tree will not guarantee shortest paths, only that the overall weight of the resulting tree is minimal (and there may be multiple unique ones) – AndyG Dec 19 '19 at 19:35
  • I came up with this: first create a graph where all nodes only have edges to their children, where every edge gets a weight of 1 and then go through all nodes again and add another edge to their parent with the weight being the max pathlength to any node further down + 1 However it seems a bit unefficent, is there a more efficient way to do this? – Lukas Loos Dec 19 '19 at 19:47

0 Answers0