Мне дан набор данных философов, который напоминает неориентированный граф. Философы хранятся в хэш-карте, где ключом является имя философа, а значением - список его соседей.
Пользователь дает 2 имени философа в качестве входных данных, и мне нужно найти кратчайший цикл (если таковой существует), который включает в себя этих 2 философов.
Сначала я подумал, что эта проблема очень похожа на проблему коммивояжера, однако в этой задаче у нас также есть расстояния перемещения, и каждую вершину можно посетить только один раз, что, по-видимому, здесь не так. Решение этой проблемы, кажется, связано с графиком, но я не совсем уверен, какой алгоритм использовать или даже какая проблема похожа на него.
Решение, которое я задумал, заключалось в нахождении всех циклов в данном графике, сводя результаты только к циклам, которые содержат философы, заданные пользователем, и выбирая только самые короткие циклы из этих, так как я оценил бы циклы на основе того, как они совершают много «прыжков», которые, по сути, будут простым счетчиком. Проблема в том, что я боюсь, что это не может быть оптимальным решением, учитывая, насколько большой набор данных и сколько циклов потенциально может быть сформировано (много).
Вывод должен быть в следующем формате: {u1, u2, u3, u4, u5, u1}, где u - имя каждого философа, который создает цикл, который я ищу. Если такого цикла не существует, мне просто нужно напечатать соответствующее сообщение.