Я пытаюсь решить это ката:
Учитывая целое число N (<1000), вернуть массив целых чисел 1..N, где сумма каждых 2 последовательных чисел является идеальным квадрат. Если это невозможно, верните <code>false.
Например, если N=15, результатом должен быть этот массив: [9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8]. Ниже N=14 ответа нет, поэтому функция должна вернуть false.
Я подумал: "Насколько это может быть сложно?" и это были долгие дни в кроличьей норе. Я программировал всего несколько месяцев, и у меня нет опыта работы с CS, поэтому я напишу, насколько я понимаю, проблему, пытаясь использовать правильные концепции, но, пожалуйста, не стесняйтесь сказать мне, если какое-либо выражение не является правильно.
Очевидно, эта проблема очень похожа на известную в теории графов проблему, называемую TSP . В этом случае вершины связны, если их сумма является идеальным квадратом. Кроме того, мне не нужно искать цикл, просто найдите один гамильтонов путь , а не все.
Я понимаю, что я использую откат назад. Я строю объект, который представляет график, а затем пытаюсь найти путь рекурсивно. Вот как я строю объект:
function buildAdjacentsObject (limit) {
const potentialSquares = getPotentialSquares(limit)
const adjacents = {}
for (let i = 0; i < (limit + 1); i++) {
adjacents[i] = {}
for (let j = 0; j < potentialSquares.length; j++) {
if (potentialSquares[j] > i) {
const dif = potentialSquares[j] - i
if (dif <= limit) {
adjacents[i][dif] = 1
} else {
break
}
}
}
}
return adjacents
}
function getPotentialSquares (limit) {
const maxSum = limit * 2 - 1
let square = 4
let i = 3
const potentialSquares = []
while (square <= maxSum) {
potentialSquares.push(square)
square = i * i
i++
}
return potentialSquares
}
Сначала я использовал таблицу ha sh с массивом смежных узлов на каждом ключе. Но когда моему алгоритму пришлось удалять вершины из объекта, ему приходилось искать элементы в массивах несколько раз, что каждый раз занимало линейное время. Я сделал смежные вершины хэшируемыми, и это улучшило мое время выполнения. Затем я ищу путь с помощью этой функции:
function findSquarePathInRange (limit) {
// Build the graph object
const adjacents = buildAdjacentsObject(limit)
// Deep copy the object before making any changes
const adjacentsCopy = JSON.parse(JSON.stringify(adjacents))
// Create empty path
const solution = []
// Recursively complete the path
function getSolution (currentCandidates) {
if (solution.length === limit) {
return solution
}
// Sort the candidate vertices to start with the ones with less adjacent vert
currentCandidates = currentCandidates.sort((a, b) => {
return Object.keys(adjacentsCopy[a]).length -
Object.keys(adjacentsCopy[b]).length
})
for (const candidate of currentCandidates) {
// Add the candidate to the path
solution.push(candidate)
// and delete it from the object
for (const candidateAdjacent in adjacents[candidate]) {
delete adjacentsCopy[candidateAdjacent][candidate]
}
if (getSolution(Object.keys(adjacentsCopy[candidate]))) {
return solution
}
// If not solution was found, delete the element from the path
solution.pop()
// and add it back to the object
for (const candidateAdjacent in adjacents[candidate]) {
adjacentsCopy[candidateAdjacent][candidate] = 1
}
}
return false
}
const endSolution = getSolution(
Array.from(Array(limit).keys()).slice(1)
)
// The elements of the path can't be strings
return (endSolution) ? endSolution.map(x => parseInt(x, 10)) : false
}
Мое решение работает «быстро», но недостаточно быстро. Мне нужно пройти более 200 тестов менее чем за 12 секунд, и пока он проходит только 150. Возможно, мой алгоритм и использование JS могут быть улучшены, поэтому мои вопросы:
-
Вы видите узкое место в коде? Шаг сортировки должен занимать больше времени, но он также помогает быстрее найти решение. Кроме того, я не уверен, использую ли я лучшую структуру данных для такого рода проблем. Я попытался использовать цикл c вместо того, чтобы использовать for..in и for..of, но это не изменило производительность.
Вы видите место, где я могу сохранить предыдущие вычисления в искать их позже?
Что касается последнего вопроса, я читал, что есть динамическое c решение проблемы, но везде, где я его нашел, он ищет минимальное расстояние, количество пути или существование пути, а не сам путь. Я читаю это везде, но я не могу применить это:
Кроме того, динамический c алгоритм программирования Беллмана, Хелда и Карпа может быть использован для решения проблемы во времени O (n2 2n). В этом методе для каждого набора S вершин и каждой вершины v в S определяется, существует ли путь, который точно покрывает вершины в S и заканчивается в v. Для каждого выбора S и v существует путь для ( S, v) тогда и только тогда, когда v имеет соседа w, так что существует путь для (S - v, w), который можно найти по уже вычисленной информации в программе Dynami c.
Я просто не могу понять, как это реализовать, если я не ищу все пути. Я обнаружил эту реализацию аналогичной проблемы в python, которая использует кэш и некоторый двоичный файл, но, опять же, я мог бы перевести его из py, но я не уверен, как применить эти концепции к моему алгоритму.
В настоящее время у меня нет идей, поэтому любой намек на то, что можно попробовать, будет очень полезным.
РЕДАКТИРОВАТЬ 1:
После комментария Фотона я попытался вернуться к использованию таблицы ha sh для графа, сохраняя соседние вершины в виде массивов. Также добавлен отдельный массив bools для отслеживания оставшихся вершин.
Это значительно улучшило мою эффективность. Благодаря этим изменениям я избежал необходимости постоянно преобразовывать ключи объекта в массивы, не нужно копировать объект графа, поскольку он не будет изменен, и не нужно l oop после добавления одного узла в путь. Плохо то, что тогда мне нужно было проверить этот отдельный объект при сортировке, чтобы проверить, какие смежные вершины все еще были доступны. Кроме того, мне пришлось отфильтровать массивы, прежде чем передавать их в следующую рекурсию.
Подход Yosef с первого ответа об использовании массива для хранения соседних вершин и доступа к ним по индексу оказывается еще более эффективным. Мой код пока (без изменений в функции поиска квадратов):
function square_sums_row (limit) {
const adjacents = buildAdjacentsObject(limit)
const adjacentsCopy = JSON.parse(JSON.stringify(adjacents))
const solution = []
function getSolution (currentCandidates) {
if (solution.length === limit) {
return solution
}
currentCandidates = currentCandidates.sort((a, b) => {
return adjacentsCopy[a].length - adjacentsCopy[b].length
})
for (const candidate of currentCandidates) {
solution.push(candidate)
for (const candidateAdjacent of adjacents[candidate]) {
adjacentsCopy[candidateAdjacent] = adjacentsCopy[candidateAdjacent]
.filter(t => t !== candidate)
}
if (getSolution(adjacentsCopy[candidate])) {
return solution
}
solution.pop()
for (const candidateAdjacent of adjacents[candidate]) {
adjacentsCopy[candidateAdjacent].push(candidate)
}
}
return false
}
return getSolution(Array.from(Array(limit + 1).keys()).slice(1))
}
function buildAdjacentsObject (limit) {
const potentialSquares = getPotentialSquares(limit)
const squaresLength = potentialSquares.length
const adjacents = []
for (let i = 1; i < (limit + 1); i++) {
adjacents[i] = []
for (let j = 0; j < squaresLength; j++) {
if (potentialSquares[j] > i) {
const dif = potentialSquares[j] - i
if (dif <= limit) {
adjacents[i].push(dif)
} else {
break
}
}
}
}
return adjacents
}
РЕДАКТИРОВАТЬ 2:
В большинстве случаев код работает нормально, но мой наихудший сценарий ios сосать:
// time for 51: 30138.229ms
// time for 77: 145214.155ms
// time for 182: 22964.025ms
РЕДАКТИРОВАТЬ 3:
Я принял ответ Йосефа, так как он был очень полезен для повышения эффективности моего JS код. Нашел способ настроить алгоритм, чтобы избежать путей с тупиками, используя некоторые ограничения из этой статьи Процедура поиска путей и цепей Гамильтона. .
По существу, перед вызовом другой рекурсии, Я проверяю 2 вещи:
- Если есть какой-либо узел без ребер, который до сих пор не является частью пути, и путь отсутствует более 1 узла
- Если их было больше, чем 2 узла с 1 ребром (один может следовать за узлом, у которого было 2 ребра до удаления ребра в текущем узле, а другой может быть последним узлом)
В обеих ситуациях невозможно найти Гамильтонов путь с оставшимися узлами и ребрами (если вы нарисуете граф, будет понятно почему). После этой логики c есть еще одно улучшение, если вы проверяете узлы только с 2 ребрами (1 способ войти, а другой - к go). Я думаю, что вы можете использовать это, чтобы удалить другие ребра заранее, но это не было необходимо, по крайней мере, для меня.
Теперь алгоритм работает хуже в большинстве случаев, когда простая сортировка по оставшимся ребрам была достаточно хороша, чтобы предсказать добавлен следующий узел и дополнительная работа, но она способна решить наихудшие случаи в гораздо лучшее время. Например, limit = 77 это решается за 15 мс, но limit=1000 изменилось с 30 мс до 100 мс.
Это очень длинный пост, если у вас есть какие-либо предложения по редактированию, дайте мне знать. Я не думаю, что публикация окончательного кода - это лучшая идея, учитывая, что вы не можете проверить решения в платформе до решения ката. Но принятый ответ и это окончательное редактирование должны быть хорошим советом, чтобы подумать об этой последней части, все еще изучая что-то. Надеюсь, это полезно.