旅行業務員問題的解可以樹形 (tree) 表示，例如 n=4，則圖1的樹形表示所有可能的 3!=6 條路徑，例如，最右邊一條路徑為 。

圖1

在這問題中我們需找出最小成本路徑，分支界定法搜尋此最佳解的概念為，將樹形不斷分支，但隨時以問題的條件限制分支的持續，亦即若知最佳解不會出現在經由此點的路徑，則不必繼續分支，因此所需搜尋的路徑將大為減少。

考慮以下的例子，表 1 為城市間的成本矩陣，例如 C₁₂=3 表示城市 1 到城市 2 的旅行成本為 3，注意 C_ij 不一定等於 C_ji，在主對角線上的 ，表示我們不需要這些值。 一個可能的路徑需矩陣中的 4 個表值，每一行且每一列恰有一個，又且，若選 C_ij，則不能選 C_ji； 若選 C_ij、C_jk，則不能選 C_ik（為什麼？），例如，表1 中所圈的 4 個值表示路徑 ， 成本為 C₁₂+C₂₃+C₃₄+C₄₁=3+6+6+9=24

首先，我們找此問題的一個下限，在成本矩陣中，若每一行（每一列）減去相同的值，顯然， 最低成本的路徑不會改變，故在第一列每項減 3（該列中最小值為 3），第二列減 3，第三列減 5， 第四列減 4，得表2 之成本矩陣，但現在成本比原來成本少 3+3+5+4=15。

第四行可減 1，故表3 之成本矩陣較原問題少 15+1=16，因此這問題的解至少 16，16 為下限。

現在我們開始分支，首先考慮第一列，因 C₁₂=0 為最小，故考慮 C₁₂，我們選 C₁₂ 或不選 C₁₂。 若不選 C₁₂，則令 ，得表4。

表4中，第一列可減 3，第二行可減 1，故得表 5，下限則為 16+(3+1)=20

若選 C₁₂，則表3中第一列第二行不能再被使用，可刪去，C₂₁ 亦不得被使用，故令 ， 得表6。

第一列可減去 1，故下限為 16+1=17，如表7。

目前樹狀分支過程如圖2

圖2

所以二元決策樹 (binary decision tree) 的每一內點表示：選 C_ij 或不選C_ij。現在因選 C₁₂ 下限17小於不選 C₁₂ 下限20， 故接著對選 C₁₂ 分支，新選的表值不一定需與 C₁₂ 連接，亦即不一定需為C_j1 或 C_2j，但為簡單起見，我們選 C_2j，表7中因 C₂₄=0，故接著的分支為選 C₂₄ 或不選 C₂₄。 若不選 C₂₄，則表7中令 ，第一列減 2，故下限為 17+2=19。若選 C₂₄， 則表7中移去對應的行與列，又令 （否則得迴路 ），故得表8 下限仍為 17。

現在我們繼續分支，由表8可知，接著必得選 C₄₃，C₃₁（否則得 ），因 C₄₃=C₃₁=0， 故下限為 17，而這條路徑 成本為 3+5+4+5=17 正為下限， 故為最佳解。 以上全部的分支界定過程如圖3。

圖3