|
#1
|
|||
|
|||
Сравнение Графов
Добрый день!
вобщем есть задача: например есть "модель-1": 1 2 *--------* | | | | *--------* 3 4 состоит из 4-х точек связи: 1->3 , 1->2 , 2->4 , 3->4 например пользователь вводит: 3 2 1 4 *---------*-----------*-----------* также у фигуры 4-е точки и связи: 1->3, 3->2, 2->4, 1->4 Сравнивая все модели в "библиотеке(файлах)" и введенные данные программа должна вывести что введенные данные по определению является "модель-1". причём точек и связей может быть неограниченно. Массивы связей и точек: Код:
Type DotRec = record id:integer; x:integer; y:integer; z:integer; end; Type LinkRec = record id:integer; first:integer; last:integer; end; var DotArr: array of DotRec; LinkArr: array of LinkRec; у точек: id - уникальный номер, x,y,z - координаты у связей: id - уникальный номер, first - начальная точка, last-конечная точка first и last выбирается выберется из массива точек по уникальному номеру. Заранее спасибо! |
#2
|
|||
|
|||
Пример ввода что-то подозрительно неправилен (напр., у модели 1 нет связи 3-2).
|
#3
|
|||
|
|||
Цитата:
вот например "эталон-1": (2.5 кб) Точки Код:
id:0 x:3 y:3 z:0 id:1 x:3 y:6 z:0 id:2 x:6 y:6 z:0 id:3 x:6 y:3 z:0 Код:
id:0 first:0 last:1 id:1 first:2 last:1 id:2 first:2 last:3 id:3 first:0 last:3 (2.5 кб) Точки Код:
id:0 x:7 y:7 z:0 id:1 x:4 y:5 z:0 id:2 x:3 y:6 z:0 id:3 x:7 y:3 z:0 Код:
id:0 first:1 last:2 id:1 first:1 last:0 id:2 first:3 last:0 id:3 first:3 last:2 и программа проанализировав эталоны должна вывести что ввод пользователя это "эталон-1". |
#4
|
|||
|
|||
Какие критерии соответсвия шаблону?
|
#5
|
|||
|
|||
Цитата:
|
#6
|
|||
|
|||
Ну так и пиши сравнение по связям - кол-во и наличие нужных связей.
Я бы сначала проверял по кол-ву точек, потом по кол-ву связей, а уже если по первым 2м критериям сошлось, то проверяешь нужные связи, при этом проверяешь прямые и обратные связи, т.е. связь 2-3 соответсвует также связи 3-2 (если связи двунаправленные). |
#7
|
|||
|
|||
Да это то понятно, но ведь пользователь необязательно введёт в таком порядке точки м связи например вот тоже "квадрат":
точки Цитата:
Цитата:
И если по такому методу сравнивать с эталоном описанном в 3-м посте то ничего не получится , хотя должно... |
#8
|
|||
|
|||
тогда еще перед сравнением сортируй точки с переименованием.
Иначе далее - распознавание образов, а это гораздо более сложная задача. |
#9
|
|||
|
|||
Спасибо! Нет это всё заведёт в тупик... распознавание образов? так ведь квадрат может быть представлен в линию или в "песочные часы", тут скорее нужно всё представлять в матрице смежности и их уже сравнивать только как?
|
#10
|
|||
|
|||
Песочные часы получатся, если поставить жёсткое ограничение, что четыре точки в одной плоскости. Но если хотя бы одна точка отклонится от этой плоскости хотя бы на чуть-чуть, то это будет уже обычная пространственная фигура без пересечений.
|
#11
|
|||
|
|||
Вобщем нужно установить изоморфизм неориентированных графов.
|