HN Explorer

Show HN: Optigraph – optimum graph network generator (github.com)

26 points by LovetheFrogs ↗ HN
I've created a tool that helps plan graph networks for the best possible connections between nodes. The idea is for it to be used as a kind of underground system planner. I am still working on improving the algorithms it uses, but please consider checking it out for new ideas/bug catching.

4 comments

[ 74.3 ms ] story [ 1358 ms ] thread
[deleted]
(comment deleted)
westurner
https://news.ycombinator.com/item?id=36942305#36946741 :

> Is re-planning routes for regenerative braking solvable with the Modified Snow Plow Problem (variation on TSP Traveling Salesman Problem), on a QC Quantum Computer; with Quantum Algorithmic advantage due to the complexity of the problem?

FWIU the Modified Snow Plow Problem is a variant of TSP the Traveling Salesman Problem which takes topological grade into account; only plow downhill.

Regenerative braking charges on downhills.

TSP can be implemented with quantum algorithms for a quantum computer.

There could be a call for and/or an ml competition for QC algos for TSP and similar:

> - QISkit tutorials > Max-Cut and Traveling Salesman Problem: docs/tutorials/06_examples_max_cut_and_tsp.ipynb: https://qiskit.org/ecosystem/optimization/tutorials/06_examp...

Quantum Algorithm Zoo probably lists existing quantum algorithms that might be useful for this application

woodglyst
The statement that this can be implemented with a quantum algorithm is a bit ambiguous. If you look in detail, the problem is only formulated on the quantum computer while the optimization routine which essential solves the problem is left to a classical computer. There are some notions of quantum gradients. But I wouldn’t know how it applies to such problems
mikhailfranco
It would help if you state the problem you are solving, the valid solutions, and the way that you solve it.

The screenshot shows a network that is not optimal. I would guess the solution using existing nodes is A-E-C-B and D-E.

Do you generate Steiner Points (additional nodes) that minimize the network length?

In the screenshot example, I guess a better solution would be A-E-C with 2 Steiner Points at the feet of the perpendiculars from B and D to the line C-E.

https://en.wikipedia.org/wiki/Steiner_point_(computational_g...

https://en.wikipedia.org/wiki/Steiner_tree_problem