javascript - 哈密顿路径
问题描述
注意: 虽然我设法找到的大多数数学论文和 SO 主题要么与回答“哈密顿路径/循环是否存在”问题有关,要么致力于寻找哈密顿循环,但我的问题略有不同 - 我需要找出顶点,哈密顿路径通过
我已经建立了以下表示的邻接矩阵(顶点索引为 1):
const vertexes = [ { vertex: 1, peers: [ 3, 8, 15 ] },
{ vertex: 2, peers: [ 7, 14, 23 ] },
{ vertex: 3, peers: [ 1, 6, 13, 22 ] },
{ vertex: 4, peers: [ 5, 12, 21 ] },
{ vertex: 5, peers: [ 4, 11, 20 ] },
{ vertex: 6, peers: [ 3, 10, 19 ] },
{ vertex: 7, peers: [ 2, 9, 18 ] },
{ vertex: 8, peers: [ 1, 17 ] },
{ vertex: 9, peers: [ 7, 16 ] },
{ vertex: 10, peers: [ 6, 15 ] },
{ vertex: 11, peers: [ 5, 14 ] },
{ vertex: 12, peers: [ 4, 13 ] },
{ vertex: 13, peers: [ 3, 12, 23 ] },
{ vertex: 14, peers: [ 2, 11, 22 ] },
{ vertex: 15, peers: [ 1, 10, 21 ] },
{ vertex: 16, peers: [ 9, 20 ] },
{ vertex: 17, peers: [ 8, 19 ] },
{ vertex: 18, peers: [ 7 ] },
{ vertex: 19, peers: [ 6, 17 ] },
{ vertex: 20, peers: [ 5, 16 ] },
{ vertex: 21, peers: [ 4, 15 ] },
{ vertex: 22, peers: [ 3, 14 ] },
{ vertex: 23, peers: [ 2, 13 ] } ]
接下来,从顶点 18 作为根和paths
数组开始,包含单个 path [[18]]
,我尝试改变该数组,将其替换为包含原始路线(如果不是死路)的临时副本,向前迈出一步,直到没有潜在的路线或路径找到长度n
(顶点总数):
while(paths.length>0){
let tempPath = [];
for(path of paths){
const nextSteps = vertexes.find(({vertex}) => vertex == path[path.length-1]).peers.filter(v => !path.includes(v));
if(!nextSteps.length) continue;
else if(path.length == n-1) return [...path, nextSteps[0]];
else nextSteps.forEach(step => tempPath.push([...path,step]));
}
paths = tempPath;
}
所以,问题是上面的代码永远不会退出循环,也没有[18, 7, 9, 16, 20, 5, 11, 14, 22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 23, 2]
返回所需的输出()。
您对上述代码为何失败以及如何修复它以返回预期输出的想法将不胜感激。
编辑:感谢@DavidSampson 和@trincot 指出我的拼写错误,我的代码现在可以工作了:
while(paths.length>0){
let tempPath = [];
for(let path of paths){
const nextSteps = vertexes.find(({vertex}) => vertex == path[path.length-1]).peers.filter(v => !path.includes(v));
if(!nextSteps.length) continue;
else if(path.length == n-1) return [...path, nextSteps[0]];
else tempPath.push(...nextSteps.map(v => [...path,v]));
}
paths = tempPath;
}
现在性能是我最关心的问题,关于如何改进有什么建议吗?
解决方案
主要问题是拼写错误,如果您使用严格模式,则可以避免该错误:
改变:
path = tempPath;
到:
paths = tempPath;
还要声明你的变量。像这儿:
for (let path of paths) {
// ^^^^
然后它对我有用:
"use strict";
function hamiltonian(vertexes, start) {
let n = vertexes.length;
let paths = [[start]];
while(paths.length>0) {
let tempPath = [];
for(let path of paths){
const nextSteps = vertexes.find(({vertex}) => vertex == path[path.length-1]).peers.filter(v => !path.includes(v));
if(!nextSteps.length) continue;
else if(path.length == n-1) return [...path, nextSteps[0]];
else nextSteps.forEach(step => tempPath.push([...path,step]));
}
paths = tempPath;
}
}
const vertexes = [ { vertex: 1, peers: [ 3, 8, 15 ] },{ vertex: 2, peers: [ 7, 14, 23 ] },{ vertex: 3, peers: [ 1, 6, 13, 22 ] },{ vertex: 4, peers: [ 5, 12, 21 ] },{ vertex: 5, peers: [ 4, 11, 20 ] },{ vertex: 6, peers: [ 3, 10, 19 ] },{ vertex: 7, peers: [ 2, 9, 18 ] },{ vertex: 8, peers: [ 1, 17 ] },{ vertex: 9, peers: [ 7, 16 ] },{ vertex: 10, peers: [ 6, 15 ] },{ vertex: 11, peers: [ 5, 14 ] },{ vertex: 12, peers: [ 4, 13 ] },{ vertex: 13, peers: [ 3, 12, 23 ] }, { vertex: 14, peers: [ 2, 11, 22 ] },{ vertex: 15, peers: [ 1, 10, 21 ] },{ vertex: 16, peers: [ 9, 20 ] },{ vertex: 17, peers: [ 8, 19 ] },{ vertex: 18, peers: [ 7 ] },{ vertex: 19, peers: [ 6, 17 ] },{ vertex: 20, peers: [ 5, 16 ] },{ vertex: 21, peers: [ 4, 15 ] },{ vertex: 22, peers: [ 3, 14 ] },{ vertex: 23, peers: [ 2, 13 ] } ];
let result = hamiltonian(vertexes, 18);
console.log('result', result);
请注意,使用动态编程可以提高运行时间。查看哈密顿路径问题的不同方法。
推荐阅读
- java - JFXPanel setScene 使用 java 11 冻结
- excel - VBA Excel:如何使用两个变量作为其位置将值放入单元格
- java - Maven 构建后 getResource() 的问题
- node.js - 使用不同用户的Mongoose查询数据时如何显示Multer上传的图像
- angular - 在订阅中访问服务变量作为组件变量 Angular7/NGRX
- mocha.js - 详细报告 Cypress/Mochawesome
- sql - 来自 SELECT 参考的子查询,给我一个“不能从这部分查询中引用”
- reactjs - 显示来自同一个 reducer 的 2 个不同状态,而状态不会重写
- sql-server - SQL Server 探查器跟踪未显示参数值
- node.js - Elastic beanstalk 请求上的 Node.js 是 HTTPS,但 express 是作为 HTTP 服务的。这安全吗?