我有一个带有起始节点S和结束节点E的图G.这个图的特殊之处在于,不是边缘有成本,而是具有成本的节点.我想找到S和E之间的方式(一组节点,W),以便最小化(W).(实际上,我对W不感兴趣,只是max(W))等价,如果我删除成本大于k的所有节点,那么最小的k是什么,以便S和E仍然连接？
我有一个想法,但想知道它是否正确和最佳.这是我目前的伪代码:
L := Priority Queue of nodes (minimum on top)
L.add(S, S.weight)
while (!L.empty) {
X = L.poll()
return X.weight if (X == G)
mark X visited
foreach (unvisited neighbour N of X, N not in L) {
N.weight = max(N.weight, X.weight)
L.add(N, N.weight)
}
}
我认为最坏的情况是O(n log n),其中n是节点数.
以下是我的具体问题(渗透)的一些细节,但我也对这个问题的算法感兴趣.节点权重在0和给定的最大值之间随机均匀分布.我的节点是在R²平面上的泊松分布,如果两个节点之间的距离小于给定的常数,则存在两个节点之间的边.可能有很多节点,因此它们是动态生成的(隐藏在伪代码中的foreach中).我的起始节点在(0,0)中,结束节点是距离(0,0)大于R的距离上的任何节点.
编辑:节点上的权重是浮点数.
如何显示在Scala中没有构造函数的类型的值有什么变化？我想对值进行模式匹配，并让Scala告诉我没有模式可以匹配，但是我愿意接受其他建议。这是一个为什么有用的简短示例。
在Scala中，可以在类型级别上定义自然数，例如使用Peano编码。
sealed trait Nat
sealed trait Zero extends Nat
sealed trait Succ[N <: Nat] extends Nat
由此我们可以定义数字等于偶数的含义。零是偶数，比偶数多2的任何数字也是偶数。
sealed trait Even[N <: Nat]
sealed case class Base() extends Even[Zero]
sealed case class Step[N <: Nat](evenN: Even[N]) extends Even[Succ[Succ[N]]]
由此我们可以证明例如两个是偶数：
val `two is even`: Even[Succ[Succ[Zero]]] = Step(Base())
但是，即使编译器可以告诉我该类型Base也Step不能居住于该类型，但我无法证明它不是偶数。
def `one is odd`(impossible: Even[Succ[Zero]]): Nothing = impossible match {
case _: Base => ???
case _: Step[_] => ???
}
编译器会很高兴地告诉我，我给出的所有情况都不可能与错误有关pattern type is incompatible with expected …