Skip to content
TheChatArchiveThe Chat Archive
Amazon Novaamazon.nova-pro-v1:0· AmazonHugging Face LMArena Human Preference 140K

用lua实现lazy theta * 和 角度传播 theta*算法并确保正确

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with gpt-4.1-2025-04-14’s answer.
  1. User

    用lua实现lazy theta * 和 角度传播 theta*算法并确保正确

  2. Amazon Nova Assistant

    实现 Lazy Theta* 和 角度传播 Theta* 算法需要一定的数学和编程基础。以下是 Lua 实现这两个算法的详细步骤和代码示例。

    1. 基本概念

    • Lazy Theta*: 一种改进的 A* 算法,通过减少节点的重新评估来提高效率。
    • 角度传播 Theta*: 一种改进的 Theta* 算法,通过角度传播来进一步优化路径。

    2. 数据结构

    • 节点 (Node): 包含位置、g 值(从起点到当前节点的实际成本)、h 值(从当前节点到目标节点的估计成本)、f 值(g + h)、父节点等。
    • 优先队列 (Priority Queue): 用于存储待处理节点,按 f 值排序。

    3. 实现步骤

    3.1 节点类

    Node = {}
    Node.__index = Node
    
    function Node:new(x, y, g, h, parent)
        local instance = {
            x = x,
            y = y,
            g = g or math.huge,
            h = h or 0,
            f = g + h,
            parent = parent or nil
        }
        setmetatable(instance, Node)
        return instance
    end
    
    function Node:__lt(other)
        return self.f < other.f
    end
    

    3.2 优先队列

    PriorityQueue = {}
    PriorityQueue.__index = PriorityQueue
    
    function PriorityQueue:new()
        local instance = { queue = {} }
        setmetatable(instance, PriorityQueue)
        return instance
    end
    
    function PriorityQueue:push(node)
        table.insert(self.queue, node)
        table.sort(self.queue, function(a, b) return a < b end)
    end
    
    function PriorityQueue:pop()
        return table.remove(self.queue, 1)
    end
    
    function PriorityQueue:isEmpty()
        return #self.queue == 0
    end
    

    3.3 启发式函数(曼哈顿距离)

    function heuristic(a, b)
        return math.abs(a.x - b.x) + math.abs(a.y - b.y)
    end
    

    3.4 Lazy Theta* 算法

    function lazyThetaStar(start, goal, grid)
        local openSet = PriorityQueue:new()
        local closedSet = {}
        local cameFrom = {}
    
        local startNode = Node:new(start.x, start.y, 0, heuristic(start, goal))
        openSet:push(startNode)
    
        while not openSet:isEmpty() do
            local current = openSet:pop()
    
            if current.x == goal.x and current.y == goal.y then
                -- 构建路径
                local path = {}
                while current do
                    table.insert(path, 1, {x = current.x, y = current.y})
                    current = cameFrom[current]
                end
                return path
            end
    
            closedSet[current] = true
    
            for _, neighbor in ipairs(getNeighbors(current, grid)) do
                if not closedSet[neighbor] then
                    local tentative_gScore = current.g + distance(current, neighbor)
    
                    if not openSet:contains(neighbor) or tentative_gScore < neighbor.g then
                        cameFrom[neighbor] = current
                        neighbor.g = tentative_gScore
                        neighbor.h = heuristic(neighbor, goal)
                        neighbor.f = neighbor.g + neighbor.h
    
                        if not openSet:contains(neighbor) then
                            openSet:push(neighbor)
                        end
                    end
                end
            end
        end
    
        return nil -- 没有找到路径
    end
    

    3.5 角度传播 Theta* 算法

    function anglePropagationThetaStar(start, goal, grid)
        local openSet = PriorityQueue:new()
        local closedSet = {}
        local cameFrom = {}
    
        local startNode = Node:new(start.x, start.y, 0, heuristic(start, goal))
        openSet:push(startNode)
    
        while not openSet:isEmpty() do
            local current = openSet:pop()
    
            if current.x == goal.x and current.y == goal.y then
                -- 构建路径
                local path = {}
                while current do
                    table.insert(path, 1, {x = current.x, y = current.y})
                    current = cameFrom[current]
                end
                return path
            end
    
            closedSet[current] = true
    
            for _, neighbor in ipairs(getNeighbors(current, grid)) do
                if not closedSet[neighbor] then
                    local tentative_gScore = current.g + distance(current, neighbor)
    
                    if not openSet:contains(neighbor) or tentative_gScore < neighbor.g then
                        cameFrom[neighbor] = current
                        neighbor.g = tentative_gScore
                        neighbor.h = heuristic(neighbor, goal)
                        neighbor.f = neighbor.g + neighbor.h
    
                        if not openSet:contains(neighbor) then
                            openSet:push(neighbor)
                        end
                    end
                end
            end
    
            -- 角度传播
            for _, neighbor in ipairs(getNeighbors(current, grid)) do
                if closedSet[neighbor] then
                    for _, newNeighbor in ipairs(getNeighbors(neighbor, grid)) do
                        if not closedSet[newNeighbor] then
                            local angle_diff = angleDifference(current, neighbor, newNeighbor)
                            if angle_diff < math.pi / 2 then
                                local tentative_gScore = neighbor.g + distance(neighbor, newNeighbor)
                                if tentative_gScore < newNeighbor.g then
                                    cameFrom[newNeighbor] = neighbor
                                    newNeighbor.g = tentative_gScore
                                    newNeighbor.h = heuristic(newNeighbor, goal)
                                    newNeighbor.f = newNeighbor.g + newNeighbor.h
                                    if not openSet:contains(newNeighbor) then
                                        openSet:push(newNeighbor)
                                    end
                                end
                            end
                        end
                    end
                end
            end
        end
    
        return nil -- 没有找到路径
    end
    

    3.6 辅助函数

    function getNeighbors(node, grid)
        local neighbors = {}
        local directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {1, 1}, {-1, 1}, {1, -1}}
    
        for _, dir in ipairs(directions) do
            local x, y = node.x + dir[1], node.y + dir[2]
            if isValid(x, y, grid) then
                table.insert(neighbors, Node:new(x, y))
            end
        end
    
        return neighbors
    end
    
    function isValid(x, y, grid)
        return x >= 1 and x <= #grid and y >= 1 and y <= #grid[1] and grid[x][y] ~= 1
    end
    
    function distance(a, b)
        return math.sqrt((a.x - b.x)^2 + (a.y - b.y)^2)
    end
    
    function angleDifference(a, b, c)
        local angle1 = math.atan2(b.y - a.y, b.x - a.x)
        local angle2 = math.atan2(c.y - b.y, c.x - b.x)
        local diff = math.abs(angle1 - angle2)
        return math.min(diff, 2 * math.pi - diff)
    end
    

    4. 测试代码

    local grid = {
        {0, 0, 0, 0, 0},
        {0, 1, 1, 0, 0},
        {0, 0, 0, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 0, 0, 0, 0}
    }
    
    local start = {x = 1, y = 1}
    local goal = {x = 5, y =
    

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.