Эффективный алгоритм раскраски плоского 4-цветного графа с подсчетом очков ⇐ Python

[Anonymous]

Я делаю игру, в которой вам нужно раскрасить изображение, используя теорему о четырех цветах. Никакие соседние регионы не могут быть одного цвета. Есть четыре цвета (красный, зеленый, синий и желтый), и вы получаете 10 очков за каждый красный регион, 6 за зеленый, 3 за синий и 1 за желтый. Я хочу, чтобы алгоритм вычислил максимальную оценку для любого данного изображения. Я извлекаю из изображения планарный граф, который дает для каждого региона список его соседей.
Моя реализация методом перебора проверяет все возможные раскраски, которые растут как 4**n для n регионов. Я могу максимально оптимизировать это, но есть ли более быстрый способ? Для двух цветов существует алгоритм линейного времени, но по соображениям игрового дизайна я не буду создавать изображения, которые можно раскрасить двумя цветами.
Вот несколько примеров словарей Python. Их ключи — это идентификаторы региона, а списки — это списки соседей этого региона:

Код: Выделить всё

easy = {2: [4], 4: [2, 3, 14, 13], 3: [4], 14: [4], 13: [4]}

Наивысший балл: 46 (я думаю), мой перебор Python: 0,1 с.

Код: Выделить всё

medium = {2: [4, 5, 6], 4: [2, 3], 3: [4, 18], 5: [2, 6], 6: [5, 2, 13, 18], 13: [6, 20, 21, 22], 18: [6, 3, 20, 22], 20: [18, 13], 22: [18, 13], 21: [13]}

Наивысший балл: 77, мой перебор Python: 7,2 с.

Код: Выделить всё

hard = {2: [5, 6, 9], 5: [2, 4], 4: [5, 23], 6: [2, 7, 10], 3: [8, 16], 8: [3, 7, 12], 7: [6, 8, 10, 11], 9: [2, 10], 10: [6, 9, 7, 13, 14, 15, 17, 18], 11: [7, 12, 13], 12: [8, 11, 15, 16, 19], 13: [10, 11, 15], 14: [10, 15], 15: [10, 13, 12, 14, 17, 19], 16: [3, 12, 25, 27], 17: [10, 15, 18], 18: [10, 17, 19, 20], 19: [15, 18, 12, 27], 20: [18, 22, 24, 26, 27, 25], 22: [20], 23: [4, 24, 26], 24: [23, 20], 25: [16, 20], 26: [23, 20], 27: [19, 20, 16]}

Мой перебор Python: неизвестно.

Подробнее здесь: https://stackoverflow.com/questions/486 ... th-scoring