Подання дерев на мові Python, Блог про шифрування

Тепер ми готові до конструювання деревоподібних програм Python. Дерево складається з вузлів, які залежно від асоційованих із нею функцій може мати дочірні вузли. Деякі вузли повертають передані програмі параметри, інші – константи, але найцікавішими є вузли, що повертають результат якоїсь операції над своїми дочірніми вузлами.

Створіть новий файл gp.py і в ньому чотири класи - fwrapper, node,

paramnode і constnode:

class fwrapper: def init (self,function,childcount,name):

def ____ init (self, fw, children):

results=[n.evaluate(inp) for n in self.children] return self.function(results)

class paramnode: def __init__(self, idx): self.idx=idx

def evaluate(self,inp): return inp[self.idx]

class constnode: def __init__(self,v): self.v=v

def evaluate(self,inp): return self.v

Ці класи призначені для таких цілей:

Обертання для функцій, які будуть знаходитися у вузлах, що представляють функції. Його члени – ім'я функції, сама функція та кількість параметрів, що приймаються.

Клас функціональних вузлів (нащадків, що мають). Ініціалізується екземпляром класу fwrapper. Метод evaluate обчислює значення дочірніх вузлів та передає їх представленій даним вузлом функції як параметри.

Клас вузлів, які просто повертають один із переданих програмі параметрів. Його метод evaluate повертає параметр, що відповідає значенню idx.

Вузли, що повертають константи. Метод evaluate просто повертає значення, яким екземпляр був ініціалізований.

Потрібні також функції, які будуть викликатись при відвідуванні вузлів. Такі функції ви повинні будете написати та передати

разом з ім'ямта лічильником параметрів конструктору класу fwrapper.

Додайте до файлу gp.py наступний перелік функцій:

addw=fwrapper(lambda l:l[0]+l[1],2,'add') subw=fwrapper(lambda l:l[0]-l[1],2,'subtract') mulw=fwrapper( lambda l:l[0]*l[1],2,'multiply')

if l[0]>0: return l[1] else: return l[2] ifw=fwrapper(iffunc,3,’if’)

if l[0]>l[1]: return 1 else: return 0 gtw=fwrapper(isgreater,2,'isgreater')

Прості функції типу add та subtract можна вбудувати за допомогою лямбда-виразів. Для решти функцію доведеться написати в окремому блоці. У будь-якому випадку функція обертається в екземпляр класу fwrapper разом зі своїм ім'ям та числом параметрів. В останньому рядку створюється список усіх функцій, щоб згодом можна було вибирати елементи випадковим чином.

Побудова та обчислення дерев

Тепер за допомогою класу node можна збудувати дерево програми, зображене на рис. 11.2. Додайте у файл gp.py функцію exampletree:

def exampletree( ): return node(ifw,[

Запустіть інтерпретатор Python та протестуйте програму: >>> import gp

Вона успішно виконує самі дії, як і еквівалентна їй функція. Таким чином, ми побудували мінімацію для представлення деревоподібних програм і написали для нього інтерпретатор на Python. Цю мову можна легко розширити за рахунок додаткових типів вузлів. Він стане основою для знайомства з генетичним програмуванням. Спробуйте ще кілька деревоподібних програм і переконайтеся, що ви розумієте, як вони працюють.

Створіть у класі node метод display, який виводить уявлення дерева у вигляді рядка:

def display(self,indent=0): print (' '*indent)+self.name для c в self.children: c.display(indent+1)

Необхідно також додати метод display в клас paramnode, де він буде просто друкувати індекс параметра, що повертається:

print '%sp%d' % ( ' *indent,self.idx)

і в клас constnode:

print '%s%d' % ( ' *indent,self.v)

Скористайтеся цими методами для друку дерева: >>> reload(gp)

Ви помітили схожість із поданням дерев рішень. Раніше було також показано, як відобразити дерева у графічному вигляді, зручнішому для сприйняття. Якщо хочете, можете скористатися тією самою ідеєю для графічного представлення деревоподібних програм.

---