Пути смежности в Scala - PullRequest
Новая
       37

Пути смежности в Scala

0 голосов
/ 30 июня 2018

Если у меня есть список смежности, представленный в Scala следующим образом: 

val l = List(
    List((1, 1), (2, 3), (4, 10)),
    List((2, 1)),
    List((3, 1), (4, 5)),
    List(4, 1)),
    List())

Каждый «Список» содержит стоимость пути от одного узла к другому в ориентированном графе. Таким образом, первый «Список» с тремя записями представляет преемников первого узла (считая от 0). Это означает, что Узел 0 направляется в Узел 1 со стоимостью 1, в Узел 2 со стоимостью 3 и в Узел 4 со стоимостью 10 и т. Д.

Как можно было бы рекурсивно вычислить, если есть пути с максимальной стоимостью от одного узла к другому? Я думал о чем-то вроде этого: 

def hasMaxCostPath: (List[List[(Int, Int)]], Int, Int, Int) => Int => Boolean = (adj, from, to, max) => len =>

Таким образом, функция получает список смежности «adj», начальный узел «from», конечный узел «to», максимальную стоимость пути «max» и максимальную длину пути «len». Поэтому я думаю, что результат должен быть похож на следующий, основанный на приведенном выше списке смежности: 

hasMaxCostPath(l, 0, 2, 2)(1) == false
hasMaxCostPath(l, 0, 2, 3)(1) == true

Кроме того, как можно было бы рекурсивно вычислить список всех затрат на пути, которые идут от одного указанного узла к другому в пределах заданной максимальной длины? Может быть так: 

def getPaths: (List[List[(Int, Int)]], List[(Int, Int)], Int, Int) => List[Int] =
(adj, vn, dest, len) =>

Таким образом, эта функция получит список смежности "adj", список уже посещенных узлов "vn" с (узел, стоимость), в котором мы берем данный узел в качестве начального узла, узел назначения "dest" и максимальная длина пути «лен». И для этой функции результаты могут быть такими: 

getPaths(l, List((0, 0)), 2, 1) == List(3)     // Node0 -> Node2
getPaths(l, List((0, 0)), 2, 2) == List(2, 3)  // Node0 -> Node1 -> Node2 AND Node0 -> Node2

Извините, я очень новичок в Scala

1 Ответ

0 голосов
/ 30 июня 2018

Это у вас работает? 

package foo

object Foo {

  def main(args: Array[String]): Unit = {
    val edges = List(
      List((1, 1), (2, 3), (4, 10)),
      List((2, 1)),
      List((3, 1), (4, 5)),
      List((4, 1)),
      List())
    println(hasMaxCostPath(edges,0,1,2))
    println(hasMaxCostPath(edges,0,2,2))
  }

  def hasMaxCostPath(edges: List[List[(Int, Int)]], start: Int, end: Int, maxCost: Int): Boolean = {
    maxCost > 0 &&
    edges(start).exists(a =>
      (a._1 == end && a._2 <= maxCost) ||
      hasMaxCostPath(edges, a._1, end, maxCost - a._2)
    )
  }

}

Редактировать: ====

Приведенное выше решение не учитывает параметр длины. Вот решение с параметром длины: 

package foo

object Foo {

  def main(args: Array[String]): Unit = {
    val edges = List(
      List((1, 1), (2, 3), (4, 10)),
      List((2, 1)),
      List((3, 1), (4, 5)),
      List((4, 1)),
      List())
      assert(! hasMaxCostPath(edges,0,4,4,3))
      assert(hasMaxCostPath(edges,0,4,4,4))
  }

  def hasMaxCostPath(edges: List[List[(Int, Int)]], start: Int, end: Int, maxCost: Int, maxLength: Int): Boolean = {
    maxLength > 0 &&
    maxCost >= 0 &&
    edges(start).exists(a =>
      (a._1 == end && a._2 <= maxCost) ||
      hasMaxCostPath(edges, a._1, end, maxCost - a._2, maxLength - 1)
    )
  }

}

=== Редактировать:

И вот решение, включающее вашу вторую проблему: 

package foo

object Foo {

  def main(args: Array[String]): Unit = {
    val edges = List(
      List((1, 1), (2, 3), (4, 10)),
      List((2, 1)),
      List((3, 1), (4, 5)),
      List((4, 1)),
      List())
    assert(! hasMaxCostPath(edges,0,4,4,3))
    assert(hasMaxCostPath(edges,0,4,4,4))
    assert(getMaxCostPaths(edges,0,0,5,5) == List())
    assert(getMaxCostPaths(edges,0,1,1,1) == List(List(0,1)))
    assert(getMaxCostPaths(edges,0,2,2,2) == List(List(0,1,2)))
    assert(getMaxCostPaths(edges,0,2,5,5) == List(List(0,2), List(0,1,2)))
  }

  def hasMaxCostPath(edges: List[List[(Int, Int)]], start: Int, end: Int, maxCost: Int, maxLength: Int): Boolean = {
    maxLength > 0 &&
    maxCost >= 0 &&
    edges(start).exists(a =>
      (a._1 == end && a._2 <= maxCost) ||
      hasMaxCostPath(edges, a._1, end, maxCost - a._2, maxLength - 1)
    )
  }

  def getMaxCostPaths(
         edges: List[List[(Int, Int)]],
         from: Int, to: Int,
         maxCost: Int,
         maxLength: Int): List[List[Int]] = {
      getMaxCostPathsRec(edges, from, to, maxCost, maxLength, List(from))
  }

  def getMaxCostPathsRec(
         edges: List[List[(Int, Int)]],
         start: Int, end: Int,
         maxCost: Int,
         maxLength: Int,
         path: List[Int]) : List[List[Int]] = {
    if (maxLength <= 0 || maxCost < 0) return List()
    val direct = edges(start).filter(a => a._1 == end && a._2 <= maxCost).map(edge => path ::: List(edge._1))
    val transitive = edges(start).flatMap(a =>
      getMaxCostPathsRec(edges, a._1, end, maxCost - a._2, maxLength - 1, path ::: List(a._1))
    )
    direct ::: transitive
  }

}
...