Алгоритм: минимальный путь чередования цветов
http://bl.ocks.org/eyaler/10586116 См. этот код, это чтение из файла и создание графика. У меня также была та же проблема, но позже я выяснил, что проблема была в json-файле, который я использовал (дополнительная запятая). Если вы получаете нуль, попробуйте напечатать ошибку, которую вы получаете, как это может быть.
d3.json("filename.json", function(error, graph) {
alert(error)
})Это работает в firefox, в хром как-то его не печатает ошибку.
1 ответ
В комментариях упоминается использование алгоритма Дейкстры, и на самом деле есть способ сделать эту работу. Если мы создадим новую «корневую» вершину в графе и соединим каждую другую вершину с ним направленным ребром, мы сможем запустить модифицированный алгоритм Дейкстры от корня наружу, который завершится, когда инверсии данного пути превысят n. Важно отметить, что мы должны разрешить повторное посещение каждой вершины в реализации, поэтому ключ каждой вершины в нашей очереди приоритетов будет не просто node_id, а кортежем (node_id, inversion_count), представляющим эту вершину на ее i -ой визит. При этом мы неявно делаем n копий каждой вершины, по одной на каждое потенциальное посещение. Визуально мы фактически делаем n копии нашего графа и переводим ребра между каждой (black_vertex, white_vertex) парой для соединения между i и i+1 -ым графами инверсии. Мы запускаем алгоритм, пока не достигнем пути с n инверсиями. В качестве альтернативы, мы можем соединить каждую вершину на n -ом графе инверсии с «вершиной» вершины и запустить любой обычный алгоритм поиска пути на этом графе без изменений. Это будет выполнено в O(n(E + Vlog(nV))) время. Вы можете оптимизировать это довольно сильно, а также рассмотреть возможность использования A * вместо эвристики smallest_inversion_weight * (n - inversion_count).
Кроме того, меня поразила другая идея, касающаяся использования знаний об требовании инверсии для ускорения поиска, но я не смог найти способ реализовать его без превышения времени O(V^2). Идея состоит в том, что вы можете использовать цепочку сложений (например, двоичное возведение в степень), чтобы разложить кратчайший n -инверсионный путь на два меньших пути, а также промыть и повторить в режиме «разделяй и властвуй». Проблема в том, что вам нужно будет построить таблицы для кратчайшего пути i -инверсии из любых двух вершин, которые будут O(V^2) записей на i и O(V^2logn) в целом. Чтобы построить каждую таблицу, для каждой записи в предыдущей таблице вам нужно добавить V других путей, так что это будет O(V^3logn) время в целом. Может быть, кто-то еще найдет способ объединить эти две идеи в алгоритм времени O((logn)(E + Vlog(Vlogn))) или что-то в этом роде.