Поиск пути при форсировании уникальных атрибутов узла - какой алгоритм мне следует использовать?
Обновление 2011-12-28: вот сообщение в блоге с менее расплывчатым описанием проблемы, которую я пытался решить, моей работы над ней и моего текущего решения: Наблюдение за каждой игрой команды MLB
Я пытаюсь решить какую-то странную задачу по поиску пути. У меня ациклический направленный граф, и каждое ребро имеет значение расстояния. И я хочу найти кратчайший путь. Все просто, правда? Что ж, есть несколько причин, по которым я не могу просто использовать Dijkstra или A *.
- Меня совершенно не волнует ни начальный узел моего пути, ни конечный узел. Мне просто нужен путь, который включает ровно 10 узлов . Но:
- У каждого узла есть атрибут, скажем, цвет. Каждый узел имеет один из 20 различных возможных цветов.
- Путь, который я пытаюсь найти, - это кратчайший путь с ровно 10 узлов, где каждый узел имеет разный цвет. Я не хочу, чтобы ни один из узлов на моем пути имел тот же цвет, что и любой другой узел.
- Было бы неплохо иметь возможность заставить мой путь иметь одно значение для одного из атрибутов (например, «хотя бы один узел должен быть синим»), но в этом нет необходимости.
Это упрощенный пример. В моем полном наборе данных фактически есть три разных атрибута для каждого узла, которые все должны быть уникальными, и у меня есть 2k + узлов, каждый из которых в среднем имеет 35 исходящих ребер. Поскольку получение идеального «кратчайшего пути» может происходить по экспоненциальному или факториальному времени, исчерпывающий поиск действительно не вариант. Что я действительно ищу, так это некоторое приближение «хорошего пути», которое удовлетворяет критерию пункта 3.
Может ли кто-нибудь указать мне на алгоритм, который я мог бы использовать (даже модифицированный)?
Некоторые статистические данные по моему полному набору данных:
- Всего узлов: 2430
- Всего ребер: 86524
- Узлы без входящих ребер: 19
- Узлы без исходящих ребер: 32
- Большинство исходящих ребер: 42
- Среднее количество ребер на узел: 35,6 (в каждом направлении)
- Из-за характера данных, Я знаю, что график ациклический
- И в полном наборе данных я ищу путь длиной 15, а не 10