0

Возникла проблема.
Нужно обойти И/ИЛИ-дерево, при этом нужно запомнить все возможные варианты.
Одна линия - это И-вершина, две линии - это ИЛИ-вершина.
Не могу придумать как запомнить все возможные варианты.
Прикладываю изображения, что я имею ввиду под вариантами и само дерево. В какую структуру лучше их записывать и как лучше это организовать?
Заранее спасибо...

Само дерево,

Само дерево

результат одной из вариаций 1 вариант обхода

следующий вариант следующий вариант

последний результат который мы должны получить. последний результат

6
  • а какие операции делать надо?
    – pavel
    9 апр 2016 в 20:40
  • @pavel нужно просто составить все возможные варианты дерева. Вообще конечные узлы это объекты. У них будет поле цена и надо подсчитать общую сумму каждого варианта. После отсеять те что не входят в веденную цену и выбрать самый оптимальный вариант. Но проблема у меня в том как обойти исходное дерево и запомнить все эти возможные варианты.
    – WilpKron
    9 апр 2016 в 20:47
  • @Grundy большое спасибо!)
    – WilpKron
    9 апр 2016 в 20:59
  • Вы бы ещё объяснили, как выглядят входные данные. И как должны выглядеть выходные тоже можно добавить, кстати.
    – AivanF.
    9 апр 2016 в 21:29
  • @AivanF. Пишу всю задачу целиком. Задачу задали в универститете. Необходимо с помощью И/ИЛИ-дерева реализовать сбор автомобиля. Вершины Г,D,M это будет типа двигатель, корпус, шины. В чем заключается моя задача задача. Придумать логику для вершин и запомнить все варианты которые возможны их я уже привел. Насчет выходных данных: должно получится что-то вроде того что на изображении. Как я себе все представляю. Будет дерево. У узлов есть метка(И или ИЛИ) и может быть несколько потомков.
    – WilpKron
    10 апр 2016 в 5:31

1 ответ 1

2

Если я правильно понял что именно нужно.

Есть дерево, в вершине есть флаг и/или, нужно посчитать количество способов выбрать все листья из дерева.

Решение - простейшая динамика по дереву. В вершине будем хранить число способов построить поддерево.

Инициализая - в листьях 1.

Пересчет- рекурсия, а ходе которой вычисляются значения для всех потомков. Результат в вершине сумма (для или) или произведение (для и) всех значений в потомках.

Ответ на задачу - значение в корне.

Если вам нужны сами варианты то хранить не количество а список списков и аккуратно реализовать операции (сложение -просто соединить списки, умножение - все варианты выбрать по 1 списку из каждого поддерева)

2
  • Да. Ты правильно меня понял. Можешь пожалуйста если у тебя есть мысль как это сделать расписать алгоритм как будет происходить запись в список, если у меня будут только ветви Г и M.
    – WilpKron
    10 апр 2016 в 8:46
  • @WilpKron ну в лист дерева пишем его имя, тут всё просто, потом для вершины ИЛИ просто копируем по очереди всё из потомков, тоже вроде не сложно. Для И всё чуть хитрее, я бы сделал так: скопировал всё из 1 потомка в вершину,Tmp =Cur.getlist(); Cur.getlist().clear(); for (list : Tmp) for (list2 : Ptm) Cur.getlist().add(list + list2); Это пример на псевдокоде. Выполнять для каждого потомка по очереди.
    – pavel
    10 апр 2016 в 10:27

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.