Skip to content
TheChatArchiveThe Chat Archive
Geminigemini-2.5-flash· GoogleHugging Face LMArena Human Preference 140K

can you further explain f(v) = wh(v) + (1-w)g(v) bound

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Amazon Novaamazon.nova-pro-v1:0’s answer.
  1. User

    can you further explain f(v) = w*h(v) + (1-w)*g(v) bound

  2. Gemini Assistant

    This question actually refers to two different, though related, forms of weighted A* algorithms. Let's break down each one.

    Assume C∗C^* is the cost of the optimal solution, and h(v)h(v) is an admissible heuristic (meaning h(v)≤h∗(v)h(v) \le h^*(v), where h∗(v)h^*(v) is the true cost from node vv to the nearest goal).


    Case 1: f(v)=w∗h(v)+(1−w)∗g(v)f(v) = w*h(v) + (1-w)*g(v) for w∈[0.5,1)w \in [0.5, 1)

    This form of the evaluation function is sometimes called "Optimality Preserving Weighted A*" or discussed in the context of ϵ\epsilon-admissible search (where ϵ=2w−1\epsilon = 2w-1).

    The tightest bound on the value of the solution CC is: C≤C∗/(2w−1)C \le C^* / (2w - 1)

    Explanation:

    1. Admissibility: Since h(v)h(v) is admissible, for any node vv, g(v)+h(v)≤g(v)+h∗(v)=Cv→goalg(v) + h(v) \le g(v) + h^*(v) = C_{v \to \text{goal}}, where Cv→goalC_{v \to \text{goal}} is the true cost from vv to the optimal goal node if vv is on an optimal path to that goal. For any node vv on an optimal path P∗P^* from the start to an optimal goal G∗G^*, we have g(v)+h∗(v)=C∗g(v) + h^*(v) = C^*. Since h(v)≤h∗(v)h(v) \le h^*(v), it implies g(v)+h(v)≤C∗g(v) + h(v) \le C^*.

    2. Algorithm's Behavior: A* and its variants extract the node with the lowest ff-value from the OPEN list. Let GG be the first goal node extracted by the algorithm, and its cost be C=g(G)C = g(G). Since GG is a goal node, h(G)=0h(G) = 0. So, f(G)=w∗0+(1−w)∗g(G)=(1−w)Cf(G) = w*0 + (1-w)*g(G) = (1-w)C.

    3. The Bound Derivation:

      • When the algorithm extracts GG, it means f(G)≤f(v′)f(G) \le f(v') for any node v′v' currently on the OPEN list.

      • Consider an optimal path P∗P^* from the start node to an optimal goal node G∗G^*. At the moment GG is extracted, there must be at least one node voptv_{opt} on P∗P^* that is still on the OPEN list (or G∗G^* itself was expanded).

      • Therefore, we must have f(G)≤f(vopt)f(G) \le f(v_{opt}).

      • Substituting the function: (1−w)C≤w∗h(vopt)+(1−w)∗g(vopt)(1-w)C \le w*h(v_{opt}) + (1-w)*g(v_{opt}).

      • Since h(vopt)h(v_{opt}) is admissible, we know h(vopt)≤C∗−g(vopt)h(v_{opt}) \le C^* - g(v_{opt}).

      • Substitute this into the inequality: (1−w)C≤w∗(C∗−g(vopt))+(1−w)∗g(vopt)(1-w)C \le w*(C^* - g(v_{opt})) + (1-w)*g(v_{opt}) (1−w)C≤wC∗−wg(vopt)+(1−w)g(vopt)(1-w)C \le wC^* - wg(v_{opt}) + (1-w)g(v_{opt}) (1−w)C≤wC∗+(1−2w)g(vopt)(1-w)C \le wC^* + (1-2w)g(v_{opt})

      • Now, consider the range w∈[0.5,1)w \in [0.5, 1).

        • If w=0.5w = 0.5: Then 1−2w=01-2w = 0. The inequality becomes (1−0.5)C≤0.5C∗+0⇒0.5C≤0.5C∗⇒C≤C∗(1-0.5)C \le 0.5C^* + 0 \Rightarrow 0.5C \le 0.5C^* \Rightarrow C \le C^*. In this specific case, f(v)=0.5h(v)+0.5g(v)=0.5(h(v)+g(v))f(v) = 0.5h(v) + 0.5g(v) = 0.5(h(v)+g(v)). Since scaling the ff-values by a positive constant does not change the order of node expansion, for w=0.5w=0.5, this algorithm behaves exactly like standard A*, which is optimal. The bound C∗/(2w−1)C^* / (2w-1) becomes C∗/0C^*/0, which signals optimality or that the bound is undefined at the limit.

        • If w∈(0.5,1)w \in (0.5, 1): Then 2w−1>02w-1 > 0, and thus 1−2w<01-2w < 0. The term (1−2w)g(vopt)(1-2w)g(v_{opt}) is negative. To find the tightest upper bound for CC, we need to maximize the right-hand side of the inequality. Since (1−2w)(1-2w) is negative, to maximize wC∗+(1−2w)g(vopt)wC^* + (1-2w)g(v_{opt}), we need to minimize g(vopt)g(v_{opt}). The smallest possible value for g(vopt)g(v_{opt}) is 00 (if the start node is still on OPEN and on the optimal path). This specific bound of C≤C∗/(2w−1)C \le C^* / (2w-1) is established in literature (e.g., by Pohl for GBA*) and arises from the property that f(v)=(1−w)g(v)+wh(v)f(v) = (1-w)g(v) + wh(v) guarantees that the ratio (g(v)+h(v))/((1−w)g(v)+wh(v))(g(v) + h(v)) / ((1-w)g(v) + wh(v)) is always bounded.

          The proof for this specific bound is quite involved and typically relies on showing that f(n)f(n) for any node nn is "well-behaved" in relation to g(n)+h(n)g(n)+h(n). The bound C≤C∗/(2w−1)C \le C^* / (2w-1) is a known theoretical guarantee for this formulation, implying that the solution found is at most 1/(2w−1)1/(2w-1) times the optimal cost. As ww approaches 0.50.5 from above, 2w−12w-1 approaches 00, meaning the bound can become arbitrarily large (but it's exactly optimal at w=0.5w=0.5). As ww approaches 11 from below, 2w−12w-1 approaches 11, meaning the bound approaches C∗C^*.


    Case 2: f(v)=w∗h(v)+g(v)f(v) = w*h(v) + g(v)

    This is the standard and most commonly used Weighted A* algorithm. For this variant, the typical range for ww is w≥1w \ge 1.

    The tightest bound on the value of the solution CC is: C≤w×C∗C \le w \times C^*

    Explanation:

    1. Algorithm's Behavior: Similar to Case 1, A* (and its weighted variants) extracts the node with the lowest ff-value from the OPEN list. Let GG be the first goal node extracted, with cost C=g(G)C = g(G).

    2. The Bound Derivation:

      • When GG is extracted, f(G)=g(G)+w∗h(G)=g(G)+w∗0=Cf(G) = g(G) + w*h(G) = g(G) + w*0 = C.

      • For any node v′v' on the OPEN list at that moment, f(G)≤f(v′)f(G) \le f(v'). So, C≤f(v′)C \le f(v').

      • Consider any node voptv_{opt} on an optimal path P∗P^* that is still on the OPEN list at the time GG is extracted.

      • We have C≤f(vopt)=g(vopt)+w∗h(vopt)C \le f(v_{opt}) = g(v_{opt}) + w*h(v_{opt}).

      • Since h(vopt)h(v_{opt}) is admissible, h(vopt)≤C∗−g(vopt)h(v_{opt}) \le C^* - g(v_{opt}).

      • Substitute this into the inequality: C≤g(vopt)+w∗(C∗−g(vopt))C \le g(v_{opt}) + w*(C^* - g(v_{opt})) C≤g(vopt)+wC∗−wg(vopt)C \le g(v_{opt}) + wC^* - wg(v_{opt}) C≤wC∗+(1−w)g(vopt)C \le wC^* + (1-w)g(v_{opt})

      • Now, consider the usual range for ww in this context, which is w≥1w \ge 1.

        • If w=1w = 1: Then 1−w=01-w = 0. The inequality becomes C≤1∗C∗+0∗g(vopt)⇒C≤C∗C \le 1*C^* + 0*g(v_{opt}) \Rightarrow C \le C^*. This is standard A*, which is optimal.
        • If w>1w > 1: Then 1−w<01-w < 0. The term (1−w)g(vopt)(1-w)g(v_{opt}) is negative. To maximize CC (i.e., find the upper bound), we need to maximize the right-hand side. Since (1−w)(1-w) is negative, we need to make g(vopt)g(v_{opt}) as small as possible. The smallest possible value for g(vopt)g(v_{opt}) is 00 (if the start node is still on OPEN and on the optimal path). So, C≤wC∗+(1−w)∗0⇒C≤wC∗C \le wC^* + (1-w)*0 \Rightarrow C \le wC^*.
      • This bound implies that the solution found by Weighted A* (with w≥1w \ge 1) will be at most ww times the optimal cost. The larger ww is, the more emphasis is placed on the heuristic, making the search faster but potentially finding a more suboptimal solution.


    Summary of Bounds:

    1. For f(v)=w∗h(v)+(1−w)∗g(v)f(v) = w*h(v) + (1-w)*g(v), with admissible hh and w∈[0.5,1)w \in [0.5, 1): C≤C∗/(2w−1)C \le C^* / (2w - 1) (The bound indicates optimality at w=0.5w=0.5 and approaches C∗C^* as w→1w \to 1.)

    2. For f(v)=w∗h(v)+g(v)f(v) = w*h(v) + g(v), with admissible hh and w≥1w \ge 1: C≤w×C∗C \le w \times C^* (The bound indicates optimality at w=1w=1 and grows linearly with ww.)

    The choice of f(v)f(v) function significantly impacts the theoretical guarantees of the algorithm. The first form is designed to maintain a specific degree of optimality, while the second (more common) form linearly trades off optimality for speed.

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