| 11:07p |
Мера сложности лабиринта
Нарисовал детям на забаву на клетчатом листе лабиринт. Лабиринт оказался детям не по зубам. В связи с этим подумалось - а нет ли хорошего способа померять сложность лабиринта? Допустим, лабиринт двумерный прямоугольный с ходами фиксированной ширины, без пустых площадей, с одним входом и одним выходом. Мера сложности объявляется хорошей, если монотонная функция сложности коррелирует с временем его прохождения человеческим существом. Количество битов, необходимое для записи выбора на каждом из ветвлений кратчайшего пути, очевидно, хорошей мерой не является. |