Как я мог оценить сложность головоломки раскраски графа?

Question

Я разрабатываю небольшую HTML-игру на основе Canvas & JavaScript для обучения и решаю создать головоломку-раскраску карты.

Изначально я планировал установить сложность головоломки, используя время, которое потребуется заданному алгоритму для ее решения, но я, наконец, решил реализовать алгоритм решения методом грубой силы. Другие алгоритмы были слишком сложными для меня, так как я не нашел каких-либо четких ресурсов, где алгоритм для оптимальной 3- или 4-окрашиваемости был бы хорошо объяснен.

Моя проблема в том, что некоторые хитрые головоломки могут быть созданы, так что решение грубой силы занимает много времени, и все же головоломка может быть легкой с другим методом решения.

Итак, как бы вы определили относительную сложность головоломки раскраски карты?

Answer 1

Ваша карта является неориентированным графом. Вершины - это поверхности, которые должны быть заполнены цветами, а края соединяют соседей.
Сложность одной головоломки невысока, когда у вас мало соседей на каждой поверхности. Сложная головоломка - та, где каждая вершина имеет много ребер.
Таким образом, способ ранжирования головоломок будет просто:

difficulty = total_number_edges - total_number_vertices

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

difficulty = (total_number_edges - total_number_vertices)  
                        * (total_number_vertices / max_edges_in_vertex)

Вы должны быть изобретателем мастер-формулы:)

Answer 2

проблема раскраски карты / графа является "NP-полной".Что это означает, что научное сообщество почти уверено, что любой данный алгоритм для решения проблемы будет затрачивать экспоненциальное (огромное) количество времени на определенные экземпляры проблемы (например, головоломки).Вот почему ЛЮБОЙ алгоритм, который вы реализуете (включая ваш механизм "грубой силы"), будет подавлять некоторые экземпляры головоломки.

Я бы порекомендовал вам реализовать несколько различных алгоритмов для решения ваших головоломок, например

• Алгоритм 1 - один за другим, выберите случайную область и дайте ей цвет, который все еще «подходит», т.е. не является цветом какого-либо цветного соседа.Если вы столкнулись с конфликтом (не можете покрасить выбранную область), остановите алгоритм.Запустите этот цикл, скажем, N раз, и рассчитайте, сколько раз цикл фактически раскрашивает всю карту;пусть это будет K. Здесь вы получите оценку K / N (в процентах), 0% = сложная проблема (возможно, невозможная), 100% = очень очень легкая проблема

• Алгоритм 2 - добавитьколичество возвратов к алгоритму 1, например, разрешить максимум 1000 шагов возврата.Запустите тот же цикл «выборки».Вы получаете еще один балл 0% -100%.

Затем используйте полученные результаты (вы получите более высокие баллы из алгоритма 2, чем из алгоритма 1, потому что он более мощный), чтобы получитьотносительная сложность для головоломок.

КЛЮЧ ко всему этому заключается в том, что если вы получаете оценку (0%, 0%), то есть вы не знаете, разрешимы ли головоломки, вы их ОТБЫВАЕТЕ, потому что выне хочу представлять проблемы аудитории, которые могут быть неразрешимыми:)

Наконец, используйте свое собственное суждение, чтобы «сопоставить» оценки с «удобочитаемыми» описаниями сложности - выберите пару головоломок, решите ихвручную проверьте результат, который рассчитывает ваша программа, а затем посмотрите, как процентные показатели соответствуют вашему восприятию сложности.

Answer 3

Я нашел абзац, который дал мне представление о том, как вы можете оценить сложность.

Один класс алгоритмов аппроксимации основанный на «жадном» методе - вершины обрабатываются по порядку, причем каждой вершине присваивается самый низкий пронумерованный цветовой класс, который не ставит его в конфликт с его ранее окрашенными соседями. Поскольку вершины, смежные с текущей вершиной, могут использовать все четыре цвета, пятый или даже шестой, седьмой и т. д. цвета может быть необходимо. Когда жадный метод должен создать новый цветовой класс, вершина которого называется impasee.

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

Я нашел цитируемый абзац в статье Быстрый вероятностный алгоритм для четырехцветных больших плоских графов от Раймонд А. Арчулета и Генри Д. Шапиро