Нахождение путей в грАфе, содержащих заданное ребро
Нужен исходник модуля или хотя бы dcu под пасквиль. Буду благодарен.
Задан граф. Надо найти все замкнутые пути в этом графе, проходящие через заданное ребро этого графа.
Нужен исходник модуля или хотя бы dcu под пасквиль. Буду благодарен.
вообще то это NP полная задача и решаеться она полным перебором
ну для 30 вершин можешь попробывать метод ветвей и границ
а если не секрет почему возникла такая задача может можно найти другой метод решения
а если не секрет почему возникла такая задача может можно найти другой метод решения
Задан чертеж вала (грубо говоря, набор мноугольников; линии сходятся необязательно под прямым углом, фаска - под 45 градусов, например). У каждой линии известны координаты ее крайних точек. Надо сориентировать все поверхности вала относительно его оси симметрии, то есть задать направление (+ или -) проекции внешней нормали к каждой поверхности на эту ось.
Поскольку чертеж может быть сколь угодно сложным, предлагается следующий алгоритм. Допустим, надо сориентировать выделенную поверхность (см. рис.). Прога обходит все ребра графа, заданного чертежом, выбирая все возможные гамильтоновы циклы, содержащие это ребро (выделенную поверхность). Цикл определяет многоугольник. Так вот, относительно каждого такого многоугольника определить внешнюю нормаль, а следовательно, и ее проекцию на ось, очень просто. Проблема в том, что в данном примере выделенная поверхность имеет как бы два направления сразу. Потому что она содержится в части вала меньшего диаметра и в другой части - большего диаметра. И относительно этих двух многоугольников она, соответственно, ориентирована в противоположных направлениях. Такой извратный алгоритм, описанный в предыдущей мессаге, нужен именно для определения таких циклов, содержащих "двунаправленные" поверхности, находящиеся на слиянии частей вала разных диаметров. Как из двух ориентаций выбрать правильную - решенная задача. Но на ее вход надо подать два цикла, в которых поверхность ориентирована двояко.