Поиск пути при форсировании уникальных атрибутов узла - какой алгоритм мне использовать?

Question

Обновление 2011-12-28: Вот сообщение в блоге с менее смутным описанием проблемы, которую я пытался решить, моя работа над ней и мое текущее решение: Просмотр каждой команды MLB Play AИгра

---

Я пытаюсь решить какую-то странную задачу поиска пути.У меня есть ациклический график направленности, и каждое ребро имеет значение расстояния.И я хочу найти кратчайший путь.Просто, правда?Ну, есть несколько причин, по которым я не могу просто использовать Дейкстру или А *.

1. Мне все равно , что является начальным узлом моего пути,ни конечный узел.Мне просто нужен путь, включающий ровно 10 узлов .Но:
2. Каждый узел имеет атрибут, скажем, его цвет.Каждый узел имеет один из 20 различных возможных цветов.
3. Путь, который я пытаюсь найти, является кратчайшим путем с точно 10 узлами, где каждый узел являетсяразного цвета.Я не хочу, чтобы какие-либо узлы в моем пути имели тот же цвет, что и любой другой узел.
4. Было бы неплохо иметь возможность заставить мой путь иметь одно значение для одного из атрибутов («хотя бы один узел должен быть синим», например), но это на самом деле не обязательно.

Это упрощенный пример.Мой полный набор данных на самом деле имеет три разных атрибута для каждого узла, которые все должны быть уникальными, и у меня есть 2k + узлов, каждый из которых имеет в среднем 35 исходящих ребер.Поскольку получение идеального «кратчайшего пути» может быть экспоненциальным или факториальным временем, исчерпывающий поиск на самом деле не вариант.Что я действительно ищу, так это примерно 1030 * приближение"хорошего пути", которое соответствует критерию под # 3.

Может кто-нибудь указать мне на алгоритм, который я мог бы использовать(даже изменено)?

---

Некоторые характеристики моего полного набора данных:

• Всего узлов: 2430
• Всего ребер: 86524
• Узлы без входящих ребер: 19
• Узлы без исходящих ребер: 32
• Большинство исходящих ребер: 42
• Среднее число ребер на узел: 35,6 (в каждом направлении)
• Из-за характера данных я знаю, что график ацикличен
• И в полном наборе данных я ищу путь длиной 15, а не 10

Answer 1

Это тот случай, когда вопрос содержит большую часть ответа.

Выполните поиск в ширину, начиная со всех корневых узлов.Когда число параллельно ищущих путей превышает некоторый предел, отбрасывают самые длинные пути.Длина пути может быть взвешена: последние ребра могут иметь вес 10, ребра пройдены 9 прыжков назад - вес 1. Также можно назначить меньший вес всем путям, имеющим предпочтительный атрибут, или путям, проходящим через слабо связанные узлы.Сохраните последние 10 узлов на пути к хеш-таблице, чтобы избежать дублирования.И сохраните где-нибудь минимальную сумму последних 9 длин ребер вместе с кратчайшим путем.

Answer 2

Если число возможных значений невелико, вы можете использовать алгоритм Floyd с небольшой модификацией: для каждого пути вы сохраняете битовую карту, которая представляет различные уже посещенные значения.(В вашем случае растровое изображение будет иметь ширину 20 бит на каждый путь.

Затем, когда вы выполняете сравнение длины, вы также И свои растровые изображения проверяете, является ли это действительный путь, и если это так, вы ИЛИ их вместе исохранить это как новое растровое изображение для пути.

Answer 3

Проблема может быть решена путем динамического программирования следующим образом.Давайте начнем с формального определения его решения.

Учитывая DAG G = (V, E), пусть C будет набором цветов посещенных вершин и пусть w[i, j] и c[i] будут соответственно весом (расстоянием)связанный с ребром (i, j) и цветом вершины i.Обратите внимание, что w[i, j] равно нулю, если ребро (i, j) не принадлежит E.Теперь определим расстояние d для перехода от вершины i к вершине j с учетом C как

d[i, j, C] = w[i, j] if i is not equal to j and c[j] does not belong to C

           = 0 if i = j

           = infinite if i is not equal to j and c[j] belongs to C

Теперь мы готовы определить наши подзадачи следующим образом:

A[i, j, k, C] = кратчайший путь от i до j, который использует ровно k ребер и учитывает цвета в C, так что никакие две вершины в пути не будут окрашены в один и тот же цвет (один из цветовв C)

Пусть m будет максимальным числом ребер, разрешенных в пути, и предположим, что вершины помечены как 1, 2, ..., n.Пусть P[i,j,k] будет вершиной предшественника j в кратчайшем пути, удовлетворяющей ограничениям от i до j.Следующий алгоритм решает проблему:

for k = 1 to m
  for i = 1 to n
    for j = 1 to n
      A[i,j,k,C] = min over x belonging to V {d[i,x,C] + A[x,j,k-1,C union c[x]]}
      P[i,j,k] = the vertex x that minimized A[i,j,k,C] in the previous statement

Установите начальные условия следующим образом:

A[i,j,k,C] = 0 for k = 0
A[i,j,k,C] = 0 if i is equal to j
A[i,j,k,C] = infinite in all of the other cases

Общая вычислительная сложность алгоритма составляет O(m n^3);принимая во внимание, что в вашем конкретном случае m = 14 (поскольку вы хотите ровно 15 узлов), из этого следует, что m = O(1), так что сложность на самом деле составляет O(n^3).Для представления набора C используйте хеш-таблицу, так что для тестирования вставки и членства требуется в среднем O (1).Обратите внимание, что в алгоритме операция C union c [x] на самом деле является операцией вставки, в которой вы добавляете цвет вершины x в хеш-таблицу для C. Однако, поскольку вы вставляете только элемент, операция set union приводит кточно такой же результат (если цвет отсутствует в наборе, он добавляется; в противном случае он просто отбрасывается и набор не изменяется).Наконец, для представления группы доступности базы данных используйте матрицу смежности.

Как только алгоритм будет выполнен, чтобы найти минимальный кратчайший путь среди всех возможных вершин i и j, просто найдите минимум среди значений A[i,j,m,C].Обратите внимание, что если это значение равно бесконечное , то допустимого кратчайшего пути не существует.Если существует допустимый кратчайший путь, то вы можете определить его, используя значения P[i,j,k] и проследив в обратном направлении по вершинам предшественника.Например, начиная с a = P[i,j,m] последнее ребро на кратчайшем пути - (a,j), предыдущее ребро задается как b = P[i,a,m-1], оно равно (b,a) и так далее.

Answer 4

Для тех, кто хочет поэкспериментировать, вот (postgres) скрипт sql для генерации поддельных данных.

SET search_path='tmp';

-- DROP TABLE nodes CASCADE;
CREATE TABLE nodes
    ( num INTEGER NOT NULL PRIMARY KEY
    , color INTEGER
    -- Redundant fields to flag {begin,end} of paths
    , is_root boolean DEFAULT false
    , is_terminal boolean DEFAULT false
    );

-- DROP TABLE edges CASCADE;
CREATE TABLE edges
    ( numfrom INTEGER NOT NULL REFERENCES nodes(num)
    , numto INTEGER NOT NULL REFERENCES nodes(num)
    , cost INTEGER NOT NULL DEFAULT 0
    );

-- Generate some nodes, set color randomly
INSERT INTO nodes (num)
SELECT n
FROM generate_series(1,2430) n
WHERE 1=1
    ;
UPDATE nodes SET COLOR= 1+TRUNC(20*random() );

-- (partial) cartesian product nodes*nodes. The ordering guarantees a DAG.
INSERT INTO edges(numfrom,numto,cost)
SELECT n1.num ,n2.num, 0
FROM nodes n1 ,nodes n2
WHERE n1.num < n2.num
AND random() < 0.029
    ;

UPDATE edges SET cost = 1+ 1000 * random();

ALTER TABLE edges
    ADD PRIMARY KEY (numfrom,numto)
    ;

ALTER TABLE edges
    ADD UNIQUE (numto,numfrom)
    ;

UPDATE nodes no SET is_root = true
WHERE NOT EXISTS (
    SELECT * FROM edges ed
    WHERE ed.numfrom = no.num
    );
UPDATE nodes no SET is_terminal = true
WHERE NOT EXISTS (
    SELECT * FROM edges ed
    WHERE ed.numto = no.num
    );

SELECT COUNT(*) AS nnode FROM nodes;
SELECT COUNT(*) AS nedge FROM edges;
SELECT color, COUNT(*) AS cnt FROM nodes GROUP BY color ORDER BY color;

SELECT COUNT(*) AS nterm FROM nodes no WHERE is_terminal = true;

SELECT COUNT(*) AS nroot FROM nodes no WHERE is_root = true;

WITH zzz AS    (
    SELECT numto, COUNT(*) AS fanin
    FROM edges
    GROUP BY numto
    )
SELECT zzz.fanin , COUNT(*) AS cnt
FROM zzz
GROUP BY zzz.fanin
ORDER BY zzz.fanin
    ;

WITH zzz AS    (
    SELECT numfrom, COUNT(*) AS fanout
    FROM edges
    GROUP BY numfrom
    )
SELECT zzz.fanout , COUNT(*) AS cnt
FROM zzz
GROUP BY zzz.fanout
ORDER BY zzz.fanout
    ;

COPY nodes(num,color,is_root,is_terminal)
TO '/tmp/nodes.dmp';

COPY edges(numfrom,numto, cost)
TO '/tmp/edges.dmp';

Answer 5

Похоже, что жадная глубина первого поиска будет вашим лучшим выбором. При разумном распределении значений атрибутов я думаю, что нахождение единственной допустимой последовательности - это время E [O (1)], то есть ожидаемое постоянное время. Я мог бы доказать это, но это может занять некоторое время. В доказательстве использовалось бы предположение, что существует ненулевая вероятность того, что на каждом шаге может быть найден действительный следующий сегмент последовательности.

Жадный поиск будет возвращаться назад всякий раз, когда нарушается ограничение уникального значения атрибута. Поиск останавливается, когда найден 15-сегментный путь. Если мы примем мою догадку, что каждая последовательность может быть найдена в E [O (1)], то это вопрос определения того, сколько параллельных поисков нужно предпринять.

Answer 6

Вы пробовали прямой подход и потерпели неудачу? Из вашего описания проблемы я не вижу причин, по которым простой жадный алгоритм, такой как поиск в глубину , мог бы просто подойти:

• Выберите начальный узел.
• Проверьте непосредственных соседей, есть ли какие-нибудь узлы, которые можно добавить к пути? Разверните путь одним из них и повторите процесс для этого узла.
• В случае неудачи вернитесь к последнему успешному состоянию и попробуйте нового соседа.
• Если у вас заканчиваются соседи для проверки, этот узел не может быть начальным узлом пути. Попробуйте новый.
• Если у вас есть 10 узлов, все готово.

Хорошую эвристику для выбора начального узла трудно дать без какого-либо знания о том, как распределяются атрибуты, но возможно, что это полезно для узлов с высокой степенью в первую очередь.