3 ms·
I 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 e
by tgflynn 13y ago
I 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.