Алгоритмы поиска решения на и-или-дереве

Изоморфные графы могут быть получены один из другого путем перенумерации их вершин. Очевидно, что изоморфизм есть отношение эквивалентности на графах. Если изоморфные преобразования проводятся с графом, заданным матрицей смежности, то они сводятся к перестановке местами соответствующих строк и столбцов. Известно, что в общем случае для определения изоморфизма графов необходимо сделать п сравнений или перестановок строк и столбцов матрицы, что для графов с л>30 не под силу даже современной ЭВМ. Поэтому необходимо применить тот или иной эвристический алгоритм поиска по дереву решений. [c.211]

Воспроизведите алгоритм поиска решения на и-илы-дереве. [c.411]

Оптимальное решение находят путем определения экстремального значения функции (44) для всего подмножества ребер, исходящих из каждой вершины. Алгоритм и программа для ЭВМ модели Минск-22 разработаны с учетом одновременного построения и просчета каждой цепи дерева в определенной последовательности. В них четко выявляются три основные составные части формирование цепей дерева, определение технологических показателей переходов и поиск оптимального сочетания переходов. [c.76]

При синтезе решений очень важным является наличие правила остановки при поиске лучших вариантов. В противном случае поиск при большом дереве решений (оно может включать тысячи вершин) будет идти неприемлемо долго. Обычно в итеративных вычислительных процессах правило остановки формируется на основе критерия устойчивости решения. В нашем случае это правило чаще всего неприменимо, так как в проектировании не всегда возможна проверка сходимости алгоритма, хотя его эффективность может быть доказана. Эффективным будем считать такое правило, которое позволяет прекратить итерационный процесс через конечное число итераций. [c.440]

Энциклопедия по машиностроению XXL

Оборудование, материаловедение, механика и ...