18
두 문자열 사이에 Levenshtein 거리 (또는 편집 거리)가있는 문자열처럼 그래프와 비슷한 것이 있는지 궁금합니다.두 그래프 사이의 거리 편집
그래프 G1을 그래프 G2으로 변환하기위한 원자 연산 (노드 및 에지 삽입/삭제)의 수를 나타내는 스칼라 측정 값입니다.
A
답변
3
참고 :
사이 그러나 그래프에서 적어도 N 사이를 검색한다! 각 에지와 정점의 신원을 찾는 위치. 고유 한 인덱스로 두 그래프를 쉽게 비교할 수 있지만 마스터 질문은 각 정점과 가장자리에 대한 ID를 정의합니다.이 질문 (변환 할 수있는 두 그래프의 각 정점과 가장자리에 대한 ID를 찾는)은 매우 어렵습니다. (Isomorphism) 문제 (NP-Complete). 동형 이력 그래프를 검색 할 수 있습니다.Levenshtein 거리 (또는 편집 거리) 두 문자열
4
일반 그래프의 경우 대답에서 언급 한 다른 NP와 마찬가지로 NP 완전 문제입니다. 그러나 트리 그래프에는 잘 알려진 다항식 알고리즘이 있습니다. 그들 중 가장 유명한 것은 1989 년에 출판 된 "Zhang Shasha"알고리즘입니다.
18
그래프 편집 거리는 당신이 찾고 있던 측정 값이라고 생각합니다. 그래프 편집 동작
그래프 편집 거리 측정의 최소 개수는 다른 하나의 그래프를 변환 및 허가 그래프 편집 동작을 포함
가- 삽입/에지 삭제/격리 정점
- 삽입 삭제 두 그래프의 그래프 편집 거리를 계산 그러나 정점/EDGE의 라벨 (경우 표시된 그래프)
변경
7
이 슬라이드는 검정 고시의 기본 개념을 소개 @ivotro 당신은 A survey of graph edit distance
관련 문제
- 1. 두 개체 사이의 거리
- 2. 2D에서 두 선 사이의 거리
- 3. 두 단어 사이의 의미 거리
- 4. 두 줄 사이의 거리 찾기
- 5. 두 점 사이의 거리 계산
- 6. 두 벡터 사이의 거리 조작
- 7. 두 점 사이의 구름 거리
- 8. 두 줄 사이의 최단 거리
- 9. OpenCV의 두 점 사이의 거리
- 10. 두 줄 사이의 거리 측정
- 11. 두 지리적 포인트 사이의 거리?
- 12. 두 점 사이의 측지 거리
- 13. 두 그래프 사이의 공백 제거
- 14. GeoDjango가있는 두 점 사이의 가장 먼 거리
- 15. TextView의 단락 사이의 거리
- 16. 두 거리 사이의 주행 거리를 얻으십시오
- 17. android app : 두 주소 사이의 거리 얻기
- 18. postgis 한 줄의 두 지점 사이의 거리
- 19. 두 이진 트리 사이의 회전 거리
- 20. 격자에서 두 사각형 사이의 거리 계산 - Java
- 21. 배열의 두 점 사이의 최대 거리
- 22. 두 개의 동심 컨투어 사이의 거리
- 23. 두 범위 사이의 거리와 거리 내에있는 요소
- 24. OpenCV - 두 가장자리 사이의 거리 측정
- 25. 두 세트의 좌표 (NSStrings) 사이의 거리 계산
- 26. 두 사용자 사이의 사회적 거리 계산
- 27. 2 차원 배열의 두 요소 사이의 거리
- 28. JENA에서 DBPedia의 두 자원 사이의 거리 계산하기
- 29. 두 벡터 사이의 OpenCV 유클리드 거리
- 30. MKMapKit 두 개의 주석 사이의 실제 거리
참조 – ivotron
기쁘게 종이 보라, http://orion.math.iastate.edu/rymartin/talks/EditDist/editIITcolloq.pdf –
@ jason.Z GED의 이론에 대한이 논문들/PPT 회담은 GED의 최신 제안에 기초한 구현입니까? – Vishrant