1. дома
  2. Вопрос и ответ
  3. Расчет минимального пути SUM в матрице препятствий?

Расчет минимального пути SUM в матрице препятствий?

2015-02-12 2 views
2

Предположим, у вас есть матрица с препятствиями и несколькими терминалами, как вы находите точку с минимальной суммой пути от этой точки до всех терминалов?Расчет минимального пути SUM в матрице препятствий?

источник

2015-02-12 Pei Zhang

+0

Имеет ли каждая точка положительное значение? Или сумма пути просто означает количество точек? –

+0

Вы можете думать об этом, так как собираетесь создать промежуточную станцию ​​на Марсе, где у вас есть несколько базовых станций (терминалов) и препятствий. Вы хотите минимизировать общий путь от промежуточной станции до всех базовых станций. Таким образом, путь здесь означает, вероятно, расстояние между двумя точками. –

ответ

2
  1. Присвоить 0 до каждой позиции матрицы
  2. Для каждого терминала, т
    1. ли в ширину первого обхода матрицы
    2. Каждое приращение узла обхода текущей позиции матрица с текущей глубины (текущая длина до t)
  3. Сканирование по матрице для позиция с наименьшим значением (сумма расстояний до каждого терминала)

источник

2015-02-12 09:38:57 aioobe

+0

Это действительно здорово! Сложность времени будет knm, k - количество терминалов, а n, m - размеры матрицы. И, кроме того, можно ли использовать более эффективный алгоритм для поиска в матрице для самого низкого значения? –

+1

Я не думаю, что окончательный поиск минимального значения имеет большое значение по сравнению с вычислениями, сделанными на предыдущем шаге. (Пожалуйста, рассмотрите [принятие] (http://meta.stackexchange.com/questions/5234/how-does-accepting-an-answer-work) этот ответ, если он отвечает на ваш вопрос.) – aioobe

Смежные вопросы

 Смежные вопросы