Создание лабиринта в виде башни (самый длинный лабиринт с ограниченными стенами)-около -оптимальная эвристика?

В игре в жанре Tower Defense у вас есть сетка NxM с началом, концом и числом стены.

Враги выбирают кратчайший путь от начала до конца, не проходя сквозь стены.(Обычно они не привязаны к сетке, но для простоты скажем так. В любом случае, они не могут пройти через диагональные "дыры")

Проблема(для этого вопроса по крайней мере)состоит в том, чтобы разместить до K дополнительных стен, чтобы максимизировать путь врагов должны взять. Например, для K=14

Моя интуиция подсказывает мне, что эта задача является NP -сложной, если(как я и надеюсь сделать)мы обобщим это, чтобы включить путевые точки, которые необходимо посетить, прежде чем перейти к финиш, а возможно и без путевых точек.

Но, существуют ли приличные эвристики для почти -оптимальных решений?

[Изменить] Я отправил связанный вопрос здесь .