7

backtrackingを使用して問題 (例: N-Queen) を解決しているとします。すべてではなく、1 つだけ (1 番目) のソリューションを見つけたい場合はどうすればよいでしょうか。

私はそれを命令的に行うことができると思います（たとえば、可変ブール値フラグを使用して）。どうすれば機能的にできるのだろうか。

4

3 に答える 3

14

ScalaOptionはここで機能しますが、他の 2 つの回答が指摘しているように、より慣用的な機能的アプローチは、"遅延リスト" Stream(Scala では ) を使用して一連のソリューションを表すことです。

たとえば、次のようなコードを書いていることに気づきました。

trait Node[A] {
  def children: Stream[A with Node[A]]

  def dfs(f: A => Boolean): Stream[A] = this.children.flatMap {
    child => if (f(child)) Stream(child) else child.dfs(f)
  }
}

ここBoardで、拡張するクラスがあり、そのクラスに有効なすべてのボードと 1 つの追加ピースを返すメソッドNode[Board]の実装があるとします。メソッド、 を含むコンパニオン オブジェクトなどchildren、他の便利なものもあるとします。sizeempty

次に、次のように記述してStream、ソリューションを取得できます。

val solutions = Board.empty.dfs(_.size == 8)

AStreamは怠け者であり、頭だけを評価するので、今のところ、最初の解を見つけるのに十分なだけツリーを検索しました。を使用してこのソリューションを取得できますhead。

scala> solutions.head
res1: Board = 
o . . . . . . .
. . . . o . . .
. . . . . . . o
. . . . . o . .
. . o . . . . .
. . . . . . o .
. o . . . . . .
. . . o . . . .

または何でも。ただし、必要に応じて他の結果を取得することもできます。

scala> solutions(10)
res2: Board = 
. o . . . . . .
. . . . . . o .
. . . . o . . .
. . . . . . . o
o . . . . . . .
. . . o . . . .
. . . . . o . .
. . o . . . . .

これは、10 番目の解を見つけるのに十分なだけツリーを検索して停止します。

Streamこのアプローチに対する大きな利点はOption、必要に応じて追加の結果を得ることができることです。

于 2012-01-19T23:21:36.330 に答える
5

これは、探しているものが見つかったときに停止する深さ優先検索の単純なケースです。OptionChris K's answer で述べたように、を利用します。

case class Tree[A](v: A, subtrees: Tree[A]*) {
  def dfs(s: A): Option[A] = {
    println("visiting " + v)
    subtrees.foldLeft(if(v == s) Some(v) else None)((r, t) => 
      if(r.isDefined) 
        r 
      else 
        t.dfs(s)
    )
  }
  override def toString() = "Tree(%s%s%s)".format(v, if(subtrees.nonEmpty) ", " else "", subtrees.mkString(", "))
}

使用法：

scala> val t = Tree(1, Tree(2, Tree(3), Tree(4)), Tree(5, Tree(6), Tree(7)))
t: Tree[Int] = Tree(1, Tree(2, Tree(3), Tree(4)), Tree(5, Tree(6), Tree(7)))

木tは次のように見えます

     1
   /   \
  2     5
 / \   / \
3   4 6   7

したがって、要素を検索して、それがアクセスするノードを追跡できます。

scala> t.dfs(6)
visiting 1
visiting 2
visiting 3
visiting 4
visiting 5
visiting 6
res42: Option[Int] = Some(6)

探しているものが見つかった後は、それ以上ノードにアクセスしないことに注意してください。

于 2012-01-19T20:54:54.480 に答える
2

再帰的な検索関数を使用していると仮定すると、関数は結果 (つまり、クイーンの配置) を返すか、そのブランチで結果が見つからなかったことを示す必要があります。Scala にはおそらくオプション/おそらくタイプがあり、それを使用できます。このアドバイスは、どの関数型言語にも等しく当てはまります。

于 2012-01-19T18:46:11.183 に答える