| 7:05p |
Сайнс фикшын
Сидит какой-нибудь программер и пишет перебор с возвратом для поиска гамильтонова цикла в графе. Как он есть программер, то все время норовит соптимизировать, там-сям ветки отсекать. Оптимизации разные, работают независимо, ветки секут где попало.
И тут друг его, математик, доказывает, что для любого достаточно большого входного графа логарифм общего числа вершин в дереве перебора не больше, чем C log N. Где C - константа, но эффективной оценки для нее из доказательства не получить. Как не получить и оценки на границу, с которой графы считать "достаточно большими". |