Найти - Пользователи
Полная версия: Помогите пожалуйста написать код для метода дерева решений
Начало » Python для новичков » Помогите пожалуйста написать код для метода дерева решений
1 2
JbanS
Мне упростили задачу до минимума, но только если успею сделать сегодня за ночь. Помогите пожалуйста сделать, ато даже это что-то не получается.

Нужно написать “И / ИЛИ” дерево. Можно уже готовое, с любыми значениями. Для умеющих, это минут 5, но я не могу найти на GitHub именно И/ИЛИ дерево. Повторюсь, главное, оно должно быть именно “И / ИЛИ”!
Основная цель “Нахождение всех покрытий цели подцелями на основе и/или дерева”
А именно, написать алгоритм, который ПЕРЕБОРОМ, пройдет по всем “ветвям” и выдаст все возможные варианты последовательности. Я набросал схему, какое примерно нужно дерево.
И алгоритм должен вывести:
Value1, Value2, Value4, Value5, Value8, Value9, Value10
Value1, Value2, Value4, Value5, Value8, Value9, Value11
Value1, Value3, Value6, Value7, Value12, Value13
Именно для этого дерева.

Ну то есть, для Value1 нужно Value2 ИЛИ Value3. Для Value2 нужно Value4 и Value5, для Value4 нужно Value8 и Value9. Для Value5 нужно Value10 ИЛИ Value11
Получаем:
Value1, Value2, Value4, Value5, Value8, Value9, Value10
ИЛИ
Value1, Value2, Value4, Value5, Value8, Value9, Value11

Надеюсь понятно написал.
Такое дерево должно быть легким, а алгоритм ПЕРЕБОРА, еще легче. Помогите пожалуйста.
PEHDOM
JbanS вы бы хоть картинку какую выложили… а то по вашему описанию хрен что поймешь.
А такое дерево в самом просто варианте пишется с помощью списка списков, поскольку у вас нет вменяемой картинки то вот простенький пример:



 class Node():
    "Generic tree node."
    def __init__(self, name='root', parent=None):
        self.name = name
        self.children = []
        if parent:
            parent.add_child(self)
    def __repr__(self):
        return self.name
    def add_child(self, node):
        assert isinstance(node, Node)
        self.children.append(node)
    def add_parent(self, node):
        assert isinstance(node, Node)
        node.add_child(self)
    def find_node(self, node_name ,lst= None):
        if lst:
            res = lst[:]
            res.append(self.name)
        else:
            res = [self.name,]
        if self.children:
            for child in self.children:
                 child.find_node(node_name, res)
        else:
            if res[-1]== node_name:
                print(res)
    def get_tree(self):
        res = [self, ]
        for child in self.children:
            res.append(child.get_tree())
        return res
root = Node('*')
one = Node('1', root)
two = Node('2', root)
three = Node('3',root)
four = Node('4', three)
five = Node('5', three)
four.add_parent(two)
print(root.get_tree)
root.find_node('4')
>>> 
[*, [1], [2, [4]], [3, [4], [5]]]
['*', '2', '4']
['*', '3', '4']
>>> 
py.user.next
Скорее всего, нужно два класса Tree и Node. У каждого класса свой набор методов для работы с соответствующими объектами (методы для работы с деревом не равны методам для работы с узлом). И вот Tree содержит корневой узел, к которому можно присоединять другие узлы. Также Tree имеет метод для работы со всем деревом, начиная от корня. А каждый узел имеет метод для заполнения себя значением и метод для присоединения к себе дочерних узлов в каком-то порядке.

Когда эта динамическая структура готова, можно сделать функцию для ввода данных и добавления этих данных в пустое дерево через его метод. Также можно сделать функцию для обхода дерева любым способом, который нужен.

А если всё сразу лепить без подготовки структуры, то, конечно, не будет ничего получатся, так как свалка из операторов даст о себе знать.
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Powered by DjangoBB