3 ms·

Show HN: Optigraph – optimum graph network generator

26 points by LovetheFrogs 2y ago

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.

deleted 2y ago
[deleted]
westurner 2y ago
https://news.ycombinator.com/item?id=36942305#36946741 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_examples_max_cut_and_tsp.html https://qiskit.org/ecosystem/optimization/tutorials/06_examp... Quantum Algorithm Zoo probably lists existing quantum algorithms that might be useful for this application
- woodglyst 2y ago
  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 2y ago
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_geometry) https://en.wikipedia.org/wiki/Steiner_point_(computational_g... https://en.wikipedia.org/wiki/Steiner_tree_problem https://en.wikipedia.org/wiki/Steiner_tree_problem

26 points by LovetheFrogs 2y ago

deleted 2y ago

[deleted]

westurner 2y ago

https://news.ycombinator.com/item?id=36942305#36946741 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_examples_max_cut_and_tsp.html https://qiskit.org/ecosystem/optimization/tutorials/06_examp... Quantum Algorithm Zoo probably lists existing quantum algorithms that might be useful for this application

woodglyst 2y ago
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 2y ago

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_geometry) https://en.wikipedia.org/wiki/Steiner_point_(computational_g... https://en.wikipedia.org/wiki/Steiner_tree_problem https://en.wikipedia.org/wiki/Steiner_tree_problem