2026-10-13
Frontier.hs
import Data.List (sortOn)
type Node = (Char, Int, Int) -- name, cost so far, estimate to goal
frontier :: [Node]
frontier = [('a', 1, 9), ('b', 5, 3), ('c', 4, 7), ('d', 6, 0)]
main :: IO ()
main = putStrLn [name | (name, _, _) <- sortOn (\(_, g, h) -> g + h) frontier]
これは何を出力するでしょうか?
Answer
dbac です。
sortOn は、渡した関数で求めたキーの小さい順に並べます。キーはここまでのコストと目的地までの見積もりの和 g + h で、a は10、b は8、c は11、d は6です。小さい順に名前を拾うと d b a c になります。
この和は、そのノードを通って目的地まで行く経路の長さの見積もりにあたります。ここまでのコストだけで並べると acbd、見積もりだけで並べると dbca になり、どちらとも違う順番です。コストがいちばん大きい d も、見積もりが0なので先頭に来ます。