Рассмотрим описанную проблемуВот (воспроизведено ниже.) Можно ли свести к этому какую-то более известную NP-полную проблему?

Эта проблема:

Есть ряд домов. Каждый дом можно покрасить в три цвета: красный, синий и зеленый. Стоимость покраски каждого дома в определенный цвет отличается. Вы должны покрасить все дома так, чтобы ни один из двух соседних домов не был одного цвета. Вы должны покрасить дома с минимальными затратами. Как бы вы это сделали?

Примечание: стоимость покраски дома 1 красным отличается от стоимости покраски дома 2 красным. Каждая комбинация дома и цвета имеет свою стоимость.