Минимальное количество ребер для формирования пути длиной L ⇐ JAVA

[Anonymous]

Я столкнулся с этой проблемой.
Дано взвешенное дерево T. Найдите минимальное количество ребер, чтобы сформировать простой путь (без повторяющихся вершин или ребер) длины L. p>

Подробнее:
L задается в качестве входных данных и может быть разной для каждого случая.
Там являются N вершинами в дереве, пронумерованными от 0 до N - 1.
Моей первой мыслью было то, что лучшее, что я могу сделать, — это пройти по всем N^2 путям в T. Вот исполняемый файл код с примером ввода.

Код: Выделить всё

import java.util.*;
class Edge {
int toVertex, weight;
Edge(int v, int w) {
toVertex = v; weight = w;
}
}
class Solver {
// method called with the tree T given as adjacency list and the path length L to achieve
// method to return minimum edges to create path of length L or -1 if impossible
public static int solve(List T, long L) {
int min = (int) 1e9;
for (int i = 0; i < T.size(); i++) {
min = Math.min(min, test(T, L, i, -1, 0, 0));
}
if (min == (int) 1e9) {
return -1;
} else {
return min;
}
}
static int test(List T, long L, int vertex, int parent, long length, int edges) {
if (length == L) {
return edges;
} else if (length < L) {
int min = (int) 1e9;
for (Edge edge : T.get(vertex)) {
if (edge.toVertex != parent) {
min = Math.min(min, test(T, L, edge.toVertex, vertex, length + edge.weight, edges + 1));
}
}
return min;
} else {
return (int) 1e9;
}
}
}
// provided code
public class Main {
static void putEdge(List T, int vertex1, int vertex2, int weight) {
T.get(vertex1).add(new Edge(vertex2, weight));
T.get(vertex2).add(new Edge(vertex1, weight));
}
public static void main(String[] args) {
// example input
List T = new ArrayList();
int N = 8;
for (int i = 0; i < N; i++) T.add(new ArrayList());
putEdge(T, 0, 1, 2);
putEdge(T, 1, 2, 1);
putEdge(T, 1, 3, 2);
putEdge(T, 2, 6, 1);
putEdge(T, 6, 7, 1);
putEdge(T, 3, 4, 1);
putEdge(T, 3, 5, 4);
System.out.println(Solver.solve(T, 5L)); // path from 4 to 5 have 2 edges and length 5
}
}

Но это превышает ограничение по времени, когда N достигает около 10 000. Я также рассматривал бинарный поиск по ответу, но проверка возможности конкретного ответа выглядит так же сложно, как и решение исходной задачи.
Есть ли более эффективный способ решения этой проблемы, чтобы как-то избежать тестирования все пути?

Подробнее здесь: https://stackoverflow.com/questions/786 ... h-length-l