Скорость просчета короткого пути

← →
Rentgen © (2006-12-28 11:58) [0]

Всем привет!
Сколько по Вашему мнению должен выполняться просчёт всех самых коротких путей в матрице с 3000 квадратами?
т.е. по результирующе таблице должно быть видно, к примеру из квадрата 705 в 1666 один путь (самый короткий) - 10 км., из 106 в 999 - 5км. итд.
есть отдельная таблица со "связанными" квадратами и соответствующими расстояниями.

***
Взялся за программку писаную не мной. Блин там пересчет расстояний выполняется около ЧАСА! Я чесно сказать ни когда не занимался подобными математическими просчетами, но кажется это слишком долго.

← →
Rentgen © (2006-12-28 11:59) [1]

просто думаю, браться за переделывание алгоритма поиска или нестоит.

← →
Ega23 © (2006-12-28 12:00) [2]

При чём тут "матрица"? Это обход графа с известными длинами рёбер.
"Пути Гамильтона", если мне память не изменяет.

← →
Rentgen © (2006-12-28 12:02) [3]

>>Ega23 © (28.12.06 12:00) [2]
Ясно. А по сабжу?

← →
Rentgen © (2006-12-28 12:34) [4]

Блин. Никто не знает, да? Хотябы предположения...

← →
Ega23 © (2006-12-28 12:38) [5]

> Ясно. А по сабжу?
>

google "алгоритмы поиска путей гамильтона".
Что непонятного-то?

← →
Jeer © (2006-12-28 12:41) [6]

> Сколько по Вашему мнению должен выполняться просчёт всех
> самых коротких путей в матрице с 3000 квадратами?

У меня под боком, например, стоит МВС-15000BM производительностью 10 терафлопс.
На пару секунд задачка.

← →
Rentgen © (2006-12-28 12:42) [7]

>>Ega23 © (28.12.06 12:38) [5]
Ёмаё.
Почему бы вопрос не посмотреть???
Гугли подскажет сколько примерно займёт просчет времени????!

← →
Думкин © (2006-12-28 12:43) [8]

Итоговая таблица, содержит порядка 4,5 миллионов записей?
То есть ищутся короткие пути, для каждой неупорядоченной пары?
Смотря на чем и как считать, но на вскидку 1 час для такого - вполне.

← →
Rentgen © (2006-12-28 12:44) [9]

>>Jeer © (28.12.06 12:41) [6]
Эт конечно круто :)
у меня стандартный ПК.
Cekeron.
1800Ghz
256 Памяти.

Хотя возможны и оптимизации. Если не считать для каждой пары с нуля.

http://lib.custis.ru/index.php/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%BB%D0%BE%D0%B9%D0%B4%D0%B0-%D0%A3%D0%BE%D1%80%D1%88%D0%BE%D0%BB%D0%BB%D0%B0

3000^3=2,7*10^10, столько вот шагов, каждый шаг - сравнение двух чисел, вычисление минимума. Если считать, что выполняется млрд операций в секунду, то получается - сотни секунд, то есть априорная оценка времени - от минут, до десятков минут.

> TUser © (28.12.06 12:55) [11]

> 3000^3=2,7*10^10, столько вот шагов,

Мудренно как-то...

Ega правильно говорил. Мне, например, проще это дело перевести в граф.

Имеем. Граф с 3000 узлами. Значить матрица инцидентности это 3000х3000, что вообщем-то совершенно не много. По моему скромному, алгоритм Дейкстры тут вполне применим. И я не верю, что он будет работать час.

А пардон! Не внимательно прочел, что ищутся все пути. Тады алгоритм Флойда... Но по времени может и час.

Скорость просчета короткого пути Найти похожие ветки