3 ms·
In this case, A* is in a finite, bounded 3030 grid. As A is just a type of branch and bound algorithm, which the degenerate form is exhaustive search. Which s
by nyrikki 3y ago
In this case, A* is in a finite, bounded 3030 grid. As A is just a type of branch and bound algorithm, which the degenerate form is exhaustive search. Which should be able to 'prove' the absence of a path by simply failing to find one before exhausting all paths.
PCB routing is not as simple as this problem for real world problems.
Digging into why TSP with a positive integer Euclidean metric is NP-C but with a real valued Euclidean metric is NP-hard may be one way to think about it.
But if you choose the right metric and huristic, in what approximates a finite space, A* can run an exhaustive search in practical time.
It is probably a good idea to separate search space exhaustion from no-instance proving which in the case of decision problems can cause confusion.
If you think of NP as relating to yes-instances, co-NP is the no-instances.
- thesz 3y agoYou are mathematician, am I right? Your answer is correct (sorta, as far as I am concerned) and does not add to the discussion I tried to open. Your answer does not show anything related to the ability of transformers to prove absence of solution, to be precise.
- nyrikki 3y agoNo, just a programmer that has to apply math. Transformers can only do what is called weak negation. if (not (goal X)), then (assert not x) One example I have seen is: "you can cross if you have no information on a train coming” VS: "you can cross if you have evidence that no train is coming" See the difference? As to what 'transformers' can encode is ambiguous and depends on many factors but here is some light reading. https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00493/112604/Saturated-Transformers-are-Constant-Depth https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00493... https://arxiv.org/abs/2204.06618 https://arxiv.org/abs/2204.06618