漢米頓路徑搜尋（Hamiltonian-path search）
/ ham-il-TOH-nee-an /
假設一位送貨司機必須把社區裡的每個地址恰好造訪一次，且只能沿著現有的道路行進。一條把每個地點各碰一次、絕不重複的路線就是漢米頓路徑；若它還回到出發點，就是漢米頓迴路。搜尋問題問的是：給定的圖中是否存在這樣的路徑（或迴路），若有就找出一條。
回溯一次加一個頂點地建路徑。從某個頂點出發並標為已訪。每一步你站在當前頂點、看它的鄰居；對每個尚未造訪的鄰居，移過去（延伸路徑）、標記它、遞迴繼續，回來時取消標記以便其他路線使用。自然的剪枝很簡單：你只能走到一個「尚未造訪且與你所站位置相鄰」的頂點。當所有 n 個頂點都被造訪時，路徑完整且是一個解（對迴路，還額外要求有一條邊回到起點）。狀態空間樹以「下一步走向哪個未訪鄰居」分岔；最壞情況下它的大小約為 n! 量級，因為一條路徑就是頂點的一種排序，但相鄰約束與已訪標記會剪掉每一步通往死路或重複的走法。
漢米頓路徑與迴路以 NP 完全著稱（這正是旅行推銷員問題之所以難的核心），所以沒有已知演算法能快速解所有實例，回溯搜尋在最壞情況下是指數的——這與歐拉路徑（每條邊各走一次）形成鮮明對比，後者有個容易的線性時間測試。這個對比就是教訓：問題只改一點點（每個頂點一次 vs. 每條邊一次），就把它從輕鬆可解翻轉成 NP 完全。對中等 n，在子集合上做動態規劃（Held-Karp，O(2^n n^2)）勝過樸素回溯，但對大 n 你只能退而用啟發式與界。
在一個頂點為 1-2-3-4、邊為 1-2、2-3、3-4、4-1 的方形圖中，從 1 搜尋：走 1 -> 2 -> 3 -> 4，四點全訪，完成——這是一條漢米頓路徑（而因 4-1 是邊，也是一個迴路）。加上只與 1 相連的第五個頂點 5：此時除非 5 是端點，否則從 1 出發走遍五點的漢米頓路徑無法以 5 結尾，而回溯會在試盡死路後發現這點。
只把路徑延伸到未訪的相鄰頂點；走遍全部 n 個頂點即為一個解，遇死路就回溯。
漢米頓（每個頂點一次）是 NP 完全的，但歐拉（每條邊一次）很容易——一張圖有歐拉路徑，恰當它連通且至多有兩個奇數度頂點。相似的措辭底下藏著難度上的巨大落差。