수학적 그래프 압축

Question

나는 다음과 같은 그래프를 그리고 싶습니다.대체 텍스트 http://img25.imageshack.us/img25/9786/problemo.png

3가지 경로를 볼 수 있습니다:a, b & c.경로를 최대한 짧게 만들기 위해 요소(1,2,3...,9)의 위치를 ​​어떻게 변경합니까?내 말은, 이 줄은 가능한 한 짧아야 한다는 뜻이다.

나는 '선을 따라가면 답을 알 수 있다'와 같은 일종의 인포그래픽과 같은 질문이 있는 그래프를 그리기 때문에 그것에 매우 관심이 있습니다.그래프 이론에 관한 내용인 것으로 알고 있습니다.너무 어렵다면, 리눅스에서 이와 같은 것을 압축할 수 있는 프로그램이 있는지 아시나요?

예를 들어 프로그램은 다음과 같이 작동해야 합니다.입력에는 3개의 경로가 있어야 합니다.

a='1,5,7,8,4,2,6'
b='4,2,3,6,9,8,5'
c='7,9'

그리고 출력에는 이 요소의 좌표가 있어야 합니다.

Answer 1

해결하기 어려운 최적화 문제가 있을 때마다 나는 생각한다. 유전자 알고리즘.아래 내 솔루션은 귀하가 GA에 익숙하다고 가정합니다(직접 구현하는 것은 그리 어렵지 않습니다).

제공한 예제 그래프를 보면서 노드가 NxN 그리드(정수 위치)에 배치된 다음 코드화한다고 가정해 보겠습니다. 게놈, 다음 구성표를 고려하십시오.

00101 00100 11010 11110 11000     
  A     B     C     D     E

여기서 각 부분은 노드의 그리드(이진수) 위치를 해당 순서대로 인코딩합니다.각 부분의 길이는 그리드의 크기( length=ceil(log2(N*N)) )에 따라 달라집니다.
그리드에는 왼쪽에서 오른쪽으로 행별로 번호가 매겨져 있습니다.

예를 들어 4개의 노드(A,B,C,D)와 3x3 그리드가 있는 완전한 그래프의 경우 문자열은 다음과 같습니다.

0011 0001 0101 1000    =   3  1  5  8 
 A    B    C    D          A  B  C  D

다음 레이아웃을 나타냅니다.

. B .       00  01  02
A . C       03  04  05
. . D       06  07  08

다음으로 우리는 크로스오버 평소와 같이 연산자(1점 또는 2점 교차) 및 돌연변이 (무작위로 1비트 뒤집기).우리는 언제든지 다음 사항만 확인하면 됩니다. 유효한 위치 그리드 내부.
마지막으로 피트니스 기능 경로에 있는 노드 사이의 거리(여러 경로에 대한 합계)의 일부 기능이 되며, 이는 긴 경로에 불이익을 줍니다(최소화 문제로).예를 들면 다음과 같습니다. 도시 블록 거리 노드 사이.
나머지 방법은 표준 유전자 알고리즘(초기화, 평가, 선택, 재생산, 종료)입니다.

예설명을 위해 다음 두 경로가 제공되는 도시 블록 거리의 이전 레이아웃을 고려해보세요. A D C B 그리고 C B D A

A -> D -> C -> B
  3  + 1  + 2    = 6        therefore
C -> B -> D -> A              fitness(0011 0001 0101 1000) = 6 + 8 = 14
  2  + 3  + 3    = 8

당연히 목표는 피트니스 기능을 최소화하는 레이아웃을 찾는 것입니다.