throughtheether

Прямой подход: перевести координаты точки в полярные и сравнить углы. Плюсы: простота реализации. Минусы: возможны нюансы с округлением (граничные эффекты).

что он лежит в интервале от нуля о 2^32, но строго не последовательно, а непрерывными 50-100 блоками (разыне подсети).

Если это IPv4-адреса, и необходимо находить longest-match, то посмотрите в сторону patricia trie. Пример промышленного использования: PySubnetTree (модуль для python, написан на C). По поводу многопоточности не могу подсказать, к сожалению.

distance += abs((i - m[i][j] / 4)) + abs((i - m[i][j] % 4))

Если вы вычисляете "манхэттенское" расстояние между текущим и идеальным положениями плитки, то почему под знаками модуля в каждом случае используется один лишь индекс i? Я полагаю, корректнее будет исправить:

distance += abs((i - m[i][j] / 4)) + abs((j - m[i][j] % 4))

UPD.

алгоритм ставит пустую фишку всегда в позицию [0, 0] а если поставить ее в другое место он "висит"

Предполагаю, это из-за вашего подсчета расстояния. Вы нулевое значение (т.е. положение пустой кдетки) игнорируете по какой-то причине.
Если исправить текст так, то указанный вами пример ([[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 11, 12], [13, 10, 14, 15]]) нормально обсчитывается



Пара комментариев - во-первых, это ad-hoc решение (для случая, когда в конечном положении пустая клетка расположена в конце). Во-вторых, по-хорошему, расстояние надо измерять от одной ноды до другой (то есть, передавать в функцию heuristic_2 текущую ноду и конечную и суммировать, какая плитка на сколько позиций сдвинута). В-третьих,

m = eval(puzz)

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

Я не вполне понял задачу, которую вы пытаетесь решать.

Как быстро выполнить топологическую сортировку дерева из списка?

У вас фактически заданы дуги (arcs) графа. Вы можете из этих данных заполнить более удобную структуру данных (adjacency list, например) и на ней уже запустить алгоритм топологической сортировки. Например, основанный на поиске в глубину. То есть, при помощи DFS (depth-first search, поиск в глубину) ищем ноду (вершину, node, vertex), из которой нет исходящих дуг (sink node), присваиваем ей значение, равное количеству нод, удаляем ее из графа, повторяем. Число - позиция ноды в результирующем списке. Сложность O(m+n), где n - число нод, m - число дуг. Это если вам достаточно топологически отсортированного списка нод.

Как наиболее быстро восстановить дерево из этого списка?

Это уже другой вопрос. Что вы имеете в виду? В каком смысле 'восстановить'? У вас дерево (как частный случай графа) уже задано списком дуг фактически, в каком виде вам его необходимо представить?
Если в виде (Name, ID, ChildID), то мне представляется, что за O(m) можно создать подобную структуру с фактически перевернутыми (относительно заданного дерева) дугами. Для каждого кортежа (Name, ID, ParentID) создаете (или обновляете поле Name, если нода уже существует) ноду (Name, ID), ноду ParentID (если она не создана), у ноды ParentID указываете наследника (child node) ID.

Предлагаю такое решение. Вес каждого пункта одинаков (20% в случае 5 вариантов ответа). Для каждого пункта известно, должен ли он быть включен в ответ (должна ли стоять галочка). Если галочка должна стоять и пользователь ее поставил - за этот пункт баллы начисляются. Если галочка должна стоять, пользователь ее не поставил - баллы не начисляются. Аналогично для пункта, который не должен быть включен в ответ.
Пример: 5 пунктов, 1 и 2 правильные, 3,4,5 - неправильные.
1 и 2 отмечены, 3,4,5 не отмечены - 100%
1 и 2 не отмечены, 3,4,5 не отмечены - 60%
1 отмечен, 2,3,4,5 не отмечены - 80%
1,3,4 отмечены, 2,5 не отмечены - 40%
1,2 не отмечены, 3,4,5 отмечены - 0%
и так далее (всего 32 варианта).

Человек поставил 1 верную галочку и 1 неверную - какой процент верности?

20% за одну верную поставленную галочку и 40% за две верные непоставленные галочки, всего 60%

Человек поставил 1 верную галочку и 2 неверных - какой процент верности?

20% за верную поставленную галочку, 20% за одну верную непоставленную галочку, всего 40%.

Возможно есть какие-либо статьи или известные решения?

Примерно так, по-моему, реализовано тестирование в coursera.

UPD. Как я понял, вас смущает тот факт, что при некоторых свойствах ответов (количество верных/неверных) пользователь может получить средний балл, вообще не ставя галочки. Если вы считаете это проблемой, то предлагаю два решения. Первое - соответственно составлять вопросы, чтобы количество верных ответов было выше количества неверных. Второе - при старте выставить галочки в случайном порядке. В таком случае (опять же, при правильном подборе параметров) получить высокий балл ничего не делая будет сложнее.

Одно из свойств этой нотации - отбрасывание констант перед членами, а также младших (менее быстро растущих) членов. Кроме того, log[base=a](N)=log[base=b](N)/log[base=b](a), т.е. при смене основания логарифма эффективно меняется константа перед соответствующим членом, что в целом не учитывается ('подавляется') О-нотацией.