Выбор - вершина
Cтраница 4
Оказывается, дело здесь в том, что в следующих друг за другом итерациях помеченные вершины включались нами в множество просмотренных с использованием разных правил. Назовем процедуру помечивания состоятельной, если всякий раз, когда имеется некоторое множество помеченных, но не просмотренных вершин, выбор вершин для отнесения их к множеству просмотренных осуществляется по одному и тому же правилу. Таккер ( 1977) доказал, что если состоятельная процедура помечивания применяется вместе с потоковым алгоритмом Форда - Фалкерсона, то алгоритм завершает работу и приводит к максимальному потоку. Фалкерсоном сформулирована ( но не опубликована) следующая гипотеза. [46]
Для этого изменим ориентацию всех дуг дерева на противоположную и пронумеруем вершины, как в случае выходящего дерева. Таблица, представляющая входящее дерево, отличается от таблицы, представляющей выходящее дерево, второй и четвертой строкой. Здесь вторая строка - номер прямого потомка, а четвертая строка - минимальный п максимальный номера непосредственных предшественников. Выбор опорной вершины осуществляется по последней непустой кл етке таблицы, представляющей текущий граф: содержимое соответствующей клетки второй строки есть номер опорной вершины. Реализация процедуры преобразования входящего дерева в ш-цепь также требует выполнения не более O ( HI log n операций. [47]
По едини дам, стоящим в этой строке, получаем номера ребер, составляющих цикл. По номерам ребер последовательно просматриваются строки матрицы инцидентности, столбцы которой определяют номера вершин. И только после этого мы получаем координаты вершин для определения топологии соединения вершин, задающих область пересечения двух граней. Необходимо иметь в виду, что в матрице циклов указываются все ребра, составляющие цикл, но порядок и направление обхода цикла не определены и, следовательно, обращение к номерам вершин не будет соответствовать их порядку в цикле. Также возникает неоднозначность в выборе вершин, через которые проходит интересующее нас ребро. Следовательно, применение матричного представления данных о топологии соединения вершин как НФ, так и СФ приводит к значительным трудностям при программировании, нерациональному использованию памяти ЭВМ, а также к длинной информационной цепочке для получения координат вершин. [48]
Важность эмпирических работ в качестве источника общих идей в исследованиях по ИИ можно ясно продемонстрировать, проследив историю создания многочисленных программ для решения задач, в которой центральную роль играли две эти идеи: поиск с выбором первыми самых лучших кандидатов и анализ средств и целей. Шахматные программы как правило были связаны ( по соображениям экономики памяти) с поиском в глубину, дополненным после 1958 г. мощной процедурой альфа-бета усечения. Похоже, что каждый из этих методов неоднократно изобретался заново, и трудно найти общие, не зависящие от конкретной задачи теоретические обсуждения решения задач в терминах этих концепций до середины или второй половины 60 - х годов. Масштабы поддержки, которую они получили со стороны формализованной математической теории, все еще незначительны: некоторые теоремы о сокращении объема поиска, которое может быть обеспечено применением альфа-бета эвристики, пара теорем ( рассмотренных в [4]) о поиске по кратчайшему пути, и несколько полученных в самое последнее время теорем о поиске с выбором лучшей вершины с применением вероятностной оценочной функции. [49]
 |
Координаты вершин прямоугольника. [50] |
Чтобы ответить на этот последний вопрос, рассмотрим, как мы намерены использовать построенное уравнение плоскости. На этом и основывается метод Бокса. Процедура движения по градиенту называется крутым восхождением. Но если окрестность зафиксирована, а уравнение задано, то нельзя сделать ничего лучше, чем расположить экспериментальные точки как можно дальше друг от друга. Такое расположение получается при выборе вершин прямоугольника, задающего окрестность нулевой точки. [51]
По нему создается база графических элементов, каждый из которых оформляется в виде подпрограммы с формальными параметрами. Каждый графический элемент имеет собственные оси координат. Для вычерчивания чертежа нужно последовательно вычерчивать элементы с переносом начала их собственных осей координат на требуемое расстояние. Программа для формирования общего вида одноковшового фронтального погрузчика составлена на алгоритмическом языке Фортран-IV для ЭВМ ЕС-1020 с использованием программного обеспечения Алграф и графопостроителя ЕС-7054. Этот метод может быть распространен и на компоновку машины не имеющей аналога. Для этого также нужно располагать базой составных частей. Если они организованы иерархически на основе И-ИЛИ дерева, то компоновку общего вида можно выполнять одновременно с составлением структурного описания. По мере выбора вершин, означающих структурные элементы технического решения, вызываются соответствующие им графические изображения, из которых по программе размещения компонуется общий вид. Программа размещения реализует решение задачи в одном из трех видов ее постановки. [52]
Страницы: 1 2 3 4