Алгоритм на графе
А про пути что нибудь известно? Есть неравенство треугольника, верно ли что длина от A до B равна длине от B до A?
Граф ориентированный или неориентированный?
и еще уточнение. Если отмеченные вершины A_1, A_2, A_N, а еще одна вершина - B, то принимаются пути вида (A_x, B, A_y) или (B, A_x, A_y) тоже подойдут?
и еще - доступны только операции, что ты описал? Или на самом деле граф задан списком вершин и ребер, т.е. можно произвольные алгоритмы придумывать?
и еще уточнение. Если отмеченные вершины A_1, A_2, A_N, а еще одна вершина - B, то принимаются пути вида (A_x, B, A_y) или (B, A_x, A_y) тоже подойдут?
и еще - доступны только операции, что ты описал? Или на самом деле граф задан списком вершин и ребер, т.е. можно произвольные алгоритмы придумывать?
algorithm design manual, автор skiena
неравенство треугольника есть.
A->B не обязательно равно B->A
но, скажем, есть оценка, что длины путей в разные стороны отичаются не более, чем в какое-то число раз.
A->B не обязательно равно B->A
но, скажем, есть оценка, что длины путей в разные стороны отичаются не более, чем в какое-то число раз.
граф ориентированный
> (B, A_x, A_y) тоже подойдут?
подойдут.
> доступны только операции, что ты описал? Или на самом деле граф задан списком вершин и ребер, т.е. можно произвольные алгоритмы придумывать?
вообще, хотелось бы, чтоб только с этими операциями (хотя, тогда от графа мало что остаётся, скорее уж метрическое пространство)
но если совсем будет плохо, то можно и граф поиметь. но это, конечно, уже другая совсем задача будет
(можно что-то на этом графе предпосчитать, чтоб потом проще было)
так что пока считаем, что графа нет.
> (B, A_x, A_y) тоже подойдут?
подойдут.
> доступны только операции, что ты описал? Или на самом деле граф задан списком вершин и ребер, т.е. можно произвольные алгоритмы придумывать?
вообще, хотелось бы, чтоб только с этими операциями (хотя, тогда от графа мало что остаётся, скорее уж метрическое пространство)
но если совсем будет плохо, то можно и граф поиметь. но это, конечно, уже другая совсем задача будет
(можно что-то на этом графе предпосчитать, чтоб потом проще было)
так что пока считаем, что графа нет.
спасибо, посмотрю
Оставить комментарий
psihodog
В общем, есть _примерно_ такая задачка:дан (большой) граф, в нём отмечено какое-то подмножество вершин (небольшое) и ещё задана вершина.
можно задать какое-то изначально ограниченное число запросов: по паре вершин говорится, какой наикратчайший путь между ними.
или по трём вершинам наикратчайший путь, проходящий по всем ним.
хочется в итоге найти пару таких отмеченных вершин, что путь проходящий через них и заданную вершину близок к минимальному среди всех таких путей.
где в эту сторону можно почитать?