TAU писал(а):
Можно здесь алгоритм описать? В двух словах?
DRAKON Editor (начиная с версии 1.9) генерирует исходный код из ДРАКОН-схем следующим образом:Создание графа алгоритмаИз графических элементов схемы выделяется абстрактный граф алгоритма.
Последовательные иконы "действие" объединяются в одну.
Веточные циклы превращаются в обычные циклы со стрелкой вверх.
Циклы "для" разворачиваются в обычные циклы со стрелкой вверх.
Переключатели преобразуются в развилки.
Производится поиск паттернов логического программирования "И" и "ИЛИ" и их упрощение.
Код:
|
A----
| |
B----|
| |
C D
| |
|----
|
становится
|
A and B--
| |
C D
| |
|--------
|
На данном этапе в графе есть только два типа узлов: действие и развилка.
Подготовка графаГраф сканируется на наличие циклов. Рёбра, ведущие вверх ("стрелки"), получают особую метку.
Вставляются "технические" узлы: начало и конец алгоритма, начала циклов.
Граф "нормализуется":
происходит проход по графу при котором игнорируются "стрелки вверх"
ветвление приводится к стандартному процедурному виду if-else
если надо, иконы копируются
Код:
|
A----
| |
| C
B----|
| |
D E
|----|
|
становится
|
A-----
| |
| C
B--| |
| | |
D E E
| | |
|------
|
ПоискЕсли б не было циклов, поиск был бы не нужен. Но циклы есть.
Общая задача поиска: привести циклы к следующему виду:
Код:
while true:
do something
if must exit:
break
if must continue
continue
Результатом процедуры поиска является иерархическая структура (дерево) алгоритма, в которой
есть две основные конструкции структурного программирования: if-else и while.
Места, куда надо вставить while true известны - это иконы, на которые указывают стрелки вверх.
Места, куда надо вставить continue, тоже найти просто: это иконы, из которых исходит стрелка вверх.
Таким образом, конкретной задачей поиска является нахождение мест, куда надо ставить break.
Пространство поиска: множество всех возможных деревьев алгоритмов.
Начало поиска: пустое дерево.
В процессе поиска в дерево добавляются узлы из графа алгоритма.
Поиск завершён, когда все узлы из графа были добавлены в дерево.
Поиск завершён успешно, когда в построенном дереве нет незаконченных елементов if и while.
Принципиальный вопрос при добавлении узла из графа в дерево: "а можно ли сюда сунуть break?".
Ветвление поиска (т.е. поиск следующих возможных состояний из текущего) происходит за счёт
выбора очерёдности добавления узлов, а также добавления или не добавления break.
Поиск в глубину зарекомендовал себя хорошо, A* - плохо.
Не все схемы можно преобразовать к структурному виду. Например, преобразованию не поддаются следующие:
- Выход из вложенного цикла ДЛЯ.
- Циклы, в которые есть более двух входов (таковые, кстати, запрещены правилами ДРАКОНА).
- Циклы, в которых есть возврат не к началу, а в середину цикла.
Данный алгоритм имеет свойство взрываться, так что я ограничиваю количество итераций.
Если за 500 шагов нет результата, скорее всего (исходя их опыта), его не будет и через 5000.
Если поиск не удался, генерируем код обычным образом (вечный цикл и перебор икон).