寻找具有 Javascript 的汉密尔顿路径。如何提高效率？
Finding a hamiltonian path with Javascript. How to improve efficiency?
我正在尝试解决这个问题：
Given an integer N (<1000), return an array of integers 1..N where the sum of each 2 consecutive numbers is a perfect square. If that's not possible, return false.
例如，如果N=15，结果应该是这个数组：[9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8]。 N=14以下没有答案，所以函数应该returnfalse.
我想 'how hard can this be?' 并且在兔子洞里呆了很长时间。我编程才几个月，没有 CS 背景，所以我会尝试使用正确的概念写下我到目前为止对问题的理解，但请随时告诉我是否有任何表达式不是正确。
显然，这个问题与图论中一个名为 TSP. In this case, the vertices are connected if the sum of them is a perfect square. Also, I don't have to look for a cycle, just find one Hamiltonian Path 的已知问题非常相似，但并非全部。
我知道我使用的是回溯。我构建了一个表示图形的对象，然后尝试递归地查找路径。这就是我构建对象的方式：
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
}
起初我使用散列table，每个键上有一个相邻节点数组。但是当我的算法必须从对象中删除顶点时，它必须多次在数组中查找元素，每次都花费线性时间。我使相邻的顶点可散列，从而缩短了我的执行时间。然后我用这个函数寻找路径：
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
}
我的解决方案有效 'fast'，但速度不够快。我需要在不到 12 秒内通过 200 多个测试，到目前为止它只通过了 150。可能我的算法和我对 JS 的使用都可以改进，所以，我的问题：
你能看出代码中的瓶颈吗？排序步骤应该花费更多时间，但它也让我更快地找到解决方案。另外，我不确定我是否使用了最好的数据结构来解决这类问题。我尝试了经典循环而不是使用 for..in 和 for..of 但它并没有改变性能。
你有没有看到我可以保存以前的计算以供以后查找的地方？
关于最后一个问题，我读到这个问题有一个动态的解决方案，但我到处都找到了一个，它寻找最小距离、路径数或路径的存在，而不是路径本身。我到处都读到这个，但我无法应用它：
Also, a dynamic programming algorithm of Bellman, Held, and Karp can be used to solve the problem in time O(n2 2n). In this method, one determines, for each set S of vertices and each vertex v in S, whether there is a path that covers exactly the vertices in S and ends at v. For each choice of S and v, a path exists for (S,v) if and only if v has a neighbor w such that a path exists for (S − v,w), which can be looked up from already-computed information in the dynamic program.
如果我不寻找所有路径，我就不知道如何实现它。我在 python 中发现了类似问题的 this 实现，它使用了缓存和一些二进制文件，但同样，我可以从 py 翻译它，但我不确定如何将这些概念应用到我的算法中。
我目前没有想法，所以任何可以尝试的提示都会非常有帮助。
编辑 1：
在 Photon 发表评论后，我尝试返回到对图形使用散列 table，将相邻顶点存储为数组。还添加了一个单独的布尔数组来跟踪剩余的顶点。
这大大提高了我的效率。通过这些更改，我避免了一直将对象键转换为数组的需要，不需要复制图形对象，因为它不会被修改，也不需要在向路径添加一个节点后循环。糟糕的是，我需要在排序时检查那个单独的对象，以检查哪些相邻顶点仍然可用。另外，我必须在将数组传递给下一个递归之前过滤它们。
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 代码的效率非常有用。使用本文 A Search Procedure for Hamilton Paths and Circuits..
中的一些限制找到了一种调整算法以避免路径死胡同的方法
基本上，在调用另一个递归之前，我检查了两件事：
- 如果有任何没有边的节点到现在为止还不是路径的一部分，并且路径缺少超过 1 个节点
- 如果有2个以上的节点有1条边（一个可以是后面的节点，那个在删除到当前节点的边之前有2条边，其他的可以是最后一个节点）
这两种情况都使得无法找到具有剩余节点和边的哈密顿路径（如果绘制图形就会清楚原因）。按照这个逻辑，如果您检查只有 2 条边的节点（一种进入方式和另一种方式出去），则会有另一项改进。我想你可以用它来提前删除其他边缘，但至少对我来说没有必要。
现在，该算法在大多数情况下表现更差，其中仅按剩余边排序就足以预测下一个节点并添加了额外的工作，但它能够在更短的时间内解决最坏的情况。例如，limit = 77 它在 15 毫秒内解决了，但 limit=1000 从 30 毫秒变成了 100 毫秒。
这篇文章很长post，如果您有任何编辑建议，请告诉我。我不认为 post 考虑到在解决套路之前您无法在平台中检查解决方案，因此最好使用最终代码。但是接受的答案和这个最终编辑应该是在学习一些东西的同时思考最后一部分的好建议。希望它有用。
通过用数组替换对象，您可以避免每次要查找长度（您经常这样做 - 在排序算法的任何步骤中）或需要时将对象转换为数组为下一位候选人获取钥匙。在我的测试中，下面的代码在执行时间方面更有效 lot
（0.102s vs 1.078s 对于 limit=4500 在我的机器上）
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');
我正在尝试解决这个问题：
Given an integer N (<1000), return an array of integers 1..N where the sum of each 2 consecutive numbers is a perfect square. If that's not possible, return
false.
例如，如果N=15，结果应该是这个数组：[9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8]。 N=14以下没有答案，所以函数应该returnfalse.
我想 'how hard can this be?' 并且在兔子洞里呆了很长时间。我编程才几个月，没有 CS 背景，所以我会尝试使用正确的概念写下我到目前为止对问题的理解，但请随时告诉我是否有任何表达式不是正确。
显然，这个问题与图论中一个名为 TSP. In this case, the vertices are connected if the sum of them is a perfect square. Also, I don't have to look for a cycle, just find one Hamiltonian Path 的已知问题非常相似，但并非全部。
我知道我使用的是回溯。我构建了一个表示图形的对象，然后尝试递归地查找路径。这就是我构建对象的方式：
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
}
起初我使用散列table，每个键上有一个相邻节点数组。但是当我的算法必须从对象中删除顶点时，它必须多次在数组中查找元素，每次都花费线性时间。我使相邻的顶点可散列，从而缩短了我的执行时间。然后我用这个函数寻找路径：
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
}
我的解决方案有效 'fast'，但速度不够快。我需要在不到 12 秒内通过 200 多个测试，到目前为止它只通过了 150。可能我的算法和我对 JS 的使用都可以改进，所以，我的问题：
你能看出代码中的瓶颈吗？排序步骤应该花费更多时间，但它也让我更快地找到解决方案。另外，我不确定我是否使用了最好的数据结构来解决这类问题。我尝试了经典循环而不是使用
for..in和for..of但它并没有改变性能。你有没有看到我可以保存以前的计算以供以后查找的地方？
关于最后一个问题，我读到这个问题有一个动态的解决方案，但我到处都找到了一个，它寻找最小距离、路径数或路径的存在，而不是路径本身。我到处都读到这个，但我无法应用它：
Also, a dynamic programming algorithm of Bellman, Held, and Karp can be used to solve the problem in time O(n2 2n). In this method, one determines, for each set S of vertices and each vertex v in S, whether there is a path that covers exactly the vertices in S and ends at v. For each choice of S and v, a path exists for (S,v) if and only if v has a neighbor w such that a path exists for (S − v,w), which can be looked up from already-computed information in the dynamic program.
如果我不寻找所有路径，我就不知道如何实现它。我在 python 中发现了类似问题的 this 实现，它使用了缓存和一些二进制文件，但同样，我可以从 py 翻译它，但我不确定如何将这些概念应用到我的算法中。
我目前没有想法，所以任何可以尝试的提示都会非常有帮助。
编辑 1：
在 Photon 发表评论后，我尝试返回到对图形使用散列 table，将相邻顶点存储为数组。还添加了一个单独的布尔数组来跟踪剩余的顶点。
这大大提高了我的效率。通过这些更改，我避免了一直将对象键转换为数组的需要，不需要复制图形对象，因为它不会被修改，也不需要在向路径添加一个节点后循环。糟糕的是，我需要在排序时检查那个单独的对象，以检查哪些相邻顶点仍然可用。另外，我必须在将数组传递给下一个递归之前过滤它们。
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 代码的效率非常有用。使用本文 A Search Procedure for Hamilton Paths and Circuits..
中的一些限制找到了一种调整算法以避免路径死胡同的方法基本上，在调用另一个递归之前，我检查了两件事：
- 如果有任何没有边的节点到现在为止还不是路径的一部分，并且路径缺少超过 1 个节点
- 如果有2个以上的节点有1条边（一个可以是后面的节点，那个在删除到当前节点的边之前有2条边，其他的可以是最后一个节点）
这两种情况都使得无法找到具有剩余节点和边的哈密顿路径（如果绘制图形就会清楚原因）。按照这个逻辑，如果您检查只有 2 条边的节点（一种进入方式和另一种方式出去），则会有另一项改进。我想你可以用它来提前删除其他边缘，但至少对我来说没有必要。
现在，该算法在大多数情况下表现更差，其中仅按剩余边排序就足以预测下一个节点并添加了额外的工作，但它能够在更短的时间内解决最坏的情况。例如，limit = 77 它在 15 毫秒内解决了，但 limit=1000 从 30 毫秒变成了 100 毫秒。
这篇文章很长post，如果您有任何编辑建议，请告诉我。我不认为 post 考虑到在解决套路之前您无法在平台中检查解决方案，因此最好使用最终代码。但是接受的答案和这个最终编辑应该是在学习一些东西的同时思考最后一部分的好建议。希望它有用。
通过用数组替换对象，您可以避免每次要查找长度（您经常这样做 - 在排序算法的任何步骤中）或需要时将对象转换为数组为下一位候选人获取钥匙。在我的测试中，下面的代码在执行时间方面更有效 lot
（0.102s vs 1.078s 对于 limit=4500 在我的机器上）
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');