Namaran

Code daily. Without assist.

2026-10-13

Route.hs

import qualified Data.Set as Set

edges :: Char -> [(Char, Int)]
edges 'S' = [('A', 1), ('G', 5)]
edges 'A' = [('G', 2)]
edges _ = []

estimate :: Char -> Int
estimate 'S' = 3
estimate 'A' = 2
estimate _ = 0

search :: Set.Set (Int, Char) -> Maybe Int
search open = do
  ((f, n), rest) <- Set.minView open
  if n == 'G'
    then Just f
    else search (foldr Set.insert rest [(f + c + estimate m, m) | (m, c) <- edges n])

main :: IO ()
main = print (search (Set.singleton (estimate 'S', 'S')))

search は、A*探索で 'S' から 'G' までの最短距離を求める関数です。open には、そのノードまでのコストと estimate による残りの見積もりの和を、ノードと組にして入れ、和が最小のものから取り出します。このグラフの最短経路は S→A→G の長さ3なので、本来は Just 3 と表示されるはずですが、いまは Just 8 と表示されます。estimate がどのノードにも0を返すように書き換えると、Just 3 が表示されます。

Answer

Wrong

((f, n), rest) <- Set.minView open
if n == 'G'
  then Just f
  else search (foldr Set.insert rest [(f + c + estimate m, m) | (m, c) <- edges n])

取り出した f は、n までのコストと n の見積もり estimate n の和です。隣の m の和に要るのは「n までのコスト + c + estimate m」ですが、このコードはコストの代わりに f を使うので、n の見積もりが m までのコストに混ざります。混ざった分は m の f の一部として次のノードへ引き継がれ、経路をたどるたびに積み上がります。

S の f は見積もりの3です。A の和は 3 + 1 + 2 で6、S から直接行く G は 3 + 5 + 0 で8になり、A を取り出すと、A 経由の G も 6 + 2 + 0 で8になります。どちらの経路も8なので、取り出した G の f の8がそのまま返ります。見積もりがすべて0なら和とコストが同じ値になり、混ざるものがないので Just 3 が返ります。とはいえ見積もりの値はどれも実際の残りの距離を超えておらず、直すべきは見積もりではありません。

Right

((f, n), rest) <- Set.minView open
let g = f - estimate n
if n == 'G'
  then Just g
  else search (foldr Set.insert rest [(g + c + estimate m, m) | (m, c) <- edges n])

和 f から n の見積もりを引けば、n までのコスト g に戻ります。隣の和を g から作れば、どのノードの f も「そこまでのコスト + そのノードの見積もり」だけになり、見積もりは積み上がりません。A の和は3、A 経由の G も3、直接の G は5になり、先に取り出される G のコスト3が返ります。G の見積もりは0なので Just f のままでも値は同じですが、返したいのはコストなので g を返します1。

  1. 引き算で戻す代わりに、集合に (f, g, n) の3つ組を入れてコストを持ち運ぶ書き方もよく使われます。和とコストを別の値として持てば、取り違えようがありません。