Як замовити графічні вузли так, щоб відстань між двома сусідніми вузлами була мінімальною - java, c ++, алгоритм, граф

Мені було цікаво, чи відома ця проблема в графікутеорія: У мене є непрямий графік без ваг G = (V, A), і я хочу розмістити вузли цього графа в рядку, щоб спрямовані вузли розміщувалися якомога ближче. Так, наприклад:

З огляду на цей графік:

a,b;a,d;b,e;c,f;c,h;f,h;e,g;e,h.

де дуги розділені знаком ";"

Мені потрібно дійти до цього рішення: a, b, d, e, g, h, c, f = 2 де 2 - максимальна відстань у рядку a, b, d, e, g, h, c, f між двома направленими вузлами.

Формально:

• нехай d (v, u) - відстань між двома вузлами відповідно до графіка.
• Знайти замовлення v_1,, v_2,, v_n,, така, що max {d (v_я,, v_{i + 1,})} є мінімальним

Відповіді:

Ну, здається ви зіткнулися з варіацією Гамільтонова проблема шляху.

У цій проблемі, враховуючи графік - ви шукаєте шлях, який проходить через усі вершини, не повторюючи жодного вузла двічі.

Зауважте, що гамільтоновий шлях є ідеальним рішенням вашої проблеми, і, отже, якщо вашу проблему можна ефективно вирішити - так це робить і проблема гамільтонового шляху.

На жаль, не існує відомого поліномного рішення проблеми гамільтонового шляху, і проблема є NP-завершена (тому загальної думки таке (ефективне) рішення не існує).

Рішення грубої сили буде O (n!) - перевірте всі можливі перестановки та виберіть оптимальну. Це можна оптимізувати за допомогою галузеві та зв'язані техніки.