7 ms·
It depends what encoding is used. If the edge costs are integers, this is true. Also such bounds are possible for rational costs (but you have to pay more atten
by wolfgke 13y ago
It depends what encoding is used. If the edge costs are integers, this is true. Also such bounds are possible for rational costs (but you have to pay more attention). It gets a lot more difficult if non-rational edge weights are allowed.
- tgflynn 13y agoI think we're talking here about problems that can be fed to a digital computer and hence can be represented by a finite number of bits. I believe that would exclude non-rational weights.
- ColinWright 13y agoNot necessarily - quantities like, for example, sqrt(2) can be represented symbolically. So can quantities like e and pi. You can get around this by multiplying all edge costs by twice the number of edges divided by the smallest non-zero difference between costs, then rounding to integers. Or something similar.
- wolfgke 13y agoNo, it wouldn't exclude non-rational weights. Consider for example the field Q[sqrt{2}]. Any element a+b * sqrt{2} of it can be represented by two rational numbers a, b. Since any field extension is a vector space (in this case of dimension 2) the addition can be implemented trivially and the multiplication is (a1, a2) * (b1, b2) = (a1 * b1 + 2 * a2 * b2, a1 * b2 + a2 * b1) (#) A formula for inversion can easily be derived from (#). TLDR: there are different kinds of encoding than binary fractions.