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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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