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

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

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

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

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

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

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

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

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

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

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

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';

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

Учитывая 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 приводит к точно такой же результат (если цвета нет в наборе, он добавляется, иначе просто отбрасывается и набор не меняется). Наконец, для представления DAG используйте матрицу смежности.

После выполнения алгоритма, чтобы найти минимальный кратчайший путь среди всех возможных вершин 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) и так далее.