Ответ 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
Далее мы создаем оператор кроссовера как обычно (одно- или двухточечный кроссовер) и мутацию (случайным образом переворачиваем один бит). Мы просто должны убедиться, что в любой момент мы имеем только действительные позиции внутри сетки.
Наконец, функция пригодности будет некоторой функцией расстояний между узлами пути (сумма для нескольких путей), которая будет наказывать длинные пути (как проблема минимизации).
Примером может служить расстояние между городами между узлами.
Остальная часть метода представляет собой стандартный генетический алгоритм (инициализация, оценка, выбор, воспроизведение, завершение).
Пример
Чтобы проиллюстрировать, рассмотрим предыдущую компоновку с расстоянием между городскими блоками, учитывая следующие два пути: 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
Очевидно, цель состоит в том, чтобы найти макет, который минимизирует функцию фитнеса.