Namaran

Code daily. Without assist.

2026-10-11

route.rs

use std::collections::HashMap;

// cheapest way to visit every city not yet in `seen`, starting from `at`
fn rest(at: usize, seen: u32, dist: &[Vec<u32>], memo: &mut HashMap<u32, u32>) -> u32 {
    if let Some(&cost) = memo.get(&seen) {
        return cost;
    }
    let cost = (0..dist.len())
        .filter(|&next| seen & (1 << next) == 0)
        .map(|next| dist[at][next] + rest(next, seen | 1 << next, dist, memo))
        .min()
        .unwrap_or(0);
    memo.insert(seen, cost);
    cost
}

fn main() {
    let dist = vec![vec![0, 2, 1, 9], vec![2, 0, 1, 1], vec![1, 1, 0, 9], vec![9, 1, 9, 0]];
    println!("{}", rest(0, 1, &dist, &mut HashMap::new()));
}

rest(at, seen, ...) は、都市 at にいて集合 seen の都市を訪れ終えたとき、残りの都市をすべて回る最小の移動費用を返すつもりの関数で、同じ計算を繰り返さないよう結果を memo に覚えます。都市 0 から出発する main の4都市では、0 → 2 → 1 → 3 と回る費用 3 が本来の答えですが、いまは 11 を出力します。都市が3つまでの入力では正しい答えが出ます。

Answer

Wrong

fn rest(at: usize, seen: u32, dist: &[Vec<u32>], memo: &mut HashMap<u32, u32>) -> u32 {
    if let Some(&cost) = memo.get(&seen) {
        return cost;
    }
    // ...
    memo.insert(seen, cost);

rest の答えは、訪れた集合 seen だけでなく、いまどこにいるかを表す at にも依存します。同じ seen でも、at が違えば次の都市までの距離が違うからです。ところが memo の鍵は seen だけなので、ある at で計算した費用が、別の at から同じ seen に来たときにもそのまま返されます。

探索は番号の小さい都市から試すので、集合 {0, 1, 2} に最初に着くのは 0 → 1 → 2 の経路です。このとき覚えられるのは、at = 2 から残りの都市 3 へ行く費用 9 です。次に 0 → 2 → 1 で同じ {0, 1, 2} に着くと、本当は 1 から 3 への 1 で済むのに 9 が返り、最適な経路が 1 + 1 + 9 = 11 と見積もられます。0 → 1 で始まる経路は正しく 12 と求まり、0 → 3 で始まる経路も覚えた値に引きずられて 19 になるので、最小値として 11 が出ます。都市が3つなら、出発点を含む2都市の集合 {0, j} に着いたときの現在地は必ず j で、全部を訪れた集合の答えは現在地によらず 0 です。そのため鍵が衝突しても値が食い違わず、誤りが表に出ません。

Right

fn rest(at: usize, seen: u32, dist: &[Vec<u32>], memo: &mut HashMap<(usize, u32), u32>) -> u32 {
    if let Some(&cost) = memo.get(&(at, seen)) {
        return cost;
    }
    // ...
    memo.insert((at, seen), cost);

鍵を (at, seen) の組にすると、答えを決める情報がすべて鍵に入ります。0 → 2 → 1 で着いた {0, 1, 2} は at = 1 の状態として別に計算され、1 から 3 への費用 1 が使われて 3 が出ます。状態の数は都市数 n に対して n × 2n 個で、訪問済みの集合と最後にいる都市を状態にするこの形は、巡回セールスマン問題の標準的な動的計画法と同じです1。

  1. この動的計画法は、1962年に Held と Karp が、同じ年に Bellman が独立に発表したもので、Held-Karp アルゴリズムと呼ばれます。