辺を選べるだけ選ぶ方法は最大で \(15 \times 13 \times 11 \times 9 \times 7 \times 5 \times 3 \times 1 = 2027025\) 通りしかなく（\(N = 15, 16\) のどちらの場合もこの個数です）、全探索が可能です。

実装例（Python）

N = int(input())
D = [[0 for j in range(N)] for i in range(N)]
for i in range(N - 1):
    d = list(map(int, input().split()))
    for j in range(i + 1, N):
        D[i][j] = D[j][i] = d[j - i - 1]


def dfs(used):
    if all(used):
        return 0
    v = used.index(False)
    used[v] = True
    ret = 0
    for w in range(v + 1, N):
        if not used[w]:
            used[w] = True
            ret = max(ret, D[v][w] + dfs(used))
            used[w] = False
    used[v] = False
    return ret


used = [False] * N
ans = 0
if N % 2 == 0:
    ans = dfs(used)
else:
    for v in range(N):
        used[v] = True
        ans = max(ans, dfs(used))
        used[v] = False
print(ans)

P.S. A, B, C の原案でした。