我正试图解决这个卡塔：
给定一个整数N(<1000)，返回一个整数1..N的数组，其中每两个连续数字的和都是一个完美的平方。如果不可能，请返回
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
}
起初，我使用的是一个哈希表，每个键上都有一个相邻节点的数组。但是，当我的算法必须从对象中删除顶点时，它必须多次查找数组中的元素，每次都需要线性时间。我使相邻的顶点可以散列，这提高了我的执行时间。然后我寻找具有此功能的路径：
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
}
我的解决方案运行得很快，但还不够快。我需要在不到12秒内通过200多项测试，而到目前为止，我只通过了150项。也许我的算法和JS的使用都可以改进，所以，我的问题是：
你能看到代码中的瓶颈吗？排序步骤应该花费更多的时间，但它也能让我更快地找到解决方案。此外，我不确定我是否使用了最好的数据结构来解决这类问题。我尝试了经典的循环而不是使用
for..in和for..of，但它并没有改变性能。你看到有什么地方可以保存以前的计算，以便以后查找吗？
关于最后一个问题，我读到有一个问题的动态解决方案，但无论我在哪里找到，它都会寻找最小距离、路径数或路径的存在，而不是路径本身。我到处都读到这个，但我无法应用它：
此外，Bellman、Held和Karp的动态规划算法可以用于在时间O(n22n)内求解该问题。在这种方法中，对于每个顶点集合S和S中的每个顶点v，确定是否存在一条完全覆盖S中顶点并终止于v的路径。对于S和v的每个选择，(S，v)存在一条路径，当且仅当v具有邻居w，使得(S−v，w)存在一个路径，该路径可以从动态程序中已经计算的信息中查找。
如果我不寻找所有的路径，我就是不知道如何实现它。我在python中发现了一个类似问题的实现，它使用了缓存和一些二进制文件，但同样，我可以从py中翻译它，但我不确定如何将这些概念应用到我的算法中。
我目前没有什么想法，所以任何尝试的暗示都会非常有帮助。
编辑1:
在Photon评论之后，我尝试重新使用图的哈希表，将相邻顶点存储为数组。还添加了一个单独的布尔数组来跟踪剩余的顶点。
这大大提高了我的效率。通过这些更改，我避免了一直将对象键转换为数组的需要，无需复制图形对象，因为它不会被修改，也无需在向路径添加一个节点后循环。糟糕的是，在排序时，我需要检查那个单独的对象，以检查哪些相邻的顶点仍然可用。此外，在将数组传递给下一个递归之前，我必须对它们进行筛选。
从使用数组存储相邻顶点并通过索引访问它们的第一个答案开始，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:
代码在大多数情况下都表现良好，但我最糟糕的情况很糟糕：
// time for 51: 30138.229ms
// time for 77: 145214.155ms
// time for 182: 22964.025ms
编辑3:
我接受了Yosef的回答，因为它对提高JS代码的效率非常有用。找到了一种调整算法的方法，使用本文中的一些限制来避免有死胡同的路径。汉密尔顿路径和电路的搜索过程。。
基本上，在调用另一个递归之前，我检查两件事：
- 如果有任何没有边的节点到目前为止都不是路径的一部分，并且路径缺少超过1个节点
- 如果有两个以上的节点有一条边(一个可以是下一个节点，在将边删除到当前节点之前有两条边，另一个可以为最后一个节点)
这两种情况都使得不可能找到具有剩余节点和边的哈密顿路径(如果你绘制图，原因就会很清楚)。根据这一逻辑，如果检查只有2条边的节点(1条进入，另一条离开)，还有另一个改进。我想你可以提前用它来删除其他边缘，但至少对我来说没有必要
现在，该算法在大多数情况下表现更差，仅按剩余边排序就足以预测下一个节点，并增加了额外的工作，但它能够在更好的时间内解决最坏的情况。例如，limit = 77在15ms内解决，但limit=1000从30ms到100ms。
这是一篇很长的帖子，如果你有任何编辑建议，请告诉我。考虑到在解决卡塔之前不能检查平台中的解决方案，我不认为发布最终代码是最好的主意。但公认的答案和最后的编辑应该是一个很好的建议，在学习的同时思考最后一部分。希望它有用。
通过用数组替换对象，您可以避免在每次想要查找长度时(在排序算法的任何步骤中都要做很多工作)，或者在想要获取下一个候选者的键时，将对象转换为数组。在我的测试中，下面的代码在执行时间方面更加有效(我的机器上limit=4500的0.102s与1.078s)
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].push(dif)
} 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
}
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 adjacentsCopy[a].length - 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 of adjacents[candidate]) {
adjacentsCopy[candidateAdjacent] = adjacentsCopy[candidateAdjacent].filter(t=>t!== candidate)
}
if (getSolution(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 of adjacents[candidate]) {
adjacentsCopy[candidateAdjacent].push(candidate);
}
}
return false
}
const endSolution = getSolution(
Array.from(Array(limit).keys()).slice(1)
)
// The elements of the path can't be strings
return endSolution
}
var t = new Date().getTime();
var res = findSquarePathInRange(4500);
var t2 = new Date().getTime();
console.log(res, ((t2-t)/1000).toFixed(4)+'s');