Раньше на n-ом уровне делался probing и по всем закрашенным клеткам этого уровня выстраивался общий список уровней, от которых они зависят.
Сейчас этот список индивидуальный для каждой закрашенной клетки.
К п.4 дорабатывается пункт 5.
Сейчас работает так
Если в уровень 20 находилась ошибка, которая зависела от 10-го уровня, то сразу стираются все уровни после 10. Десятый уровень исправлялся и дальше снова шёл 11 уровень.
Пытаюсь доработать, чтобы исправлялся уровень 10. Уровни с 11 по 19 не трогаются (если они не зависят от 10-го). И снова запускается 20 уровень.
О, мой solver в статистике (Syromolotov). С тех пор добавил несколько идей по backtracking-у
Здесь начинает играть большую роль, какая из клеток будет выбрана в качестве следующего расширения потенциального решения.
И вот тут начинается самое интересное. Распишу по этапам эволюции моего backtracking
1) Очевидно (может и не очевидно, но эксперементально проверено), что выбор клеток по порядку не лучший вариант.
2) Логично предположить, что если выбрать клетку, которая на этапе «probing» даёт больше закрашиваемых клеток, то это даст лучший результат. Тут у меня появилось два метода (я писал только черно-белый решатель):
а) Искать клетку у которой один цвет даёт максимальный результат и начинать с него.
б) Искать клетку, у которой минимум по двум цветам (черный и белый) даёт максимальный результат и начинать с максимального цвета.
Метод б) эксперементально даёт лучший результат. Но голый этап 2 тоже не продуктивный, так как на каждом этапе поиска клетки (уровне рекурсии backtracking-а) приходится делать probing по всем незакрашенным клеткам.
3) А что если на каждом уровне рекурсии backtracking-а делать probing не по всем незакрашенным клеткам, а только по тем, у которой набор закрашиваемых клеток пересекается с набором закрашиваемых клеток с выбранной клеткой на предыдущем этапе. Для этого после каждого probinga клетки его закрашиваемые клетки записываются в список закрашиваемых. И наоборот в закрашенную после probingа клетку помещается список тех клеток, которые её закрасили. Данный этап дал огромный скачек в решений, который задвинул меня в список лидирующих солверов в webpbn.com/survey
4) Последний этап на данный момент (который уже писался после попадания в webpbn.com/survey). Проблемы есть из-за последовательного выполнения рекурсии. Покажем на примере. Допустим у нас есть 3 уровня рекурсии
1 уровень. Мы нашли клетку1 и пошли в черный цвет
2 уровень. Мы нашли клетку2 и пошли в чёрный цвет
3 уровень. Мы нашли клетку3 и пошли в черный цвет. Узнали, что черный цвет ошибочен проверили белый цвет. Узнали что он тоже ошибочен. И пошли на уровень ниже. То есть на уровень2. И там меняем клетку2 на белую и возвращаемся в уровень3.
А что если закрашенные клетки на уровне 3 и закрашенные клетки на уровне 2 не зависимы друг от друга (например находятся вообще в разных углах кроссворда и никак друг на друга не влияют). Тогда получается, что мы зря вернулись на уровень2. А сразу могли бы вернутся на уровень 1 и проверять белый цвет Клетки1. Если между зависимыми уровнями, например 10 независимых, то это огромная работа сделанная впустую.
Для того, чтобы выявить зависимость между уровнями, я при закрашивании клеток в probing-е, помечаю какие клетки повлияли на выбор этого цвета и смотрю, в каком уровне они были закрашены. После этого можно смело пропускать уровни, которые не повлияли на закрашивания уровня n.
4-й этап дал так же очень хороший скачок в решении.
Раньше на n-ом уровне делался probing и по всем закрашенным клеткам этого уровня выстраивался общий список уровней, от которых они зависят.
Сейчас этот список индивидуальный для каждой закрашенной клетки.
К п.4 дорабатывается пункт 5.
Сейчас работает так
Если в уровень 20 находилась ошибка, которая зависела от 10-го уровня, то сразу стираются все уровни после 10. Десятый уровень исправлялся и дальше снова шёл 11 уровень.
Пытаюсь доработать, чтобы исправлялся уровень 10. Уровни с 11 по 19 не трогаются (если они не зависят от 10-го). И снова запускается 20 уровень.
К сожалению, Данная статистика теряет актуальность.Страница webpbn.com/survey не обновлялась с
А товарищ Jan Wolter (jan) (создатель этого сайта, собиратель этой статистики, автор pbnsolver) — умер в декабре 13-го — январе 14-го
И вот тут начинается самое интересное. Распишу по этапам эволюции моего backtracking
1) Очевидно (может и не очевидно, но эксперементально проверено), что выбор клеток по порядку не лучший вариант.
2) Логично предположить, что если выбрать клетку, которая на этапе «probing» даёт больше закрашиваемых клеток, то это даст лучший результат. Тут у меня появилось два метода (я писал только черно-белый решатель):
а) Искать клетку у которой один цвет даёт максимальный результат и начинать с него.
б) Искать клетку, у которой минимум по двум цветам (черный и белый) даёт максимальный результат и начинать с максимального цвета.
Метод б) эксперементально даёт лучший результат. Но голый этап 2 тоже не продуктивный, так как на каждом этапе поиска клетки (уровне рекурсии backtracking-а) приходится делать probing по всем незакрашенным клеткам.
3) А что если на каждом уровне рекурсии backtracking-а делать probing не по всем незакрашенным клеткам, а только по тем, у которой набор закрашиваемых клеток пересекается с набором закрашиваемых клеток с выбранной клеткой на предыдущем этапе. Для этого после каждого probinga клетки его закрашиваемые клетки записываются в список закрашиваемых. И наоборот в закрашенную после probingа клетку помещается список тех клеток, которые её закрасили. Данный этап дал огромный скачек в решений, который задвинул меня в список лидирующих солверов в webpbn.com/survey
4) Последний этап на данный момент (который уже писался после попадания в webpbn.com/survey). Проблемы есть из-за последовательного выполнения рекурсии. Покажем на примере. Допустим у нас есть 3 уровня рекурсии
1 уровень. Мы нашли клетку1 и пошли в черный цвет
2 уровень. Мы нашли клетку2 и пошли в чёрный цвет
3 уровень. Мы нашли клетку3 и пошли в черный цвет. Узнали, что черный цвет ошибочен проверили белый цвет. Узнали что он тоже ошибочен. И пошли на уровень ниже. То есть на уровень2. И там меняем клетку2 на белую и возвращаемся в уровень3.
А что если закрашенные клетки на уровне 3 и закрашенные клетки на уровне 2 не зависимы друг от друга (например находятся вообще в разных углах кроссворда и никак друг на друга не влияют). Тогда получается, что мы зря вернулись на уровень2. А сразу могли бы вернутся на уровень 1 и проверять белый цвет Клетки1. Если между зависимыми уровнями, например 10 независимых, то это огромная работа сделанная впустую.
Для того, чтобы выявить зависимость между уровнями, я при закрашивании клеток в probing-е, помечаю какие клетки повлияли на выбор этого цвета и смотрю, в каком уровне они были закрашены. После этого можно смело пропускать уровни, которые не повлияли на закрашивания уровня n.
4-й этап дал так же очень хороший скачок в решении.