LINUX.ORG.RU

Алгоритм need help

 alghorithm, ,


0

1

Дерево состоит из узлов вида

Node(MD, parent, next, depends)
md - некоторые данные, суть их не важна
parent - предок (Node)
childs - список потомков (Node list)
depends - список Node
Есть функция P(MD1, MD2), которая возвращает true или false. А также функция M(MD1, MD2), которая модифицирует MD1 таким образом, что P(MD1, MD2) = true. Если в Node1.depends есть Node2, то в Node2.depends будет Node1. Для простоты описания можно считать, что P(Node) = P(Node.MD)

Желаемый результат для каждой Node:

  • P(Node, Node.parent)=true
  • P(Node, Node.childs)=true; 0<i<length(Node.childs)
  • P(Node, Node.depends)=true; 0<i<length(Node.childs)
  • минимизировать количество случаев, когда не соблюдаются условия выше

Доп. информация:

  • M(Node, Node.parent) может изменить результат P(Node, Node.childs) либо для всех i, либо не для одного.
  • M(Node, Node.childs) может изменить результат P(Node, Node.parent), а может не изменить

Кто силён в деревьях, помогите сделать алгоритм, который будет гарантировано сводить нежелательные результаты для каждой Node к минимуму.

Там где есть описание i, имеется в виду выборка из списка, к примеру childs(i), \[i\] кушается лортегами

pseudo-cat ★★★
() автор топика
Последнее исправление: pseudo-cat (всего исправлений: 1)

P(MD1, MD2), которая возвращает true или false

Если в Node1.depends есть Node2, то в Node2.depends будет Node1

Желаемый результат <skip /> P(Node, Node.depends)=true; 0<i<length(Node.childs)

на первый взгляд последнее либо лишнее, либо исключающее

а вообще всё это похоже на извращённое дерево поиска по ключу P. Хотя это не так иначе такое странной задачи с изменением MD (данных в узле?) не возникло бы.

Без знаний принципа организации дерева, свойств P() и M() общего алгоритма «пофиксить данные узлов» скорее нет

зы. зря вот вы пытаетесь изложить конкретную проблему в общем виде, да и ещё академичным языком. Чем кокретнее вопрос тем больше вероятность получить ответ

MKuznetsov ★★★★★
()
Ответ на: комментарий от MKuznetsov

Желаемый результат <skip /> P(Node, Node.depends)=true; 0<i<length(Node.childs)

ошибся, должно быть:

P(Node, Node.depends[i])=true; 0<i<length(Node.depends)

вообще depends нужно чтобы перейти от неориентированного графа к дереву, то есть, к примеру, есть граф вида:

a-b-c
 \-/
получается дерево
a-b-c(a)
ничего толком не меняется, но мне почему-то так легче было представить задачу.

функцию M(Node1.MD, Node2.MD) можно представить как ф-цию изменяющую Node1.MD в соотв с Node2.MD, причём в отдельных случаях она может не нарушать зависимости P(Node1.MD, Node1.childs[i]) и P(Node1.MD, Node1.depends[i]). Т.о. представьте дерево вида

a[i]-a[i+1]-...-a[n]
P(m.MD,n.MD) = true, для i<=m,n<=n кроме m=i+r, n=i+r+1 
тогда решением будет:
l = i+r+1; t = i+r
1. M(a[l].MD, a[t].MD)
2. если l<=n, 
     тo l <- l+1, t <- t+1, переходим в шаг 3.
     иначе переходим в шаг 4.
3. если P(a[l].MD, a[t].MD) = true,
     то переходим в шаг 4.
     иначе переходим в шаг 1.
4. ветвь решена.
это один из возможных путей решения дерева, построенного по графу без циклов, если дерево построено по графу с циклами(в дереве есть узлы с не пустыми списками depends), то решений может быть больше и нужно найти хоть одно.

Я на всякий случай напишу описание подхода, накоденного мной, он не во всех случаях способен найти решение когда оно есть, именно поэтому я прошу подсказать что нибудь полезное.
Я помечаю пройденные узлы и ставлю им счетчик количества применений ф-ции P, где они стоят первым аргументом. Используя прямой проход по дереву, я его выравниваю от корня к листьям - P(parent, child)!=true then M(child, parent). Когда встречается узел A с не пустым списком помеченных пройденными depends, то если в depends один узел и его счетчик применений M больше счетчика A, то M(A, depends[[1]]) и начинается обратный проход по дереву(A->A.parent), после которого продолжается прямой проход с этой точки, иначе для всех depends: M(depends[i], A) и продолжаю прямой проход по дереву.

pseudo-cat ★★★
() автор топика
Ответ на: комментарий от anonymous

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

pseudo-cat ★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.