Heuristic Path-Value Density

The problem

It is difficult to choose between multiple tasks when some are high-reward but require massive effort while others are easy but provide less value. Humans often struggle to find the most efficient balance between what they want to achieve and the work required to get there.

What it does

It scores different paths by multiplying their estimated value by the inverse of the effort required to complete them. This creates a ranking that shows which options provide the most progress for the least amount of work.

Why it matters

It provides a clear way to prioritize actions based on their actual return on effort rather than just looking at the highest rewards or the easiest tasks.

Validation

It was run inside an isolated container with no network access. This is the exact command and the real output it produced — captured process output, not written by a model.

$ python3 heuristic_path_value_density.py
Graph: 10 nodes, 14 edges, start=A, alpha=0.5
------------------------------------------------------------
 # 1 | HVD=2.8500 | effort=1.00 | value=3.80 | A -> B
       labels: physics, quantum
 # 2 | HVD=1.6016 | effort=1.20 | value=4.30 | A -> C
       labels: math, topology
 # 3 | HVD=1.1515 | effort=1.10 | value=2.80 | A -> F
       labels: algorithms, cs
 # 4 | HVD=0.6315 | effort=3.50 | value=5.45 | A -> F -> G -> H
       labels: math, physics, quantum
 # 5 | HVD=0.6417 | effort=2.00 | value=3.30 | A -> C -> D
       labels: graph, math
 # 6 | HVD=0.5743 | effort=2.60 | value=3.80 | A -> B -> E
       labels: physics, relativity
 # 7 | HVD=0.4823 | effort=2.10 | value=3.30 | A -> F -> G
       labels: cs, distributed
 # 8 | HVD=0.4850 | effort=2.50 | value=3.80 | A -> C -> E
       labels: physics, relativity
 # 9 | HVD=0.4499 | effort=4.00 | value=5.45 | A -> C -> D -> H
       labels: math, physics, quantum
 #10 | HVD=0.4302 | effort=2.50 | value=3.30 | A -> B -> D
       labels: graph, math

A screenshot of that run.

A clean run proves this does what is shown above, in a CPU-only sandbox. It is a small research demo — not a production tool, and nothing here was published anywhere.

The code

All of it — 294 lines, one file, standard library only.

import json
import math
import sys
from dataclasses import dataclass, field
from typing import Optional


# ---------------------------------------------------------------------------
# Data types
# ---------------------------------------------------------------------------

@dataclass
class Node:
    id: str
    labels: set[str] = field(default_factory=set)
    metadata: dict = field(default_factory=dict)

    @property
    def value_estimate(self) -> float:
        base = self.metadata.get("value", 1.0)
        label_bonus = len(self.labels) * 0.15
        return base + label_bonus


@dataclass
class Edge:
    source: str
    target: str
    effort: float = 1.0


@dataclass
class Graph:
    nodes: dict[str, Node] = field(default_factory=dict)
    edges: list[Edge] = field(default_factory=list)


@dataclass
class Path:
    node_sequence: list[str]
    total_effort: float
    endpoint_value: float

    @property
    def nodes_visited(self) -> set[str]:
        return set(self.node_sequence)


# ---------------------------------------------------------------------------
# Graph utilities
# ---------------------------------------------------------------------------

def build_adjacency(graph: Graph) -> dict[str, list[Edge]]:
    adj: dict[str, list[Edge]] = {nid: [] for nid in graph.nodes}
    for e in graph.edges:
        adj.setdefault(e.source, []).append(e)
    return adj


def edge_effort_map(graph: Graph) -> dict[tuple[str, str], float]:
    return {(e.source, e.target): e.effort for e in graph.edges}


def path_effort(node_sequence: list[str],
                effort_lookup: dict[tuple[str, str], float]) -> float:
    total = 0.0
    for i in range(len(node_sequence) - 1):
        key = (node_sequence[i], node_sequence[i + 1])
        total += effort_lookup.get(key, 1.0)
    return total


# ---------------------------------------------------------------------------
# Path-Cost Entropy Score
# ---------------------------------------------------------------------------

def path_cost_entropy(path: Path, already_covered: set[str]) -> float:
    if not path.node_sequence:
        return 0.0
    novel = path.nodes_visited - already_covered
    novelty_ratio = len(novel) / len(path.node_sequence)
    density = 1.0 / (1.0 + path.total_effort)
    return novelty_ratio * density


# ---------------------------------------------------------------------------
# Path Diversity Score
# ---------------------------------------------------------------------------

def jaccard_distance(a: set[str], b: set[str]) -> float:
    if not a and not b:
        return 0.0
    union = a | b
    return 1.0 - (len(a & b) / len(union))


def path_diversity(path: Path, ranked: list[Path]) -> float:
    if not ranked:
        return 1.0
    distances = [jaccard_distance(path.nodes_visited, r.nodes_visited)
                 for r in ranked]
    return sum(distances) / len(distances)


# ---------------------------------------------------------------------------
# Heuristic Path-Value Density — composite score
# ---------------------------------------------------------------------------

def heuristic_path_value_density(path: Path,
                                 already_seen: set[str],
                                 previously_ranked: list[Path],
                                 alpha: float = 0.5) -> float:
    if path.total_effort <= 0 or path.endpoint_value <= 0:
        return 0.0

    entropy = max(0.0, path_cost_entropy(path, already_seen))
    diversity = max(0.0, path_diversity(path, previously_ranked))
    blend = alpha * entropy + (1 - alpha) * diversity
    value_density = path.endpoint_value / path.total_effort
    return blend * value_density


# ---------------------------------------------------------------------------
# Path generation via BFS expansion
# ---------------------------------------------------------------------------

def generate_candidate_paths(graph: Graph,
                             start: str,
                             max_depth: int = 5,
                             max_paths: int = 150) -> list[Path]:
    if start not in graph.nodes:
        return []

    effort_lookup = edge_effort_map(graph)
    adj = build_adjacency(graph)
    paths: list[Path] = []
    queue: list[list[str]] = [[start]]

    while queue and len(paths) < max_paths:
        seq = queue.pop(0)
        if len(seq) > max_depth + 1:
            continue

        effort_val = path_effort(seq, effort_lookup)
        tail = seq[-1]
        val = graph.nodes[tail].value_estimate if tail in graph.nodes else 0.0
        paths.append(Path(node_sequence=list(seq),
                          total_effort=effort_val,
                          endpoint_value=val))

        if len(seq) <= max_depth:
            visited_set = set(seq)
            for e in adj.get(tail, []):
                if e.target not in visited_set:
                    queue.append(seq + [e.target])

    return paths


# ---------------------------------------------------------------------------
# Ranking engine — sequential greedy selection
# ---------------------------------------------------------------------------

def rank_paths(graph: Graph,
               start: str,
               max_depth: int = 5,
               top_k: int = 10,
               alpha: float = 0.5,
               ) -> list[tuple[Path, float]]:
    candidates = generate_candidate_paths(graph, start, max_depth)
    if not candidates:
        return []

    scored: list[tuple[Path, float]] = []
    ranked_so_far: list[Path] = []
    cumulative_visited: set[str] = set()
    remaining = list(candidates)

    picks = min(top_k, len(remaining))
    for _ in range(picks):
        best_path: Optional[Path] = None
        best_score = -1.0

        for p in remaining:
            hvd = heuristic_path_value_density(p, cumulative_visited,
                                                ranked_so_far, alpha=alpha)
            if hvd > best_score:
                best_score = hvd
                best_path = p

        if best_path is None or best_score <= 0:
            break

        remaining.remove(best_path)
        scored.append((best_path, best_score))
        ranked_so_far.append(best_path)
        cumulative_visited |= best_path.nodes_visited

    return scored


# ---------------------------------------------------------------------------
# Demo graph
# ---------------------------------------------------------------------------

def demo_graph() -> Graph:
    g = Graph()
    for nid, labels, value in [
        ("A", {"root"}, 1.0),
        ("B", {"physics", "quantum"}, 3.5),
        ("C", {"math", "topology"}, 4.0),
        ("D", {"math", "graph"}, 3.0),
        ("E", {"physics", "relativity"}, 3.5),
        ("F", {"cs", "algorithms"}, 2.5),
        ("G", {"cs", "distributed"}, 3.0),
        ("H", {"math", "physics", "quantum"}, 5.0),
        ("I", {"biology", "neural"}, 4.0),
        ("J", {"biology", "evolution"}, 3.5),
    ]:
        g.nodes[nid] = Node(nid, labels=labels,
                            metadata={"value": value})

    g.edges = [
        Edge("A", "B", 1.0), Edge("A", "C", 1.2),
        Edge("B", "D", 1.5), Edge("C", "D", 0.8),
        Edge("D", "H", 2.0), Edge("C", "E", 1.3),
        Edge("E", "H", 1.8), Edge("A", "F", 1.1),
        Edge("F", "G", 1.0), Edge("G", "H", 1.4),
        Edge("H", "I", 2.2), Edge("I", "J", 1.0),
        Edge("B", "E", 1.6), Edge("C", "F", 1.9),
    ]
    return g


# ---------------------------------------------------------------------------
# JSON graph parsing
# ---------------------------------------------------------------------------

def graph_from_json(data: dict) -> Graph:
    g = Graph()
    for n in data.get("nodes", []):
        nid = n["id"]
        g.nodes[nid] = Node(
            id=nid,
            labels=set(n.get("labels", [])),
            metadata={"value": n.get("value", 1.0)},
        )
    for e in data.get("edges", []):
        g.edges.append(Edge(
            source=e["source"],
            target=e["target"],
            effort=e.get("effort", 1.0),
        ))
    return g


# ---------------------------------------------------------------------------
# CLI
# ---------------------------------------------------------------------------

def main() -> None:
    if len(sys.argv) > 1:
        filepath = sys.argv[1]
        with open(filepath) as fh:
            data = json.load(fh)
        graph = graph_from_json(data)
    else:
        graph = demo_graph()

    start = sys.argv[2] if len(sys.argv) > 2 else "A"
    alpha = float(sys.argv[3]) if len(sys.argv) > 3 else 0.5

    print(f"Graph: {len(graph.nodes)} nodes, {len(graph.edges)} edges, "
          f"start={start}, alpha={alpha}")
    print("-" * 60)

    scored = rank_paths(graph, start, max_depth=5, top_k=10, alpha=alpha)

    for rank, (path, score) in enumerate(scored, 1):
        seq = " -> ".join(path.node_sequence)
        endpoint = path.node_sequence[-1]
        labels = graph.nodes[endpoint].labels
        print(f" #{rank:2d} | HVD={score:.4f} | "
              f"effort={path.total_effort:.2f} | "
              f"value={path.endpoint_value:.2f} | {seq}")
        if labels:
            print(f"       labels: {', '.join(sorted(labels))}")

    if not scored:
        print("No paths scored -- check connectivity or start node.")


if __name__ == "__main__":
    main()