Найдите самый длинный список цепочек?

Question

У меня много объектов. Некоторые объекты могут создавать список цепочек, и все объекты имеют продолжение цепочки при условии. Пример будет объяснять больше. Скажем, у меня есть эти два объекта:

[ 
    { 
    "name": "ObjectA", 
    "produce": "ChainA", 
    "continuations": [ 
     { "ChainB": "ChainC" }, 
     { "ChainC": "ChainC" } 
    ] 
    } 
    { 
    "name": "ObjectB", 
    "produce": null, 
    "continuations": [ 
     { "ChainA": "ChainB" } 
    ] 
    } 
] 

Мне нужно найти список:

ChainA (ObjectA) => ChainB (ObjectB) => ChainC (ObjectA) => ChainC (ObjectA) 

Я просто не могу найти лучший способ, что зацикливание снова и снова. У некоторых из вас есть идея?

Благодаря

Answer 1

Эта проблема является NP-полной, потому что если вы имели эффективный алгоритм ее решения, то вы могли бы решить https://en.wikipedia.org/wiki/Longest_path_problem. Так что это довольно безнадежно.

Вот это сокращение. Учитывая ориентированный граф G, помечайте края как объекты и назовите вершины как цепочки. Каждый «объект» (край) создает «цепочку», к которой относится вершина. Каждый «объект» (край) имеет единственное продолжение от исходной «цепочки» (вершины) до целевой «цепи» (вершины).

Теперь примените гипотетический алгоритм. Самый длинный список цепочек будет краем желаемого самого длинного пути для G.