-
0 votesanswersviews
如何改进TSP的遗传算法？
这是我的遗传算法，一步一步： 随机生成两个初始种群，并从两者中选择最适合的游览 . 执行有序交叉，按顺序选择第一个适合游览的随机部分并从第二个填充其余部分 . 通过随机交换两个城市来改变这个旅游，如果旅行的次数只是初始人口中前10％的旅行的1.3倍（我实际上只是通过归纳完成，挑选出来的穷人旅行） - 我会喜欢要改变这一点，却想不出更好的方法 . 突变选自几个突变的群体 . 返回... -
0 votesanswersviews
改进星型算法以在迷宫中搜索多个目标
如果我已经在迷宫中完成了A *算法的实现，以找到单个目标的最短路径（就像pacman游戏一样），我应该如何改进我目前的启发式（曼哈顿到目标旅行费用的距离从头开始）这样我的算法就可以在迷宫中支持多个目标 . 基本上，我想找到通过迷宫中所有目标的最短路径 . 为了确保路径是最优的，假设我们忽略问题的一致性，则需要允许启发式函数 . 我知道这就像旅行商问题，但是现在我只处理相对少量的数据，所以我想继续使... -
1 votesanswersviews
在图中查找周期（不一定是哈密顿量或访问所有节点）
我有图像一个在图1（第一图像）和要连接的红色节点具有周期，但周期不必是哈密顿像图2和图3（最后两个图像） . 这个问题比TSP有更大的搜索空间，因为我们可以访问节点两次 . 像TSP一样，不可能在大图中评估所有组合，我应该尝试启发式，但问题是，与TSP不同，周期或游览的长度在这里不固定 . 因为访问所有蓝色节点不是强制性的，并且这导致具有可变长度，包括一些蓝色节点 . 如何在每次评估时生成可能的&... -
6 votesanswersviews
这个问题NP难吗？
我正在尝试为这个问题提出一个合理的算法： 假设你有一堆球 . 每个球至少有一种颜色，但也可以是多色的 . 每个球上都有一个数字 . 还有一堆盒子，每个盒子只有一种颜色 . 目标是最大化框中球的数字总和，唯一的规则是： 为了将球放在一个盒子里，它必须至少有一个盒子的颜色 你每个盒子里只能放一个球 . 例如，您可以将蓝色和绿色球放入蓝色框或绿色框中，但不能放入红色框中 . 我已经提出了一些... -
10 votesanswersviews
这在多项式（或伪多项式）时间内是否可解？
我正在尝试为这个问题提出一个合理的算法： 假设你有一堆球 . 每个球至少有一种颜色，但也可以是多色的 . 每个球都有一个重量和一个与之相关的值 . 还有一堆盒子，每个盒子只有一种颜色 . 每个盒子都有最多可以容纳的球 . 目标是在保持总重量W的同时最大化盒子中的值的总和，唯一的规则是： 为了将球放入盒子中，它必须至少具有盒子的颜色 （例如，您可以将蓝色和绿色球放入蓝色框或绿色框中，但不能放入红色框... -
2 votesanswersviews
Google Directions API单向而非原点和目的地
我正在使用谷歌的方向API来解决TSP . 有没有办法利用谷歌的路线优化，而不提供原点和目的地 . 为了我的目的，我只关心设定原点 . 目的地可以是最适合所给出的航点的任何地方 . 即 https://maps.googleapis.com/maps/api/directions/xml?origin=A&destination=“”＆waypoints = optimize：true |... -
3 votesanswersviews
列出所有TSP路径组合（5个顶点）
我想列出所有TSP路线组合 . 有5个顶点，因此有10个边： 所有边缘如下： edges = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('A', 'E'), ('B', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'D'), ('C', 'E'), ('D', 'E')] 注意： ('A', 'B') 与 ('B', 'A') 相同，... -
2 votesanswersviews
找到给定源和一组目标之间的最短路径
您将获得一个加权连接图（20个节点），所有边都具有正权重 . 我们有一个从A点开始的机器人，它在例如B，D和E点通过 must . 我们的想法是找到连接所有这4个点的最短路径 . 机器人也有一个有限的电池，但它可以在某些点充电 . 在互联网上研究后，我有两个算法： Dijkstra's 和 TSP . Dijkstra's 将找到节点与每个其他节点之间的最短路径， TSP 将找到连接所有点... -
1 votesanswersviews
用于metric_tsp_approx的boost :: graph隐式图中的ColorMap
我正在尝试完成以下操作：有一个函数 computeTspTour(size, start, distance) ，它给我一个近似的最短游览 size 许多顶点，从 start 开始 . 这里， distance 是一个函数对象，它接受两个索引并返回它们之间的距离 . 我想利用 boost::graph 的 metric_tsp_approx . 为此，我需要一个完整的基数图 size ，所以我想... -
9 votesanswersviews
TSP变量的近似算法，固定开始和结束任何地方，但在每个顶点允许的起点多次访问
注意：由于旅行不是在它开始的同一个地方结束的事实，而且只要我仍然访问所有这些点，每个点都可以被访问多次这一事实，这不是真正的TSP变体，而是我之所以说是因为缺乏对问题的更好定义 . 所以.. 假设我正在徒步旅行，有n个兴趣点 . 这些景点都通过远足径相连 . 我有一张 Map 显示了所有距离的路径，给我一个有向图 . 我的问题是如何近似一个从A点开始并且访问所有n个兴趣点的旅游，同时结束旅行的任何... -
1 votesanswersviews
IBM Cplex中对称旅行商的子消除约束
IBM Cplex中有一个旅行商问题的示例代码 . 它将subour排除约束定义为： forall (s in subtours) sum (i in Cities : s.subtour[i] != 0) x[<minl(i, s.subtour[i]), maxl(i, s.subtour[i])>] <= s.size-1; 有人可以用这个... -
1 votesanswersviews
从线性编程解决方案中检索顶点路径
我一直在努力解决路由问题，比如 TSP （旅行商问题），但有一些曲折 . 我使用线性编程（ CPlex library ）和有向图（带有原点顶点）（ Coin-Or::Lemon library ）对问题进行了建模 . 线性程序找到解决方案，但我的问题在于如何检索路径 . 我可以迭代图形的每个顶点和边缘以找出线性程序正在使用的内容，所以我想我只是从Origin开始并使用所选边缘到达下一个节点，直到... -
6 votesanswersviews
代表旅行推销员作为线性表达
我在网上看到，人们可以将旅行商问题写成线性表达式，并使用CPLEX for java等软件进行计算 . 我有1000个城镇，需要找一小段距离 . 我计划将这1000个城镇划分为约100个城镇的集群，并在这些单独的集群上执行一些线性规划算法 . 我的问题是，我究竟如何将其表示为线性表达式 . 所以我有100个城镇，我相信每个人都知道TSP是如何工作的 . 我完全不知道如何编写满足TSP的线性约束，目... -
-1 votesanswersviews
如何做粒子群优化的移动函数（下一个位置）来解决c中的TSP
我的计划摘要： 我正在读取一个文本文件，每行都有一个int（节点标识符）和3个浮点数（x，y，z位置） . 始终开始的节点ID为1并按顺序递增 . 在我读完这些信息之后，我创建了一个邻接矩阵来获取每个节点到每个其他节点的距离 . 截至目前，在我的PSO算法类中，我首先创建一个粒子向量（我制作的一个类） . 在粒子类中，构造函数接受一个int，这是最大的节点号 . 然后，它创建一个所有节点的随机路径...