Labyrinth Optimization Version

Problem description

This problem modifies its corresponding decision problem by minimizing the number of instances of "push" in a solution. For a labyrinth of size NxN and a maximum number m of steps, the objective function to minimize is as follows:

sum { push(z,d,s) : 1 ≤ z ≤ N, d in {"n","s","e","w"}, 1 ≤ s ≤ m }

Except for the objective function to minimize, the problem description is the same as the one of the corresponding decision problem.

Input format

See corresponding decision problem.

Output format

See corresponding decision problem.

Author: Martin Gebser
Affiliation: University of Potsdam