Заливка^©

Гайд по игре в Floodfill

Проблема использования минимального количества цветов для раскрашивания карты имеет долгую историю, как объясняется, например, в этой статье Википедии. Теорема о том, что 4 цвета всегда достаточны для раскрашивания карты плоскости, стала известна как первая большая математическая теорема, которая могла быть доказана только компьютером, а не с помощью «математического» доказательства, созданного человеком.

Не существует алгоритма, который всегда эффективно раскрашивал карты. Под "эффективно" мы подразумеваем, что если количество областей N очень велико, то количество необходимых попыток раскраски растет только как N^k, где k - число, которое не зависит от N. Другими словами, для «эффективных» алгоритмов количество попыток растет только как полином N. Вместо этого известные алгоритмы раскрашивания имеют так называемую экспоненциальную сложность, т.е. количество попыток зависит от N, как 4^N.

Если бы было разрешено использовать 5 или 6 цветов, или если бы карте нужно было только 2 цвета, то эффективные алгоритмы были бы известны.

Еще одна возможность получить эффективный метод состоит в том, чтобы отказаться от требования о том, что алгоритм ВСЕГДА эффективен. Такая эвристика (т.е. набор инструкций), которая работает по крайней мере во многих случаях, будет рассмотрена ниже:

Q. Какой регион следует красить первым?

Q. Какой выбор цветов бесплатный?

Q. Какой регион следует раскрасить следующим?