Уплотнение математического графика

Всякий раз, когда у меня возникает проблема оптимизации, которую трудно решить, я думаю о генетических алгоритмах . Мое нижеприведенное решение предполагает, что вы знакомы с GA (не очень сложно реализовать его самостоятельно)

Глядя на приведенный вами пример графа, предположим, что узлы будут размещены в сетке NxN (целые позиции), а затем в кодифицируйте геномы , рассмотрите следующую схему:

00101 00100 11010 11110 11000     
  A     B     C     D     E

где каждая часть кодирует позицию в сетке (в двоичном формате) узлов (в указанном порядке). Длина каждой части зависит от размера сетки (длина = 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

представляет следующее layout:

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

Затем мы проектируем оператор кроссовера как обычно (одно- или двухточечное кроссовер), а также мутацию (меняем один бит наугад). Нам просто нужно убедиться, что в любой момент у нас есть только действительных позиций внутри сетки.
Наконец, функция приспособленности будет некоторой функцией расстояний между узлами на пути (сумма для нескольких путей), что будет штрафовать длинные пути (как проблема минимизации). В качестве примера возьмем расстояние городских кварталов между узлами.
Остальная часть метода представляет собой стандартный генетический алгоритм (инициализация, оценка, отбор, воспроизведение, завершение).

Пример Чтобы проиллюстрировать это, рассмотрим предыдущий макет с расстоянием между городскими кварталами, учитывая следующие два пути: ADCB и CBDA

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

Очевидно, цель состоит в том, чтобы найти макет, который минимизирует функцию пригодности.