Алгоритм дерева всех комбинаций

Question

У меня есть вопрос, связанный с деревьями. У меня есть около 100 предложений на тему, как «автомобиль». Эти предложения в основном говорят об автомобиле. Если пользователь отправляет запрос: «Найти все комбинации словосочетаний между словами« двигатель »и« масло ».» Я хочу найти все возможные ссылки на слова, чтобы "двигатель" и "масло" соединялись любым количеством похожих слов в предложении.

Например.

1. Во время работы двигатель горячий.
2. Автомобиль имеет двигатель.
3. Автомобиль использует масло.

В этом случае ответ будет: двигатель-> автомобиль-> масло (комбинация из трех слов). И я хочу найти все возможные комбинации, чтобы в итоге «двигатель» и «масло» соединились друг с другом. Это не самый короткий или самый длинный путь, но все возможные пути, идущие во всех направлениях и словах. Можно даже иметь 1000 комбинаций слов для обозначения «двигателя» и «масла», если пути, конечно, не похожи.

Есть ли способ сделать это. Я попробовал использовать хлеб сначала, но это немного сложно. Например, комбинации могут быть.

1. Движок> автомобиль-> run-> Stop-> масло
2. Движок> автомобиль-> масло
3. Движок> быстро-> brake-> масло

Может кто-нибудь, пожалуйста, помогите мне с этим. В чем тут логика и идея. Я не могу игнорировать слово, которое я уже посетил, потому что это остановит алгоритм и не даст мне все ссылки.

Пожалуйста, помогите и идеи.

Спасибо.

fa323

Answer 1

Ваш вопрос слишком недооценен ... то есть даже в вашем примере неясно, почему ответ не включает engine->an->oil.

Кроме того, на самом деле он не имеет ничего общегос деревьями, скорее он имеет дело с графами.

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

Тогда вам нужно решить, что вы хотите вывести.Я очень сомневаюсь, что вы хотите все пути.Зачем?Что ж, если вы построите график, который я описал, то даже используя только ваше первое предложение, есть 24 пути от двигателя до масла, не считая пути с циклами.Однако, если это то, что вам нужно в любом случае, вы можете найти все нециклические пути в графе с помощью поиска в глубину, где вы отмечаете посещенный узел, когда помещаете его в стек, и снимаете отметку, когда вынимаете его.