Нахождение пути с максимальным минимальным весом
чтобы узнать подробности о Утре, Ночи и & amp; В воскресенье, чтобы отобразить над столбцами,
необходимо использовать роль столбца 'tooltip' .
столбец всплывающей подсказки принимает тип данных 'string'.
см. Следующий рабочий фрагмент ...
google.charts.load('current', {
packages: ['corechart']
}).then(function () {
var data = google.visualization.arrayToDataTable([
['Month', 'Boards', {type: 'string', role: 'tooltip'}, 'Chairs', {type: 'string', role: 'tooltip'}, 'Speakers', {type: 'string', role: 'tooltip'}],
['January', 1090, '80 in the Morning\n1,000 in the night\n10 Sundays', 580, '20 in the Morning\n5000 in the night\n60 Sundays', 62, '40 in the Morning\n10 in the night\n12 Sundays'],
['February', 350, '30 in the Morning\n300 in the night\n20 Sundays', 143, '22 in the Morning\n60 in the night\n61 Sundays', 145, '90 in the Morning\n33 in the night\n22 Sundays'],
]);
var chart = new google.visualization.ColumnChart(document.getElementById('chart_div'));
var options = {
colors: ['#ffa726', '#7e57c2', '#7cb342'],
height: 400,
legend: {
position: 'bottom'
},
tooltip: {
trigger: 'both'
}
};
// add selection to make tooltip visible when drawn
google.visualization.events.addListener(chart, 'ready', function () {
chart.setSelection([{row: 0, column: 1}]);
});
chart.draw(data, options);
});
5 ответов
Взгляните на UppercuT. Он приносит большую отдачу, и он делает то, что вы ищете, и многое другое.
UppercuT использует NAnt для сборки, и это безумно простой в использовании Build Framework.
Автоматизированная сборка так же проста, как (1 ) имя решения, (2) путь к исходному контролю, (3) название компании для большинства проектов!
Здесь есть хорошие объяснения: Просто измените их, чтобы они останавливались, когда обнаруживают, что вершины, о которых вы спрашиваете, связаны.
РЕДАКТИРОВАТЬ: Вы запрашиваете максимальный минимум, но ваш пример выглядит так, как будто вы хотите минимальный максимум. В случае максимального минимума алгоритм Краскала не будет работать.
РЕДАКТИРОВАТЬ: Пример в порядке, моя ошибка. Тогда будет работать только алгоритм Прима.
Вы также можете использовать парадигму «двоичного поиска ответа». То есть выполните двоичный поиск по весам, проверяя для каждого веса w , можете ли вы найти путь в графе, используя только ребра с весом больше w .
наибольший w , для которого вы можете (найти с помощью двоичного поиска), дает ответ. Обратите внимание, что вам нужно только проверить, существует ли путь, поэтому просто поиск в ширину / в глубину O (| E |), а не кратчайший путь. Таким образом, это O (| E | * log (max W)) в целом, что сравнимо с O (| E | log | V |) у Дейкстры / Крускала / Прима. не могу сразу увидеть доказательства и для них).
Эту проблему можно решить с помощью алгоритма стиля BFS, однако вам понадобятся два варианта:
- Вместо того, чтобы отмечать каждый узел как «посещенный», вы отмечаете его минимальным весом на пути, по которому вы дошли до него.
Например, если I и J являются соседями, I имеет значение w1, а вес ребра между ними равен w2, тогда J = min (w1, w2).
- Если вы дойдете до отмеченного узла со значением w1, вам может потребоваться отметить и обработать его снова, если присвоено новое значение w2 (и w2> w1). Это необходимо, чтобы убедиться, что вы получили максимум из всех минимумов.
Например, если I и J являются соседями, I имеет значение w1, J имеет значение w2, а вес ребра между ними равен w3, тогда, если min (w2, w3)> w1, вы должны отметить J и снова обработать всех его соседей.
Хорошо, отвечу на мой собственный вопрос здесь, чтобы попытаться получить небольшую обратную связь, которую я получил по предварительному решению, которое я разработал перед публикацией здесь:
Каждый узел хранит «фрагмент пути» , это пока весь путь к самому себе.
0) установить текущую вершину в начальную вершину
1) Сгенерируйте все фрагменты пути из этой вершины и добавьте их в приоритетную очередь
2) Возьмите фрагмент сверху очереди приоритетов и установите текущую вершину в конечную вершину этого пути
3) Если текущая вершина является целевой вершиной, то вернуть путь
4) goto 1
Я не уверен, что это найдет лучший путь, но я думаю, что условие выхода на третьем шаге немного амбициозно. Я не могу придумать лучшего условия выхода, поскольку этот алгоритм не закрывает вершины (на вершину можно ссылаться в любом количестве фрагментов пути), вы не можете просто ждать, пока все вершины закроются (как у Дейкстры для пример)
Вы все еще можете использовать команду Дейкстры!
Вместо использования + используйте оператор min ().
Кроме того, вы захотите сориентировать кучу / priority_queue так, чтобы самые большие вещи были наверху.
Что-то вроде этого должно работать: (я, вероятно, пропустил некоторые детали реализации)
let pq = priority queue of <node, minimum edge>, sorted by min. edge descending
push (start, infinity) on queue
mark start as visited
while !queue.empty:
current = pq.top()
pq.pop()
for all neighbors of current.node:
if neighbor has not been visited
pq.decrease_key(neighbor, min(current.weight, edge.weight))
Гарантируется, что всякий раз, когда вы добраться до узла, по которому вы следовали оптимальным путем (поскольку вы находите все возможности в порядке убывания, и вы никогда не сможете улучшить свой путь, добавив ребро)
Временные границы такие же, как у Дейкстры - O (Vlog (E)) .
РЕДАКТИРОВАТЬ: о, подождите, это в основном то, что вы опубликовали. LOL.