C++ генерирует случайные графики, подходящие для TSP

Question

Я тестирую различные модели/алгоритмы TSP. Сейчас я использую полную матрицу смежности, заполненную случайными значениями от 1 до 100, которая представляет собой полный направленный граф.

Я ищу более строгий подход, который позволил бы мне попробовать различные виды случайных графов, таких как Erdos-Renyi, сети малого мира и сети, свободные от масштаба.

Я знаю, что мне, возможно, придется переключиться на списки смежности для новых графиков.

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

BTW Я думал об использовании библиотеки Boost Graph, но я не знаком с ней, и, возможно, есть что-то более подходящее. Предложения по альтернативам приветствуются, но не следует считать основной сферой этого вопроса.

Мне не нужен решатель TSP, мне нужно что-то, чтобы помочь в создании приемлемых проблем.

Спасибо.

Answer 1

Вы можете попробовать монотонный серый код, a.k.a кривую гильберта. Это может помочь найти путь гамильтониана: http://en.m.wikipedia.org/wiki/Gray_code.

Answer 2

Я ищу более строгий подход, который позволил бы мне попробовать различные виды случайных графов,

Проверьте Mathematica. Он имеет встроенный предикат, чтобы проверить, имеет ли данный график гамильтонов путь или нет. Он также имеет предикат для генерации случайных гамильтоновых графов.

Кроме того, если вы еще не попробовали, TSBLIB содержит (трудно и просто) экземпляры, которые могут оказаться вам полезными.