[HN Gopher] Show HN: Optigraph - optimum graph network generator
       ___________________________________________________________________
        
       Show HN: Optigraph - optimum graph network generator
        
       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.
        
       Author : LovetheFrogs
       Score  : 23 points
       Date   : 2024-05-19 09:30 UTC (2 days ago)
        
 (HTM) web link (github.com)
 (TXT) w3m dump (github.com)
        
       | westurner wrote:
       | 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
        
       | mikhailfranco wrote:
       | 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
        
       ___________________________________________________________________
       (page generated 2024-05-21 12:02 UTC)