既存投稿一覧ページへのリンク
雑記
半年前に手も足も出なかった問題に対して、取っ掛かりが掴めるようになった感覚は歯がゆくもあり、気持ちよくもある⋯
早くこの停滞感を抜けたいものよ。
サンプルコード
sample_code.py
def tsp_dp(dist_matrix):
n = len(dist_matrix)
all_visited = (1 << n) - 1
INF = float('inf')
# DPテーブル初期化 [訪問済み都市のビットマスク][現在地]
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0 # 開始都市0（ビットマスクの最下位ビット=1）
for mask in range(1 << n):
for i in range(n):
if not (mask & (1 << i)):
continue # 現在都市iが未訪問の場合はスキップ
for j in range(n):
if mask & (1 << j):
continue # 都市jが既に訪問済みの場合はスキップ
new_mask = mask | (1 << j)
dp[new_mask][j] = min(dp[new_mask][j], dp[mask][i] + dist_matrix[i][j])
# 全都市訪問後、開始都市0に戻る経路を計算
min_cost = INF
for i in range(1, n):
if dp[all_visited][i] != INF:
final_cost = dp[all_visited][i] + dist_matrix[i][0]
min_cost = min(min_cost, final_cost)
return min_cost if min_cost != INF else -1
# 使用例（4都市の例）
if __name__ == "__main__":
# 都市間の距離行列（例）
dist = [
[0, 10, 15, 20,35],
[10, 0, 35, 25, 15],
[15, 35, 0, 30, 45],
[20, 25, 30, 0, 15],
[35, 15, 45, 15, 0]
]
print("最短経路コスト:", tsp_dp(dist)) # 出力: 80
ビットマスクイメージ
考えれば毎回わかるのだけど、まだ自然体でパッと脳内変換出来ないんだよなぁ。
初めて勤めていた会社にいたときは、
◇◇◇◇◆◆◇◆◇
というランプを見て瞬間的に「26」と分かったり、ランプ点滅の四則演算平気でやっている業界にいたものだけど。
私の周囲の人間もこの能力持っていたから、必死にその勉強したんだよなぁ。
当時は何の疑問も持たなかったけれど、業界から離れると、あの技能って特殊能力だったと思い返せますわ。
今は、ビット演算系は「昔できていたのに今は出来ない」と苦しむ種にしかなっていない⋯
もう一度、ランプ計算の練習しようかな。
for mask in range(1 << 5)の内側について
for mask in range(1 << n):
for i in range(n):
if not (mask & (1 << i)):
continue # 現在都市iが未訪問の場合はスキップ
のロジックによって、下図の赤いブロックのみ処理を行う対象とする。
for mask in range(1 << n):
for i in range(n):
if not (mask & (1 << i)):
continue # 現在都市iが未訪問の場合はスキップ
for j in range(n):
if mask & (1 << j):
continue # 都市jが既に訪問済みの場合はスキップ
のロジックによって、下図の赤いブロックが訪問済みかどうか判定する。
動的計画法(n=5)については、下のブロックを追っていけば、何とか読み取れるかな⋯
何年プログラミングしていても、自分で考えて書いたコード以外の3重ループ以上を脳内イメージするのは難しいですね。
ODCPのO問題が毎回DPの躓きポイントだからな・・・