思维之树（ToT）法

思想树（Tree of Thoughts，ToT）是Yao和Long于2023年发表的论文《Tree of Thoughts (ToT): A Framework for Advanced Problem Solving》中提出的一种语言模型提示方法，非常适合需要战略性思考和探索的复杂任务。ToT利用类似树状的思维结构，结合系统性问题解决的搜索算法，扩展了思维链（Chain-of-Thought，CoT）提示的概念。

Large Language Model Guided Tree-of-Thought.pdf388.93KB

Tree of Thoughts- Deliberate Problem Solving with Large Language Models.pdf748.36KB

ToT的运作方式

简单来说，Tree of Thoughts（ToT）方法是将探索多种可能性并寻找最优解的过程，用树状结构来表现出来。这样，语言模型就能够像人一样从多个方向进行思考，并且在需要时能够回到之前的阶段，尝试其他方法。

ToT备受关注的原因

•

树状结构：ToT像树的分枝一样，通过多种路径来探索问题解决的过程。每一“分枝”代表了解决问题的一个想法或步骤。（可以联想到我们经常在资源管理器里见到的文件夹结构。）

•

想法生成与评估：就像人类解决问题时会提出多种想法并评估哪种最好一样，语言模型会给出多种方案，并从中找到最优解。

•

探索与回溯：为了解决问题，会探索多条路径，必要时还可以返回前一步，从不同的方向重新思考。

实际应用方式

CoT的一个问题是无法进行回溯。如果只能走到最后看到结果后才能继续，而ToT最吸引人的地方就是可以在中间就回溯并修正。正如前面所述，假设需要解决一个对LLM来说比较困难的数学问题，比如下面这样的题目。

"4x4 스도쿠 퍼즐의 빈 칸을 채워 넣으시오."

一般方法

•

过程：一般方法是分别在每一行、每一列、2x2网格中找出缺失的数字，并依次填入空格。

•

结果：按顺序填满空白格完成拼图。

我创建的4x4数独谜题中，所有格子都是空白的。要解这个谜题，完整的数独棋盘如下：

1 2 3 4
3 4 1 2
2 1 4 3
4 3 2 1

ToT方法

ToT流程额外提示

•

步骤1：语言模型会建议填入第一个空格的数字。

•

步骤2：考虑下一个空格应该填入的数字。

•

回溯：如果某一步发现无法解决该谜题，语言模型就会回到前一步，尝试其它数字。

•

最终输出：准确填写所有空格，完成谜题。

通过一步步解决4x4数独谜题，总共花了14个步骤准确填满了所有空格。最后完成的数独如下：

1 2 3 4
3 4 2 1
4 3 1 2
2 1 4 3

其实这么看的话，区别不是很明显。但如果看一下这位朋友解决的代码，就会明白了。

普通提示方式

# 4x4 Sudoku puzzle generator and solver
import numpy as np
import random

def is_safe(grid, row, col, num):
    """
    Check if it's safe to place a number in a given position.
    """
    # Check if we find the same num in the similar row
    for x in range(4):
        if grid[row][x] == num:
            return False

    # Check if we find the same num in the similar column
    for x in range(4):
        if grid[x][col] == num:
            return False

    # Check if we find the same num in the particular 2x2 matrix
    start_row = row - row % 2
    start_col = col - col % 2
    for i in range(2):
        for j in range(2):
            if grid[i + start_row][j + start_col] == num:
                return False
    return True


def solve_sudoku(grid, row, col):
    """
    Solving the puzzle using backtracking
    """
    # Check if we have reached the 4x4 matrix end
    if row == 3 and col == 4:
        return True
    
    # Check if column value becomes 4, we move to next row
    if col == 4:
        row += 1
        col = 0

    # Check if the current position is filled
    if grid[row][col] > 0:
        return solve_sudoku(grid, row, col + 1)

    for num in range(1, 5):
        # Check if it is safe to place the num
        if is_safe(grid, row, col, num):
            grid[row][col] = num

            # Checking for next possibility with next column
            if solve_sudoku(grid, row, col + 1):
                return True

        # Removing the assigned num
        grid[row][col] = 0
    return False


def generate_sudoku():
    """
    Generate a 4x4 sudoku puzzle
    """
    grid = np.zeros((4,4), dtype=int)

    # Filling the diagonal 2x2 matrices
    for i in range(0, 4, 2):
        num = 1
        for j in range(i, i+2):
            for k in range(i, i+2):
                grid[j][k] = num
                num += 1

    # Removing random numbers to create the puzzle
    for i in range(4):
        remove = random.randint(1,2)  # Number of digits to remove from each row
        while remove > 0:
            col = random.randint(0,3)
            if grid[i][col] != 0:
                grid[i][col] = 0
                remove -= 1

    return grid

# Generate a 4x4 sudoku puzzle
puzzle = generate_sudoku()
puzzle_original = np.copy(puzzle)
# Solve the puzzle
solve_sudoku(puzzle, 0, 0)
puzzle, puzzle_original

ToT方式

# Function to find the next empty cell in the sudoku grid
def find_empty_location(grid):
    for row in range(4):
        for col in range(4):
            if grid[row][col] == 0:
                return row, col
    return -1, -1

# Function to check if a number can be placed in a specific cell
def is_valid(grid, row, col, num):
    # Row check
    if num in grid[row]:
        return False

    # Column check
    if num in [grid[i][col] for i in range(4)]:
        return False

    # 2x2 square check
    start_row, start_col = 2 * (row // 2), 2 * (col // 2)
    for i in range(start_row, start_row + 2):
        for j in range(start_col, start_col + 2):
            if grid[i][j] == num:
                return False

    return True

# Function to solve the sudoku using backtracking
def solve_sudoku_step_by_step(grid, step=0):
    row, col = find_empty_location(grid)
    
    # If there is no empty location, we are done
    if row == -1:
        return True, grid, step

    for num in range(1, 5):
        if is_valid(grid, row, col, num):
            grid[row][col] = num
            solved, final_grid, next_step = solve_sudoku_step_by_step(grid, step + 1)
            
            if solved:
                return True, final_grid, next_step

            # Undo the current cell for backtracking
            grid[row][col] = 0

    return False, grid, step

# Generate a 4x4 sudoku puzzle with some empty spaces
sudoku_puzzle = np.array([
    [1, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 2],
    [0, 0, 0, 0]
])

# Solve the sudoku step by step
solved, final_sudoku, steps = solve_sudoku_step_by_step(sudoku_puzzle)
final_sudoku, steps

如果这在GPT-3.5上运行，可以像下面这样确认。

普通提示与ToT提示结果的区别

从结果来看，可以发现，通过这些提示方法，我们在GPT-4上实现的内容，用GPT-3.5或LLaMA2等也可以很好地复现。（用GPT-4的话，直接编码就能解决了。

Made with Slashpage