Неверные результаты для среднего расстояния с использованием Dijkstra (Java) - PullRequest
Новая
       10

Неверные результаты для среднего расстояния с использованием Dijkstra (Java)

1 голос
/ 09 июля 2010

График не взвешен, элемент массива соседей HashSets [] является узлом соседей [1] является узел 1 (они начинаются с 0, обратите внимание) с его уникальными соседними узлами, скажем, 2 3 4 5. (таким образом, соседи [5] будут содержать 1). И у меня есть следующий метод, который я сделал с большой помощью, так как я не получаю алгоритм намного выше теории. Возвращаемое число должно быть средним расстоянием между двумя узлами на графике.

Представьте, что у меня есть следующий график (узел: in_links | out_links; соседей [] не содержит циклов 0 в узле 0 и не имеет дубликатов, как я уже сказал.) 

0: 0 0 0 | 0 0 0 1 1 1 2 3 5 6 7 7 8 8 9 9 11 
1: 0 0 0 | 2 2 3 4 4 5 6 8 
2: 0 1 1 | 3 
3: 0 1 2 | 4 9 
4: 1 1 3 | 5 12 
5: 0 1 4 | 6 7 10 
6: 0 1 5 | 10 11 12 
7: 0 0 5 | 
8: 0 0 1 | 10 
9: 0 0 3 | 12 
10: 5 6 8 | 11 
11: 0 6 10 | 
12: 4 6 9 |

И для этого тривиального графика возвращаемое расстояние составляет 5.781686749230769E8?!?! код: 

    public double getAvgDistance() {
    double total = 0;
    int[] dist = new int[n];
    ArrayList<Integer> Q = new ArrayList<Integer>();
    int tmp, index = 0, w = 0;

    for (int u=0; u<n; u++) {
        System.out.print("Avg Dist at "+u+"\r");
        // Initialise Q and dist for this iteration
        for (int v=u+1; v<n; v++) {
            Q.add(v);

            if (neighbours[u].contains(v)) {
                dist[v] = 1;
            } else {
                dist[v] = Integer.MAX_VALUE;
            }
        }

        while (!Q.isEmpty()) {

            tmp = dist[0];
            for (int e=1; e<Q.size(); e++) {
                if (dist[e] < tmp) {
                    w = Q.get(e);
                    tmp = dist[w]; // smallest dist is for this element w so far
                    index = e;
                }
            }
            Q.remove(index);

            for (int z : neighbours[w]) {
                if ( Q.contains(z)
                        && (dist[w]+1 < dist[z]) ) {

                    dist[z] = dist[w]+1;
                }
            }

        } // while end

        for (int v = u+1; v < n; v++ ) {
            total += dist[v];
        }

    } // for 0-n end

    return total /= (double)(n*(n-1)/2);
}

У меня нет большого опыта в кастинге или печати реальных чисел, поэтому я надеюсь, что это как-то связано с ними! Все комментарии приветствуются

Ответы [ 3 ]

1 голос
/ 11 июля 2010

Если я правильно понимаю ваш вопрос, узлы 7, 11 и 12 не имеют внешних ссылок и, следовательно, не имеют действительных путей к другим узлам.

Ваш алгоритм принудительно задает путь, вставляя ссылку со стоимостьюInteger.MAX_VALUE в этих случаях?Если это так, это объяснило бы, почему у вас такая высокая средняя стоимость.

Мне также хотелось бы знать, будет ли лучше оценивать как прямой, так и обратный пути.В ориентированном графе стоимость пути AB не обязательно равна стоимости пути BA.С вашим текущим алгоритмом вычисляется стоимость каждого пути, заканчивающегося в узле 12, но пути, начинающиеся в узле 12, не оцениваются.

0 голосов
/ 11 июля 2010

Я только догадываюсь, но я вижу, что расстояния иногда устанавливаются на Integer.MAX_VALUE. Если эти числа фактически входят в результат, а затем делятся на один или два фактора из 10, это очень хорошо объясняет, почему среднее значение намного, намного больше, чем ожидалось, и примерно в том же приблизительном значении, что и MAX_VALUE.

Это нормально иметь это большое значение в вашем графике, когда оно используется для определения кратчайшего пути среди альтернатив, но как только вы дойдете до точки, где вы определяете фактические расстояния, это число должно пройти!

Либо у вас есть длина пути в приблизительном значении MAX_VALUE, которая говорит, что пути нет. Эта длина пути, следовательно, не входит в ваш средний. Либо длина вашего пути представляет собой небольшое целое число с той же величиной, что и ваши расстояния в графике, тогда она действительна и вы можете включить ее в свои вычисления.

Урок, который следует извлечь из этого: просто потому, что число пришло из компьютерной программы, но это не значит, что оно заслуживает доверия или правильно!

0 голосов
/ 09 июля 2010

Я не уверен, полностью ли я понимаю ваш вопрос, но, похоже, у вас могут возникнуть проблемы с тем значением, которое вы печатаете, которое не соответствует вашим ожиданиям. Я подозреваю, что проблема может быть, когда вы печатаете значение double. Всякий раз, когда вы конвертируете double напрямую в String, я знаю, что вы можете получить неожиданные результаты.

Этот пост предлагает использовать BigDecimal вместо double для поддержания точности: Сохранение точности с двойным в Java

Так что, возможно, попробуйте сделать что-то вроде следующего и посмотреть, если у вас есть лучшие результаты. 

BigDecimal.valueOf(<your double value here>).toPlainString();
...