tikz 中的分支定界樹

Question 1

我會使用一種專門的樹繪圖包。更具體地說，我會使用forestor，如果失敗的話，tikz-qtree.如果您這樣做，您可以非常簡潔、簡單且輕鬆地指定樹，並確保它們的格式一致。

就 Forest 而言，該套件還將為您完成大量佈局工作，儘管標籤不是以這種方式處理的，因此這種特殊的優勢對於這種特殊類型的樹木可能沒有多大好處。

branch and bound下面是一個定義Forest 樣式的範例。當應用於樹時，會發生以下情況：

tree node、S和thick應用於樹中的所有節點，並且內容以數學模式設定；
邊緣也是thick；
樹上增加了一些空間，以分隔分支和層次；
解析樹後，每個節點的內容在每個冒號處分割：<left label>:<node content>:<right label>:<edge label>;
- 第一個冒號之前的部分成為左標籤（位於170）。下一部分設定為主節點內容（tree node在數學模式下使用、等）。第三部分設定為右側標籤（位於10）。最後一部分成為分支上的標籤：中點左側為左側分支，右側為右側分支。
邊緣標籤的內容可以設定為文字模式（text branch labels）或數學模式（maths branch labels）；
- 可以使用以下之一來添加前綴和後綴
  - set branch labels={<left branch prefix>}{<left branch suffix>}{<right branch prefix>}{<right branch suffix>}
  - set maths branch labels={<left branch prefix>}{<left branch suffix>}{<right branch prefix>}{<right branch suffix>}
  - set text branch labels={<left branch prefix>}{<left branch suffix>}{<right branch prefix>}{<right branch suffix>}
樹的每片葉子下方都畫有一條水平線。

然後我們可以指定我認為是你的第二棵樹，現在根據註釋進行編輯，以根據等級改變邊緣標籤，

\begin{forest}
  branch and bound,
  where level=1{
    set branch labels={x\leq}{}{x\geq}{},
  }{
    if level=2{
      set branch labels={}{\geq y}{}{\leq y},
    }{},
  }
  [1055.56:S:950
    [1000:S_1:950:5
    ]
    [1033:S_2:950:6
      [1033:{S_2,1}:950:1]
      [950:{S_2,2}:1033:2]
    ]
  ]
\end{forest}

這顯然更加簡潔並產生

我不知道這種樹的標準是什麼，所以這可能需要一些調整才能正常工作。例如，邊緣標籤可能並不總是採用x\leqand的形式x\req，或者有時可能只有一個或兩個以上的子標籤。然而，這至少應該說明這種方法的潛在力量。

完整程式碼：

\documentclass[border=10pt]{standalone}
\usepackage{forest}
\tikzset{
  tree node/.style = {align=center, inner sep=0pt, font = \scriptsize},
  S/.style = {draw, circle, minimum size = 8mm, top color=white, bottom color=blue!20},
  tree node label/.style={font=\scriptsize},
}
\forestset{
  declare toks={left branch prefix}{},
  declare toks={right branch prefix}{},
  declare toks={left branch suffix}{},
  declare toks={right branch suffix}{},
  tree node left label/.style={
    label=170:#1,
  },
  tree node right label/.style={
    label=10:#1,
  },
  maths branch labels/.style={
    branch label/.style={
      if n=1{
        edge label={node [left, midway] {$\forestoption{left branch prefix}##1\forestoption{left branch suffix}$}},
      }{
        edge label={node [right, midway] {$\forestoption{right branch prefix}##1\forestoption{right branch suffix}$}},
      }
    },
  },
  text branch labels/.style={
    branch label/.style={
      if n=1{
        edge label={node [left, midway] {\foresteoption{left branch prefix}##1\forestoption{left branch suffix}}},
      }{
        edge label={node [right, midway] {\forestoption{right branch prefix}##1\forestoption{right branch suffix}}},
      }
    },
  },
  text branch labels,
  set branch labels/.style n args=4{%
    left branch prefix={#1},
    left branch suffix={#2},
    right branch prefix={#3},
    right branch suffix={#4},
  },
  set maths branch labels/.style n args=4{
    maths branch labels,
    set branch labels={#1}{#2}{#3}{#4},
  },
  set text branch labels/.style n args=4{
    text branch labels,
    set branch labels={#1}{#2}{#3}{#4},
  },
  branch and bound/.style={
    /tikz/every label/.append style=tree node label,
    maths branch labels,
    for tree={
      tree node,
      S,
      math content,
      s sep'+=20mm,
      l sep'+=5mm,
      thick,
      edge+={thick},
    },
    before typesetting nodes={
      for tree={
        split option={content}{:}{tree node left label,content,tree node right label,branch label},
      },
    },
    where n children=0{
      tikz+={
        \draw [thick]  ([yshift=-10pt, xshift=-2.5pt].south west) -- ([yshift=-10pt, xshift=2.5pt].south east);
      }
    }{},
  },
}
\begin{document}
\begin{forest}
  branch and bound,
  where level=1{
    set branch labels={x\leq}{}{x\geq}{},
  }{
    if level=2{
      set branch labels={}{\geq y}{}{\leq y},
    }{},
  }
  [1055.56:S:950
    [1000:S_1:950:5
    ]
    [1033:S_2:950:6
      [1033:{S_2,1}:950:1]
      [950:{S_2,2}:1033:2]
    ]
  ]
\end{forest}
\end{document}

Answer