Я работаю над алгоритмом планирования пути, который эквивалентен задаче коммивояжера. Я не знаю, сколько узлов у меня может быть, поэтому я готов пожертвовать точностью ради скорости. Моя проблема может быть смоделирована как полностью связанный граф, при этом стоимость перехода между узлами связана не только с расстоянием между узлами. Я хотел бы ограничить свое пространство поиска соединениями, которые лежат на триангуляции Делоне (в исследовании, которое я читал, отмечается, что 95-100% соединений в решениях TSP лежат на триангуляции Делоне), но поскольку мой график не может быть выражен как 2D или даже 3D геометрию, я не могу напрямую использовать ее в моем представлении. Существует ли алгоритм, который приводит к триангуляции, эквивалентной триангуляции Делоне, которая применяется к графам, которые не соответствуют геометрическому представлению (стоимость соединений не может быть выражена как геометрическое расстояние между точками из-за чрезмерного ограничения)?
Эквивалент триангуляции Делоне для неориентированного графа
comment
Не понимаете, зачем вам использовать 3D-геометрию? Согласно вики, это можно сделать в самолете.
- person Dewfy schedule 17.04.2012
comment
Сами узлы существуют в 3D, но их стоимость не полностью зависит от расстояния. Сам граф не может быть выражен как 2-мерная или даже 3-мерная геометрия, потому что связи между узлами чрезмерно ограничены. Я знаю, что триангуляцию можно найти для плоскости или даже для трехмерной гиперплоскости, но мне нужно эквивалентное представление для n-мерной геометрии.
- person Alex Londeree schedule 17.04.2012
Ответы (1)
Для n-мерности вы можете попробовать код Грея.
person
Gigamegs
schedule
17.04.2012
