Namaran

Code daily. Without assist.

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なので先頭に来ます。