4. Local Search and Adversarial Search

Optimization Problem

An optimization problem is one where all states/nodes can be a solution (to different degrees) but the target is to find the state that optimizes (min, max, ...) the solution according to an objective function. I.e., finding "best" states; there are no (explicit) goal state and also no path (costs).

Objective/Evaluation Function (Zielfunktion)

• tells how good a state is, also in comparison to other states

• either minimized or maximized depending on the optimization problem

Local Search

Local search algorithms traversing only a single state rather than saving multiple paths in memory. It modifies its state iterative, trying to improve a criteria

-> In many optimization problems the sequence of actions and costs are irrelevant

-> goal is to find a state fulfilling all goal constraints not the path to reach it!

Advantages:

• Uses a very little/constant amount of memory

• Find a reasonable solution in very large state spaces (where systematical approaches fail)

Disadvantages:

• No guarantees for completeness or optimality

• Expand current state (all Neighbors)

• Move to highest Evaluation

• Repeat until reached a maximum

Problem:

• might not be optimal (plateaus, ridges..)

•