Алгоритм: кратчайший путь между всеми точками
Минималистичный и полнофункциональный подход ES6:
const setCookie = (name, value, days = 7, path = '/') => {
const expires = new Date(Date.now() + days * 864e5).toUTCString()
document.cookie = name + '=' + encodeURIComponent(value) + '; expires=' + expires + '; path=' + path
}
const getCookie = (name) => {
return document.cookie.split('; ').reduce((r, v) => {
const parts = v.split('=')
return parts[0] === name ? decodeURIComponent(parts[1]) : r
}, '')
}
const deleteCookie = (name, path) => {
setCookie(name, '', -1, path)
}
3 ответа
Взгляните на задачу коммивояжера .
Вы можете изучить некоторые из эвристических решений . Они могут не дать вам 100% точных результатов, но часто они могут предложить достаточно хорошие решения (на 2-3% от оптимальных) в разумные сроки.
Очевидно, это проблема коммивояжера . В частности, для N = 10 вы можете либо попробовать наивный алгоритм O (N!) , либо использовать динамическое программирование , вы можете уменьшить его до O (n ^ 2 2 ^ n) , путем обмена.
Кроме того, поскольку это NP-сложная проблема, вы можете надеяться только на приближение или эвристику, учитывая обычные предостережения.
Как уже говорили другие, это экземпляр TSP. Я думаю, что Concord, разработанный в Georgia Tech, является современным решателем. Он может обрабатывать до 10 000 точек в течение нескольких секунд. У него также есть API, с которым легко работать.