Алгоритмы Rhizome

В Rhizome три типа проектов на одном графе. Алгоритмы поверх графа разные. На этой странице - два, что считают по графу что показать дальше: для LMS (подсказка следующей темы) и для трекера (критический путь до цели).

В вики алгоритма поверх графа нет: ученик читает в любом порядке, навигация - browser-style.

---

Алгоритм LMS - следующая тема

В режиме Обучение после каждого квиза ученик видит две кнопки: Дальше и Другая тема. Что именно подставится под каждой - решает скоринг-функция. Ниже её разбор по частям.

Формула

score(n) = isReady(n) ? α · betweenness(n) + β · unlockCount(n) + retryBonus(n) : 0

Константы:

α = 1     β = 2     FAILED_BONUS = 3     MISCONCEPTION_BONUS = 5

Если нода не «готова» к показу - её скор 0, дальше она не попадёт. Готовые ноды сортируются по скору, наверху - следующая.

isReady - готова ли нода

Нода «готова», если все её прямые пререквизиты в статусе mastered. Не «не not-started», а именно mastered. Это важно: failed и особенно misconception пререквизит блокируют downstream.

function isReady(n) {
  const prereqs = edges.filter(e => e.directed && e.target === n);
  return prereqs.every(p => statuses[p.source] === 'mastered');
}

betweenness - центральность ноды

Это классическая graph-метрика - сколько кратчайших путей в графе проходит через ноду. Ноды-хабы получают высокий betweenness, листья - почти нулевой. Считается один раз при загрузке графа, результат - Map<nodeId, number>.

Зачем: при прочих равных предпочесть «магистральную» тему частной. Магистраль откроет больше путей, чем тупиковая.

unlockCount - что мы разблокируем

Это гипотетический счётчик: «если бы я прошёл ноду n прямо сейчас, сколько not-started нод стало бы готовыми?»

function unlockCount(n) {
  const hypothetical = { ...statuses, [n]: 'mastered' };
  return nodes.filter(other =>
    other !== n &&
    statuses[other] === 'not-started' &&
    !isReady(other, statuses) &&         // сейчас не готова
    isReady(other, hypothetical)         // станет готовой если n замастерим
  ).length;
}

unlockCount весит вдвое сильнее центральности (β = 2 vs α = 1). Логика: лучше двигать ученика по фронту графа - чтобы открывались новые темы - чем подсовывать «важную, но изолированную» ноду.

retryBonus - чтобы заваленное всплывало

Если нода уже failed или misconception, к её скору добавляется бонус: +3 за failed, +5 за misconception. Это значит, что заваленные темы стабильно поднимаются над not-started соседями того же веса.

misconception весит больше, потому что он диагностический - ученик не просто ошибся, а попал в ловушку, которую автор поставил против конкретного заблуждения. Разбираться нужно явно.

Две кнопки - один скор

• «Дальше» - сканирует только прямых потомков текущей ноды (directed исходящие рёбра), берёт лучшего по скору. Если потомков нет или у всех скор 0 - откат на «Другую тему».
• «Другая тема» - сканирует весь граф, берёт лучшего глобально.

Стандартный сценарий: правильно ответил - «Дальше» ведёт по веточке. Ошибся - заваленная нода получает retryBonus и через несколько правильных ответов на других ветках всплывает обратно через «Другую тему».

Повторения - SM-2-lite

Отдельная панель, не связанная с основной навигацией. Кнопка «Повторения» в action-bar показывает счётчик due-нод и открывает панель повторения.

Алгоритм - облегчённая SM-2:

интервал = min(1 день · 2^consecutiveCorrect, 180 дней)

После того как нода стала mastered:

• через 1 день - первое повторение
• успех -> через 2 дня
• успех -> через 4
• 8, 16, 32, 64, 128, 180, 180, 180 ...

Ошибка в повторении сбрасывает consecutiveCorrect в 0 - но статус остаётся mastered. Логика: «забыл, не выучил заново». Следующее повторение через 1 день.

180 дней - потолок: дальше уже бессмысленно дробить, лучше признать «помнит и помнит».

Зачем это вообще

Цель - чтобы ученик не задумывался «что учить дальше». В обычной LMS это кнопка «Next lesson» в плейлисте, и порядок задаёт автор. В графовой LMS у ученика всегда есть выбор по фронту, и алгоритм просто ставит самый полезный из готовых наверх. Если ученик не согласен - есть «Другая тема», которая берёт глобального лучшего.

Алгоритм простой - три слагаемых, шесть строк кода, никакого machine learning. Этого хватает: на учебных графах из 30 - 200 нод видно, что ученика ведёт по фронту графа без застревания.

---

Алгоритм трекера - критический путь

В трекер-проекте у задачи есть статус, дедлайн и сложность 1-5. Алгоритм находит критический путь до каждой активной цели и подсвечивает рёбра на нём.

Веса нод

isActive(n) = n.status ∉ {Готово, Отменена}
weight(n)   = isActive(n) ? (n.complexity ?? 1) : 0

Готово и Отменена ноды весят 0 - то есть «бесплатно» проходятся в цепочке. Это даёт правильное поведение когда часть пути уже сделана: критический путь автоматически пересчитывается на оставшийся хвост.

Если сложность не задана, считается за 1 - то есть длина пути меряется в задачах. Если задана хоть на одной ноде - суммируется по сложности.

Longest path в DAG

Один проход в топологическом порядке:

longestTo[n]   = max(longestTo[p] + weight(p)) для всех предков p
predOnPath[n]  = p, давший максимум

Сложность - O(V + E). На графе из 200 задач считается за миллисекунды на каждое изменение.

Трассировка пути

Для каждой ноды g с isGoal && isActive(g) идём назад по predOnPath[g], пока не упрёмся в корень или в Готово ноду. Рёбра на трассе складываем в criticalEdges: Set<EdgeId>. Объединение по всем целям - итоговый набор рёбер критического пути.

Если у цели несколько входящих цепочек разной длины - в путь попадает самая длинная. Альтернативные остаются обычным цветом.

Срочность дедлайна

Независимый сигнал, с критическим путём не смешивается:

daysLeft = (deadline - now) / 86400000

  daysLeft < 0   → overdue   (красный + пунктирная рамка)
  daysLeft < 3   → urgent    (красный)
  daysLeft < 7   → soon      (жёлтый)
  иначе          → normal    (серый)

Активные цели и «что дальше»

В сайдбаре - список активных целей, отсортированных по daysLeft (ближайшие сверху), потом по remainingComplexity (почти готовые сверху). Цель попадает в список если она isGoal и в её предках есть хоть одна неготовая нода.

«Что дальше» - первая нода на критическом пути с isActive && все предки Готово. Один проход по criticalEdges, выдаёт одну рекомендацию. Если такой ноды нет (например, фронт работы - сразу несколько параллельных) - подсказка не показывается.

Зачем это вообще

В привычном трекере задач (kanban, list, gantt) альтернативные пути к одной цели либо не выражены явно, либо выражены через ветвление досок. Граф позволяет выразить их как часть структуры - две входящие цепочки в одну ноду-цель. Алгоритм longest path сам выбирает самую длинную из активных, и при изменении статусов перестраивается. Видно «что реально двигает срок до цели» без лишней математики.