Return to discussion

Post Timeline

deleted 5 characters in body; deleted 2 characters in body

Source Link

edited Oct 13, 2025 at 12:27

Neil Butcher

1.1k
1
3
12

Best path: [5, 1, 2[9, 3, 47, 5, 6, 72, 10]10, 4]

tastiness: 112108

distance: 6738.0217494145607476636379741122

score: 12.671099321911575578592030360124

from itertools import permutations
from math import sqrt, pow
from collections import namedtuple

Location = namedtuple('Location', ['x', 'y' ])
Node = namedtuple('Node', ['id', 'location', 'tastiness' ])

nodes = [
    Node(1,  Location(2, 8),    7),
    Node(2,  Location(15, 3),   17),
    Node(3,  Location(6, 6),    8),
    Node(4,  Location(20, 15),  30),
    Node(5,  Location(11, 2),   12),
    Node(6,  Location(14, 1),   15),
    Node(7,  Location(7, 3),    5),
    Node(8,  Location(1, 12),   12),
    Node(9,  Location(3, 6),    3),
    Node(10, Location(14, 13),  18)]


def score_path(n):
    node = n[-1]
    if len(n) == 1:
        distance = sqrt(pow((node.location.x-0),2)+pow((node.location.y-0),2))
        tastiness = node[2]
        return distance, tastiness

    prior_node = n[-0]2]
    predistance, pretastiness = score_path(n[:-1])
    distance = predistance + sqrt(pow((node.location.x-prior_node.location.x),2)+pow((node.location.y-prior_node.location.y),2))
    tastiness = pretastiness + node.tastiness

    return distance, tastiness

Path = namedtuple('Path', ['path','tastiness','distance','score'])

best_path = Path(None, None, None, 0)
for n in permutations(nodes, 8):
    distance, tastiness = score_path(n)
    score = tastiness/distance
    if(score>best_path.score):
        best_path = Path(n, tastiness, distance, score)

print(f"Best path: {[i[0] for i in best_path.path]}")
print(f"tastiness: {best_path.tastiness}")
print(f"distance: {best_path.distance}")
print(f"score: {best_path.score}")

Best path: [5, 1, 2, 3, 4, 6, 7, 10]

tastiness: 112

distance: 67.02174941456074

score: 1.6710993219115755

from itertools import permutations
from math import sqrt, pow
from collections import namedtuple

Location = namedtuple('Location', ['x', 'y' ])
Node = namedtuple('Node', ['id', 'location', 'tastiness' ])

nodes = [
    Node(1,  Location(2, 8),    7),
    Node(2,  Location(15, 3),   17),
    Node(3,  Location(6, 6),    8),
    Node(4,  Location(20, 15),  30),
    Node(5,  Location(11, 2),   12),
    Node(6,  Location(14, 1),   15),
    Node(7,  Location(7, 3),    5),
    Node(8,  Location(1, 12),   12),
    Node(9,  Location(3, 6),    3),
    Node(10, Location(14, 13),  18)]


def score_path(n):
    node = n[-1]
    if len(n) == 1:
        distance = sqrt(pow((node.location.x-0),2)+pow((node.location.y-0),2))
        tastiness = node[2]
        return distance, tastiness

    prior_node = n[-0]
    predistance, pretastiness = score_path(n[:-1])
    distance = predistance + sqrt(pow((node.location.x-prior_node.location.x),2)+pow((node.location.y-prior_node.location.y),2))
    tastiness = pretastiness + node.tastiness

    return distance, tastiness

Path = namedtuple('Path', ['path','tastiness','distance','score'])

best_path = Path(None, None, None, 0)
for n in permutations(nodes, 8):
    distance, tastiness = score_path(n)
    score = tastiness/distance
    if(score>best_path.score):
        best_path = Path(n, tastiness, distance, score)

print(f"Best path: {[i[0] for i in best_path.path]}")
print(f"tastiness: {best_path.tastiness}")
print(f"distance: {best_path.distance}")
print(f"score: {best_path.score}")

Best path: [9, 3, 7, 5, 6, 2, 10, 4]

tastiness: 108

distance: 38.76636379741122

score: 2.78592030360124

from itertools import permutations
from math import sqrt, pow
from collections import namedtuple

Location = namedtuple('Location', ['x', 'y' ])
Node = namedtuple('Node', ['id', 'location', 'tastiness' ])

nodes = [
    Node(1,  Location(2, 8),    7),
    Node(2,  Location(15, 3),   17),
    Node(3,  Location(6, 6),    8),
    Node(4,  Location(20, 15),  30),
    Node(5,  Location(11, 2),   12),
    Node(6,  Location(14, 1),   15),
    Node(7,  Location(7, 3),    5),
    Node(8,  Location(1, 12),   12),
    Node(9,  Location(3, 6),    3),
    Node(10, Location(14, 13),  18)]


def score_path(n):
    node = n[-1]
    if len(n) == 1:
        distance = sqrt(pow((node.location.x-0),2)+pow((node.location.y-0),2))
        tastiness = node[2]
        return distance, tastiness

    prior_node = n[-2]
    predistance, pretastiness = score_path(n[:-1])
    distance = predistance + sqrt(pow((node.location.x-prior_node.location.x),2)+pow((node.location.y-prior_node.location.y),2))
    tastiness = pretastiness + node.tastiness

    return distance, tastiness

Path = namedtuple('Path', ['path','tastiness','distance','score'])

best_path = Path(None, None, None, 0)
for n in permutations(nodes, 8):
    distance, tastiness = score_path(n)
    score = tastiness/distance
    if(score>best_path.score):
        best_path = Path(n, tastiness, distance, score)

print(f"Best path: {[i[0] for i in best_path.path]}")
print(f"tastiness: {best_path.tastiness}")
print(f"distance: {best_path.distance}")
print(f"score: {best_path.score}")

Source Link

created Oct 13, 2025 at 12:16

Neil Butcher

1.1k
1
3
12

Best path: [5, 1, 2, 3, 4, 6, 7, 10]

tastiness: 112

distance: 67.02174941456074

score: 1.6710993219115755

I did this in python.

I used an in-built method, permutations to get the possible 8-node paths which could be taken through the graph.

Then I scored each, using a dynamic programming technique, where I scored a path of length 7, and then added the 8th node, performing this recursively to the base-case where a path has length 1 remaining.

from itertools import permutations
from math import sqrt, pow
from collections import namedtuple

Location = namedtuple('Location', ['x', 'y' ])
Node = namedtuple('Node', ['id', 'location', 'tastiness' ])

nodes = [
    Node(1,  Location(2, 8),    7),
    Node(2,  Location(15, 3),   17),
    Node(3,  Location(6, 6),    8),
    Node(4,  Location(20, 15),  30),
    Node(5,  Location(11, 2),   12),
    Node(6,  Location(14, 1),   15),
    Node(7,  Location(7, 3),    5),
    Node(8,  Location(1, 12),   12),
    Node(9,  Location(3, 6),    3),
    Node(10, Location(14, 13),  18)]


def score_path(n):
    node = n[-1]
    if len(n) == 1:
        distance = sqrt(pow((node.location.x-0),2)+pow((node.location.y-0),2))
        tastiness = node[2]
        return distance, tastiness

    prior_node = n[-0]
    predistance, pretastiness = score_path(n[:-1])
    distance = predistance + sqrt(pow((node.location.x-prior_node.location.x),2)+pow((node.location.y-prior_node.location.y),2))
    tastiness = pretastiness + node.tastiness

    return distance, tastiness

Path = namedtuple('Path', ['path','tastiness','distance','score'])

best_path = Path(None, None, None, 0)
for n in permutations(nodes, 8):
    distance, tastiness = score_path(n)
    score = tastiness/distance
    if(score>best_path.score):
        best_path = Path(n, tastiness, distance, score)

print(f"Best path: {[i[0] for i in best_path.path]}")
print(f"tastiness: {best_path.tastiness}")
print(f"distance: {best_path.distance}")
print(f"score: {best_path.score}")

I tried caching the results of scoring paths, so that the score of sub-paths could be reused, but it didn't improve the speed enough to warrant the memory, maybe it would if the path size increased to 9 or higher.

On that note this doesn't scale very well with the node count, but solved sufficiently quickly for this problem size.

I hadn't used named tuples before but thought these may act as a good compromise between tuples and classes. So far I haven't seen any advantage over writing a class however.

Collectives™ on Stack Overflow