问题标签 [shortest]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
1 回答
7048 浏览

java - Java 2D数组从A点到B点的最短路径有障碍物

目标:找到到达目的地所需的最少移动量。

场景:在 2D Array 8*8 中,包含以下元素:

在哪里

  • “A”代表起点。
  • “B”代表目的地点。
  • “*”表示障碍物。
  • “.”代表一个空单元格。

目前我已经完成了以下代码:

它的工作是找到到达目的地所需的“最短”步数,但是它将任何/障碍视为可以移动到的空单元。

我目前无法找到一种方法来对其进行编码,使其能够识别下一个动作的正确决定。

我正在考虑使用数组列表和一些算法,但是我尝试阅读一些算法,例如Dijkstra 的算法,但它看起来真的很混乱,有人可以帮助我以一种非常简单的方式理解它以在 java 中实现它吗?

//-(对不起我的编码技能,我还是个初学者)-

0 投票
2 回答
734 浏览

path - Neo4j-使用 Gremlin 寻找最短路径及其遍历成本

我想将我的加权图从起始节点遍历到某个深度并打印遍历节点和累积权重。

例如,在这样的图中:A--1--B--2--C--1--D,A--1--B--1--F--1--G 起始节点深度为 3 的 A 应返回以下内容:A,B,F,G,cost:3

我使用以下代码取得了一些进展,但它不计算路径的权重:

我如何编写它来计算路径的成本和遍历列表?

提前致谢...

0 投票
1 回答
1165 浏览

operating-system - SJF 抢占式调度

我得到这张表是为了先发制人的 Shortest Job First

在 G 之前,它执行前还有 2 秒,我需要包括它吗?

我的回答中使用甘特图给出的表格是

我的问题是,是否可以包括 F 到达之前的等待时间?

0 投票
1 回答
420 浏览

algorithm - 图搜索算法,其中边缘可以被障碍物阻挡

我想在有向图的两个顶点之间找到一条低成本路径,其中每条边的成本相同。易于实现算法和执行时间非常重要,因此如果算法更简单、更快,我愿意为接近最优的解决方案牺牲一个最优解决方案。

边缘可以被障碍物阻挡。边缘被阻塞的概率是预先知道的。阻塞是相互独立的。当到达边缘头部的顶点时,发现边缘未被阻塞或阻塞。

我的问题类似于加拿大旅行者问题,但我的理解是随机规划问题的解决方案相对难以实现,并且找到最优策略所花费的时间可能相对较高。

目前,我正在考虑将问题转换为确定性问题,以便可以使用像 A* 这样的搜索算法来解决它。这是一个好方法吗?如果是,我该怎么做?

0 投票
1 回答
1403 浏览

java - 计算 3D 框外最短路径的距离

我需要一些帮助来解决我被分配的作业背后的数学问题。问题是计算从蚂蚁到糖果的距离。糖果总是在盒子的顶部,蚂蚁可以在任何地方,除了侧面。蚂蚁可以在顶部和侧面爬行,但不能飞。它们以连续 6 个数字的形式为您提供蚂蚁和糖果的坐标。前 3 个是蚂蚁的,接下来的 3 个是糖果的。我遇到的问题是第三个样本输入(0 0 0 5 4 3.0)。他们如何得到 8.60 个单位作为答案?当向上距离为 3 且到角点的距离为 6.40 时,总数应为 9.40。我的猜测是他们在上升时偷工减料,但我不知道如何制定一个公式来找到这样的最短长度。感谢您的帮助:D 如果您需要更多信息,请询问。

该框是 x,z,y 格式的 (5,4,3)。

0 投票
0 回答
409 浏览

c# - 增强 Dijkstra 的导航算法

我已经为与 ArcGIS 集成的 Dijkstra 算法编写了一个实现,该实现是用 C#.net 编写的。

对于具有 80,000 个节点的图(最坏情况时间),我已经达到了大约 20 秒的求解时间,我使用了 Alexey Kurakin 的优先级队列实现(非常感谢),我认为我无法做任何事情来提高这个时间.

我有几个问题:

  1. 这是一个可以接受的时间吗?
  2. 我该如何改进它?
  3. 在另一个平台(我认为是 Delphi 或 C++)中编写解决方案是否可以提高时间?

此致。

0 投票
5 回答
135570 浏览

java - Java - 在距离加权地图中查找两点之间的最短路径

我需要一种算法来找到地图中两点之间的最短路径,其中道路距离由数字表示。

给出的内容: 起始城市 A 目的地城市 Z

城市间距离列表:

A - B : 10
F - K : 23
R - M : 8
K - O : 40
Z - P : 18
J - K : 25
D - B : 11
M - A : 8
P - R : 15

我以为我可以使用 Dijkstra 的算法,但是它找到到所有目的地的最短距离。不只是一个。

任何建议表示赞赏。

0 投票
1 回答
839 浏览

matlab - 排序成对最短距离

这是我的问题。

随机排序数组

可以看出,绘制的轮廓具有重叠区域。所以我想画一个不重叠的闭合轮廓。我得到的一个想法是对矩阵的元素进行排序,使矩阵元素之间的相邻距离最小。因此,最近的点将彼此相邻。

谁能指定我该怎么做?我尝试使用 pdist2 但失败了。

0 投票
1 回答
2359 浏览

python - Python:如何在文本文件中打印最短和最长的单词?

我试图让我的程序打印出在文本文件中找到的最短和最长的单词。假设我输入“派很美味”作为我的文本块。然后我单独在一行上键入 EOF 以结束输入阶段。我输入了选项 1 来查看 Shortest word,应该会弹出“is”,但我只得到字母“p”作为我的输出。对于第二个选项,我得到了相同的结果,即找到最长的单词,当它应该是“美味”时,我最终得到了字母“p”。顺便说一句,我正在使用 min 和 max 函数来做到这一点。

0 投票
1 回答
593 浏览

algorithm - 查找伦敦塔任务的最小移动次数

我正在为类似于河内塔任务的任务寻找解决方案,但这与河内不同,因为磁盘不受大小限制。我正在创建的伦敦塔任务有 8 个磁盘,而不是传统的 3 个或 5 个(如维基百科链接所示)。我使用的PEBL软件“主要用 C++ 编程(尽管您不需要了解 C++ 即可使用 PEBL),但也使用 flex 和 bison(lex 和 yacc 的 GNU 版本)来处理解析。”

以下是该任务的实际效果视频:http ://www.youtube.com/watch?v=IiBJ94HRpeM&noredirect=1

*每个磁盘都是一个数字。例如,蓝盘=1,红盘=2,等等。

左侧由您必须移动的磁盘组成,以匹配右侧。有3列。

因此,如果我用 8 个磁盘制作它,我会创建一个如下所示的试用版:

我如何确定左侧看起来像右侧所需的最小移动量是多少?我不需要使用 PEBL 来编写代码,但我需要知道,因为我正在计算一个人每次试验的最低值有多接近。